臺灣博碩士論文加值系統

曲面交線的計算在幾何及實體模型中是常重覆用到的運算. 近年來代數曲
面逐漸受到重視,如何有效且精確地計算出兩個代數曲面間的交線是一個
重要的問題. 我們在本論文中提出一個計算兩個代數曲面間的交線的演算
法 ,其著重於正確性和奇點的解決.此演算法包含三個主要步驟.第一, 先
將曲面的交線以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.