四面體剖分的實現(xiàn)

1、四面體剖分的實現(xiàn)1研究現(xiàn)狀網(wǎng)格剖分算法經(jīng)歷了從平面到曲面，再到三維實體剖分的發(fā)展過程，國內(nèi)外 學(xué)者為推動網(wǎng)格剖分的發(fā)展做出了很多貢獻(xiàn)。作為當(dāng)前網(wǎng)格生成領(lǐng)域研究熱點的 四面體剖分，出現(xiàn)了很多方法，其中比較成熟和普遍使用的算法有：Delaunay 法和詢沿推進(jìn)法，以及映射法、柵格法、模板法和多區(qū)域法等。Delaunay法在三維空間存在邊界一致性和薄元處理等問題，由于這些問題 的存在，使Delaunay法適用范圍有限，穩(wěn)定性不好。針對存在的這些問題，Y Bai 等改良了約束Delaunay網(wǎng)格生成算法；陳學(xué)工等提出可消除退化現(xiàn)象引起的潛 在錯誤的方法。前沿推進(jìn)法是節(jié)點和單元同步生成。前沿推進(jìn)法是一種

2、全自動網(wǎng) 格剖分算法，三維的前沿推進(jìn)法是從待剖分域的表面三角形集合（稱作初始前沿 隊列）開始，循環(huán)往復(fù)，當(dāng)前沿隊列為空時結(jié)束的一種網(wǎng)格劃分方法。前沿推進(jìn) 法缺乏一般性的理論支撐，要進(jìn)行大量的算術(shù)判斷，占用了大量時間，因此對數(shù) 據(jù)結(jié)構(gòu)的要求很髙，對于三維空間前沿推進(jìn)法還存在收斂性等問題。基于此很多 人都對前沿推進(jìn)法做了改進(jìn)工作，吳寶海等提出一種兩側(cè)推進(jìn)的波前法，Li等 人釆用III內(nèi)而外的波前推進(jìn)的方式生成了全六面體網(wǎng)格。除過以上介紹的算法，四面體網(wǎng)格劃分有針對不同問題的算法。如陳一民等 提出對多面體進(jìn)行劃分的算法；B Jonathan等提出一種多材質(zhì)的四面體網(wǎng)格生 成算法；J Wang等提出了

3、一種能得到高質(zhì)量四面體網(wǎng)格的自適應(yīng)算法；S Tian 等提出了一種在模型輪廓的基礎(chǔ)上生成網(wǎng)格的算法；R Montenegro等提出自動 生成自適應(yīng)四面體網(wǎng)格的算法。如何自動劃分網(wǎng)格逐漸成為有限元法發(fā)展的瓶頸，許多科學(xué)家和工程師在全 自動有限元網(wǎng)格劃分算法的研巧和實現(xiàn)上努力。網(wǎng)格生成是實際問題求解的前 提，對于超薄、相鄰或包含關(guān)系的復(fù)雜模型，生成符合實際要求的有限元網(wǎng)格是 一個耗時很大的任務(wù)。此時，網(wǎng)格的自動生成算法節(jié)省時間的同時提供了髙精度, 保證了問題分析的準(zhǔn)確性。自動網(wǎng)格剖分算法發(fā)展至今，很多商業(yè)軟件如 Fluent> Ansys > Hyper mash等都提供了相應(yīng)的網(wǎng)格剖

4、分模塊，對于規(guī)則的兒 何形狀，生成的網(wǎng)格可很好的解決一般線性問題，但很難對復(fù)雜或非線性問題生 成符合工程實際要求的高質(zhì)量網(wǎng)格。雖然己有很多針對不同問題而且發(fā)展成熟的 網(wǎng)格剖分理論算法，山于工程實踐中模型的復(fù)雜性、差異性越來越大，使理論算法向工程 實際的轉(zhuǎn)化成為有限元法應(yīng)用的難點問題。隨著四面體剖分應(yīng)用領(lǐng)域的不斷擴(kuò)大、研究層次的不斷深入，四面體剖分遇 到了越來越大的挑戰(zhàn)，有時為了得到更好的剖分結(jié)果，需要兒種剖分方法的結(jié)合。 J Kucwaj等討論了結(jié)合前沿推進(jìn)法的三維Delaunay網(wǎng)格生成法的效率問題； Fumiaki Nobuyama等在Dynamic Bubble System基礎(chǔ)上使用通

