三維網格模型的局部三角剖分算法

李巖席， 賀可太， 朱冬梅

（北京科技大學機械工程學院， 北京100083）

0 引言

利用計算機輔助進行三維模型設計，一直以來是計算機圖形領域的核心問題之一。三維網格模型是建立三維模型的一個重要表達方式。Delaunay 三角網格模型在創建地貌模型、逆向工程、表面重建等領域均有廣泛的應用。

由于在有限元分析領域中三角網格剖分被廣泛應用，所以眾多的研究者們對其進行了大量的研究。 20 世紀70 年代初，Lawson 對三角剖分進行研究從而繪制二維流場等值線[2]，Green 和Silbson 等從純數學的角度對這一問題進行研究[3]。 20 世紀80 年代初，Bowyer Watson 分別提出了Bowyer 算法和Watson 算法[4]。

三角網生長法：Green 等[3]首次實現三角網生長算法，隨后被眾多學者進行完善。 其算法思想是先任選點集內一點，然后遍歷點集尋找距離該點最近的點，并連接這兩點作為基邊， 接著再根據空外接圓法則尋找第三點形成一個三角形，再以三角形的一邊為基邊尋找下一個點，最后重復此過程直到點集中全部點搜索完畢形成完整的三角網。 三角網生長算法在遍歷點集尋找符合要求的離散點這一步中需要消耗大量的時間， 因此眾多學者對三角網生長算法的改進都圍繞這一點， 其中最常用的方案為縮小選點范圍。 有應用了閉角概念且采用正負區法搜索離散點， 以優先點為中心的Delaunay 三角網生長算法[9]；有提出在尋找第三點時在可選范圍內刪除封閉點并在外接圓檢測時只對距離基邊中點最近的n 個點進行檢測，封閉點就是在剖分過程中，一個點一旦成為封閉點，則它將不會再對后續的擴展三角形產生影響， 那么將其刪除可以有效地提高構建Delaunay 三角網效率。 縮小選點范圍還有一個重要手段——對點集進行分區， 有提出弧帶搜索排除法將點集劃分為若干個弧帶， 接著在弧帶內進行搜索第三點，縮小了第三點的搜索范圍，整體上提高了算法的效率[10]。

分治算法是由Shamos 等[11]首先提出并將其應用到Delaunay 三角網的構網中。隨后Lee 等[12]對其進行了改進和完善，提出了分割-歸并算法。分割-歸并算法的基本思想是將點集分為若干個部分并分別構網， 然后對所構建的網格進行合并。此算法的改進方案分為兩種：直接改進合并算法，將分割-歸并算法與其他兩種方案相結合。 第一種方案可以有效改進算法效率， 改進了算法中最后一步合并算法，通過對點集子集內點的排序，提前確定支撐點范圍，減小了搜索范圍，有效地提高了算法效率。 雖然分治算法含有大量的遞歸運算，消耗內存較大，但是其效率高，如文獻[13]將分割-歸并算法和逐點插入算法相結合，先將點集劃分成若干個點集子集，然后利用逐點插入算法生成點集子集Delaunay 三角網， 最后將其合并生成完整Delaunay 三角網，先對點集中的點進行排序，然后分塊儲存到列表中，接著利用逐點插入法生成子塊三角網，最后將鏈表中的各子網合并， 最終生成完整Delaunay 三角網；呂英英等[14]采取了二叉樹結構儲存子塊三角網，最后將二叉樹中父節點相同的子網合并， 最終生成完整Delaunay 三角網。

逐點插入算法，該算法于1977 年由Lawson[15]提出。逐點插入算法的主要思想為首先創建一個大三角形，然后將點集中的任意一點插入大三角形中形成三角網格，再依次將點集中待插入點插入已生成的三角網格中形成新的三角網格， 并對新生成的三角形進行外接圓檢測并調整， 待點集中所有點全部插入三角網格后刪除和大三角形有相同頂點的三角形，形成最終Delaunay 的三角網。此算法原理簡單，但是其時間復雜度較高。因為插入每個待插入點時都需要遍歷已構建的三角網， 故許多研究學者對其進行改進， 主要改進方案有兩點： 改進點定位算法，對點集分區縮小查找范圍。其中第一種方案主要對點定位算法本身進行改進，增加了搜索效率，如對點定位算法直接進行改進[16]，省去了求相交邊和三角形重心的步驟，有效地提高點定位效率；文獻[17]提出最速方向定位法提高待插入點的插入速度。 第二種方案則是采取了劃分點集的手段縮小尋找范圍，節省時間，算法效率得到了有效地提升。 例如文獻[18]先對待插入點進行排序，將已構網的三角形分區域標記， 從而減少尋找待插入點位置的時間。

