張娟

摘 要：文章研究了約束Delaunay四面體網(wǎng)格生成算法，引入了優(yōu)化的網(wǎng)格算法，提高了四面體剖分單元的質(zhì)量；重點(diǎn)研究了指定區(qū)域的邊界邊與邊界面的一致性這兩個(gè)Delaunay三角化算法迫切需要解決的關(guān)鍵性問題。結(jié)果表明，文章提出的約束Delaunay三角化算法適用性、效率及網(wǎng)格單元質(zhì)量等方面都得到了提高，且該算法易于實(shí)現(xiàn)。

關(guān)鍵詞：約束Delaunay三角化；網(wǎng)格算法；四面體剖分

有限元方法是一種解決復(fù)雜工程實(shí)際問題的有效手段，基于三維實(shí)體四面體剖分相對于二維領(lǐng)域的復(fù)雜性，Delaunay算法的研究成果還不夠完善。目前Delaunay三角化方法仍具有算法速度慢、穩(wěn)定性不良、適用范圍有限、網(wǎng)格質(zhì)量較差等和其他三維區(qū)域四面體剖分算法一樣普遍存在的問題。

Delaunay準(zhǔn)則是保證優(yōu)化的網(wǎng)格結(jié)構(gòu)的前提，由于目前現(xiàn)有的算法都無法較好地保證Delaunay準(zhǔn)則，因此導(dǎo)致網(wǎng)格質(zhì)量無法保證，造成狹長三角形單元的出現(xiàn)，致使誤差超出范圍，造成算法不穩(wěn)定性。而需要解決的最關(guān)鍵的三維Delaunay三角化方法的問題就是指定區(qū)域的邊界邊、邊界面的一致性問題。為了保證指定區(qū)域邊界的一致性，保證邊界邊、邊界面在Delaunay三角化中的存在性，必須要進(jìn)行邊界的恢復(fù)。

1 Delaunay四面體剖分的基本理論—邊界一致

設(shè)Σ是一個(gè)三圍區(qū)域W邊界的離散化-曲面網(wǎng)格。邊界一致的問題是要求生成一個(gè)符合Σ的四面體網(wǎng)格T，即Σ是一個(gè)由Γ元素組成的組合體。T中可以有額外的點(diǎn)（Steiner點(diǎn)），但是這種點(diǎn)的數(shù)目應(yīng)該被限制得越少越好，這個(gè)問題對很多應(yīng)用軟件來說是最基本的。

在三維中，解決這個(gè)問題面臨很多困難，有一些簡單的多面體如果沒有Steiner點(diǎn)（40個(gè)），就不能被四面體剖分。判定一個(gè)非凸多面體不存在Steiner點(diǎn)能否進(jìn)行四面體剖分，是NP（NP-complete）問題，Chazelle認(rèn)為對一個(gè)簡單的多面體進(jìn)行四面體剖分可能需要很多Steiner點(diǎn)。

目前已經(jīng)提出了很多的邊界一致的算法，這些方法都有一個(gè)共同特點(diǎn)。首先，建立對多面體P的頂點(diǎn)集的初始Delaunay四面體剖分；然后，多面體P的邊界會被覆蓋，通過修改這個(gè)四面體剖分實(shí)現(xiàn)邊/面恢復(fù)，當(dāng)需要的時(shí)候可以加入Steiner點(diǎn)，對于解決很多工程問題這個(gè)方法是有效的，但是它們不是對任意的輸入都可行，對于一些反常的案例Steiner點(diǎn)的數(shù)目可能會很大。

約束Delaunay四面體剖分的特性的一個(gè)理論上的方法是通過往多面體P的邊界里加入Steiner點(diǎn)，以豐富多面體P的頂點(diǎn)集V，直到豐富后的頂點(diǎn)集的邊界被恢復(fù)。

對多面體P的約束Delaunay四面體剖分被定義為將P剖分成T，使得T是單純復(fù)型且每個(gè)單一的T都滿足約束Delaunay規(guī)則。按照這個(gè)定義，對P的約束Delaunay四面體剖分可能包含Steiner點(diǎn)，這些點(diǎn)包含在S＼V（P）中。

