基于加權漸進插值的Loop細分曲面等距逼近

陳甜甜， 趙 罡

（北京航空航天大學機械工程及自動化學院，北京 100191）

基于加權漸進插值的Loop細分曲面等距逼近

陳甜甜， 趙 罡

（北京航空航天大學機械工程及自動化學院，北京 100191）

等距曲面在 CAD/CAM 領域有著重要的作用，由于細分曲面沒有整體解析表達式，使得計算細分曲面等距比參數曲面更加困難。針對目前已有的兩種等距面逼近算法進行了改進，利用加權漸進插值技術避免了傳統細分等距逼近算法產生網格偏移的問題。此外，提出了針對邊界等距處理方案，使得等距后的細分曲面在內部和邊界都均勻等距。該方法無需求解線性方程組，具有全局和局部特性，能夠處理閉網格和開網格，為Loop細分曲面數控加工奠定了良好的基礎算法。最后給出的實例驗證了算法的有效性。

等距；Loop細分曲面；漸進插值；逼近

曲面等距在快速成型、數控加工、機器人運動干涉的避免以及帶厚度薄片實體（如汽車車身、箱包等）的計算機輔助幾何設計中有著廣泛的應用，尤其在數控加工刀具軌跡的生成方面，通過將等距面與一系列平面相交可以產生無干涉的刀具軌跡[1]。可見，曲面等距是CAD/CAM領域最重要的幾何操作之一。

近十幾年來，隨著細分理論基礎的不斷加深與拓展，細分造型技術已經成為三維模型造型中非常重要的一類技術。細分曲面是初始網格通過對細分規則不斷迭代生成光滑曲面的造型方法，結合了多邊形造型和參數曲面造型的優點，能夠將光滑的設計模型和離散的加工模型整合與統一模型中[2]。除保留了傳統NURBS曲面保凸性、局部可調等良好性質外，其優于NURBS曲面的拓撲任意性和一致性使得細分曲面逐漸受到工業造型和數控加工領域的廣泛關注。但是細分曲面這一非常具有潛力的造型技術還未真正應用于工程領域，究其原因，一是細分曲面沒有顯式的數學表達公式；二是細分曲面沒有完善的配套幾何工具，例如等距和相交，這就限制了細分曲面在CAD/CAM中的應用。

目前，針對細分曲面等距逼近的研究還較少，主要有反算法和直接法。Kurgan和Suzuki[3]最先提出了基于 Catmull-Clark細分曲面的等距逼近算法。丁俊勇[4]等人在該算法基礎上提出了改進的高斯雅克比迭代的Loop細分曲面等距逼近算法。白杰[5]重點研究了帶折痕的 Loop細分曲面等距問題。上述細分等距算法被稱為反算法。Loop細分反算法的主要思想是首先將初始網格細分1～2次，以確保每一個面都是三角形且至多包含一個奇點；然后將細分曲面的等距轉化為細分曲面控制網格的等距，通過解全局線性方程組來得到等距后的細分曲面控制頂點。但是，當控制網格的數據量較大時，全局操作的反算法計算速度慢，靈活度小。此外，由于Loop細分的收縮性，導致了細分后的控制網格與初始網格的偏移。如圖1所示，Loop細分一次后的網格與初始網格相比有明顯的收縮，每次細分之后，細分的邊長將會是原來的一半左右，這會造成被等距的網格與初始網格的偏移。

圖1 Loop細分一次前后網格對比[6]

另一種曲面等距逼近方法是直接法。主要思想是根據逼近誤差計算出細分次數，控制網格經細分后直接計算出逼近的等距面[7]。從等距面的生成步驟看直接法更加簡單，省去了反算法求解方程組的步驟，計算速度快。但是，隨著細分次數的增加，控制頂點越來越逼近極限曲面的同時，控制頂點與初始網格頂點的偏移會越來越大。上述兩種等距逼近算法都會造成初始網格與極限曲面的偏移，從而導致等距面的偏移。在邊界問題上，兩類算法都未給出具體的邊界處理方法，對于開網格等距逼近效果不理想。

由于三角形網格模型在實際應用中最為常用，四邊形網格也需要劃分為三角面片進行處理，故針對C2連續的Loop細分曲面，提出了一種不需解線性方程組且能避免與初始網格偏移的 Loop細分曲面等距逼近算法。針對曲面等距中的邊界保持、誤差控制和自交問題進行了深入分析，此等距逼近算法同樣適用于其他細分模式。

1 加權漸進插值

1.1 Loop細分曲面漸進插值

不論是反算法還是直接法都存在細分后的控制網格與初始網格偏移的問題。為了避免與初始網格的偏移，利用漸進插值技術，通過不斷迭代修正控制頂點得到一系列控制網格，其極限曲面插值于初始網格。

具體地，給定一個3D三角網格M=M0，通過漸進插值迭代方法來生成一個光滑的Loop細分曲面S插值于初始網格M0的所有控制頂點。對于M0上的每一個頂點V0，閉合網格Loop細分漸進插值算法具體步驟如下：

