三維網(wǎng)格模型的局部三角剖分算法

李巖席， 賀可太， 朱冬梅

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

0 引言

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

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

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

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

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

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

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

1 三角剖分算法

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

圖1 二維參數(shù)平面和三維空間

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

Delaunay 三角網(wǎng)具有六種優(yōu)異特性：

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

（2）唯一性：不論從區(qū)域何處開始構(gòu)建，最終都將得到一致的結(jié)果。

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

（4）最規(guī)則：如果將三角網(wǎng)中的每個三角形的最小角進行升序排列，則Delaunay 三角網(wǎng)的排列得到的數(shù)值最大。

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

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

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

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

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

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

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

圖2 Delaunay 三角剖分

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

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

2 三角剖分算法改進

在建立Delaunay 三角網(wǎng)格過程中，在原平面區(qū)域內(nèi)插入了新的點，并且打斷原有的連接邊，建立了新的連接邊。

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

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

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

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

（5）連接新點與H 的頂點，形成插點后的網(wǎng)格系統(tǒng)，更新數(shù)據(jù)結(jié)構(gòu)。

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

2.1 數(shù)據(jù)結(jié)構(gòu)

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

表1 三角形數(shù)據(jù)的接口

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

2.2 添加三角節(jié)點

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

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

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

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

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

3 三維網(wǎng)格網(wǎng)格模型的三角剖分

3.1 網(wǎng)格疏密控制

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

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

3.2 網(wǎng)格細化生成

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

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

圖5 三角網(wǎng)格的細化

3.3 邊界檢驗

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

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

4 實驗結(jié)果和討論

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

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

圖6 C 形區(qū)域的三角剖分

5 結(jié)論

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