5、用圖形處理器提 岀了一種并行自動網(wǎng)格生成算法；Yami耐隅等提出了一種對于復(fù)雜模型的三維 混合網(wǎng)格生成算法；Yan Li等和常麗娟等都分別提出前沿推進(jìn)法和Delaunay法 相互結(jié)合的網(wǎng)格劃分算法。四面體網(wǎng)格剖分還有很多開源的三維網(wǎng)格生成器，如Netgen、Tetgen和 Gambit等。這些開源代碼為研究者提供了強(qiáng)大理論和技術(shù)支持，由于可針對要 分析的具體問題在這些開源代碼上做任意改進(jìn)，所以應(yīng)用很廣泛，研究人員提出 了很多基于此的理論創(chuàng)新和實際應(yīng)用。如孫黎明等在Netgen的基礎(chǔ)上提出應(yīng)用 于層狀地質(zhì)體的四面體網(wǎng)格剖分算法；荊永濱等利用Tetgen實現(xiàn)了復(fù)雜FLAC 3D 模型可視化的建模。

6、其中Netgen是奧地利科學(xué)家Joachim Schoberl編寫的以詢 沿推進(jìn)法為基礎(chǔ)的網(wǎng)格剖分程序，是網(wǎng)格剖分程序中極為先進(jìn)和完善的開源代 碼，在三維網(wǎng)格剖分領(lǐng)域應(yīng)用很廣。2四面體網(wǎng)格生成算法概述四面體劃分算法有點集的、區(qū)域的和限定的網(wǎng)格剖分算法。點集的四面體劃 分是給定一個空間點的集合，要求生成網(wǎng)格單元的頂點都是給定點集中的點；區(qū) 域的四面體剖分是給定區(qū)域的內(nèi)外邊界，將其剖分成許多四面體的集合，單元的 頂點無限制，可根據(jù)需要在區(qū)域內(nèi)任意加點；限定的四面體剖分是網(wǎng)格剖分要滿 足指定的一些點、線、面的限定條件，如圖I所示生成限定四面體網(wǎng)格的截面 圖，A、B、C為約束點，約束線段MN、DE,

7、一個長方形的約束平面和一個球形的約束曲面。圖1限定的網(wǎng)格剖分（1）Delaunay 法Delaunay法生成的網(wǎng)格的主要特征：最小角最大化和空圓（球）特性。常 用的Delaunay法有逐點插入法、邊/面交換算法、分治算法等。在這些算法中， 逐點插入法是己經(jīng)很成熟的方法，Bowyer-Watson法是使用最多的一種逐點插入 法，大部分Delaunay算法都是基于Bowyer-Watson法和邊/面交換法的。Bowyer-Watson法是基于空圓（球）特性的逐點插入法，在三維空間的基本 流程如圖2所示，點P是插入的節(jié)點。國內(nèi)外學(xué)者對Bowyer-Watson法做了很多 研究,Borouchaki和

8、George Zagar is等分別提出了兩種三維快速Bowyer-Watson 算法。圖2 Bowyer-Watson算法流程邊/面交換算法比Bowyer-Watson算法實現(xiàn)簡單，通過有限步的邊/面交換操作總是可以使網(wǎng)格滿足Delaunay準(zhǔn)則。Guibasi等提出了一個二維空間的邊/面交換算法；Joe將邊/面交換算法推廣到了三維。(2) 前沿推進(jìn)法前沿推進(jìn)法生成的網(wǎng)格質(zhì)量高，且能保證邊界一致。前沿推進(jìn)法的思想是先 離散模型的邊界區(qū)域，二維空間是線段的集合，三維空間是三角面片的集合。這 些線段或三角面片作為前沿面集合進(jìn)行推進(jìn)，當(dāng)填滿整個區(qū)域時剖分結(jié)束。如圖 3所示的是二維前沿推進(jìn)法的基本過程。圖3前沿推進(jìn)法示意圖前沿推進(jìn)法的基本流程如下。(a) 確定前沿面集合。山實體模型的閉合曲面蘭角形組成(b) 當(dāng)前前沿。從前沿面集合中選取前沿作為當(dāng)前詢沿(c) 計算最優(yōu)點位置。根據(jù)單元尺寸控制方法訃算最優(yōu)點的插入位置(d) 選擇最佳節(jié)點。在候選隊列中依次檢查，從而可可以找到一個符合相 關(guān)有效性檢查的節(jié)點作為最佳節(jié)點，并與當(dāng)前前沿生成四面體網(wǎng)格(e) 更新前沿面集合。刪除當(dāng)前前沿，把新生成的前沿面放到詢沿面集合(3) 映射法映射法有網(wǎng)格生成速度快、單元密度可控制、單元質(zhì)量高等優(yōu)點，對多連通 域模型，將模