1、 收稿日期:2004207213.作者簡介:關文革(19662 , 女, 博士研究生; 北京, 中國礦業大學資源與安全學院(100083 .E 2m ail :gwg -007基金項目:教育部跨世紀優秀人才基金資助項目(200023 ; 教育部青年骨干教師基金資助項目(2000265 ; 河北省科技廳攻關資助項目(032135125 .約束數據域Delaunay 四面體網格生成算法關文革1,2武強1賈麗萍2劉明海2(1中國礦業大學資源與安全學院, 北京100083;2石家莊經濟學院, 河北石家莊050031摘要:提出了一種快速Delaunay 四面體網格生成的分治算法三角剖分, 然后從邊界三角

2、形開始遞歸生成四面體網格. 四面體, 邊界三角形都將成為內部四面體的面, , , 而且.關鍵詞:; ; 網格生成; 邊界一致中圖分類號:文獻標識碼:A 文章編號:167124512(2005 0520067203Algorithm of mesh generation of Delaunaytetrahedral in constrained domainGuan Wen ge W u Qiang Jia L i pi ng L i u M i nghaiAbstract :A fast dividing and conquering algorithm of mesh generation

3、of Delaunay tetrahedra in con 2strained domain was presented. After the boundary of the given domain was divided into Delaunay triangles from a given sample point set , tetrahedral meshes was made by selecting a suit point from given point cloud to have Delaunay property. The surface triangles becom

4、e a direct consequence of interior tetrahedron. The algorithm does not require any surface conforming checks to avoid penetrated surface boundaries and over 2lapped tetrahedrons.K ey w ords :constrained domain ; Delaunay tetrahedron ; mesh generation ; boundary conformanceG uan Wen ge Doctoral candi

5、date ; School of Resource &Security , China University of Mining and Tech 2nology , Beijing 100083, China.目前, 四面體網格生成技術廣泛用于地質領域、有限元分析及科學計算可視化等許多領域. 該類算法研究已取得許多重要進展, 主要有局部變換法、Delaunay 三角化增量算法、四叉樹/八叉樹算法、單元生長法、網格前沿法等. 這些算法1,2對二維任意域Delaunay 三角化和三維凸域De 2launay 四面體網格生成的實現比較成熟, 但在三維限定區域四面體網格生成算法理論上還沒有定

6、論. 本文提出一種高效的Delaunay 四面體網格生成算法, 生成的四面體符合空球原則, 邊界三角形是內部四面體的面, 不需邊界一致性檢查, 可避免四面體穿過邊界和狹長四面體的產生, 且算法方便編程.1基本概念四面體網格生成:將空間中任意分布的離散點用直線連在一起, 形成在空間既不重疊又無間隙的緊鄰四面體集. Delaunay 規則:在三維情況下網格符合空球原則, 即每個四面體外接球面內不包含其他點. 在二維情況下網格符合空圓原則, 即每個三角形的外接圓弧內不包含其他點3. 約束Delaunay 剖分:在實際應用中, 部分散亂點之間常常存在某種約束關系, 在進行Delaunay 剖分時, 剖

7、分結果既要符合Delaunay 規則, 又要保證離散點之間的約束關系.第33卷第5期華中科技大學學報(自然科學版 Vol. 33No. 52005年5月J. Huazhong Univ. of Sci. &Tech. (Nature Science Edition May 2005 2約束數據域四面體生成算法描述2. 1數據結構考慮到算法需要, 本文僅對三角形和四面體數據結構簡單描述. 三角形三個頂點的PID 按逆時針排布; 四面體的四個頂點A B CD 則按照如下原則排列:A B C 是四面體的一個面, 從其相對的頂點D 看按逆時針排列, D 是按右手法則大拇指指向的該面對應頂點.2

8、. 2數據域剖分主算法tri -Extend已知三維約束數據域S p s v |v R 3組成, . 首先將數據域S Delaunay 三角剖分, 構成三角形集合a fl =f |f =v i |i =1, 2, 3,v i R 3.本文算法采用文獻4, 5中提供的算法實現.算法tri -Extend 是一個遞歸的分治算法, 輸入數據是簡單數據域S i 的散亂點坐標集合p s 和邊界Delaunay 三角形集合, 輸出結果是剖分所得四面體集合. 為提高四面體剖分效率, 算法的核心思想是在遞歸過程中依次利用垂直于X 軸、Y 軸或者Z 軸的平面a fl -face 將給定數據域空間分為兩個半空間p

9、 s 1和p s 2, 并將初始邊界三角形和四面體生成過程中產生的新三角形, 按照與平面a fl -face 交叉、在平面a fl -face 左側、右側的位置不同依次存放在三角形鏈表a fl0, a fl1和a fl2中. 函數每次遞歸僅對與平面a fl -face 相交的三角形構造Delaunay 四面體, 然后遞歸調用函數, 依次在半空間p 1和p 2中構造四面體.算法中a fl 是主程序傳來的簡單數據域邊界三角形鄰接面表, a fl -face 可以是垂直于X 軸、Y 軸或者Z 軸的平面, 初始值為垂直X 軸的平面. 邊界三角形頂點順序從給定數據域內部觀看按照逆時針方向排列, 由四面體

10、產生的三角形從四面體外部觀看按逆時針排布. 算法步驟如下:步驟1置三角形鏈表a fl0, a fl1, a fl2初值為空.步驟2使用一個平面a fl -face 將點集p s 分割為三部分p s 0, p s 1和p s 2.步驟3將a fl 分割為三個三角形鄰接面表a fl0, a fl1和a fl2.步驟4對a fl0中每個三角形f 1調用簇狀四面體集構造算法MakeSimplex (f , p s , a fl0 生成四面體簇t -link ,ten -lin k =ten -lin k t -link ; 對生成的新四面體除f 1之外的其他面f 調用函數Update (f , a f

11、l0 ; 求a fl -face 的新值.步驟5如果平面a fl1非空, 則遞歸調用函數tri -Extend (int s -id , p -bound , p s 1, a fl1 . 步驟6如果平面a fl2非空, 則遞歸調用函數tri -Extend (int s -id , p -bound , p s 2, a fl2 . 2. 3簇狀四面體集算法MakeSimplex判定點P 與給定A B 所在平面的位置關系公式. D (x , y , , 已A 1, y , (, y 2, z 2 , C (x 3,3A B C 所在平面的位置:假定A B C 頂點順序按逆時針方向排列, 按照

12、右手法則確定, 點D 在右手大拇指所指向方向, 表示在平面的上方; 在右手大拇指所指向方向逆向, 表示在平面下方.設H =xy z 1x 1y 1z 11x 2y 2z 21x 3y 3z 31, 則當H =0時, 表示D 點在平面上; 當H >0時, 表示D 點在平面上方; 當H <0時, 表示D 點在S 面的下方.MakeSimplex 函數算法思想是:依據給定的三角形f 構造一個與當前已經構造的四面體集合和已知的當前數據域邊界三角形沒有重疊和交叉的Delaunay 四面體. 構造過程實際上是尋找與三角形f 對應的另一個頂點V 的過程, 記T (f ,V 為三角形f 與頂點V

13、構成的四面體. 尋找的頂點V 符合以下原則:a . 頂點V 在三角形f 所在平面上方; b . 四面體T (f , V 是Delaunay 四面體, 即外接球內不包含其他頂點;c . 在尋找頂點V 的過程中同時記錄下與V頂點在同一個外接球球面上的其他頂點集合, 存放在鏈表v -link 中. 四面體T (f , V 構造成功后, 會生成除f 之外的新三角形, 繼續為這些新產生的三角形在鏈表v -link 中尋找合適的點構造新四面體.3算法正確性分析3. 1幾個引理設點P 和點Q 位于三角形f 所在平面異側, 以三角形f 所在平面為界將空間分為兩個半空間, 用H (f , P 表示P 一側的半空

14、間. T (f , P 表示三角形f 與P 構成的四面體.86華中科技大學學報(自然科學版 第33卷 引理1設點P 和點Q 在三角形f 的異側, 則四面體T (f , Q 的外接球包含Q 點的充要條件是四面體T (f , P 的外接球包含P 點.引理2設點P 和點Q 在三角形f 的同側, 如果點P 落在四面體T (f , Q 內部或者T (f ,Q 的外接球內部, 則四面體T (f , P 的外接球在半空間H (f , P 一側的半球一定落在T (f ,Q 的外接球在半空間H (f , P 一側的半球內.引理3若四面體T (f , P 是三角形f 與點P 構成的Delaunay 四面體, 則在

15、半空間H (f ,P 一側T (f , P 以與三角形f 構成Delaunay H (f , P 與f 然在T (f , P .引理4若四面體T (f , P 是三角形f 與點P 構成的Delaunay 四面體, 設點P 與點Q 位于f 異側, 若點Q 在T (f , P 外接球的球面上, 則T (f , Q 必然是Delaunay 四面體. 3. 2算法思想正確性分析a . 點V 在三角形f 所在平面上方是選取頂點的必要條件. 證明如下:三角形f 頂點按逆時針排列, f 或者是當前區域外邊界三角形, 或者是一個已經構成的四面體的某個側面, 若頂點V 在平面的下方, 四面體T (f , V 必

16、定在給定數據域邊界以外或者與已經構成的四面體相交; 若在平面的上面, 則不能構成四面體. 因此頂點V 在三角形f 所在平面上方.b . 在有限時間內可生成四面體網格. 設p s是空間中的有限點集, 三角形f 已經與點D 構成Delaunay 四面體T (f , D , 則依據f 構造的另一個四面體的新頂點V 肯定在以f 為界的與點D 異側的半空間內. 由于四面體T (f , D 是Delau 2nay 的, 因此其外接球內必然不包含V 點, 由引理1可知T (f , V 的外接球也必不包含D 點. 由引理2可知半空間H (f , D 一側的點必然不包含在T (f , V 的外接球內, 因此在尋

17、找新點V 構造第二個四面體時, 只需測試半空間H (f , V 一側的點是否包含在T (f , P 的外接球內即可.設點V 和V 1在四面體T (f , D 的同側, 若四面體T (f , V 外接球內部包含點V 1, 由引理2可知, 為T (f , V 1 的外, 選擇V 1作為一, , 因此最V , 使得四面體T (f , V 是Delaunay 四面體.由引理3和引理4可知, 應該將位于當前正在測試四面體外接球球面上的點用鏈表保存, 然后選擇形狀最佳的四面體.參考文獻1Sloa S W. A fast algorithm generating constrained De 2launay

18、 triangulation of Boundary SurfacesJ.Comput 2ers &Structures , 1991, 39(5 :4935002Xu Y A , Y ang Q. The algorithm of 3D constrained De 2launay triangulation J .Journal of S oftware , 2001, 12(1 :1031103Victor J D T. Delaunay triangulations in creation :Anoverview and a linear 2time algorithm J.International Journal of G eographical Information Systems , 1993, 7(6 :5015244Wu Q , Xu H. An ap