陳甜甜， 趙 罡

（北京航空航天大學(xué)機(jī)械工程及自動(dòng)化學(xué)院，北京 100191）

基于加權(quán)漸進(jìn)插值的Loop細(xì)分曲面等距逼近

陳甜甜， 趙 罡

（北京航空航天大學(xué)機(jī)械工程及自動(dòng)化學(xué)院，北京 100191）

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

等距；Loop細(xì)分曲面；漸進(jìn)插值；逼近

曲面等距在快速成型、數(shù)控加工、機(jī)器人運(yùn)動(dòng)干涉的避免以及帶厚度薄片實(shí)體（如汽車車身、箱包等）的計(jì)算機(jī)輔助幾何設(shè)計(jì)中有著廣泛的應(yīng)用，尤其在數(shù)控加工刀具軌跡的生成方面，通過將等距面與一系列平面相交可以產(chǎn)生無(wú)干涉的刀具軌跡[1]?？梢?，曲面等距是CAD/CAM領(lǐng)域最重要的幾何操作之一。

近十幾年來(lái)，隨著細(xì)分理論基礎(chǔ)的不斷加深與拓展，細(xì)分造型技術(shù)已經(jīng)成為三維模型造型中非常重要的一類技術(shù)。細(xì)分曲面是初始網(wǎng)格通過對(duì)細(xì)分規(guī)則不斷迭代生成光滑曲面的造型方法，結(jié)合了多邊形造型和參數(shù)曲面造型的優(yōu)點(diǎn)，能夠?qū)⒐饣脑O(shè)計(jì)模型和離散的加工模型整合與統(tǒng)一模型中[2]。除保留了傳統(tǒng)NURBS曲面保凸性、局部可調(diào)等良好性質(zhì)外，其優(yōu)于NURBS曲面的拓?fù)淙我庑院鸵恢滦允沟眉?xì)分曲面逐漸受到工業(yè)造型和數(shù)控加工領(lǐng)域的廣泛關(guān)注。但是細(xì)分曲面這一非常具有潛力的造型技術(shù)還未真正應(yīng)用于工程領(lǐng)域，究其原因，一是細(xì)分曲面沒有顯式的數(shù)學(xué)表達(dá)公式；二是細(xì)分曲面沒有完善的配套幾何工具，例如等距和相交，這就限制了細(xì)分曲面在CAD/CAM中的應(yīng)用。

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

圖1 Loop細(xì)分一次前后網(wǎng)格對(duì)比[6]

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

由于三角形網(wǎng)格模型在實(shí)際應(yīng)用中最為常用，四邊形網(wǎng)格也需要?jiǎng)澐譃槿敲嫫M(jìn)行處理，故針對(duì)C2連續(xù)的Loop細(xì)分曲面，提出了一種不需解線性方程組且能避免與初始網(wǎng)格偏移的 Loop細(xì)分曲面等距逼近算法。針對(duì)曲面等距中的邊界保持、誤差控制和自交問題進(jìn)行了深入分析，此等距逼近算法同樣適用于其他細(xì)分模式。

1 加權(quán)漸進(jìn)插值

1.1 Loop細(xì)分曲面漸進(jìn)插值

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

具體地，給定一個(gè)3D三角網(wǎng)格M=M0，通過漸進(jìn)插值迭代方法來(lái)生成一個(gè)光滑的Loop細(xì)分曲面S插值于初始網(wǎng)格M0的所有控制頂點(diǎn)。對(duì)于M0上的每一個(gè)頂點(diǎn)V0，閉合網(wǎng)格Loop細(xì)分漸進(jìn)插值算法具體步驟如下：

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

Step 2 計(jì)算V0與極限位置之間的距離添加距離D0進(jìn)行修正得到新的頂點(diǎn)和新的三角網(wǎng)格M1；

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

其中

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

1.1.1 最優(yōu)權(quán)因子的選取

既然漸進(jìn)插值算法是一個(gè)局部修正的迭代過程，那么需考慮其收斂速度。通過對(duì)控制頂點(diǎn)進(jìn)行加權(quán)迭代，即能夠達(dá)到控制漸進(jìn)插值收斂速度的目的。對(duì)于每一個(gè)權(quán)因子其極限網(wǎng)格都是相同的，文獻(xiàn)[8]討論了使得迭代過程收斂速度最快的權(quán)因子。對(duì)于大部分模型，迭代過程收斂速度最快的權(quán)因子分布在，方便起見本文取最優(yōu)權(quán)因子。結(jié)合實(shí)例模型，Loop細(xì)分曲面漸進(jìn)插值權(quán)因子與迭代次數(shù)的關(guān)系如表 1所示，加權(quán)的Loop漸進(jìn)插值算法只需更少的迭代次數(shù)，便能夠得到大致相同的誤差精度。

表1 權(quán)因子ω與漸進(jìn)插值迭代次數(shù)之間的關(guān)系

1.2 邊界處理

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

圖2 Loop細(xì)分邊界模版（圓代表規(guī)則點(diǎn)，三角形代表奇點(diǎn)）

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

圖3 邊界頂點(diǎn)極限位置模版

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

2 Loop細(xì)分曲面等距逼近

2.1 Loop細(xì)分曲面極限位置法矢

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

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

圖4 利用頂點(diǎn)分裂求奇異頂點(diǎn)法矢

2.2 自相交處理

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

3 實(shí)驗(yàn)結(jié)果與討論

本文是結(jié)合OpenGL在Visual C++6.0下實(shí)現(xiàn)該算法。實(shí)驗(yàn)環(huán)境是基于Windows XP操作系統(tǒng)，奔騰IV3.0GHZ處理器，1GB內(nèi)存，采用的數(shù)據(jù)結(jié)構(gòu)是半邊數(shù)據(jù)結(jié)構(gòu)。

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

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

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

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

4 結(jié) 論

本文提出一種簡(jiǎn)單新穎的Loop細(xì)分曲面等距逼近算法。利用最優(yōu)權(quán)因子不斷迭代修正控制頂點(diǎn)，得到無(wú)偏移的插值于初始網(wǎng)格的Loop 細(xì)分曲面。等距后的細(xì)分曲面與初始網(wǎng)格具有相同的拓?fù)浣Y(jié)構(gòu)，特別是邊界處等距效果較好。與傳統(tǒng)細(xì)分曲面等距算法相比，該方法避免求解線性方程組，能夠統(tǒng)一處理開網(wǎng)格和閉網(wǎng)格等距逼近。未來(lái)的工作將對(duì)等距中的自相交問題進(jìn)一步研究，尤其是凹陷處局部自相交的檢測(cè)和去除。

[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細(xì)分曲面的等距曲面的逼近[J]. 計(jì)算機(jī)學(xué)報(bào), 2003, 26(7): 789-796.

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

[6] 張景嶠. 細(xì)分曲面生成及其在曲面造型中的應(yīng)用[D].浙江: 浙江大學(xué), 2003.

[7] 王占東. 細(xì)分曲面關(guān)鍵技術(shù)研究[D]. 南京: 南京航空航天大學(xué)機(jī)械學(xué)院, 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

國(guó)家自然科學(xué)基金(61170198)

陳甜甜（1982-），女，上海人，博士，主要研究方向?yàn)镃AD/CAM。E-mail：candy_ctt@163.com

趙 罡（1972-），男，河北文安人，教授，博士生導(dǎo)師，主要方向?yàn)镃AD/CAM，幾何造型，虛擬現(xiàn)實(shí)。Email：zhaog@buaa.edu.cn