約束Delaunay 三角剖分主要需要解決的問題是如何確保在剖分結果中存在應有的約束邊和約束面， 通常采取兩種方案解決此問題： 第一種方案為先增加剖分點以確保在剖分結果中有應有的約束面和約束邊； 第二種方案為先進行Delaunay 三角剖分， 然后將約束面和約束邊嵌入Delaunay 三角網中， 這樣的后果是約束面或約束邊周圍的三角形可能不是Delaunay 三角形。

為了保持生成的網格依然保持原三維網格模型幾何特征。另外為了盡可能減少新增的節點和三角單元，本文基于Bowyer-Watson 插點算法， 提出一種三維網格模型的局部三角剖分算法。

1 三角剖分算法

在工程應用中， 通常需要從三維空間中的幾何曲面生成三維網格。如圖1 所示，常見的幾何曲面，如平面，柱面，球面，B 樣條曲面都是通過二維參數平面映射到三維空間。 所以三維網格模型是在二維參數平面中生成三角網格，再通過參數表達映射到三維空間中。

圖1 二維參數平面和三維空間

在二維參數平面上，三角剖分是對給定的平面點集，生成三角形集合的過程。這個過程也稱作三角化。對于一給定點集，往往會存在多個三角剖分情況。為避免出現狹長三角形，使三角形形狀盡可能接近等邊三角形。當所有三角形的外接圓均滿足空圓性質的三角剖分， 稱為Delaunay 三角剖分。 這時的三角形質量較優，而且有利于數值計算的使用。 三角剖分后生成的Delaunay 三角網是唯一的，并且通過最大化最小角確保接近于規則的三角網。

Delaunay 三角網具有六種優異特性：

（1）最接近性：三角形的三個頂點是點集內最近鄰的三個點，且三角形的所有邊皆不相交。

（2）唯一性：不論從區域何處開始構建，最終都將得到一致的結果。

（3）最優性：任意兩個相鄰三角形形成的凸四邊形的對角線如果可以互換的話， 那么兩個三角形六個內角中最小的角度不會變大。

（4）最規則：如果將三角網中的每個三角形的最小角進行升序排列，則Delaunay 三角網的排列得到的數值最大。

（5）區域性：新增、刪除、移動某一個頂點時只會影響臨近的三角形。

（6）具有凸多邊形的外殼：三角網最外層的邊界形成一個凸多邊形的外殼。

Delaunay 三角剖分對三角形的形狀進行了定義，具體生成Delaunay 三角網的方法有三角網生成算法、分割-歸并算法和逐點插入算法。 其中三角網生長算法理論平均復雜度為O（n3/2），最壞情況為O（n2）；分割-歸并算法理論平均復雜度為O（nlogn），最壞情況為O（nlogn）；逐點插入算法理論平均復雜度為O（n3/2），最壞情況為O（n2）。 三角網生成算法是靜態算法，只存儲新生成的三角形，存儲需求較低，但其第三個點需要遍歷點集，時間消耗較高。分割-歸并算法利用了分而治之的思想，將較大的點集劃分為小區域的點集，時間消耗少，但伴隨著大量的遞歸計算，存儲需求較高。 逐點插入算法是動態生成的算法，時間復雜度和空間復雜度均不高。 從時間效率和空間使用綜合考慮， 所以當前基于逐點插入算法的Delaunay 三角剖分應用較為廣泛。 其中Bowyer-Watson 插點算法縮短了搜索壞邊的過程，在實際使用中具有更高的計算效率。

本文基于Bowyer-Watson 插點算法， 它是一種逐點插入的方法。首先生成輸入點集的初始三角網格，添加節點重新生成新的網格，遍歷直到所有的點添加完畢。

Bowyer-Watson 插點算法具體過程為：

Step1：建立初始三角網格：針對給定的點集V，計算得到一個包含該點集的矩形包圍盒R。 連接R 的任意一條對角線，形成兩個超三角形，作為初始Delaunay 三角剖分T0。

Step2： 將點集V 中的頂點逐一插入現有的三角剖分，現在在它里面再插入一個點P，需要找到該點P 所在的三角形。從P 所在的三角形開始，搜索該三角形的鄰近三角形，并進行空外接圓檢測。找到外接圓包含點P 的所有的三角形并刪除這些三角形，如圖2 所示形成一個包含P 的多邊形空腔， 叫做Delaunay 空腔。 然后連接P 與Delaunay 腔的每一個頂點，形成新的Delaunay 三角網格。

