孫 林

(合肥工業(yè)大學(xué)數(shù)學(xué)學(xué)院，安徽 合肥 23009)

0 引言

細分方法是根據(jù)初始控制頂點，經(jīng)過連續(xù)細化而生成曲線曲面的離散化造型方法，其起源可以追溯到1956年de Rham的割角逼近方法.在1974年Chaikin提出的曲線生成方法引起CAGD領(lǐng)域的關(guān)注.1978 年 Catmull和 Clark[1]，Doo 和 Samin[2]則分別提出了任意拓撲網(wǎng)格上的雙三次和雙二次B樣條曲面細分方法，使得細分方法開始應(yīng)用于曲面造型.1987年Loop[3]提出了一種基于三角形網(wǎng)格的細分方法，將四次三項Box樣條推廣到任意的三角形網(wǎng)格上.1991年Dyn[4]給出了一種可達C2連續(xù)的四點逼近格式.1998年 Sederberg[5]等提出了廣義Doo－Sabin細分規(guī)則和廣義Catmull－Clark細分規(guī)則，使得NURBS成為它的子集.其中，若細分方法生成的極限曲面通過全部原控制頂點，則稱為插值細分方法，否則稱為逼近細分方法.上面提到的Doo－Sabin細分、Catmull－Clark細分、Loop細分等是逼近方法;而Kobbelt[6]方法和蝴蝶方法等是插值方法.

細分方法具有拓撲任意性這一重要優(yōu)點，可以有效解決曲線曲面的造型問題.其中Doo－Sabin方法可以很好的保持網(wǎng)格一些轉(zhuǎn)角特征.實際應(yīng)用中，發(fā)現(xiàn)上述幾種基本細分方法在相對正規(guī)性的網(wǎng)格上得到很好的結(jié)果，但當網(wǎng)格中出現(xiàn)顯著扭曲面片時，就會出現(xiàn)不理想的細分結(jié)果.針對這種情況，文獻[7]給出了基于泊松網(wǎng)格編輯方法控制網(wǎng)格變形，在Loop和Catmull－Clark兩種細分模式下有良好的結(jié)果，但其實施過程需要手工指定目標網(wǎng)格區(qū)域，不便于細分過程的自動化.

本文提出一種比較通用的基于相鄰點的面片扭曲變形控制方法，可以根據(jù)需要集成到經(jīng)典Doo－Sabin方法，Catmull－Clark方法和 Loop方法中，實現(xiàn)細分方法對扭曲面片的校正優(yōu)化處理.

1 經(jīng)典細分方法在處理扭曲面片時的不足

經(jīng)典細分方法在處理規(guī)則網(wǎng)格時，能給出具有光滑性和連續(xù)性等良好的結(jié)果;但在處理的含有顯著扭曲面片時，出現(xiàn)的結(jié)果就不是很理想，以汽車或船舶造型中用網(wǎng)格模擬鋼板扭曲為例，由于材料的韌性，會產(chǎn)生均勻向性扭曲，如圖1中原始網(wǎng)格上，面片EFGH繞面片的一個中心軸轉(zhuǎn)動120°，帶動面片CDEH產(chǎn)生顯著扭曲.理想狀態(tài)下，原始網(wǎng)格均勻扭曲得到的新網(wǎng)格，是一個可展曲面，這個曲面在一個平面上重新展開時，期望它能得到與原網(wǎng)格幾何特性相同的結(jié)果.對于圖1中的扭曲網(wǎng)格，理想細分結(jié)果應(yīng)該是中間部分保持寬度的情況下均勻變化接合首尾面片，如圖1中理想扭曲細分所示，這個網(wǎng)格平展后基本保持與原始網(wǎng)格一致.經(jīng)典細分方法在處理規(guī)則網(wǎng)格時都能達到一些光滑性較好的結(jié)果，但沒有顧及到上述這種顯著扭曲的情形，在含有顯著扭曲面片的場合下得到的結(jié)果往往與期望結(jié)果有出入，如圖2所示，兩種經(jīng)典細分方法對圖1中有扭曲面片的網(wǎng)格進行細分后的結(jié)果及其在平面上展開的結(jié)果.

