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

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

一、引言

網(wǎng)格生成是工程科學(xué)與計(jì)算科學(xué)相交叉的一個(gè)重要研究領(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ù)雜外形且自動(dòng)性高，逐漸成為數(shù)值求解偏微分方程的有效方法之一，它在有限元分析、科學(xué)計(jì)算可視化、生物醫(yī)學(xué)和機(jī)器人等學(xué)科領(lǐng)域具有重要的應(yīng)用價(jià)值。

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

二、CDT定義及算法

（一）CDT定義

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

（二）CDT存在性

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

（三）CDT算法

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

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

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

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

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

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

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

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

三、應(yīng)用實(shí)例

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

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

四、結(jié)束語

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

參考文獻(xiàn)：

[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）

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

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