三角網格曲面模型快速分層算法

孫殿柱 朱昌志 李延瑞

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

三角網格曲面模型快速分層算法

孫殿柱 朱昌志 李延瑞

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

提出一種三角網格曲面模型快速分層算法,該算法基于 R*-tree建立三角網格動態空間索引結構,依據索引結構數據結點的分布狀況計算各層截平面的位置;采用深度優先遍歷方法獲取與截平面相交的三角面片集合,并計算該集合中各面片與截平面的交線,將交線首尾相連,生成截面輪廓線,實現三角網格曲面模型的快速分層;實例證明該算法可對各種復雜三角網格曲面模型進行分層,算法準確、穩定,運行效率高.

三角網格曲面模型;R*-tree;深度優先遍歷;截面輪廓線;快速分層

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

目前,三角網格曲面模型的分層方法主要有2類:第 1類基于三角網格拓撲關系進行分層[2-3];第 2類基于三角面片幾何特征進行分層[1,4-5].

第 1類方法建立三角面片鄰接關系表,令第1個與截平面相交的三角面片為初始面片,計算其與截平面的交線段,依據鄰接關系表查詢初始面片的鄰接三角面片,并計算該面片與截平面的交線,依次追蹤,直至得到當前層封閉的截面輪廓線;重復上述過程獲取所有層的截面輪廓線,實現三角網格曲面模型的分層處理.該方法需建立三角面片鄰接關系表,系統資源消耗高,算法運行效率低.

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

針對上述問題,提出一種三角網格曲面模型的快速分層算法,該算法基于 R*-tree[6-8]建立三角網格動態空間索引結構,以該結構組織三角面片間的拓撲關系,基于該結構計算各層截平面的位置并獲取與截平面相交的三角面片集合,計算集合中各面片與截平面的交線,并將交線首尾相連,生成截面輪廓線;最后通過 2組實驗方案驗證了該算法的可行性.

1 動態空間索引結構的建立

通過改進 R*-tree建立三角網格動態空間索引結構,實現三角網格的動態存取及相交三角面片的快速查詢.

1.1 索引結點規范化表示

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

圖1 索引結點規范化表示

1.2 三角面片集合的 k-m eans聚類分簇

采用 k-means算法[10]實現三角面片集合的空間聚類分簇.在選取初始分簇中心時,為減少 kmeans迭代次數,將結點中心相距最遠的一對結點的 MBR中心作為初始分簇中心.

確定初始分簇中心后,將數據對象添加到中心距其最近的分簇中.為使結點 MBR均勻,避免出現 MBR奇異的結點,根據 R*-tree定義,若分裂所得結點的子結點數 k小于 R*-tree最小子結點數 m,則將另一簇中距離當前簇較近的(m-k)個結點插入到當前簇中,并調整分裂結果.

采用 k-means算法對 R*-tree索引結點進行聚類分簇,需要迭代定位最終的分簇中心.對于同簇結點中的 N個索引結點,其四維標準化坐標為分簇中心坐標)可由下式計算:

各索引結點至聚類分簇中心的距離,可由公式(1)計算:

該索引結構由 4種結點組成,最上層為根結點,最底層為數據結點,次底層為葉結點,其余為內部結點,每個數據結點存儲一個三角面片.基于四維點表示的三角網格動態空間索引結構如圖 2所示.

圖2 維納斯頭像網格模型的空間索引結構

2 三角網格曲面模型的快速分層

2.1 索引結點與截平面的位置關系

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

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

圖3 索引結點與截平面的位置關系

2.2 截平面位置的計算

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

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

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

2.3 相交三角面片的獲取

基于以上判斷法則,深度優先遍歷三角網格動態空間索引結構,獲取與截平面相交的三角面片,具體步驟如下:

1)輸入 R*-tree根結點;

2)若當前結點為數據結點,判斷該結點與截平面的位置關系,若相交,則將該結點包含的三角面片添加到相交三角面片序列 L中;

3)若結點為內部結點,則循環取得當前結點的子結點,執行步驟 2).

2.4 交線段的計算及排序

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

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

2)若無點落在截平面上,則依據三角面片各頂點計算交線段;

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

圖4 三角面片與截平面的位置關系

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

3 應用實例

制定 2組實驗方案對本文算法進行驗證.方案 1采用本文算法及相關算法對同一三角網格曲面模型進行分層處理,分析不同算法的分層效果;方案 2采用本文算法及相關算法對不同三角網格曲面模型進行分層,分析不同算法的運行效率及適應性.

方案 1中,采用本文算法及文獻[5]算法對圖 5a所示三角網格模型進行分層處理,層數均為50,分層效果如圖 5b和圖 5c所示.可以看出,本文算法分層處理后的模型在型面特征復雜區域截面數據分布較為密集,在平坦區域截面數據分布較為稀疏,達到了準確表達模型外形信息的目的.

圖5 b lade模型及分層效果

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

圖6 三角網格模型

表 1 不同算法的運行時間 s

4 結 論

本文算法與相關算法相比具有以下優點:

1)基于 R*-tree建立三角網格曲面模型動態空間索引結構,可對各種復雜型面三角網格曲面模型進行分層,算法適應性強;

2)依據索引結構各層數據結點的分布情況計算相鄰層截平面的位置,有效提高了分層數據的準確性;

3)基于三角網格動態空間索引結構,快速準確地獲取與截平面相交的三角面片,提高了三角網格曲面模型的分層效率.

References)

[1]胡德州,李占利,李滌塵,等.基于 STL模型幾何特征分類的快速分層處理算法研究[J].西安交通大學學報,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]趙吉賓,劉偉軍.快速成形技術中基于 STL模型的分層算法研究[J].應用基礎與工程科學學報,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數據模型的快速切片算法[J].北京航空航天大學學報,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].西安交通大學學報,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]孫殿柱,朱昌志,李延瑞.散亂點云邊界特征快速提取算法[J].山東大學學報:工程科學版,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]孫殿柱,范志先,李延瑞,等.散亂數據點云型面特征分析算法的研究與應用[J].機械工程學報,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的三角網格曲面非均勻精簡算法[J].西安交通大學學報,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樹家族的演變和發展[J].計算機學報,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

國家 863計劃資助項目(2006AA 04Z105)

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