❶ 靈活約束的四面體化
研究幾何模型所固有的物理特性的基礎步驟是網格化。基於簡單形體（即二維的三角形和三維的四面體）的結構化網格對自然物體的建模非常有意義，因為它們對填充由簡單邊界（即二維情形中的邊和三維情形中的三角形）所定義的區域的物性非常靈活。
自從提出了三角剖分一個多邊形的O（n）最優演算法（Chazelle,1991）後，從計算幾何學觀點來看，二維情況現在已可以很好地處理了。二維情況的其他重要演算法有Chew（1987）的約束Delaunay三角剖分方法和Ruppert（1993）的限制縱橫比三角剖分方法，前者給出一種來考慮給定連接關系的點集的三角剖分方法，後者可提供一個具有「好」的元素的網格。
所以，給定一個可在其端點彼此相交的邊界集合定義的二維模型，便可能利用三角形來填充所定義的全部區域。圖2.13顯示一個二維三角剖分模型的例子。
圖2.13二維模型的三角形化（Joel Conraud,1995）
●輸入角點；——輸入邊界
如果所有給定的邊界都在剖分結果中出現，這樣一個模型的三角剖分被稱作約束三角剖分；而如果一些邊界被分割後出現在剖分結果中，則被稱為匹配三角剖分（即在這些邊界上增加稱為「Steiner點」的一些點，用來分割它們）。為了考慮特定的連接，Chew修改了對Delaunay三角剖分的「空球標准」的定義，在文獻（Nackman and Srinivason,1991）中提出了一種在輸入的邊界上增加一些點，用來實現一種保持Delaunay特點的匹配三角剖分方法。
三維情況。三維情況要難得多，所有在二維中的一系列命題不再有效：
●有n條邊的多邊形的三角剖分有（n-2）個三角形；但一個多面體的四面體剖分具有不同數目的剖分結果。
●所有的多邊形都能被三角剖分；但有些多面體，如果其邊界拓撲不改變就不能被四面體填充；換句話說，不能對它們進行約束三維三角剖分，而只能進行匹配三維三角剖分的計算。
●二維點集的Delaunay三角剖分對所有可能的三角剖分的最小角最大化；但三維點集的Delaunay三角剖分做不到。
文獻（Ruppert and Seidel,1992）對非凸多面體的四面體化所涉及的困難有一個更詳細的描述。因此，如果有人想對一個涉及節點、邊和三角形的幾何結構四面體化，一般情況下需要增加Steiner點，它們的數目可能是很大的，導致一個復雜得多的四面體化。本節給出一個類似於匹配三維三角剖分的方法，稱為靈活約束的四面體化方法，這將大大減少增加點的數目。
問題。首先給出一些定義，然後描述我們感興趣的問題。
定義1：我們定義一個基於簡單邊界的模型M為三維空間中三角剖分定義的曲面的集合。曲面之一是閉合的，並且確定了我們研究的區域，而其他曲面有的確定了子區域，有的確定了不連續體（即面具有不閉合的邊界）。它們可以沿著三角形邊界彼此相交。
定義2：T是M四面體化的點集，當且僅當M的每個頂點是T的四面體頂點。
定義3：T是M的一個約束四面體化，當且僅當每個三角形（邊和頂點）是T的四面體表面（邊和頂點）。正如上面所寫的，不總是有一個與模型相聯系的四面體化。
定義4：T是M的一個匹配四面體化，當且僅當M的每個三角形：
●可以是T的四面體的表面；
●或者與T中四面體的表面有一個相關部分，這種情況意味著已增加了Steiner點。
從一個四面體化點集開始，怎樣修改使它成為M的一個可接受的四面體網格呢？
初步觀察。這個工作從以下觀察開始：
我們想對圖2.14所示的錐體作四面體化，在這個棱錐的表面，有三角形ABD、ABC。如果我們使用Delaunay三維點集三角剖分演算法（例如文獻Watson,1981中的方法）產生一個初始解，則由於d（C,D）＜d（A,B）（在一個Delaunay三角剖分中，對於存在4個共面點的情況，生成的兩個三角形遵循對角線最短原則），在點A和B之間連接的情況不會出現在棱錐的表面拓撲中，因此也就不會出現在四面體剖分網格中。
圖2.14錐體的Delaunay四面體化（Joel Conraud,1995）
如果我們忽略在共面區域這兩種三角剖分的不同之處，則生成的兩個四面體的邊界定義了由六個輸入三角形描述的同一個多面體。所以，即使拓撲結構不同，幾何形態是相同的。在一個靈活約束的四面體化方法中，上面的四面體網可被視作輸入的可接受的近似。
有時，一個僅基於模型節點剖分而成的四面體網格中的三角形，與一個基於邊界剖分而成的三角形網格不匹配。在研究這種情況時，則可發現兩種另外的方案：
（1）雖然，邊界三角形與四面體網格邊界不相交，但幾何形狀不相似。如果圖2.15中的點D沿ACB面的垂線向遠離E的方向移動，這個錐體被變形為一個凹多面體。按以前的情形生成兩個四面體，但這時在輸入三角形和四面體形成的多面體表面之間出現一個間隙。在圖2.15中的截面上可看出問題。
圖2.15（a）改變D的位置（Joel Conraud,1995）
圖2.15（b）（E,D,C）被兩個四面體共用（Joel Conraud,1995）
（2）邊界三角形與一個四面體邊界相交。在圖2.16的例子中，三角形（C,B,E）與四面體的邊（A,D）相交。要麼在交點處插入一個點，要麼進行網格的局部更新：可用四面體（A,B,C,E）和（D,E,B,C）代替四面體（A,D,C,E）、（A,D,E,B）、（A,D,B,C），產生一個具有8個輸入三角形的網格作為四面體的表面，但該表面不再是Delaunay的了。
圖2.16（a）由8個三角形確定的多面體（Joel Conraud,1995）
圖2.16（b）（A,B,C,D,E,F）的Delaunay四面體化（Joel Conraud,1995）
靈活約束四面體化的目標是僅當上述的第二種情況出現時，去組合測試模型的四面體化的點集並局部修改它。對付第一種情況（不論移不移D點），則用前面的方法，通過局部網格修改或增加點來處理（George等，1991）。
下面，我們給出靈活約束四面體化的如下定義：
定義5：T是一個靈活約束四面體化，當且僅當M的每個三角形：
●可以是T的一個四面體表面；
●或者與T中四面體的表面有一個重合部分；
●或者屬於一組n個相連的三角形GTgr1，通過它我們可以聯系一組n個四面體表面GTetra，這組四面體與相互連接的三角形組有相同的表面。
也就是說，靈活約束的四面體化只要求約束面與四面體表面的一部分幾何上重合，拓撲可以不同。
下面描述從一個模型的四面體化點集來構建一個靈活約束四面體化的演算法。
演算法。從一個簡單邊界的模型M和一個用M中的點通過無約束四面體剖分形成的四面體集TPoint Set（M）開始，演算法分為四步：
（1）計算無約束四面體剖分TPoint Set（M）中與M中的三角形不匹配的三角形集合SUnMatched
for每個M中的t
if non-matched（t,M,TPoint Set）/＊用判斷函數判斷＊/
then SUnMatched←SUnMatched∪｛t}
endif
endfor
這里non-matched（）函數定義如下：
（t是基於三個頂點：v1,v2和v3的三角形）
TetraFaces←φ
If edge（v1,v2）不存在於TPoint Set中Retur false
else TetraFaces←TetraFaces U tetrafaces（edge（v1,v2））
If edge（v2,v3）不存在於TPoint Set中Return false
else TetraFaces←TetraFaces U tetrafaces（edge（v2,v3）
If edge（v3,v1）不存在於TPoint Set中Return false
else TetraFaces←TetraFaces U tetrafaces（edge（v3,v1））
Return#TetraFaces=1
（2）將SUnMatched分為相連的三角形子集
SConnex←φ
for SUnMatched中的每個三角形t
Connex←｛t和M中的鄰近t的三角形以及SUnMatched的成員｝
SUnMatched←SUnMatchedConnex/＊把找到的三角形從SUnMatched中去掉＊/
SConnex←SConnex∪｛Connex}/＊把找到的三角形合並到SConnex中去＊/
endfor
（3）將每個SConnex的子集分為由邊界既存在於M又存在於TPoint Set約束的三角形的子集
SBoundedConnex←φ
for SConnex中的三角形Connex的每一個集合
for Connex的每個三角形t
BoundedConnex←｛t和Connex中鄰近t的三角形以及既在M中又在TPoint Set沒有共享邊界的三角形｝
Connex←ConnexBoundedConnex/＊把找到的三角形從Connex中去掉＊/
SBoundedConnex←SBoundedConnex∪｛BoundedConnex｝
/＊把找到的三角形合並到SBoundedConnex中去＊/
endfor
endfor
（4）對於每個子集BoundedConnex，其數據項的個數與基於同一邊界的四面體表面集合的數據項個數進行對比
for SBoundedConnex的每一個三角形集合BoundedConnex do
① 計算集合edges（BoundedConnex,M）和edges（BoundedConnex,TPoint Set）
edges（BoundedConnex,M）←φ
edges（BoundedConnex,TPoint Set）←φ
BoundedConnexVertices←Vertices（BoundedConnex）
for BoundedConnexVertices的每一個頂點vdo
for基於v的TPoint Set的每一條邊e do
opposite=opposite（e,v）
if opposite是BoundedConnexVertices的成員
then edges（BoundedConnex,TPoint Set）←
edges（BoundedConnex,TPoint Set）Ue
ifM中在e和opposite之間存在邊
then edges（BoundedConnex,M）←
edges（BoundedConnex,M）Ue
endif
endif
endfor
endfor
② 計算共享edges（BoundedConnex,M）的四面體表面集合TetraFaces
TetraFaces←φ
for edges（BoundedConnex,M）的每一個邊e do
for基於e的TPoint Set的每一個四面體表面tfdo
for i from 1 to 3 do
neighber_edge←edge（tf,i）
if neighber_edge≠e
and member of edges（BoundedConnex,M）
then TetraFaces←TetraFaceUtf
endif
endfor
endfor
endfor
③ 計算在BoundedConnex的邊界上的邊集合BorderEdges
BorderEdges←φ
for BoundedConnex的每一個三角形t do
for i from 1 to 3 do
edge←edge（t,i）
trgl←neighber（t,i）
if trgl不是BoundedConnex的成員（或不存在）
then BorderEdges←BorderEdgesUedge
endif
endfor
endfor
④ BorderEdges定義一條閉合曲線，TetraFaces的某些元素在其外部，刪除它們
for TetraFaces的每一個四面體表面tf do
for i from 1 to 3 do
e←edge（tf,i）
if e不是BorderEdges的成員
then
for基於e的每一個四面體表面tf′ do
iftf′≠tf並且tf′為TetraFaces成員
then TetraFaces
←TetraFaces
{tf′以及TetraFaces中tf′的鄰接面
直到遇到BorderEdges的邊界）
endif
endfor
endif
endfor
endfor
⑤ 對比＃TetraFaces和＃BoundedConnex
if#TetraFaces=BoundedConnex
then OK
else局部網格修改（或增加Stiener點或同時進行）
endif
endfor
下一節我們將給出上述實現的結果。
實驗結果。上面所述演算法的一個C+＋版本已被結合到GOCAD軟體中，GOCAD軟體是一個自然物體的三維建模工具，特別適用於石油工業中地下情況的建模。
從模型點集的一個Delaunay三維三角剖分（在浮點運算中使用Watson的演算法。由Schroeder等，1990和George等，1992中所提到了同類型檢查方法使得數據結構的有效性在增加點後保持不變）開始，上一節的組合演算法使我們可以鑒別在TPoint Set和M之間的間隙。此時，還未應用上一節後面所講的局部網格修改。在後處理過程中，通過在區域內增加一些點來使最終的網格可用。
基本的例子。如果M被簡化為定義一個立方體的閉合三角剖分曲面，立方體的每個面分成兩個三角形，我們可得到以下結果（圖2.17）。
圖2.17正方體的四面體化（Joel Conraud,1995）
小窗口中顯示的四面體化的網格，元素在其中心周圍收縮，以便讓用戶看到結構內部。這個立方體的三個可見面的三角剖分，在約束面上和四面體邊界上是不同的。但兩個對象定義的幾何形體是一樣的。
實例。彩色圖版1.1是一個描繪具有超過8000個節點和17000個三角形的地質體的簡單三角剖分曲面。如果這個面的網格質量好的話，是不需要對四面體網格進行修改的。
彩圖版1.2中，M定義一個閉合的曲面（下面沒顯示），它和另外三個曲面定義四個地質層位。
彩色圖版2.1表示四面體網格的一個切片，我們可以看到三個曲面定義的界面的「傷疤」。
在具有256M的HP9000/800 K200上實現第二、第三個例子需要10min和12min的CPU時間，Delaunay三維三角剖分和M的三角形與四面體表面相比較花費的時間不及總時間的1/4。
討論。靈活約束的四面體化方法對地下情況建模的目的來說，提供了一個可接受的基於邊界模型的近似：在某些情況下，以用盡可能少的元素得到四面體化網格比考慮全部的三角形更重要。如果有人想在表面三角形和四面體TPoint Set的邊界表面之間得到1對1的關聯，則有必要從TPoint Set中提取約束和「靈活約束」的元素，從而得到一個新的基於邊界的模型M′，它與M幾何形狀相同，但拓撲不同。第二類型靈活約束改造的TPoint Set是一個M′約束的四面體化。
下一步工作將包括比較靈活約束四面體化方法與在TPoint Set中與M不匹配的每個三角形增加Steiner點的方法的計算效率比較。