孫殿柱 朱昌志 李延瑞

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

三角網(wǎng)格曲面模型快速分層算法

孫殿柱 朱昌志 李延瑞

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

提出一種三角網(wǎng)格曲面模型快速分層算法,該算法基于 R*-tree建立三角網(wǎng)格動(dòng)態(tài)空間索引結(jié)構(gòu),依據(jù)索引結(jié)構(gòu)數(shù)據(jù)結(jié)點(diǎn)的分布狀況計(jì)算各層截平面的位置;采用深度優(yōu)先遍歷方法獲取與截平面相交的三角面片集合,并計(jì)算該集合中各面片與截平面的交線,將交線首尾相連,生成截面輪廓線,實(shí)現(xiàn)三角網(wǎng)格曲面模型的快速分層;實(shí)例證明該算法可對(duì)各種復(fù)雜三角網(wǎng)格曲面模型進(jìn)行分層,算法準(zhǔn)確、穩(wěn)定,運(yùn)行效率高.

三角網(wǎng)格曲面模型;R*-tree;深度優(yōu)先遍歷;截面輪廓線;快速分層

快速成型制造中,通常將 CAD模型離散為三角面片,生成三角網(wǎng)格曲面模型,隨后進(jìn)行分層處理生成截面輪廓線,采用光敏樹(shù)脂等材料堆積出與截面輪廓線形狀一致的薄層,逐層累加,得到零件的實(shí)體模型.高效準(zhǔn)確地對(duì)三角網(wǎng)格曲面模型進(jìn)行分層處理是快速成型制造的首要條件[1].

目前,三角網(wǎng)格曲面模型的分層方法主要有2類(lèi):第 1類(lèi)基于三角網(wǎng)格拓?fù)潢P(guān)系進(jìn)行分層[2-3];第 2類(lèi)基于三角面片幾何特征進(jìn)行分層[1,4-5].

第 1類(lèi)方法建立三角面片鄰接關(guān)系表,令第1個(gè)與截平面相交的三角面片為初始面片,計(jì)算其與截平面的交線段,依據(jù)鄰接關(guān)系表查詢初始面片的鄰接三角面片,并計(jì)算該面片與截平面的交線,依次追蹤,直至得到當(dāng)前層封閉的截面輪廓線;重復(fù)上述過(guò)程獲取所有層的截面輪廓線,實(shí)現(xiàn)三角網(wǎng)格曲面模型的分層處理.該方法需建立三角面片鄰接關(guān)系表,系統(tǒng)資源消耗高,算法運(yùn)行效率低.

第 2類(lèi)方法分別依據(jù)三角面片 z坐標(biāo)的最小值和最大值對(duì)所有三角面片排序,得到最小值序列和最大值序列;在分層處理時(shí),分別遍歷兩序列,排除最小 z值大于截平面高度和最大 z值小于截平面高度的面片,得到與截平面相交的三角面片,并計(jì)算其與截平面的交線,將交線首尾相連,得到截面輪廓線.該方法需對(duì)三角面片進(jìn)行 2次排序,且查詢相交三角面片時(shí)分別遍歷最小值序列與最大值序列,算法運(yùn)行效率低.

針對(duì)上述問(wèn)題,提出一種三角網(wǎng)格曲面模型的快速分層算法,該算法基于 R*-tree[6-8]建立三角網(wǎng)格動(dòng)態(tài)空間索引結(jié)構(gòu),以該結(jié)構(gòu)組織三角面片間的拓?fù)潢P(guān)系,基于該結(jié)構(gòu)計(jì)算各層截平面的位置并獲取與截平面相交的三角面片集合,計(jì)算集合中各面片與截平面的交線,并將交線首尾相連,生成截面輪廓線;最后通過(guò) 2組實(shí)驗(yàn)方案驗(yàn)證了該算法的可行性.

1 動(dòng)態(tài)空間索引結(jié)構(gòu)的建立

通過(guò)改進(jìn) R*-tree建立三角網(wǎng)格動(dòng)態(tài)空間索引結(jié)構(gòu),實(shí)現(xiàn)三角網(wǎng)格的動(dòng)態(tài)存取及相交三角面片的快速查詢.

1.1 索引結(jié)點(diǎn)規(guī)范化表示