Step 1 利用 Loop細分曲面極限位置公式(1)，計算V0在其細分曲面S0上的極限位置

Step 2 計算V0與極限位置之間的距離添加距離D0進行修正得到新的頂點和新的三角網格M1；

Step 3 如果三角網格M1對應的細分曲面S1與初始網格M0之間的距離小于給定的誤差，則停止迭代，否則進入Step2，即對 V1添加距離D1進行修正；

其中

Qi是頂點V的1-領域點。由此看出，迭代漸進插值算法是局部過程，故可以處理任意大小的網格。需要指出的是，雖然這個插值過程是不斷迭代得到，但也可以不需要重復迭代k次，直接跳過中間的計算得到三角網格 Mk+1。只需限制M0與細分曲面 Sk+1之間的距離小于給定的誤差即可。

1.1.1 最優權因子的選取

既然漸進插值算法是一個局部修正的迭代過程，那么需考慮其收斂速度。通過對控制頂點進行加權迭代，即能夠達到控制漸進插值收斂速度的目的。對于每一個權因子其極限網格都是相同的，文獻[8]討論了使得迭代過程收斂速度最快的權因子。對于大部分模型，迭代過程收斂速度最快的權因子分布在，方便起見本文取最優權因子。結合實例模型，Loop細分曲面漸進插值權因子與迭代次數的關系如表 1所示，加權的Loop漸進插值算法只需更少的迭代次數，便能夠得到大致相同的誤差精度。

表1 權因子ω與漸進插值迭代次數之間的關系

1.2 邊界處理

對于開網格，Loop細分漸進插值算法類似于閉網格，主要需要考慮的是邊界的處理。就Loop細分而言，邊界頂點與內部頂點具有不同的細分模版。使用如下圖1的邊界模版，從而保證產生的光滑曲面在邊界處達到 C1連續。其中圓點代表規則點，即邊界頂點度為4如圖2(a)；三角形代表邊界奇點，即邊界頂點度不為4，如圖2(b)～(d)。

圖2 Loop細分邊界模版（圓代表規則點，三角形代表奇點）

由1.1節可知，Loop細分漸進插值最重要的環節是計算頂點極限位置，邊界頂點可通過與周圍鄰頂點的線性組合得到該點極限位置，這些頂點或者是規則點或者是奇點，根據不同類型的頂點就能夠得到不同邊界頂點的極限位置，六種不同的邊界頂點極限位置模版如圖3所示。若邊界頂點為規則頂點，則極限位置計算公式如圖3(a)～(c)；若邊界頂點為奇點，則極限位置計算公式如圖3(d)～圖3(f)。

圖3 邊界頂點極限位置模版

需要注意的是，Loop細分漸進插值邊界頂點細分計算只需要邊界頂點的參與，所以漸進插值對于邊界的處理可以首先計算邊界的漸進插值。一旦邊界處理完畢后，就可以進行內部頂點的漸進插值算法，而無需邊界頂點任何的改變。最終得到的網格將插值于邊界頂點和內部頂點。不論邊界如何不連續，都可以采用局部幾何運算同時計算邊界插值，從而避免了求解多個線性方程組。對于邊界頂點運用漸進插值技術其收斂性也是可以證明的[8]。

2 Loop細分曲面等距逼近

2.1 Loop細分曲面極限位置法矢

利用上述加權漸進插值算法可以得到無偏移的插值于初始網格的Loop細分曲面。給定距離d，沿著法矢方向等距就可以得到最終的細分曲面等距逼近。

在光滑頂點（規則點）處可以利用加權平均法向量得到該光滑頂點的法矢。對于尖銳特征（奇點）處，如果按照加權平均法計算法矢就會產生較大的誤差，故需要特殊處理。利用多法向量法[9]計算奇點處的法矢，即通過將奇頂點分裂為多個頂點來求得新的法矢，如圖4所示,將頂點V分裂為V1和V2。

圖4 利用頂點分裂求奇異頂點法矢

2.2 自相交處理

細分曲面等距后，可能會引起兩種類型的自交：一類為局部自交，是指凹陷處的局部曲率半徑小于等距值，導致等距曲面相交；另一類為全局自交，是指曲面片分離間隙小于等距值，導致等距曲面相交。利用Loop細分模式的凸包性，通過檢測等距后的三角控制網格是否自交，可以快速判別等距曲面是否自交。3D模型直接檢測和去除等距面自相交較困難，通過與一系列平面相交生成二維刀具軌跡后更容易處理。去除刀具軌跡中的自相交環得到無干涉的刀具軌跡[10]。

3 實驗結果與討論

本文是結合OpenGL在Visual C++6.0下實現該算法。實驗環境是基于Windows XP操作系統，奔騰IV3.0GHZ處理器，1GB內存，采用的數據結構是半邊數據結構。

