約束Delaunay四面體剖分

張娟

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

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

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

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

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

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

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

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

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

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

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

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

2 無約束Delaunay四面體剖分

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

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

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

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

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

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

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

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

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

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

Step5：網格細化及優化。

3 算法實現及開發平臺

3.1 開發平臺

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

3.2 實驗數據說明

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

3.3 實驗結果分析

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