圖2 Delaunay 三角剖分

Step3：刪除矩形包圍盒R：重復步驟2），當點集V 中所有點都已經插入到三角形網格中后， 將頂點包含輔助窗R 的三角形全部刪除。

在每次添加節點時都需要找到該點所在的三角形，確定其所在三角形并刪除邊構建Delaunay 腔。

2 三角剖分算法改進

在建立Delaunay 三角網格過程中，在原平面區域內插入了新的點，并且打斷原有的連接邊，建立了新的連接邊。

（1）建立包含帶剖分區域的大凸殼。

（2）以新插點所在的三角形（或某個被破壞的三角形） 為起始凸腔H。

（3）依次檢驗凸腔H 的邊是否被打斷。若被打斷，去掉該邊，把新找到的三角形的另兩條邊放到凸腔中；若未被打斷，則檢驗下一個邊。

（4）重復步驟（3），直到凸腔H 的所有邊均不被打斷為止。

（5）連接新點與H 的頂點，形成插點后的網格系統，更新數據結構。

（6）插入下一個點，重復步驟（2）～（4），直到所有點全部被插完。

2.1 數據結構

兩種數據結構通常用于實現三角測量算法： 基于邊的數據結構，其中最著名的是雙連接邊表，以及基于三角形的數據結構。 這兩種數據結構的共同點是記錄表示邊或三角形，記錄存儲指向相鄰邊或三角形的指針。許多三角測量算法的實現直接讀取和更改這些指針。 本方法如表1 所示，通過添加或刪除由頂點指定的三角形，以自然的方式訪問三角測量。 三角測量存儲庫完全負責確定三角形鄰接關系，并正確維護其內部使用的任何指針。

表1 三角形數據的接口

AddTriangle 和DeleteTriangle 這兩個過程通過指定三角形的頂點來創建和刪除三角形， 以便存儲在數據結構中的所有三角形都具有正方向。 這種數據結構強制執行一個不變量，即一條邊只能有兩個三角形相鄰，而且邊的每一邊只能有一個三角形。因此，如果數據結構包含一個正向三角形uvw，并且應用程序調用AddTriangle（u，v，w），則三角形uvw 被拒絕，數據結構不會改變。 至少支持兩種查詢操作。 如果三角剖分包含一個正向三角形uvw，則過程Adjacented （u，v）返回頂點w，否則返回空集。 鄰邊（u，v）和鄰邊（v，u）返回不同的三角形，在邊uv 的對邊。 AdjacentOne（u）識別一個頂點為u 的任意三角形，如果不存在這樣的三角形，則返回空集。

2.2 添加三角節點

將輸入頂點包圍在一個巨大的三角形邊界框中，所有的頂點都被插入后，每個有邊界框頂點的三角形都會被刪除。這種方法的困難之處在于，如果邊界框頂點靠得太近，它們可能會在三角剖分中留下凹痕，而且不容易確定它們需要離多遠。 計算加權Delaunay 三角化，將三個邊界盒頂點的權重賦為負無窮。 這三個無限權值必須是不可比較的，這樣包含兩個邊界盒頂點的測試才能一致地運行。

在點定位過程中。大多數Delaunay 網格生成算法都是在形狀不好或超大的三角形的圓內生成新的頂點，在這種情況下，點的位置是自由的。 然而，對于作為網格生成器輸入的域頂點來說，點的位置不是自由的。在三角剖分中定位這些點有時是增量插入算法中最耗時和最復雜的部分。本算法，將搜索和連接被打斷邊所在的點過程限定在局部范圍進行。在形成Delaunay 空腔過程中，建立三角形內包含頂點列表，可以更快定位插入點所在三角形。在插入點周圍鄰域內進行局部的搜索， 這可以提高三角剖分的效率。

Bowyer-Watson 算法只有在新插入的頂點位于三角剖分內時才有效。當頂點位于三角形外部時，在三角形外插入一個頂點。開圓是虛頂點。圓形箭頭表示實際上是同一條邊的兩條虛邊。三個虛三角形和三個實三角形（陰影）被刪除， 并被兩個新的虛三角形和六個新的實三角形所取代。如圖3 所示。每個虛三角形的第三個頂點是虛頂點，一個由每個虛三角形共享的“無窮”頂點。 每個虛三角形都有兩條虛邊與虛頂點相鄰。不是虛的三角形稱為實三角形。

圖3 插入點位于剖分三角形外部