對曲面網(wǎng)格Σ進(jìn)行“約束四面體剖分”被定義為對所有的單純復(fù)形Σ的四面體剖分后的T也是單純復(fù)形，這就意味著非Steiner點(diǎn)被加入到Σ，但也可能加入到區(qū)域Ω的內(nèi)部。約束Delaunay四面體剖分的定義中，在Σ和Ω中允許存在Steiner點(diǎn)。在這個(gè)意義上，它也可以被稱作是“半約束”四面體剖分。

一般來說，對P（Steiner點(diǎn)的不同選擇）有多種約束Delaunay四面體剖分，我們完全有能力找到一個(gè)對P的約束Delaunay四面體剖分，使得它包含的Steiner點(diǎn)最少。

2 無約束Delaunay四面體剖分

Delaunay三角剖分是網(wǎng)格生成技術(shù)的研究重點(diǎn)，但是約束四面體剖分需要滿足兩個(gè)必要條件：（1）符合Delaunay準(zhǔn)則；（2）滿足點(diǎn)、線、面在網(wǎng)格中的存在性。這兩個(gè)條件使Delaunay三角剖分變得很復(fù)雜，本文主要從算法研究解決這個(gè)問題。

本文是基于逐點(diǎn)插入法的三維Delaunay三角化方法，對三維空間進(jìn)行四面體剖分。定義：（輸入模型）輸入模型Ω由3元組{V，S，F(xiàn)}構(gòu)成，其中：

V（vertices） ={ vi }代表點(diǎn)的集合；

S（segment） ={ sj }代表約束線段的集合；

F（Facet） ={ fk }代表約束面的集合；

從輸入模型Ω開始，對輸入三維模型進(jìn)行三角化需要以下幾個(gè)步驟：

Stepl：生成一個(gè)包含輸入模型Ω的初始四面體凸殼；

Step2：對輸入的點(diǎn)集V進(jìn)行初始Delaunay四面體剖分；

Step3：檢測發(fā)生丟失約束線段并對其進(jìn)行恢復(fù)；

Step4：檢測發(fā)生丟失約束面并對其進(jìn)行恢復(fù)；

Step5：網(wǎng)格細(xì)化及優(yōu)化。

3 算法實(shí)現(xiàn)及開發(fā)平臺

3.1 開發(fā)平臺

本文涉及的數(shù)據(jù)結(jié)構(gòu)和算法采用C#編程語言在Visual Studio.NET開發(fā)平臺進(jìn)行程序開發(fā)，實(shí)現(xiàn)約束Delaunay四面體剖分，并利用微軟提供的Direct X 9.0控件顯示三維網(wǎng)格剖分結(jié)果。微軟 Direct X 控件是用于三維可視化的控件，與C#能夠很好地集成，便于實(shí)現(xiàn)三維網(wǎng)格剖分與可視化。

3.2 實(shí)驗(yàn)數(shù)據(jù)說明

算法實(shí)現(xiàn)采用了微軟.X 數(shù)據(jù)格式，這種數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)簡單，便于在程序中處理。.X數(shù)據(jù)的頭文件中說明了離散點(diǎn)、約束邊、約束面的個(gè)數(shù)及其相關(guān)信息，同時(shí)文件中包含了離散點(diǎn)的坐標(biāo)，約束邊與約束面的頂點(diǎn)索引等信息。

3.3 實(shí)驗(yàn)結(jié)果分析

該算法已經(jīng)通過C#編程實(shí)現(xiàn)，并在CPU主頻為1.81 GHz的AMD Athlon（tm） 64 Processor 3000+處理器及512 MB內(nèi)存的PC機(jī)，基于Windows XP操作系統(tǒng)進(jìn)行測試，算法可處理空間散亂點(diǎn)，實(shí)現(xiàn)對空間離散點(diǎn)的Delaunay四面體剖分。有8個(gè)頂點(diǎn)的六面體以及一個(gè)約束面，經(jīng)過Delaunay四面體剖分后的網(wǎng)格圖，其中初始剖分生成的四面體個(gè)數(shù)為6個(gè)，插入約束面后的四面體個(gè)數(shù)為11個(gè)，共插入Steiner點(diǎn)2個(gè)（見圖1）。