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

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

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

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

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

5、用圖形處理器提 岀了一種并行自動(dòng)網(wǎng)格生成算法；Yami耐隅等提出了一種對(duì)于復(fù)雜模型的三維 混合網(wǎng)格生成算法；Yan Li等和常麗娟等都分別提出前沿推進(jìn)法和Delaunay法 相互結(jié)合的網(wǎng)格劃分算法。四面體網(wǎng)格剖分還有很多開源的三維網(wǎng)格生成器，如Netgen、Tetgen和 Gambit等。這些開源代碼為研究者提供了強(qiáng)大理論和技術(shù)支持，由于可針對(duì)要 分析的具體問題在這些開源代碼上做任意改進(jìn)，所以應(yīng)用很廣泛，研究人員提出 了很多基于此的理論創(chuàng)新和實(shí)際應(yīng)用。如孫黎明等在Netgen的基礎(chǔ)上提出應(yīng)用 于層狀地質(zhì)體的四面體網(wǎng)格剖分算法；荊永濱等利用Tetgen實(shí)現(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)格生成算法概述四面體劃分算法有點(diǎn)集的、區(qū)域的和限定的網(wǎng)格剖分算法。點(diǎn)集的四面體劃 分是給定一個(gè)空間點(diǎn)的集合，要求生成網(wǎng)格單元的頂點(diǎn)都是給定點(diǎn)集中的點(diǎn)；區(qū) 域的四面體剖分是給定區(qū)域的內(nèi)外邊界，將其剖分成許多四面體的集合，單元的 頂點(diǎn)無限制，可根據(jù)需要在區(qū)域內(nèi)任意加點(diǎn)；限定的四面體剖分是網(wǎng)格剖分要滿 足指定的一些點(diǎn)、線、面的限定條件，如圖I所示生成限定四面體網(wǎng)格的截面 圖，A、B、C為約束點(diǎn)，約束線段MN、DE,

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

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