代數曲面的曲面交線計算

Abstract

曲面交線的計算在幾何及實體模型中是常重覆用到的運算. 近年來代數曲 面逐漸受到重視,如何有效且精確地計算出兩個代數曲面間的交線是一個 重要的問題. 我們在本論文中提出一個計算兩個代數曲面間的交線的演算 法 ,其著重於正確性和奇點的解決.此演算法包含三個主要步驟.第一, 先 將曲面的交線以monoid計算法將其映到一個平面曲線 h(x,y)=0.這種做法 的優點是我們可以用二次轉換法將奇點處理掉. 第二步是找出交線各個部 份的起始點. 我們用迴圈偵測法找出 z=0 和 z=h(x,y) 的臨界點. 按照 這些臨界點, 我們將 (x,y) 定義域加以分割. 然後再找每個小部分的邊 線和 h(x,y)=0 的交點. 因為上面所提到的對映方式是雙向的, 所以 h( x,y)=0 上的起始點對應到真正交線的起始點. 最後的步驟是從起始點找 出交線的各部分. 在追蹤的過程中若遇到奇點,則轉而追蹤 h(x,y)=0 直 到安全地通過奇點,再繼續原來的追蹤過程.本論文所提的方法可找出交線 的各部分, 而且可以有系統地解決奇點的問題. 所付出的代價在monoid計 算法,尤其是次數較高的曲面. 我們也在此論文中說明實做上的問題及一 些實驗性的結果. The evaluation of surface intersections is a recurring operation in geometric and solid modeling. Since algebraic surface have recently become more important, how to efficiently, accurately, and robustly compute the intersection between two algebraic surfaces is a crucial problem. We propose in this thesis an algorithm for computing the intersection of two algebraic surfaces, emphasizing on the issues of robustness and singularities resolution. The algorithm consists of three steps. In the first step, the surface intersection is mapped to a planar curve, say h(x,y)=0, by the monoid computation. The mapping of the surface intersection to a planar curve is advantageous since with the planar curve the singularities can be resolved completely by quadratic transformations. The second step is devoted to the derivation of starting points on each curve component. Loop detection is performed to locate the critical points of the intersection between z=0 and z=h(x,y). Based on the critical points, the (x, y)-space is subdivided selectively and the starting points are obtained as the intersection of the grid boundary and h(x,y)=0. Since the mapping is birational, the starting points on h(x,y)=0 are starting points on the corresponding intersection component. Finally, in the third step, each intersection component is traced from a starting point. The tracing is switched to the tracing of h(x,y)=0 whenever a singularity is encountered, and it is resumed after the singularity is safely passed. The proposed algorithm is able to detect all intersection components and to resolve the singularities completely and systematically. This is achieved at the cost of monoid computations, especially for surfaces of high degree. In the thesis, we also address the implementation issues and experimental results.