本文方法的采樣節點都盡可能的遵循原網格的特征，在優化過程中不改變原網格節點的位置，只改變這些節點間連接的拓撲關系。 這樣在很大程度上保持原網格的特征。在插入新的三角節點后，破壞的三角單元數目越多，三角剖分計算的性能表現越差。

3 三維網格網格模型的三角剖分

3.1 網格疏密控制

網格疏密控制方法有偏微分方程法、 基網格法和邊界驅動法等。 偏微分方程在微分方程中加入了網格疏密控制方法源項的辦法來控制網格疏密， 區域內的網格疏密過渡光滑，但此方法計算的工作量較大。網格疏密控制方法邊界驅動法則不能夠實現區域內部的網格加密和放大，只能實現邊界網格尺度向內部平穩過渡。 球填充算法可以生成高質量的網格節點構型。 球填充算法的核心思想是采用小球表示網格節點， 小球的球心表示節點的位置，小球球心的距離對應網格單元的尺寸。通過緊密地填充小球可以生成高質量的網格節點構型。 采用合適的算法連接這些節點可以生成高質量的網格。

在網格疏密控制貫穿剖分過程， 本文基于郭宇飛等的算法[22]，先對網格的特征邊界進行識別并采用球填充法在特征邊界上采集合適的采樣點作為新生成網格節點，然后在模型上其他部分采集合適的采樣點添加到新生成網格節點集，最后連接這些節點重生成高質量的網格。

3.2 網格細化生成

在兩個邊界交叉處出現三角單元三個頂點全在邊界的情況， 還有如圖4 的狹長針狀三角形和帽子三角形。Chew 和Ruppert 優化Delaunay 算法的核心是在質量差的圓周中心插入頂點， 基于Bowyer-Wastons 算法對三角剖分部分增量更新，并保持Delaunay 性質。經過如圖5 細化后， 保證三角形一般為圓周與最短邊之比大于適當邊界B。 Delaunay 插入頂點v 所創建的唯一新邊是連接到v的邊。 因為v 是某個Delaunay 三角形t 的圓心，而在插入v 之前，t 的圓周內沒有頂點，所以沒有一條新邊可以短于t 的圓周半徑。因為t 的圓周與最短邊之比大于B，所以每條新邊的長度至少是t 最短邊的B 倍。

圖4 針狀三角形和帽狀三角形

圖5 三角網格的細化

3.3 邊界檢驗

在網格剖分過程中的， 浮點運算產生的計算誤差會影響插入點和三角形位置關系的判斷， 從而產生錯誤結果，在計算三角形外界圓半徑、圓心坐標和距離時，采用雙精度和區域誤差來進行邏輯判斷。

對于多連通區域， 計算內邊界的外法線方向來確定無效的三角形。 為了保證新網格對原網格幾何形狀的保真度，采用了兩個誤差度量來評估兩個網格之間的距離。邊折疊和邊分割用于改變網格頂點的數量。 邊翻轉和頂點重定位提高了網格三角形的質量。 基于區域的網格重劃分過程是我們的網格重劃分方案的核心， 它產生一個具有高質量三角形和所需頂點采樣的網格。 另外兩個階段進一步提高網格質量。 正則化階段提高了網格連通性的規律性，只留下少量不規則的頂點。 然后，基于角度的平滑在不改變其連通性的情況下對網格進行拋光以獲得最佳網格幾何形狀。

4 實驗結果和討論

我們在C++平臺上實現了本三角剖分方法， 所有的實驗都是在一臺PC 計算機上進行， 它有如下配置：Intel（R） Core （TM） i7-12700H，2.70GHz，16G RAM，NVIDIA GeForce RTX3070 Ti GPU。

如圖6 所示，Bowyer-Watson 插點算法在一些多連通區域生成的網格對于如圖6（a）內凹的C 形區域，圖6（b）中會出現剖分后的三維網格系統不符合原幾何形狀。 在剖分過程中，需要對網格的邊界作進一步的限制。以八個頂點為節點進行Delaunay 三角剖分， 本方法能夠進行劃分，得到準確的結果。

圖6 C 形區域的三角剖分

5 結論

本文提出了一種面向三維網格模型的三角剖分算法， 本文的三角剖分方法基于Bowyer-Watson 插點算法實現。 通過在新插入點的鄰域內搜索三角形來提高三角剖分的效率， 通過對網格的幾何形狀和連通性進行局部修改來提高網格質量。 通過尺寸場來約束控制三角剖分區域， 使得生成的網格質量和算法性能有較好的綜合表現。通過實驗也能夠證明，在多連通的條件下也能夠得到正確的結果。