R*-tree結(jié)點(diǎn)插入算法以 MBR(Minimum Bounding Rectangle)體積增量[9]作為結(jié)點(diǎn)聚類(lèi)分簇的判定條件,該算法應(yīng)用于三角面片集合的空間聚類(lèi)分簇時(shí),若局部三角面片平行于坐標(biāo)平面分布,結(jié)點(diǎn)的 MBR將由三維退化為二維,體積增量為零,導(dǎo)致 R*-tree結(jié)點(diǎn)插入失效,破壞了R*-tree結(jié)點(diǎn)的聚合性.為解決該問(wèn)題,如圖 1所示,將三角面片及索引結(jié)構(gòu)的結(jié)點(diǎn)MBR統(tǒng)一表示為四維點(diǎn)對(duì)象(x,y,z,r),其中 x,y,z為結(jié)點(diǎn) MBR中心坐標(biāo),r為結(jié)點(diǎn) MBR外接球半徑.

圖1 索引結(jié)點(diǎn)規(guī)范化表示

1.2 三角面片集合的 k-m eans聚類(lèi)分簇

采用 k-means算法[10]實(shí)現(xiàn)三角面片集合的空間聚類(lèi)分簇.在選取初始分簇中心時(shí),為減少 kmeans迭代次數(shù),將結(jié)點(diǎn)中心相距最遠(yuǎn)的一對(duì)結(jié)點(diǎn)的 MBR中心作為初始分簇中心.

確定初始分簇中心后,將數(shù)據(jù)對(duì)象添加到中心距其最近的分簇中.為使結(jié)點(diǎn) MBR均勻,避免出現(xiàn) MBR奇異的結(jié)點(diǎn),根據(jù) R*-tree定義,若分裂所得結(jié)點(diǎn)的子結(jié)點(diǎn)數(shù) k小于 R*-tree最小子結(jié)點(diǎn)數(shù) m,則將另一簇中距離當(dāng)前簇較近的(m-k)個(gè)結(jié)點(diǎn)插入到當(dāng)前簇中,并調(diào)整分裂結(jié)果.

采用 k-means算法對(duì) R*-tree索引結(jié)點(diǎn)進(jìn)行聚類(lèi)分簇,需要迭代定位最終的分簇中心.對(duì)于同簇結(jié)點(diǎn)中的 N個(gè)索引結(jié)點(diǎn),其四維標(biāo)準(zhǔn)化坐標(biāo)為分簇中心坐標(biāo))可由下式計(jì)算:

各索引結(jié)點(diǎn)至聚類(lèi)分簇中心的距離,可由公式(1)計(jì)算:

該索引結(jié)構(gòu)由 4種結(jié)點(diǎn)組成,最上層為根結(jié)點(diǎn),最底層為數(shù)據(jù)結(jié)點(diǎn),次底層為葉結(jié)點(diǎn),其余為內(nèi)部結(jié)點(diǎn),每個(gè)數(shù)據(jù)結(jié)點(diǎn)存儲(chǔ)一個(gè)三角面片.基于四維點(diǎn)表示的三角網(wǎng)格動(dòng)態(tài)空間索引結(jié)構(gòu)如圖 2所示.

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

2 三角網(wǎng)格曲面模型的快速分層

2.1 索引結(jié)點(diǎn)與截平面的位置關(guān)系

令索引結(jié)點(diǎn)的頂點(diǎn)為 vi(1≤i≤8),q為截平面上任意點(diǎn),n為截平面的法矢,采用公式(2)判斷索引結(jié)點(diǎn)與截平面的位置關(guān)系.

若 εi＜0,表示索引結(jié)點(diǎn)位于截平面負(fù)側(cè);若 εi＞0,表示索引結(jié)點(diǎn)位于截平面正側(cè).如圖 3a所示,若索引結(jié)點(diǎn) 8個(gè)頂點(diǎn)的 εi值均為正(或負(fù)),則表示該結(jié)點(diǎn)與截平面相離;如圖 3b所示,若 εi的值不同時(shí)為正(或負(fù)),表示該結(jié)點(diǎn)與截平面相交.

圖3 索引結(jié)點(diǎn)與截平面的位置關(guān)系

2.2 截平面位置的計(jì)算

設(shè)截平面平行于 xOy平面分布,法矢 n指向z軸正方向,三角網(wǎng)格在 z軸上的極值為 zmin與zmax,采用公式(3)計(jì)算初始截平面位置:

其余各層截平面的位置可由公式(4)計(jì)算:

令與第 i層截平面相交的數(shù)據(jù)結(jié)點(diǎn)集合為 L,則 εj為 L中各數(shù)據(jù)結(jié)點(diǎn)的頂點(diǎn)距截平面的距離,由公式(2)計(jì)算;n為 L中位于截平面正側(cè)(即εj＞0)的數(shù)據(jù)結(jié)點(diǎn)頂點(diǎn)數(shù);μ為控制層數(shù)的參數(shù),與層數(shù)成反比,通常取 1.0.

2.3 相交三角面片的獲取

