參數曲面的曲面交線計算

Abstract

我們提出一計算任意類型之參數曲面的曲面交線演算法．此演算法包含三 大步驟：起先，針對每一曲面交線，我們分割參數曲面之定義域來找一起 始點(starting point)；其次，我們使用一在數值上甚穩定之曲線追溯 法 (curve tracing) 來計算曲面的交線；於最後步驟中，我們處理於前 兩步驟中無法尋得之較小的曲面交線(small features)，諸如small loops 和切面交點 (tangential contact points)．由於此演算法不需要 排序 (sorting) 程序來尋得完整之曲面交線，而且對每一交線它只計算 一起始點，所以此演算法會較快且有效率(efficient) ；又因為我們使用 之曲線追溯法於數值上很穩定，所以它比其他方法更為精確 (accurate) ；此外，我門慎重地處理較小之曲面交線的問題，所以此演算法將比其他 以曲面分割為主(subdivision-based) 之方法更robust ．但由於分割法 本身之先天限制，我們無法保證此演算法的 robustness ．雖然所採用之 曲線追溯法可以尋得大部分的交線奇點 (singularities)，但奇點問題 (singular problems) 仍無法獲得完整地解決． An algorithm for computing the surface intersection between two general parametric surfaces is proposed. The algorithm consists of three steps. In the first step, surface subdivision based on domain partition is involved to obtain one starting point on each component. The second step traces the curve component in a numerically stable manner. Finally in the third step, the small features, such as small loops and isolated tangential contact points, that might be missed in the first two steps are carefully recovered. It is well recognized that a good surface intersection algorithm should balance three conflicting objectives: efficiency, accuracy, and robustness. The proposed algorithm should be more efficient than the existing methods of the similar type since it computes only one starting point for each component and derives the intersection curves without sorting, and should be more accurate than others since a numerically stable tracing approach is employed. Moreover, the algorithm should be more robust than other subdivision-based methods since the problems of missing small features are carefully handled. Nevertheless, due to the limitation of subdivision the robustness cannot be fully guaranteed. Also, as shown in other existing methods singularities cannot be completely resolved although the employed tracing procedure is capable of handling many of the singularities.