為驗證上述算法的有效性，對大量模型進行了檢測，具體參數信息如表2所示。利用最優權因子加速漸進插值的收斂速度，減少了的迭代次數，提高了計算效率。下面給出幾個模型實例。圖5是兩個閉合網格模型pig模型和knot模型。根據1.1節的步驟，分別迭代修正控制頂點4次和8次生成Loop細分曲面圖5(b)和圖5(e)；光滑且保留了初始網格的細節特征的等距曲面見圖5(c)和圖5(f)。圖6(a)是帶有內環的閉網格casting實體圖，無偏移的插值于初始網格的Loop細分曲面如圖6(b)；按照2.1節求出等距網格頂點的外法矢方向等距后得到圖6(c)，可以看出內環處均勻等距。

表2 基于WPI的Loop細分曲面（ω=1.7）

對于開網格face模型見圖7(a)，首先利用1.2節對邊界進行處理，然后按照1.1節步驟處理內部頂點。為了更加直觀比較，本文給出face模型Loop細分曲面等距逼近的正面圖和側面圖。圖7(a)是初始網格實體圖的正面圖和側面圖。圖7(d)是利用文獻[7]中的算法生成的Loop細分曲面等距逼近。很明顯，從正面圖和側面圖都可以看出在邊界處有凹凸不平，邊界處與初始網格相比有明顯的收縮。而利用本文算法生成的Loop細分曲面等距逼近能夠統一處理開網格和閉網格，無論在內部和還是邊界處等距效果都較好，見圖7(c)。

圖7 face模型Loop細分等距逼近(ω=1.7)

4 結 論

本文提出一種簡單新穎的Loop細分曲面等距逼近算法。利用最優權因子不斷迭代修正控制頂點，得到無偏移的插值于初始網格的Loop 細分曲面。等距后的細分曲面與初始網格具有相同的拓撲結構，特別是邊界處等距效果較好。與傳統細分曲面等距算法相比，該方法避免求解線性方程組，能夠統一處理開網格和閉網格等距逼近。未來的工作將對等距中的自相交問題進一步研究，尤其是凹陷處局部自相交的檢測和去除。

[1] Qu X Z, Brent S. A 3D surface offset method for STL-format models [J]. Rapid Prototyping Journal, 2003, 9(3): 133-141.

[2] Lu C J, Ting K L. Subdivision surface-based finish machining [J]. International Journal of Production Research, 2006, 44(12,15): 2445-2463.

[3] Kurgano J, Suzuki H, Kimura F. Generation of NC tool path for subdivision surfaces[C]. Proceedings of CAD/Graphics. China, 2001: 676-682.

[4] 丁俊勇, 胡事民, 周登文. Loop細分曲面的等距曲面的逼近[J]. 計算機學報, 2003, 26(7): 789-796.

[5] 白 杰, 趙 罡, 姚福生. 帶折痕的Loop細分曲面等距面處理算法[J]. 計算機輔助設計與圖形學學報, 2008, 20(10): 1261-1265.

[6] 張景嶠. 細分曲面生成及其在曲面造型中的應用[D].浙江: 浙江大學, 2003.

[7] 王占東. 細分曲面關鍵技術研究[D]. 南京: 南京航空航天大學機械學院, 2003.

[8] Cheng F H, Fan F T, Lai S H. Loop subdivision surface based progressive interpolation [J]. Journal of Computer Science and Technology, 2009, 24(1): 39-46.

[9] Deng C Y, Ma W Y. Weighted progressive interpolation of Loop subdivision surfaces [J]. Computer Aided Design, 2012, 44(5): 424-431.

[10] Kim S J, Yang M Y. Triangular mesh offset for generalized cutter [J]. Computer Aided Design, 2005, 37(10): 999-1014.

[11] Jung W, Kim D S, Choi B K. Self-intersection removal in triangular mesh offsetting [J] . Computer Aided Design, 2004, 1(1-4): 477-484.

Offset Approximation of Loop Subdivision Surface Based on Weighted Progressive Interpolation

Chen Tiantian, Zhao Gang
( College of Mechanical Engineering and Automation, Beijing University of Aeronautics and Astronautics, Beijing 100191, China )

Offset plays an important role in the field of CAD/CAM. The offset approximation computation is more difficult for subdivision surfaces than parametric surfaces because subdivision surfaces have no analytical expression. The proposed approach is an improvement of two existed subdivision surface offset algorithms. Using the weighted progressive interpolation (WPI) method avoids the mesh deviation caused by the traditional methods. The boundary offset treatment is presented to obtain the uniform offset mesh. The proposed method avoids solving a linear equation system and has the advantages of both local and global methods. The method can be used to deal with either closed or open meshes. Offset approximation is an important operator to the applications of Loop subdivision surfaces in NC machining. Some typical examples are illustrated to demonstrate the efficiency of the proposed approach in the end.

offset; Loop subdivision surface; progressive interpolation; approximation

TP 391

A

2095-302X (2013)05-0066-05

2013-05-03；定稿日期：2013-06-08

國家自然科學基金(61170198)

陳甜甜（1982-），女，上海人，博士，主要研究方向為CAD/CAM。E-mail：candy_ctt@163.com

趙 罡（1972-），男，河北文安人，教授，博士生導師，主要方向為CAD/CAM，幾何造型，虛擬現實。Email：zhaog@buaa.edu.cn