三角網(wǎng)格模型的自動分割算法

孫殿柱,朱昌志,李延瑞,牛宗偉

(山東理工大學機械工程學院,淄博 255091)

逆向工程中,為便于對三角網(wǎng)格模型進行編輯、造型,通常將 1個三角網(wǎng)格分為多個,即網(wǎng)格分割.現(xiàn)有的方法主要基于曲率對網(wǎng)格模型進行自適應分割[1-3],將曲率值相近的三角面片劃為同一區(qū)域,該方法不能根據(jù)設(shè)計意圖自由選取分割邊界,適應性差.

文獻[4]提出基于最短路徑的三角網(wǎng)格交互式分割算法,由用戶指定分割線的起點和終點,采用 Dijkstra算法在指定區(qū)域內(nèi)計算 2個點間的最短路徑,以該路徑為分割線,對三角網(wǎng)格進行分割,對于型面特征復雜的三角網(wǎng)格,該算法難以快速有效地選擇分割線所在區(qū)域,計算最短路徑時,需遍歷較多的三角面片,算法運行量大,且該方法在分割面處會產(chǎn)生鋸齒現(xiàn)象,不能準確地表達分割后模型的邊界信息.

針對上述問題,本文提出一種根據(jù)設(shè)計意圖的三角網(wǎng)格模型自動分割算法,該算法采用 R*-tree(recangle*-tree)建立三角網(wǎng)格空間索引結(jié)構(gòu),基于該結(jié)構(gòu),采用深度優(yōu)先遍歷方法快速準確地查詢與分割面相交的三角面片,對相交三角面片進行分割并重新剖分,實現(xiàn)三角網(wǎng)格模型不受曲率等條件限制的自動分割,該算法可對各種復雜型面三角網(wǎng)格進行分割,算法運行效率高,且能有效避免分割區(qū)域的鋸齒現(xiàn)象.

1 三角網(wǎng)格空間索引結(jié)構(gòu)

采用 R*-tree[5-7]建立三角網(wǎng)格空間索引結(jié)構(gòu),依據(jù) MBR(m inimum bounding rectangle)體積增量衡量幾何對象間的相似性,若局部三角面片平行于坐標平面分布,結(jié)點 MBR體積增量為 0,導致 R*-tree結(jié)點分裂失效,破壞了結(jié)點間的聚合性.針對上述問題,將三角面片及索引結(jié)點 MBR統(tǒng)一表示為四維點對象(x,y,z,r),其中,x,y,z為 MBR中心坐標,r為 MBR外接球半徑值,采用 k-means算法[8]對 R*-tree各層結(jié)點進行空間聚類分簇,建立三角網(wǎng)格空間索引結(jié)構(gòu),實現(xiàn)三角網(wǎng)格的動態(tài)存取及相交三角面片的快速查詢.

圖1為維納斯頭部三角網(wǎng)格曲面模型的空間索引結(jié)構(gòu),該結(jié)構(gòu)由 4種結(jié)點組成,最上層為根結(jié)點,最底層為數(shù)據(jù)結(jié)點,次底層為葉結(jié)點,其余為內(nèi)部結(jié)點,每個數(shù)據(jù)結(jié)點存儲 1個三角面片.

2 相交三角面片的查詢

索引結(jié)點 MBR的頂點為 vi(1≤i≤8),q為分割面上任意點,n為分割面的法向量,采用式(1)判斷索引結(jié)點與分割面的位置關(guān)系,即

圖1 維納斯頭像網(wǎng)格模型的空間索引結(jié)構(gòu)Fig.1 Spatialindexstructureoftriangularmesh

若 εi＜0,表示索引結(jié)點位于分割面負側(cè);若 εi＞0,表示索引結(jié)點位于分割面正側(cè).如圖 2(a)所示,若索引結(jié)點 8個頂點的 εi值均為正(或負),則表示索引結(jié)點與分割面相離;如圖 2(b)所示,若 εi值不全部為正(或負),表示索引結(jié)點與分割面相交.基于以上判斷法則,獲取分割面相交三角面片的具體步驟為:1)輸入 R*-tree根結(jié)點;2)如果輸入結(jié)點為數(shù)據(jù)結(jié)點,判斷該結(jié)點與切片的位置關(guān)系,若相交,則執(zhí)行步驟 3),否則執(zhí)行步驟 4);3)依據(jù)三角面片的頂點與分割面的位置關(guān)系判斷其是否與分割面相交,若相交,則將其添加到序列 L中;4)若結(jié)點為內(nèi)部結(jié)點,則循環(huán)取當前結(jié)點的子結(jié)點,執(zhí)行步驟 2).基于三角網(wǎng)格空間索引結(jié)構(gòu),采用深度優(yōu)先遍歷方法獲取與分割面相交的三角面片,如圖 3所示,其中,深色所示為與分割面相交的索引結(jié)點或三角面片,可以看出,本文算法只對少數(shù)三角面片進行相交判斷,顯著減小了數(shù)據(jù)處理量.

圖2 索引結(jié)點與分割面的位置關(guān)系Fig.2 Therelationshipbetweenindexnodeandsliceplane

圖3 相交三角面片的獲取Fig.3 Acquireofintersectiontriangles

