三維約束Delaunay四面體網(wǎng)格生成算法及實現(xiàn)

【摘 要】三維四面體網(wǎng)格生成算法在有限元分析領(lǐng)域具有重要的應(yīng)用價值，約束Delaunay四面體（CDT）算法是三維四面體網(wǎng)格化的有效方案。本文討論了CDT關(guān)鍵概念，設(shè)計出三維域CDT算法，并基于此算法編制了網(wǎng)格生成程序，給出了工程實例的網(wǎng)格生成，獲得了理想結(jié)果。

【關(guān)鍵詞】網(wǎng)格生成；四面體網(wǎng)格；約束Delaunay四面體；算法

一、引言

網(wǎng)格生成是工程科學與計算科學相交叉的一個重要研究領(lǐng)域，是有限元前置處理的關(guān)鍵技術(shù)。從總體上講，網(wǎng)格生成技術(shù)分為結(jié)構(gòu)化網(wǎng)格和非結(jié)構(gòu)化網(wǎng)格兩大類，其中，非結(jié)構(gòu)網(wǎng)格能適應(yīng)復(fù)雜外形且自動性高，逐漸成為數(shù)值求解偏微分方程的有效方法之一，它在有限元分析、科學計算可視化、生物醫(yī)學和機器人等學科領(lǐng)域具有重要的應(yīng)用價值。

當前，典型的非結(jié)構(gòu)四面體網(wǎng)格生成算法主要有八叉樹法（Octree）、前沿推進法（AFT）和Delauay法等。較其它方法而言，Delauay法具有成熟的理論基礎(chǔ)和判斷準則，更適用于三維實體的網(wǎng)格生成。Delaunay法最早由Delaunay于1934年提出，在此基礎(chǔ)上，Chew、Ruppert、Miller和等學者在算法改良方面開展了大量研究。目前，二維Delaunay法的研究已趨成熟，但三維Delaunay法在處理復(fù)雜實體的邊界一致性問題仍是學者研究的熱點。本文在前人研究的基礎(chǔ)上，采用約束Delaunay四面體（Constrained Delaunay Tetrahedralization ，CDT）法來處理指定區(qū)域的邊界一致性問題，編制了基于CDT的三維自適應(yīng)四面體網(wǎng)格生成程序，并對工程實例進行了分析。

二、CDT定義及算法

（一）CDT定義

在三維區(qū)域的四面體網(wǎng)格生成中，四面體的外接球內(nèi)部不包含任何網(wǎng)格頂點的四面體稱為符合Delaunay準則的四面體，如果一個點集的四面體生成中每個四面體都符合Delaunay準則，則此四面體生成是點集的Delaunay四面體生成。在一定條件限定之下以Delaunay準則為標準將空間分解成許多四面體稱為約束Delaunay四面體生成。通常情況下，將約束Delaunay三角（二維）/四面體（三維）生成的問題記為CDT。

（二）CDT存在性

由于三維空間存在不能劃分為四面體集合的多面體（如多面體），故給定一個用分段線性復(fù)合體（piecewise linear complexes，PLCs）描述的三維區(qū)域，的CDT可能不存在。對于CDT算法，一個關(guān)鍵的問題就是要保證計算域的CDT存在。在實際應(yīng)用中，假定為中的點的Delaunay四面體網(wǎng)格劃分，為中的一個四面體，為的一個相鄰的四面體（與共面），是和的點集。如果中所有的點都在同一個外接球內(nèi)，就稱為的局部退化[9]。如果D不包含局部退化，并且包含著中所有的線段，則的CDT存在。

（三）CDT算法

假定初始的PLC為，則約束四面體網(wǎng)格生成（CDT）由以下幾步構(gòu)建。

（1）采用基于空外接圓（球）準則的B-W增量插點算法，對點集中點進行初始的Delaunay四面體網(wǎng)格生成。

（2）通過在丟失的邊上插點恢復(fù)內(nèi)中的邊，更新。

（3）通過點的擾動或插入新點，去除內(nèi)的局部退化，更新，。

（4）通過空腔重新生成四面體的方法，恢復(fù)內(nèi)中的面，實現(xiàn)面的恢復(fù)。

