約束Delaunay四面體剖分

張娟

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

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

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

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

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

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

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

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

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

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

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

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

2 無約束Delaunay四面體剖分

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

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

V（vertices） ={ vi }代表點的集合；

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

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

從輸入模型Ω開始，對輸入三維模型進行三角化需要以下幾個步驟：

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

Step2：對輸入的點集V進行初始Delaunay四面體剖分；

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

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

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

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

3.1 開發(fā)平臺

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

3.2 實驗數(shù)據(jù)說明

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

3.3 實驗結果分析

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