基于以上判斷法則,深度優(yōu)先遍歷三角網(wǎng)格動(dòng)態(tài)空間索引結(jié)構(gòu),獲取與截平面相交的三角面片,具體步驟如下:

1)輸入 R*-tree根結(jié)點(diǎn);

2)若當(dāng)前結(jié)點(diǎn)為數(shù)據(jù)結(jié)點(diǎn),判斷該結(jié)點(diǎn)與截平面的位置關(guān)系,若相交,則將該結(jié)點(diǎn)包含的三角面片添加到相交三角面片序列 L中;

3)若結(jié)點(diǎn)為內(nèi)部結(jié)點(diǎn),則循環(huán)取得當(dāng)前結(jié)點(diǎn)的子結(jié)點(diǎn),執(zhí)行步驟 2).

2.4 交線段的計(jì)算及排序

如圖 4所示,三角面片與截平面相交存在以下 3種情況,交線段的計(jì)算方法如下:

1)若有 2點(diǎn)落在截平面上,則以該 2點(diǎn)組成的線段為交線段;

2)若無(wú)點(diǎn)落在截平面上,則依據(jù)三角面片各頂點(diǎn)計(jì)算交線段;

3)若只有一點(diǎn)落在截平面上,則不計(jì)算其與截平面的交線段.

圖4 三角面片與截平面的位置關(guān)系

采用文獻(xiàn)[1]算法將交線段首尾相連,得到有序的截面輪廓線,實(shí)現(xiàn)三角網(wǎng)格曲面模型的分層處理.

3 應(yīng)用實(shí)例

制定 2組實(shí)驗(yàn)方案對(duì)本文算法進(jìn)行驗(yàn)證.方案 1采用本文算法及相關(guān)算法對(duì)同一三角網(wǎng)格曲面模型進(jìn)行分層處理,分析不同算法的分層效果;方案 2采用本文算法及相關(guān)算法對(duì)不同三角網(wǎng)格曲面模型進(jìn)行分層,分析不同算法的運(yùn)行效率及適應(yīng)性.

方案 1中,采用本文算法及文獻(xiàn)[5]算法對(duì)圖 5a所示三角網(wǎng)格模型進(jìn)行分層處理,層數(shù)均為50,分層效果如圖 5b和圖 5c所示.可以看出,本文算法分層處理后的模型在型面特征復(fù)雜區(qū)域截面數(shù)據(jù)分布較為密集,在平坦區(qū)域截面數(shù)據(jù)分布較為稀疏,達(dá)到了準(zhǔn)確表達(dá)模型外形信息的目的.

圖5 b lade模型及分層效果

方案 2中,采用本文算法及文獻(xiàn)[5]算法對(duì)圖 6所示的 4種三角網(wǎng)格模型進(jìn)行分層,各模型的三角面片數(shù)分別為 12 520,40 168,1 087 716,1765388,將各模型分為 50層,各算法運(yùn)行時(shí)間如表 1所示.可見(jiàn),本文算法有效提高了三角網(wǎng)格曲面模型的分層效率,平均提高 30%～50%.

圖6 三角網(wǎng)格模型

表 1 不同算法的運(yùn)行時(shí)間 s

4 結(jié) 論

本文算法與相關(guān)算法相比具有以下優(yōu)點(diǎn):

1)基于 R*-tree建立三角網(wǎng)格曲面模型動(dòng)態(tài)空間索引結(jié)構(gòu),可對(duì)各種復(fù)雜型面三角網(wǎng)格曲面模型進(jìn)行分層,算法適應(yīng)性強(qiáng);

2)依據(jù)索引結(jié)構(gòu)各層數(shù)據(jù)結(jié)點(diǎn)的分布情況計(jì)算相鄰層截平面的位置,有效提高了分層數(shù)據(jù)的準(zhǔn)確性;

3)基于三角網(wǎng)格動(dòng)態(tài)空間索引結(jié)構(gòu),快速準(zhǔn)確地獲取與截平面相交的三角面片,提高了三角網(wǎng)格曲面模型的分層效率.

References)

[1]胡德州,李占利,李滌塵,等.基于 STL模型幾何特征分類(lèi)的快速分層處理算法研究[J].西安交通大學(xué)學(xué)報(bào),2000,34(1):37-40 Hu Dezhou,Li Zhanli,Li Dichen,et al.Algorithm for rapid slicing based on geometric feature classification of STLmodel[J].Journal of Xi'an Jiaotong University,2000,34(1):37-40(in Chinese)

[2]Pan Haipeng,Zhou Tianrui.Generation and optimization of slice profile data in rapid prototyping and manufacturing[J].Journal of Materials Processing Technology,2007,187/188:623-626