步驟（1）主要是構(gòu)建，先尋找一個外接圓包含待插入點的基單元，再利用單元相鄰關(guān)系找到所有不符合外接圓準則的單元（空腔），然后刪除空腔內(nèi)所有單元，連接待插入點和空腔邊界三角形，在空腔內(nèi)形成新的三角化。經(jīng)過邊恢復(fù)（2）和局部退化（3）后，保證了的CDT存在。步驟4可以在不增加點的前提下實現(xiàn)面恢復(fù)。

（四）算法實現(xiàn)

算法代碼在Visual C++6.0下編寫，主體程序包括輸入輸出、控制和網(wǎng)格劃分三大部分，程序總體流程見圖1。在數(shù)據(jù)結(jié)構(gòu)上采用點—邊—面—四面體—四面體網(wǎng)格的存在結(jié)構(gòu)和鏈表的存儲方式來實現(xiàn)圖元數(shù)據(jù)的存儲，用指針實現(xiàn)圖元之間的聯(lián)系。同時，程序為CDT算法提供了必要的數(shù)據(jù)交換接口，將現(xiàn)有CAD軟件模型導(dǎo)入、有限元網(wǎng)格數(shù)據(jù)生成及有限元軟件分析功能綜合在一起，為工程應(yīng)用搭建了平臺。

三、應(yīng)用實例

圖2（a）為一個由3DMAX創(chuàng)建的機械部件模型，圖2（b）、（c）、（d）給出了不同控制參數(shù)（、）下，應(yīng)用本文算法生成的模型頂部網(wǎng)格生成截面放大圖實例，表格1給出了、分別為（2.0，—）、（1.2，—）、（2.0，3.0）、（2.0，2.0）、（1.2，2.0）時對應(yīng)的生成網(wǎng)格參數(shù)。其中，為外接球半徑與四面體最短邊長的比率，為四面體單元的最大體積限制，硬件平臺為P4 2.6GHz、512M內(nèi)存。

圖2及表1表明：（1）該算法可以生成三維約束Delaunay四面體網(wǎng)格，生成網(wǎng)格的質(zhì)量以及計算時間能夠滿足有限元計算的要求。（2）三維約束Delaunay四面體網(wǎng)格的質(zhì)量要求越高，所需的剖分時間相對更長，可根據(jù)實際網(wǎng)格質(zhì)量需求選擇合適的生成控制參數(shù)進行網(wǎng)格生成。

四、結(jié)束語

本文基于Delaunay理論及準則，采用約束Delaunay四面體法處理三維計算區(qū)域的邊界一致性問題，利用Visual C++6.0編制了基于CDT算法的三維約束四面體網(wǎng)格生成程序，并對工程實例進行了網(wǎng)格生成。結(jié)果表明，本文所研究的算法可以生成三維約束Delaunay四面體網(wǎng)格，生成的網(wǎng)格能夠滿足科學計算及工程分析的實際需要，約束Delaunay四面體算法是三維四面體網(wǎng)格化的有效方案。

參考文獻：

[1]H-Si. Meshing Piecewise Linear Complexesby Constrained Delaunay Tetrahedralizations[A]. In：14th International Meshing Roundtable[C].（ 2005），P.147-161.

[2]J.R. Shewchuk. General-Dimensional Constrained Delaunay and Constrained Regular Triangulations.To appear in Discrete&Computational Geometry（2005）.

[3]J. Ruppert. A Delaunay refinement algorithm for quality 2-dimensional mesh generation. Journal of Algorithms（J）.Vol.18（1995），P.548–585

[4]G.L. Miller， T. Phillips， D. Sheehy. Linear-size meshes[C]. In：20th Canadian Conference on Computational Geometry（2008）

[5] E. die Zerlegung von Dreieckspolyedern in Tetraeder.Mathematische Annalen. 1928（98）：309～312.

[6]Si. Hang. An Analysis of Shewchuk's Delaunay Refinement Algorithm， in： Proc. 18th International Meshing（2009）

基金支持：云南省自然科學研究基金（基于時域有限元的諧振腔問題研究，2011）

作者簡介：鐘汝能（1979—），男，云南臨滄人，講師，主要從事電磁場數(shù)值計算研究。