3 相交三角面片的剖分

針對圖 4所示三角面片與分割面的位置關(guān)系,制定 5組方案對相交三角面片進行剖分,具體為:1)如圖 4(a)所示,若 1個頂點位于分割面上,其余 2個頂點位于分割面同側(cè),則不對該三角面片進行剖分;2)如圖 4(b)所示,若 1個頂點位于分割面上,其余 2個頂點位于分割面異側(cè),則將△ABC分為△ABD和△BCD;3)如圖 4(c)所示,若三角形的 3個頂點分別位于分割面的兩側(cè),則將其分為 3個三角形;4)如圖4(d)所示,若三角面片有 2個頂點位于分割面上,則不對其進行剖分;5)如圖 4(e)所示,若三角面片的 3個頂點均位于分割面上,即三角面片所在平面與分割面重合,則不對其進行剖分.

圖4 三角面片與分割面的位置關(guān)系Fig.4 The relationshipbetween triangle and section plane

4 應用實例

制定 2組方案對本文算法進行驗證:

方案 1中,采用文獻[4]算法及本文算法對圖 5(a)所示摩托車油箱三角網(wǎng)格模型進行分割,該模型的三角面片數(shù)為 10111,從圖 5中可以看出,文獻[4]算法以相交三角面片的邊作為相交邊界,分割后的模型在分割面處出現(xiàn)了鋸齒現(xiàn)象,邊界特征不明顯,本文算法對相交三角面片進行分割與重構(gòu),有效避免了此問題.

圖5 摩托車油箱模型的分割效果Fig.5 Partition result of oil box

方案 2中,采用文獻[4]算法及本文算法對圖 6所示三角網(wǎng)格模型進行分割,模型的三角面片數(shù)分別為 9412、56 459、69 474、1765388,運行時間如表 1所示.從表 1中可以看出,本文算法的運行效率明顯高于文獻[4]算法,平均提高 2～3倍.

圖6 三角網(wǎng)格模型Fig.6 Triangularmesh models

表1 2種算法的運行時間比較Tab le 1 Running time of different algorithms s

5 結(jié)論

1)基于 R*-tree建立三角網(wǎng)格模型動態(tài)空間索引結(jié)構(gòu),可對各種復雜型面三角網(wǎng)格模型進行分割,算法適應性強;

2)基于三角網(wǎng)格空間索引結(jié)構(gòu),采用深度優(yōu)先遍歷方法可快速準確地獲取與分割面相交的三角面片,提高了算法運行效率,平均提高 2～3倍;

3)對分割面相交三角面片進行剖分與重構(gòu),避免了分割面處的鋸齒現(xiàn)象.

[1]呂漢明,王揚.采用混合策略的三角網(wǎng)格模型區(qū)域劃分算法[J].華中科技大學學報:自然科學版,2007,35(增刊):54-57.LüHan-ming,WANG Yang.Using hybrid strategy to partition trianglemeshes[J].Journal of Huazhong University of Science and Technology:Nature Science Edition,2007,35(Supp.):54-57.(in Chinese)

[2]孟敏,計忠平,劉利剛.基于保特征調(diào)和場的交互式網(wǎng)格分片[J].計算機輔助設(shè)計與圖形學學報,2008,20(9):1146-1152.MENG Min,JI Zhong-ping,LIU Li-gang.Interactive mesh segmentation based on feature preserving harmonic field[J].Journalof Computer-Aided Design＆Computer Graphics,2008,20(9):1146-1152.(in Chinese)

[3]VANCO M,BRUNNETT G.Towards automatic segmentation in reverse engineering[C]//Proceeding of the International Symposium on Cyberworlds.Tokyo:[s.n.],2002:24-32.

[4]神會存,周來水,安魯陵,等.曲面三角網(wǎng)格模型頂點法矢計算與交互式分割[J].計算機輔助設(shè)計與圖形學學報,2005,17(5):1030-1033.SHEN Hui-cun,ZHOU Lai-shui,AN Lu-ling.Vertex normal calculation and interactive segmentation of triangle mesh[J].Journal of Computer-Aided Design＆Computer Graphics,2005,17(5):1030-1033.(in Chinese)

[5]孫殿柱,李心成,范志先,等.采用R*-tree的三角網(wǎng)格曲面非均勻精簡算法[J].西安交通大學學報,2008,42(9):1179-1183.SUN Dian-zhu,LIXin-cheng,FAN Zhi-xian,etal.Research on simplification algorithm for triangularmesh surface based on R*-tree[J].Academic Journalof Xi'an Jiaotong University,2008,42(9):1179-1183.(in Chinese)

[6]郭薇,郭菁,胡志勇.空間數(shù)據(jù)庫索引技術(shù)[M].上海:上海交通大學出版社,2006:237-243.

[7]BECKMANN N,KRIEGEL H P,SCHNEIDER R,et al.The R*-tree:an efficient and robust accessmethod for points and rectangles[J].ACM SIGMOD Record,1990,19(2):322-331.

[8]BRAKATSOULAS S,PFOSER D,THEODORIDIS Y.Revisiting R-tree construction principles[C]//ADBIS.Bratislava,Slovakia:[s.n.],2002:149-162.