利用特徵點之曲面交線計算

Abstract

我們提出一計算任意類型之參數曲面的曲面交線演算法。此演算法包含二 大步驟: 起先我們找出特徵點(significant points)- u-轉折點 (u- turning points) 和邊界點(border points); 第二步驟使用一數值上甚 穩定之曲線追溯法(curve tracing) 來計算曲面的交線。一個好的曲面相 交的演算法應該平衡三個互相衝突的目標: 健全(robustness),精確( accuracy) 和效率(efficiency)。我們所提的演算法是健全的因為我們利 用找特徵點來找出每條交線上至少一個起始點, 且在曲線追溯的過程中, 因為我們可找出曲線追溯方向之明顯表示式, 所以我們的演算法會較有效 率。但我們觀察到在計算 NURBS 曲面之特徵點是沒效率的, 特別是 degree 高的曲面。雖然所採用的曲線溯法可以尋得大部分交線奇點 (singularities), 但奇點問題(singular problems) 仍然無法獲得完整 地解決。 An algorithm for computing the surface intersection between two general parametric surfaces is proposed. Th algorithm consists of two steps. In the first step, we find the significant points - u-turning and border points. The second step traces the curve component in a numerically stable manner. It is well recognized that a good surface intersection algorithm should balance three conflicting objectives: robustness, accuracy, and efficiency. The proposed alogrithm is robust because it can find at least one starting point for each intersection component by locating the significant points. Morever, in tracing process, our proposed alogrithm should be more efficient because we obtain the tracing direction explicitly. Nevertheless, we observe that computing the significant points for NURBS surfaces is not efficient, especially for high degree surfaces. 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.