可以看到，兩種細分結(jié)果的光順性都非常好，這個是它們的優(yōu)點;但在扭曲角度較大的情況下，經(jīng)典細分方法得到的網(wǎng)格在平面展開后，中間收縮得非常接近，以致幾乎喪失了原來面片的基本特征，這種扭曲能模擬類似橡膠材質(zhì)等彈性面的扭曲變形，與鋼板等韌性材料均勻受力扭曲變形的實際情況相差甚遠.因而對這種模擬韌性材質(zhì)顯著扭曲面片情況下的網(wǎng)格進行有針對性的處理是非常必要的.

圖1 含扭曲面片的網(wǎng)格理想變形

圖2 含扭曲面片的網(wǎng)格細分變形

2 面片扭曲分析與檢測

在圖3中，未扭曲的四邊形面片ABCD若沿中心軸旋轉(zhuǎn)一圈則得到一個棱臺;扭曲后四邊形面片ABCD沿中心軸旋轉(zhuǎn)一圈得到的立體是圓錐面的一部分.面片ABCD發(fā)生前述韌性扭曲的時候，我們期望它是沿棱臺的表面產(chǎn)生扭曲，而經(jīng)典細分給出的結(jié)果是按圓錐曲面進行扭曲的.

圖3 多邊形扭曲檢測

一個面片是否發(fā)生扭曲，可以用相鄰棱來判定.如圖3中的四邊形ABCD，它的AD邊繞中心軸轉(zhuǎn)動，帶動面片發(fā)生扭曲.設(shè)該四邊形幾何中心為O，則在AD轉(zhuǎn)動過程中，三角形BOC、AOD的形狀保持不變，這兩個三角形所在的兩個面片之間的有序夾角恰好反映了當前面片的扭曲情況.設(shè)圖中四邊形ABCD的中心是O點，AD旋轉(zhuǎn)了一定角度?，AB棱上隨面片扭曲后的任意一點T，其細分位置是在某個圓錐曲面上的，根據(jù)棱臺與圓錐之間的關(guān)系，可以按下式將T點從沿著圓錐曲面位置修正到沿著棱臺曲面的位置:

其中是兩個相對棱的扭曲角度，為當前T點局部扭曲角度.

圖4 經(jīng)典Doo－Sabin細分過程

圖5 Doo－Sabin細分與扭曲校正細分結(jié)果的對比

對于多邊形面片，只要將目標棱及其兩端的鄰棱一起，構(gòu)成一個四邊形，就可以按照四邊形的操作方法進行扭曲檢測和對細分頂點進行校正，如圖3中的多邊形面片，當我們使用細分方法處理它的時候，在BC棱上，與棱BC相鄰的分別是棱AB和棱CD，連接A、D構(gòu)成一個虛擬四邊形ABCD，若A與D重合，則ABCD是一個三角形面片，不需要處理;否則是一個四邊形面片，這時按照前面所述處理四邊形面片的方法進行處理即可.

下面以經(jīng)典Doo－Sabin細分方法為例，詳細介紹如何修改細分過程使之能恰當?shù)奶幚砗信で嫫木W(wǎng)格.

3 Doo－Sabin方法對扭曲面片的校正

經(jīng)典Doo－Sabin細分方法簡述:對于初始控制網(wǎng)格Mk，其中任意一個多邊形Pk的頂點(0≤i≤n)，細分后對應(yīng)的多邊形為Pk+1，每個頂點生成對應(yīng)的新的頂點:

具體細分步驟:

(1)對初始控制網(wǎng)格Mk的每個頂點應(yīng)用式(2)生成新的頂點;

