李巖席， 賀可太， 朱冬梅

（北京科技大學(xué)機(jī)械工程學(xué)院， 北京100083）

0 引言

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

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

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

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

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

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

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

1 三角剖分算法

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

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

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

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

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

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

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

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

（5）區(qū)域性：新增、刪除、移動(dòng)某一個(gè)頂點(diǎn)時(shí)只會(huì)影響臨近的三角形。

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

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

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

Bowyer-Watson 插點(diǎn)算法具體過程為：

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

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

圖2 Delaunay 三角剖分

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

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

2 三角剖分算法改進(jìn)

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

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

（2）以新插點(diǎn)所在的三角形（或某個(gè)被破壞的三角形） 為起始凸腔H。

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

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

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

（6）插入下一個(gè)點(diǎn)，重復(fù)步驟（2）～（4），直到所有點(diǎn)全部被插完。

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

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

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

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

2.2 添加三角節(jié)點(diǎn)

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

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

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

圖3 插入點(diǎn)位于剖分三角形外部

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

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

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

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

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

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

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

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

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

3.3 邊界檢驗(yàn)

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

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

4 實(shí)驗(yàn)結(jié)果和討論

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

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

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

5 結(jié)論

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