[3]趙吉賓,劉偉軍.快速成形技術(shù)中基于 STL模型的分層算法研究[J].應(yīng)用基礎(chǔ)與工程科學(xué)學(xué)報(bào),2008,12(6):224-233 Zhao Jibin,Liu Weijun.Research on slicing algorithm based on STLmodal for rapid prototyping technology[J].Journal of Basic Science and Engineering,2008,12(6):224-233(in Chinese)

[4]趙保軍,汪蘇,陳五一.STL數(shù)據(jù)模型的快速切片算法[J].北京航空航天大學(xué)學(xué)報(bào),2004,30(4):329-333 Zhao Baojun,Wang Su,Chen Wuyi.Algorithm for rapid slicing STLmodel[J].Journal of Beijing University of Aeronautics and Astronautics,2004,30(4):329-333(in Chinese)

[5]李占利,梁棟,李滌塵,等.基于信息繼承的快速分層處理算法研究[J].西安交通大學(xué)學(xué)報(bào),2002,36(1):43-46 Li Zhanli,Liang Dong,Li Dichen,et al.Algorithm for rapid slicing based on the information inheriting[J].Journal of Xi'an Jiaotong University,2002,36(1):43-46(in Chinese)

[6]孫殿柱,朱昌志,李延瑞.散亂點(diǎn)云邊界特征快速提取算法[J].山東大學(xué)學(xué)報(bào):工程科學(xué)版,2009,39(1):84-86 Sun Dianzhu,Zhu Changzhi,Li Yanrui.An improved extraction of boundary characteristic from scattered data[J].Journal of Shandong University:Engineering Science,2009,39(1):84-86(in Chinese)

[7]孫殿柱,范志先,李延瑞,等.散亂數(shù)據(jù)點(diǎn)云型面特征分析算法的研究與應(yīng)用[J].機(jī)械工程學(xué)報(bào),2007,43(6):133-136 Sun Dianzhu,Fan Zhixian,Li Yanrui,et al.Research and application of surface feature analysis for scatter data points[J].Chinese Journal of Mechanical Engineering,2007,43(6):133-136(in Chinese)

[8]孫殿柱,李心成,范志先,等.采用 R*-tree的三角網(wǎng)格曲面非均勻精簡(jiǎn)算法[J].西安交通大學(xué)學(xué)報(bào),2008,42(9):1179-1183 Sun Dianzhu,Li X incheng,Fan Zhixian,et al.Simplified algorithm for triangular mesh surface based on R*-tree[J].Journal of Xi'an Jiaotong University,2008,42(9):1179-1183(in Chinese)

[9]張明波,陸鋒,申排偉,等.R樹(shù)家族的演變和發(fā)展[J].計(jì)算機(jī)學(xué)報(bào),2005,28(3):289-300 Zhang Mingbo,Lu Feng,Shen Paiwei,et al.The evolvement and progress of r-tree family[J].Chinese Journal of Computers,2005,28(3):289-300(in Chinese)

[10]Brakatsoulas S,Pfoser D,Theodoridis Y.Revisiting R-tree construction principles[C]//Manolopoulos Y,Ndvrat P.6th East European Conference on Advances in Databases and Information Systems.London:Springer-Verlag,2002:149-162

(編 輯:文麗芳)

Fast slicing algorithm for triangular mesh model

Sun Dianzhu Zhu Changzhi Li Yanrui

(School of Mechanical Engineering,Shandong University of Technology,Zibo 255091,China)

A fast slicing algorithm for triangular mesh model was proposed.The node splitting algorithm and the clustering algorithm of R*-tree were improved and the spacial index structure of triangular mesh model was established based on the improved R*-tree.The position of slice planes was computed according to data nodes'distributing of the spacial index structure,thus the distribution of slice planes was intensive in the cragged region of triangular mesh,and the distribution of slice planes was sparse in the smooth region of triangular mesh.The intersection triangular facets with slice plane were obtained with depth-first traversal algorithm of R*-tree.The intersection line segments between slice plane and interection triangular facets were computed and they were sorted end to end,then the orderly section contour lines were obtained.It was proved that this algorithm can obtain section contour line accurately,effectively and has strong adaptability of triangular mesh model.

triangular mesh;R*-tree;depth-first traversal;section contour line;slicing algorithm

TP 391.72

A

1001-5965(2010)03-0279-04

2009-02-27

國(guó)家 863計(jì)劃資助項(xiàng)目(2006AA 04Z105)

孫殿柱(1956-),男,山東煙臺(tái)人,教授,zhuchzhi@126.com.