(2)依次連接控制網(wǎng)格Mk的每個面中的所有新生成的頂點得到F面;

(3)依次連接控制網(wǎng)格Mk的每個邊兩邊面所對應(yīng)的新頂點得到E面;

(4)依次連接控制網(wǎng)格Mk的每個點新生成的頂點得到V面;

經(jīng)典Doo－Sabin屬于逼近型細分方法，具有良好的光滑性，當初始網(wǎng)格為正則四邊形的時候，可以生成二次B樣條曲面，在奇異點處至少可以達一階連續(xù).其中F面生成過程是內(nèi)斂的，與外部面無關(guān)，我們可以在經(jīng)典Doo－Sabin生成F面的(2)過程中加入對扭曲的檢測，即對當前面片的每一條棱，檢測與它端點相鄰的棱是否為邊緣棱(這個棱只有一個相鄰面)，如果是邊緣棱則按上節(jié)討論進行扭曲判斷與校正;否則棱有兩個相鄰面，這時交由細分方法進行正常處理.這里不討論棱沒有相鄰面或者棱有多于兩個相鄰面等對于細分方法來說是病態(tài)網(wǎng)格的情況.

對于Catmull－Clark細分，只要在其第一次細分時應(yīng)用上述方法對網(wǎng)格進行處理校正即可;LOOP細分也是在第一次三角化時應(yīng)用上述方法對面片進行處理校正，這里不再贅述.

這里選擇莫比烏斯面，分別使用經(jīng)典Doo－Sabin細分和使用了扭曲校正的Doo－Sabin細分改進方法，得到圖5的結(jié)果.

4 實際結(jié)果及分析

從圖5可以看到，在圖形右側(cè)有顯著扭曲的面片處，經(jīng)典Doo－Sabin細分方法在處理顯著扭曲面片時，扭曲處會收縮得非常窄(如圖5中“第四次細分”上箭頭標注);而在增加扭曲修正后，得到的面片基本符合期望的韌性扭曲特征.

此方法可以根據(jù)需要，在網(wǎng)格中存在顯著扭曲而經(jīng)典細分不能給出期望結(jié)果時對細分結(jié)果進行校正，且不會改變原細分方法的連續(xù)性和光順性，所以原細分方法仍保持自己的連續(xù)性特征.

5 結(jié)論

從經(jīng)典細分過程在空間網(wǎng)格中含有顯著扭曲面片情況下會產(chǎn)生的不理想結(jié)果開始，詳細討論了問題形成原因及解決思路，給出了較通用的扭曲面片校正方法，此方法簡捷有效易于實現(xiàn)，且可以集成到經(jīng)典Doo－Sabin細分方法中使用而且保持原有的細分方法的光滑特性，在實踐中得到了較好的結(jié)果.此外，該方法與其它細分方法的結(jié)合，還需要做進一步研究.

[1]Catmull E，Clark J.Recursively Generated B － spline Surfaces on Arbitrary Topological Meshes[J]Computer － Aided Design，1978，10(6):350 －355.

[2]Doo D，Sabin M.Behavior of Recursive Division Surfaces Near Extraordinary Points[J]Computer － Aided Design，1978，10(6):356－360.

[3]Loop C T.Smooth Subdivision Surfaces Based on Triangles[D].M.S.Thesis，Department of Mathematics，University of Utah，1987.

[4]Nira Dyn，David Levin.Subdivision Schemes in Geometric Modelling[EB]，1998.Israel Tel－ Aviv University 19 －23.

[5]Sederberg，T.，Zheng，J.，Swell，D.，Sabin，M.，Non － uniform Recursive Subdivision Surfaces.In Computer Graphics Proceedings，ACM SIGGRAPH，1998:387－394.

[7]張湘玉.保細節(jié)的基于曲面控制的網(wǎng)格變形[J].華南理工大學(xué)學(xué)報，2010，38:39 －44.