基于頂點(diǎn)光滑度判定的牙齦三角網(wǎng)格自適應(yīng)細(xì)分改進(jìn)

馬天 李嬌嬌 李赟

摘 要：在牙齦三角網(wǎng)格中普遍存在狹長三角網(wǎng)格區(qū)域，針對基于面積判定的自適應(yīng)細(xì)分算法處理該類區(qū)域的質(zhì)量較低的問題，提出一種基于頂點(diǎn)光滑度判定的牙齦三角網(wǎng)格自適應(yīng)細(xì)分改進(jìn)算法。首先，通過求解頂點(diǎn)1-領(lǐng)域內(nèi)相鄰三角面片法向量夾角平均值作為頂點(diǎn)光滑度，采用該值作為細(xì)分判定準(zhǔn)則，在細(xì)分前從整體上一次性對頂點(diǎn)1-鄰域區(qū)域光滑度進(jìn)行計(jì)算;然后，通過比較頂點(diǎn)的頂點(diǎn)光滑度與光滑閾值的大小，確定細(xì)分區(qū)域并進(jìn)行Loop細(xì)分，設(shè)計(jì)了平均光滑度指標(biāo)來評價細(xì)分效果，這種評價方法綜合考慮了細(xì)分后網(wǎng)格頂點(diǎn)個數(shù)對判斷細(xì)分效果的影響;最后，在VTK環(huán)境下實(shí)現(xiàn)改進(jìn)算法及相關(guān)算法，在真實(shí)掃描的牙頜三維模型數(shù)據(jù)上進(jìn)行牙齦軟組織形變仿真三角網(wǎng)格細(xì)分對比實(shí)驗(yàn)。結(jié)果表明：改進(jìn)算法的細(xì)分效率更高，細(xì)分時間占比平均約節(jié)約了4.12%;平均光滑度對細(xì)分效果的評價更合理，細(xì)分的三角網(wǎng)格更規(guī)則、分布更均勻，曲面光順質(zhì)量更好，較好地滿足了軟組織形變仿真中真實(shí)性與高效性的要求。

關(guān)鍵詞：三角網(wǎng)格;二面角;自適應(yīng)細(xì)分;牙齦變形

中圖分類號：TP 391.41

文獻(xiàn)標(biāo)志碼：A

文章編號：1672-9315（2021）03-0549-10

DOI：10.13800/j.cnki.xakjdxxb.2021.0321

Abstract：In order to solve the problem that the adaptive subdivision algorithm based on area determination is poor in quality，an improved algorithm for adaptive subdivision of gingival triangular mesh based on vertex smoothness judgment is proposed.Firstly，the average angle between the normal vectors of adjacent triangular patches in the vertex 1-domain is calculated as the vertex smoothness，and the value is used as the subdivision criterion.Before subdivision，the smoothness of vertex 1-neighborhood region is calculated once.Then，the subdivision area is determined and loop subdivision is carried out by comparing the vertex smoothness and smoothness threshold.The average smoothness index is designed to evaluate the subdivision effects.This evaluation method comprehensively involves the influence of the number of mesh vertices after subdivision on the subdivision effect.Finally，the improved algorithm and related algorithms are implemented in the VTK environment，and the triangle mesh subdivision contrast experiment of gingival soft tissue deformation simulation is carried out on the real scanned dental three-dimensional model data.The results show that the subdivision efficiency of the improved algorithm is higher，and the average subdivision time is saved by 4.12%;the average smoothness is more reasonable to evaluate the subdivision effect，the subdivision triangle mesh is more regular，the distribution is more uniform，and the surface fairing quality is higher，which can better meet the requirements of authenticity and efficiency in soft tissue deformation simulation.Key words：triangular mesh;dihedral angle;adaptive subdivision;gingival deformation

0 引 言

虛擬牙齒矯正系統(tǒng)通過計(jì)算機(jī)逼真地模擬牙齒矯正過程，為患者量身定制治療計(jì)劃，進(jìn)而將不整齊的牙齒排列整齊。牙齒（剛體）改變位置通常會引起牙齦（軟組織）變形，因此精確、高效地模擬牙齦軟組織的形變是該系統(tǒng)重要的一部分。在計(jì)算機(jī)圖形學(xué)和計(jì)算機(jī)輔助設(shè)計(jì)中，通常用三角形網(wǎng)格來表示復(fù)雜的三維實(shí)體模型，在模擬牙齦軟組織形變過程中通常會在牙齦表面產(chǎn)生褶皺，這種褶皺會影響形變仿真的真實(shí)性，因此對牙齦表面進(jìn)行細(xì)分光滑處理顯得十分必要。

細(xì)分算法的基本思想最早追溯到50年代中期到70年代末。CATMULL和CLARK第1次明確地提出了細(xì)分曲面的概念[1]。80年代初到90年代，形成了很多經(jīng)典的細(xì)分算法。90年代中期，細(xì)分理論逐步完善并開始應(yīng)用于工業(yè)鄰域。近年來，三角網(wǎng)格細(xì)分技術(shù)不斷被應(yīng)用到計(jì)算機(jī)視覺、模式識別以及虛擬現(xiàn)實(shí)等鄰域[2]。一般來說，三角網(wǎng)格模型的網(wǎng)格越密集，三角網(wǎng)格逼近程度越高，模型表面光滑度越好，模型精度越高[3]。均勻的小尺寸單元雖然可以保證滿足網(wǎng)格的質(zhì)量和計(jì)算精度，但會在過度平坦的區(qū)域產(chǎn)生過多的單元，從而極大地降低程序的時空效率[4]。因此，生成幾何自適應(yīng)光順曲面網(wǎng)格就十分有必要。

用特殊的細(xì)分規(guī)則，在保證網(wǎng)格曲面光滑度要求的同時減少網(wǎng)格數(shù)量，這種方法就稱為網(wǎng)格自適應(yīng)細(xì)分[5]。自適應(yīng)細(xì)分算法就是在均勻細(xì)分算法的基礎(chǔ)上，采用特殊的判定準(zhǔn)則，通常是設(shè)置閾值來判斷某個三角網(wǎng)格是否進(jìn)行下一次迭代細(xì)分[6]。通過控制細(xì)分深度，使那些滿足精度的面片不再參與細(xì)分，而不滿足的繼續(xù)細(xì)分，從而大大減少冗余面片，提高模型的處理速度，減輕計(jì)算機(jī)的負(fù)擔(dān)[7]。

自適應(yīng)細(xì)分判定準(zhǔn)則主要包括非幾何準(zhǔn)則和幾何準(zhǔn)則2類。非幾何準(zhǔn)則主要取決于外部環(huán)境，根據(jù)感興趣區(qū)域或可見區(qū)域?qū)δＰ瓦M(jìn)行自適應(yīng)細(xì)分。幾何準(zhǔn)則通過計(jì)算一小塊鄰域的幾何信息來決定細(xì)分深度，主要包括：基于網(wǎng)格控制頂點(diǎn)與其極限位置間距離的準(zhǔn)則[8];基于網(wǎng)格面片與其相應(yīng)曲面片間距離的準(zhǔn)則;基于控制頂點(diǎn)曲率的準(zhǔn)則;基于三角面片面積的準(zhǔn)則;基于碰撞檢測的準(zhǔn)則;基于運(yùn)動時間的準(zhǔn)則[9];基于網(wǎng)格面夾角的準(zhǔn)則。實(shí)際應(yīng)用中經(jīng)常選擇幾何準(zhǔn)則作為自適應(yīng)細(xì)分判定準(zhǔn)則。

基于網(wǎng)格控制頂點(diǎn)與其極限位置間距離的準(zhǔn)則，僅適用于逼近型細(xì)分，對于插值型細(xì)分，網(wǎng)格控制頂點(diǎn)與其極限位置間距離始終為零?；诰W(wǎng)格面片與其相應(yīng)曲面片間距離的準(zhǔn)則，要求細(xì)分算法有對應(yīng)的參數(shù)表示，但并非所有細(xì)分曲面都有參數(shù)表示?；诳刂祈旤c(diǎn)曲率的準(zhǔn)則中，離散點(diǎn)曲率的計(jì)算比較復(fù)雜[10]，該方法也具有一定的局限性?；谌敲嫫娣e的準(zhǔn)則，對于面積相同的規(guī)則三角形和狹長三角形難以很好的區(qū)分?；谂鲎矙z測的準(zhǔn)則，是指當(dāng)研究對象與其他物體發(fā)生碰撞時[11]，對碰撞區(qū)域進(jìn)行細(xì)分從而避免發(fā)生穿透等來更加精確的模擬物體運(yùn)動。鮑義東等將這種基于碰撞檢測的自適應(yīng)細(xì)分算法應(yīng)用在虛擬手術(shù)訓(xùn)練系統(tǒng)中實(shí)現(xiàn)了較好的仿真效果[12]。但這里研究的是軟組織的形變仿真，不適合使用該準(zhǔn)則?；谶\(yùn)動時間的準(zhǔn)則，是指根據(jù)物體在不同時刻的運(yùn)動狀態(tài)進(jìn)行細(xì)分，因此也不適用于研究鄰域?；诰W(wǎng)格面夾角的準(zhǔn)則，也叫做二面角準(zhǔn)則，最早由AMRESH和FARIN等提出，是目前廣泛采用的幾何準(zhǔn)則[13]。近年來，這種方法主要應(yīng)用在其他仿真鄰域，對于牙齦軟組織形變仿真涉及到的不多。陳云翔等在對三維地形進(jìn)行仿真時提出了平坦度的概念，其自適應(yīng)判定準(zhǔn)則以一個面片為基準(zhǔn)，判斷該面片1-鄰域面片與該基準(zhǔn)面片的夾角平均值與閾值的大小關(guān)系[14]。周怡等在對CAD零件模型進(jìn)行自適應(yīng)細(xì)分時采用基于平均法向量的自適應(yīng)細(xì)分判定準(zhǔn)則，以一個頂點(diǎn)為基準(zhǔn)，判斷該頂點(diǎn)1-鄰域面片每個面片的平均法向量與其法向量夾角的平均值與閾值的大小關(guān)系。王艷艷等在進(jìn)行自適應(yīng)細(xì)分時采用頂點(diǎn)1-鄰域內(nèi)與該頂點(diǎn)相連較長3條邊的端點(diǎn)構(gòu)成的平面去代替其平均平面，并將頂點(diǎn)到其平均平面的距離作為判斷頂點(diǎn)重要度的標(biāo)準(zhǔn)來對三角網(wǎng)格進(jìn)行自適應(yīng)細(xì)分[15]，但該方法不僅會造成較差的細(xì)分精度，細(xì)分后三角面片數(shù)仍較多。鐘李濤等在對布料進(jìn)行形變仿真時提出的頂點(diǎn)權(quán)重變形度也是一種基于二面角的方法[16]，但該方法在實(shí)際應(yīng)用中需要鍵入命令來執(zhí)行細(xì)分程序，因而靈活性不高。

總之，上述方法在進(jìn)行自適應(yīng)細(xì)分時或者細(xì)分效率較低，或者生成的三角網(wǎng)格質(zhì)量較低、曲面光順質(zhì)量不高。主要研究虛擬牙齒矯正系統(tǒng)中牙齦軟組織的形變仿真，為了更加真實(shí)、高效地模擬牙齦軟組織的形變，需要對形變后牙齦三角網(wǎng)格進(jìn)行自適應(yīng)細(xì)分。因此，如何在保證細(xì)分效率的同時，使生成的三角網(wǎng)格更加規(guī)則，曲面光順性更好，成為研究的主要問題。

1 Loop細(xì)分規(guī)則

Loop細(xì)分是一種基于三角網(wǎng)格、逼近型、1-4面分裂細(xì)分算法，由美國猶他大學(xué)的CHARLES LOOP于1987年在其碩士論文中提出[17]。該算法細(xì)分規(guī)則簡單，光滑性好，生成的曲面質(zhì)量較高，但對尖銳特征的保持能力較弱，處理后曲面會產(chǎn)生較大的收縮，在正則點(diǎn)處可以達(dá)到C2連續(xù)，在奇異點(diǎn)處達(dá)到C1連續(xù)，是目前應(yīng)用最廣泛的細(xì)分算法之一[18]。以Loop細(xì)分算法作為研究基礎(chǔ)來對三角網(wǎng)格進(jìn)行自適應(yīng)細(xì)分。

2 三角網(wǎng)格質(zhì)量評價方法

在虛擬牙齦軟組織形變仿真過程中，牙齦表面通常會產(chǎn)生褶皺影響仿真效果。為了對比仿真效果，提高仿真精度，并進(jìn)行后續(xù)的網(wǎng)格處理，研究三角網(wǎng)格質(zhì)量評價方法具有重要意義。三角網(wǎng)格質(zhì)量是指三角形幾何形狀的合理性，一般通過三角形單元的邊長、面積、內(nèi)角等來衡量[19]。三維模型中三角網(wǎng)格的數(shù)量、網(wǎng)格的大小、網(wǎng)格的形狀以及網(wǎng)格單元拓?fù)浣Y(jié)構(gòu)是決定計(jì)算效率和精度的主要因素。因此網(wǎng)格質(zhì)量度量方法主要包括：基于曲率的方法、基于三角形大小的方法、基于三角形規(guī)則度的方法、基于頂點(diǎn)度數(shù)的方法和基于二面角的方法。

基于曲率的方法。曲率可以度量曲面的凹凸程度，通常用平均曲率與原曲率的差值來確定頂點(diǎn)的調(diào)整量進(jìn)而進(jìn)行網(wǎng)格光順。劉勝蘭等提出主曲率均勻的光順?biāo)惴ǎ脏忺c(diǎn)的主曲率和主方向的加權(quán)平均值作為光順后頂點(diǎn)的主曲率和主方向來確定頂點(diǎn)的調(diào)整量，從而較好的保持了模型的體積[20]?；谌切未笮〉姆椒?。三角形的大小是決定網(wǎng)格質(zhì)量的一個重要標(biāo)準(zhǔn)，過大的三角形會影響模型的精度，過小的三角形會增加計(jì)算負(fù)擔(dān)。潘炯波通過計(jì)算三角面片的面積與整個三角網(wǎng)格模型平均面積的比值，并比較該值與設(shè)定的閾值標(biāo)準(zhǔn)的大小來確定細(xì)分區(qū)域[21]?；谌切我?guī)則度的方法。通常三角面片越接近正三角形，三維網(wǎng)格模型的質(zhì)量越好。規(guī)則度度量最為常見的是頂點(diǎn)周圍的最小角和最大角，另外還有網(wǎng)格外接圓半徑等[22]。王忠飛等采用半徑比的方法來評價三維模型的變形效果[23]，該方法不利于判斷整個三維模型形變區(qū)域的光順性?；陧旤c(diǎn)度數(shù)的方法，良好的網(wǎng)格模型不僅需要每個三角形接近正三角形，而且要求三角形之間具有良好的拓?fù)潢P(guān)系[24]。頂點(diǎn)的度數(shù)是指共享該頂點(diǎn)的邊的條數(shù)，是衡量三角網(wǎng)格模型質(zhì)量又一個重要的標(biāo)準(zhǔn)?；诙娼堑姆椒?。基于二面角的方法通過計(jì)算三維網(wǎng)格相鄰三角面片法向量夾角來度量粗糙程度[25]。史卓等通過對三角面片兩兩之間的夾角閾值做判斷，并按一定的細(xì)分規(guī)則進(jìn)行局部細(xì)分，從而使模型局部特征明顯的部分更加精細(xì)[26]。

網(wǎng)格質(zhì)量優(yōu)化通過將節(jié)點(diǎn)不斷的重定位到其鄰域空間內(nèi)的最優(yōu)位置來提升曲面網(wǎng)格的質(zhì)量。其目標(biāo)是在精確地表示原始模型的基礎(chǔ)上，盡可能地輸出更為規(guī)則的網(wǎng)格，得到頂點(diǎn)分布比較均勻、三角形也盡可能接近正三角形的網(wǎng)格。但對網(wǎng)格形變操作后，衡量網(wǎng)格形變效果也是一個重要的方面。為了改善形變仿真后模型整體的仿真效果、提升網(wǎng)格質(zhì)量，網(wǎng)格光順質(zhì)量度量是必不可少的環(huán)節(jié)?；诠饣戎蚚27]，采用平均光滑度來度量網(wǎng)格光順質(zhì)量。

3 細(xì)分判定改進(jìn)

3.1 頂點(diǎn)光滑度判定

文中基于二面角準(zhǔn)則，提出頂點(diǎn)光滑度判定準(zhǔn)則來對三角網(wǎng)格進(jìn)行自適應(yīng)細(xì)分，細(xì)分方式基于Loop細(xì)分模式。

三角網(wǎng)格中各個頂點(diǎn)vi的頂點(diǎn)光滑度是通過求該頂點(diǎn)1-鄰域內(nèi)相鄰三角面片對的法向量夾角的平均值求得的，其公式為

式中 k為頂點(diǎn)1-鄰域內(nèi)三角面片的個數(shù);nj和n（j+1）%k分別為該頂點(diǎn)1-鄰域內(nèi)的相鄰三角面片對Cj和C（j+1）%k的單位法向量;α為相鄰三角面片對的法向量夾角。頂點(diǎn)1-鄰域三角面片及其法向量如圖3所示。

圖3通過設(shè)定光滑閾值來選取自適應(yīng)細(xì)分區(qū)域，光滑閾值為所有頂點(diǎn)的頂點(diǎn)光滑度的平均值，即

式中 θi為細(xì)分前每個頂點(diǎn)的頂點(diǎn)光滑度;N為細(xì)分前模型的頂點(diǎn)個數(shù)。

根據(jù)頂點(diǎn)光滑度及光滑閾值的定義可知：如果頂點(diǎn)1-鄰域區(qū)域比較光滑，那么該頂點(diǎn)1-鄰域內(nèi)相鄰三角面片對的法向量夾角就越小，這樣頂點(diǎn)光滑度就越小;否則，頂點(diǎn)光滑度就越大。將頂點(diǎn)光滑度作為衡量頂點(diǎn)1-鄰域區(qū)域光滑度大小的標(biāo)準(zhǔn)，然后再將該值與光滑閾值進(jìn)行比較，從而來確定自適應(yīng)細(xì)分區(qū)域。因此，可以說頂點(diǎn)的頂點(diǎn)光滑度和設(shè)定的光滑閾值決定著整個網(wǎng)格的自適應(yīng)細(xì)分情況。采用這種細(xì)分策略，對在形變過程中遭受拉伸扭曲較為劇烈的區(qū)域中的三角面片進(jìn)行自適應(yīng)細(xì)分，可以顯著地減少網(wǎng)格的扭曲程度，獲得更好的變形效果。在三維網(wǎng)格質(zhì)量評價背景下，通過這種自適應(yīng)細(xì)分算法生成的網(wǎng)格質(zhì)量相對更優(yōu)。

3.2 改進(jìn)細(xì)分算法

在對三角網(wǎng)格進(jìn)行自適應(yīng)細(xì)分時，通過比較頂點(diǎn)的頂點(diǎn)光滑度與光滑閾值的大小，可以確定細(xì)分區(qū)域。為了降低形變時間開銷，提高形變速度，文中對判定為需要細(xì)分的區(qū)域進(jìn)行一次細(xì)分操作，對判定為不需要細(xì)分的區(qū)域不進(jìn)行細(xì)分，如果θi>θ，則表示需要對該頂點(diǎn)周圍三角面片進(jìn)行細(xì)分;如果θi≤θ，則表示不需要對該頂點(diǎn)周圍三角面片進(jìn)行細(xì)分。

改進(jìn)細(xì)分算法如下

Step 1.初始狀態(tài)下將形變區(qū)域中所有頂點(diǎn)、邊、面都標(biāo)記為False，表示不需要進(jìn)行細(xì)分。

Step 2.計(jì)算頂點(diǎn)光滑度，設(shè)定光滑閾值。

Step 3.將每個頂點(diǎn)的頂點(diǎn)光滑度與初始設(shè)定的光滑閾值進(jìn)行比較。

Step 3.1.若頂點(diǎn)光滑度大于光滑閾值，則將該頂點(diǎn)標(biāo)記為true。

Step 3.2.若一條邊上2個頂點(diǎn)都為True，則該邊標(biāo)記為True。

Step 3.3.若一個三角面片上3個頂點(diǎn)都為True，則該面標(biāo)記為True。標(biāo)記為True表示該元素需要進(jìn)行細(xì)分。

Step 4.對標(biāo)記為True的三角面進(jìn)行Loop細(xì)分。

Step 4.1.計(jì)算每個三角網(wǎng)格上增加的新E-頂點(diǎn)的位置;更新原始三角網(wǎng)格頂點(diǎn)的位置作為新V-頂點(diǎn)。

Step 4.2.順次連接新E-頂點(diǎn)，連接新E-頂點(diǎn)與新V-頂點(diǎn)，重新建立連接信息，并計(jì)算每個新頂點(diǎn)的法向量和每個新面的法向量，得到新的控制網(wǎng)格。

Step 4.3.將新生成的頂點(diǎn)、邊、面標(biāo)記為False，表示完成對原始三角面片的一次細(xì)分操作。

Step 5.當(dāng)所有頂點(diǎn)、邊、面都標(biāo)記為False時，說明此時的細(xì)分曲面滿足了細(xì)分需求，完成細(xì)分操作，生成細(xì)分曲面。

采用平均光滑度來度量自適應(yīng)細(xì)分效果，平均光滑度為細(xì)分后所有頂點(diǎn)的頂點(diǎn)光滑度之和與模型頂點(diǎn)個數(shù)之商，其公式為

式中 θi為細(xì)分后每個頂點(diǎn)的頂點(diǎn)光滑度;M為細(xì)分后模型的頂點(diǎn)個數(shù)。這種方法綜合考慮了細(xì)分后網(wǎng)格頂點(diǎn)個數(shù)對判斷細(xì)分網(wǎng)格質(zhì)量的影響，因而可以更加合理的評價細(xì)分算法的性能。

4 實(shí)驗(yàn)結(jié)果及分析

4.1 實(shí)驗(yàn)環(huán)境及實(shí)驗(yàn)數(shù)據(jù)

實(shí)驗(yàn)基于Intel（R）Core（TM）i5-3230 M CPU 2.60 GHz處理器，Intel（R）HD Graphics 4000顯卡的筆記本電腦，在Windows 7操作系統(tǒng)，Visual Studio 2019開發(fā)環(huán)境下，采用C++語言并利用VTK開源庫，將文中改進(jìn)的基于頂點(diǎn)光滑度的三角網(wǎng)格自適應(yīng)細(xì)分算法應(yīng)用在牙齦軟組織的形變仿真上。

通過查閱國內(nèi)外關(guān)于自適應(yīng)細(xì)分算法研究的文獻(xiàn)發(fā)現(xiàn)：近年來對三維網(wǎng)格構(gòu)成的牙齦軟組織進(jìn)行自適應(yīng)細(xì)分的研究較少，對于軟組織方面的文獻(xiàn)也較少且不具有代表性;許多自適應(yīng)細(xì)分算法是應(yīng)用在機(jī)械零件或者布料仿真鄰域。布料相對機(jī)械零件來說，與軟組織較為相似，都不屬于剛體。因此，選擇鐘李濤等應(yīng)用在布料上的自適應(yīng)細(xì)分算法與本章改進(jìn)的自適應(yīng)細(xì)分算法進(jìn)行對比[16]。這篇文章雖然將自適應(yīng)細(xì)分算法應(yīng)用在布料仿真上，但主要是為了對三維模型進(jìn)行自適應(yīng)細(xì)分，因此算法應(yīng)該都是相通的。

將改進(jìn)的細(xì)分算法（簡記為文中算法）與鐘李濤等采用的基于頂點(diǎn)權(quán)重變形度的細(xì)分算法（文獻(xiàn)[16]）分別應(yīng)用在牙齦軟組織形變仿真上并進(jìn)行對比。為了能準(zhǔn)確地對比仿真結(jié)果，文中選用頂點(diǎn)個數(shù)、面片個數(shù)、總形變時間、細(xì)分時間、細(xì)分時間占比以及平均光滑度6個指標(biāo)來進(jìn)行分析。實(shí)驗(yàn)中對牙齒施加較小的力使牙齒平移或旋轉(zhuǎn)，在大量牙頜模型測試的基礎(chǔ)上選取一口牙頜模型中下頜的3顆牙齒（磨牙、前磨牙、切牙）進(jìn)行數(shù)據(jù)展示分析，下頜牙齒模型如圖4所示，頂點(diǎn)數(shù)60 171，面片數(shù)120 338。

4.2 數(shù)值度量結(jié)果分析

牙齦形變過程包括前期外力作用下的形變和自適應(yīng)細(xì)分下的形變2個步驟，因此總形變時間包括外力作用下的形變時間和細(xì)分時間2部分。其中，前期外力作用下的形變在文獻(xiàn)[27]中已經(jīng)進(jìn)行分析，主要分析自適應(yīng)細(xì)分產(chǎn)生的形變。圖5～圖8為對形變區(qū)域采用不同自適應(yīng)細(xì)分算法細(xì)分三角網(wǎng)格后，形變區(qū)域頂點(diǎn)個數(shù)和面片個數(shù)的對比情況。從圖5、6、7、8可以看出，自適應(yīng)細(xì)分增加了頂點(diǎn)個數(shù)以及面片個數(shù)，并且改進(jìn)算法相對文獻(xiàn)[16]算法細(xì)分后頂點(diǎn)個數(shù)和面片個數(shù)都較大。因此，相比未進(jìn)行自適應(yīng)細(xì)分的情況來說，增加自適應(yīng)細(xì)分算法會使整個牙齦形變時間增加，即總形變時間增加。為了更好的對比細(xì)分算法，這里主要對比自適應(yīng)細(xì)分時的網(wǎng)格細(xì)分時間。通過對比不同細(xì)分算法的細(xì)分效率和細(xì)分效果，對改進(jìn)算法進(jìn)行分析。牙齦網(wǎng)格的細(xì)分速度通過細(xì)分時間占比來度量，細(xì)分時間占總形變時間越小，細(xì)分速度越快，細(xì)分效率越高;牙齦網(wǎng)格的細(xì)分效果通過平均光滑度來度量，平均光滑度越小，細(xì)分后牙齦褶皺越少，細(xì)分效果越好。

牙齒平移牙齦曲面網(wǎng)格細(xì)分效率對比見表1，牙齒旋轉(zhuǎn)牙齦曲面網(wǎng)格細(xì)分效率對比見表2，2個表中分別對比了2種算法下3類牙齒平移和旋轉(zhuǎn)后的牙齦總形變時間、細(xì)分時間、細(xì)分時間占比以及平均光滑度。從表中可以看出，不論是在牙齒平移的情況下，還是在牙齒旋轉(zhuǎn)的情況下，改進(jìn)算法相對文獻(xiàn)[16]算法，雖然細(xì)分后頂點(diǎn)個數(shù)和面片個數(shù)相對稍大，但通過空間換時間使細(xì)分時間減少了。改進(jìn)算法在自適應(yīng)細(xì)分過程中通過計(jì)算頂點(diǎn)光滑度從整體上一次性對頂點(diǎn)1-鄰域區(qū)域光滑度進(jìn)行衡量，相對文獻(xiàn)[16]算法中通過計(jì)算基于三角面片面積的頂點(diǎn)權(quán)重變形度來定義高變形區(qū)、中變形區(qū)以及低變形區(qū)的方法來說，節(jié)省了自適應(yīng)細(xì)分判定時間，從而提高了細(xì)分效率。從細(xì)分時間占比一列可以看出，文獻(xiàn)[16]算法的細(xì)分時間占整個牙齦形變仿真時間平均為23.56%，而文中算法細(xì)分時間占比平均為19.44%，因此改進(jìn)算法的細(xì)分效率更高，細(xì)分時間占比平均約節(jié)約了4.12%。從平均光滑度一列可以看出，不論是對牙齒進(jìn)行平移還是旋轉(zhuǎn)，不論是對磨牙、前磨牙還是切牙進(jìn)行操作，改進(jìn)算法細(xì)分后網(wǎng)格平均光滑度更小，網(wǎng)格光順質(zhì)量更好。

4.3 視覺效果分析

圖9、圖10為對1號牙齒（磨牙）進(jìn)行平移和旋轉(zhuǎn)后的整體細(xì)分效果和局部細(xì)分效果;圖11，圖12為對2號牙齒（前磨牙）進(jìn)行平移和旋轉(zhuǎn)后的整體細(xì)分效果和局部細(xì)分效果;圖13，圖14為對3號牙齒（切牙）進(jìn)行平移和旋轉(zhuǎn)后的整體細(xì)分效果和局部細(xì)分效果。局部細(xì)分區(qū)域?yàn)檎w細(xì)分效果圖中紅色實(shí)線方框所選區(qū)域;局部細(xì)分效果圖中紅色虛線圓框所選區(qū)域?yàn)椴煌惴ㄗ赃m應(yīng)細(xì)分效果對比較為明顯的區(qū)域。圖中分別對比了細(xì)分前、文獻(xiàn)[16]算法以及改進(jìn)算法這3種算法下，牙齒平移或旋轉(zhuǎn)后的牙齦的實(shí)體模型效果和網(wǎng)格模型效果。實(shí)體模型中白色部分表示牙齒，紅色部分表示牙齦;網(wǎng)格模型中白色線條表示牙齒三角網(wǎng)格，紅色線條表示牙齦三角網(wǎng)格，細(xì)分算法就是作用于這些牙齦三角網(wǎng)格。從圖中可以看出，對3類牙齒進(jìn)行平移或旋轉(zhuǎn)操作時，改進(jìn)算法相比文獻(xiàn)[16]算法來說，能夠很好的對牙齦形變區(qū)域三角網(wǎng)格進(jìn)行細(xì)分，這是因?yàn)?，文獻(xiàn)[16]算法中采用三角面片面積作為權(quán)重來計(jì)算頂點(diǎn)權(quán)重變形度，對于面積相同且符合閾值約束的規(guī)則三角形與狹長三角形難以很好的區(qū)分，在細(xì)分區(qū)域判定過程中將實(shí)際不符合光滑度條件的狹長三角形當(dāng)做與其面積相同且規(guī)則的三角形來進(jìn)行處理，從而沒能進(jìn)行很好的細(xì)分。而改進(jìn)算法中采用的頂點(diǎn)光滑度，是通過計(jì)算頂點(diǎn)1-鄰域三角面片對的法向量夾角平均值來判定細(xì)分區(qū)域的，這種方法從整體上對曲面光滑度進(jìn)行衡量，因而產(chǎn)生的細(xì)分三角網(wǎng)格較為規(guī)則，生成的細(xì)分曲面較為光滑。因此，改進(jìn)算法能夠很好的識別需要細(xì)分的區(qū)域，進(jìn)而改善牙齦軟組織的形變效果，使形變后牙齦表面形變區(qū)域三角網(wǎng)格更加接近規(guī)則的正三角形、分布更加均勻，曲面光順質(zhì)量更好。

5 結(jié) 論

1）提出采用頂點(diǎn)光滑度作為自適應(yīng)細(xì)分區(qū)域的判定準(zhǔn)則，對虛擬牙齒矯正系統(tǒng)中牙齒移動后牙齦的形變區(qū)域進(jìn)行自適應(yīng)細(xì)分，從而使牙齦表面三角網(wǎng)格光順質(zhì)量更好。該算法通過比較每個頂點(diǎn)周圍1-鄰域內(nèi)相鄰面片對的法向量夾角平均值與光滑閾值的大小關(guān)系，來決定細(xì)分區(qū)域，對于細(xì)分區(qū)域采用Loop細(xì)分算法細(xì)分三角網(wǎng)格。

2）在真實(shí)掃描的牙頜三維模型數(shù)據(jù)上進(jìn)行牙齦軟組織形變仿真三角網(wǎng)格細(xì)分對比實(shí)驗(yàn)的結(jié)果表明，改進(jìn)的自適應(yīng)細(xì)分算法相對基于頂點(diǎn)權(quán)重變形度的細(xì)分算法來說，能夠更好的識別需要細(xì)分的區(qū)域，細(xì)分時間占比平均約節(jié)約了4.12%;平均光滑度對細(xì)分效果的評價更合理，細(xì)分的三角網(wǎng)格更規(guī)則、分布更均勻，曲面光順質(zhì)量更好，較好地滿足了軟組織形變仿真中真實(shí)性與高效性的要求。

3）主要研究的是自適應(yīng)細(xì)分算法中的細(xì)分區(qū)域選擇問題，但在自適應(yīng)細(xì)分過程中不同細(xì)分精度的網(wǎng)格之間可能會產(chǎn)生裂縫，后續(xù)還需研究牙冠和牙齦連接處協(xié)同細(xì)分處理的問題。

參考文獻(xiàn)（References）：

[1] 周怡，宋小文，胡樹根.自適應(yīng)Doo-Sabin細(xì)分算法改進(jìn)研究[J].機(jī)電工程，2008，25（10）：77-79.ZHOU Yi，SONG Xiaowen，HU Shugen.Research of improving the adaptive refinements in Doo-Sabin in subdivision scheme[J].Mechanical & Electrical Engineering Magazine，2008，25（10）：77-79.

[2]王克剛，耿國華.Canny邊緣檢測改進(jìn)中的自適應(yīng)平滑與增強(qiáng)[J].西安科技大學(xué)學(xué)報(bào)，2008，28（3）：577-580.WANG Kegang，GENG Guohua.An improved Canny edge detection based on adaptive smoothing and enhancement[J].Journal of Xian university of science and technology，2008，28（3）：577-580.

[3]RAHIMI M，SHEN Y.Adaptive spatial mapping of electro-tactile threshold based on subdivision bio-impedance feedback[C]//Proceedings of The 2019 IEEE International Conference on Real-time Computing and Robotics，Russia，University of Canberra，2019：164-169.[4]YANG J，GONG Y，WU H，et al.A feature preserved mesh subdivision framework for biomedical mesh[C]//Proceedings of The 2017 IEEE 17th International Conference on Bioinformatics and Bioengineering，2017：394-401.

[5]吳劍煌，劉偉軍，王天然.面向三角網(wǎng)格的自適應(yīng)細(xì)分[J].計(jì)算機(jī)工程，2006，32（12）：14-16.WU Jianhuang，LIU Weijun，WANG Tianran.Adaptive refinement scheme for triangular meshes[J].Computer Engineering，2006，32（12）：14-16.

[6]ZHAO G，Ye G，LIU H，et al.Electronic interpolation interface based on linear subdivision method for sinusoidal optical encoders[J].IEEE Sensors Journal，2020，20（7）：3646-3654.

[7]LI Q，CHEN G，WANG S.Softness-based adaptive mesh refinement algorithm for soft tissue deformation[J].BioSystems，2020，191-192（4）：104103.

[8]MIN L，CHEN Y，WANG H，et al.Loop adaptive subdivision surface[C]//Proceedings of the journal of physics.China：Institute of Physics Publishing，2019：1-9.[9]郭新龍.曲面網(wǎng)格模型細(xì)分技術(shù)的研究[D].上海：華東理工大學(xué)，2013.GUO Xinlong.Research on surface mesh subdivision technology[D].Shanghai：East China University of Science and Technology，2013.

[10]劉德平，王彩勤.軟巖雙連拱隧道施工模擬與力學(xué)分析[J].西安科技大學(xué)學(xué)報(bào)，2010，30（6）：672-676.LIU Deping，WANG Caiqin.Simulation of soft double multi-arch tunnel and mechanical analysis[J].Journal of Xian university of science and technology，2010，30（6）：672-676.

[11]張?zhí)燔?，張磊，張超，?巷道與鉆孔交叉三維數(shù)值建模方法[J].西安科技大學(xué)學(xué)報(bào)，2015，35（6）：688-694.ZHANG Tianjun，ZHANG Lei，ZHANG Chao，et al.3D grid modeling method of roadway borehole intersecting[J].Journal of Xian university of science and technology，2015，35（6）：688-694.

[12]鮑義東，吳冬梅.自適應(yīng)細(xì)分及優(yōu)化編碼八叉樹碰撞檢測算法[J].上海交通大學(xué)學(xué)報(bào)，2015，49（8）：1114-1122.BAO Yidong，WU Dongmei.A novel algorithm for collision detection based on octree of adaptive subdivision and encoding[J].Journal of Shanghai Jiaotong University，2015，49（8）：1114-1122.

[13]AMRESH A，F(xiàn)ARIN G，RAZDAN A.Adaptive subdivision schemes for triangle meshes[J].Arizona State University，2001，19（3）：1-9.

[14]陳云翔，劉文杰，丁永生，等.基于蝶形細(xì)分自適應(yīng)算法的三維地形仿真[J].計(jì)算機(jī)仿真，2009，26（1）：229-232.CHEN Yunxiang，LIU Wenjie，DING Yongsheng，et al.3D terrain simulation based on an adaptive algorithm with butterfly subdivision[J].Computer Simulation，2009，26（1）：229-232.

[15]王艷艷，惠麗峰，羅曉峰，等.三角網(wǎng)格頂點(diǎn)重要度的自適應(yīng)Loop細(xì)分算法[J].計(jì)算機(jī)工程與應(yīng)用，2014，50（13）：201-227.WANG Yanyan，HUI Lifeng，LUO Xiaofeng，et al.Adaptive loop subdivision algorithm for triangle mesh based on vertexs importance[J].Computer Engineering and Applications，2014，50（13）：201-204.[16]鐘李濤，候進(jìn)，龔隨，等.基于低精度布料采樣的多精度布料構(gòu)建方法[J].計(jì)算機(jī)應(yīng)用研究，2019，36（1）：278-283.ZHONG Litao，HOU Jin，GONG Sui，et al.Multi-resolution cloth construction based on low-resolution cloth sampling[J].Application Research of Computers，2019，36（1）：278-283.

[17]楊雷雷.基于Haptics的牙齒曲面微變形設(shè)計(jì)技術(shù)[D].南京：南京航空航天大學(xué)，2010.YANG Leilei.Haptics-based micro-deformation design techniques for dental model surface[D].Nanjing：Nanjing University of Aeronautics and Astronautics，2010.

[18]閔莉，陳穎，王洪暢.Loop自適應(yīng)細(xì)分曲面算法研究[J].沈陽建筑大學(xué)學(xué)報(bào)（自然科學(xué)版），2020，36（1）：163-171.MIN Li，CHEN Ying，WANG Hongchang.The research on loop adaptive subdivision surface algorithm[J].Journal of Shenyang Jianzhu University（Natural Science），2020，36（1）：163-171.

[19]林曉穗，李桂清，尹夢曉，等.優(yōu)化變形能的平面多邊形同構(gòu)剖分[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2014，26（12）：2115-2125.LIN Xiaosui，LI Guiqing，YIN Mengxiao，et al.Compatible triangulations of planar polygons based on deformed energy optimization[J].Journal of Computer Aided Design & Computer Graphics，2014，26（12）：2115-2125.

[20]劉勝蘭，周儒榮，聶軍洪，等.主曲率均勻的網(wǎng)格光順[J].計(jì)算機(jī)學(xué)報(bào)，2004，27（1）：79-84.LIU Shenglan，ZHOU Rurong，NIE Junhong，et al.Mesh smoothing using principal curvature flow[J].Chinese Journal of Computers，2004，27（1）：79-84.

[21]潘炯波.三角網(wǎng)格的自適應(yīng)細(xì)分研究[J].計(jì)算機(jī)工程與應(yīng)用，2011，47（18）：186-187.PAN Jiongbo.Adaptive subdivision research for triangular mesh[J].Computer Engineering and Applications，2011，47（18）：186-187.[22]宮翔飛，張樹道.Laplacian與局部優(yōu)化方法相結(jié)合的網(wǎng)格光滑技術(shù)[J].北京理工大學(xué)學(xué)報(bào)，2010，30（5）：616-621.GONG Xiangfei，ZHANG Shudao.One mesh smoothing algorithm combining Laplacian and local optimization-based mesh smoothing techniques[J].Transactions of Beijing Institute of Technology，2010，30（5）：616-621.

[23]王忠飛，金慶仙.基于梯度變形的多邊形建模方法研究[J].機(jī)電工程，2017，34（12）：1417-1421.WANG Zhongfei，JIN Qingxian.Polygon modeling based on gradient deformation[J].Journal of Mechanical & Electrical Engineering，2017，34（12）：1417-1421.[24]嚴(yán)冬明，胡楷模，郭建偉，等.各向同性三角形重新網(wǎng)格化方法綜述[J].計(jì)算機(jī)科學(xué)，2017，44（8）：9-17.YAN Dongming，HU Kaimo，GUO Jianwei，et al.Survey of recent isotropic triangular remeshing techniques[J].Computer Science，2017，44（8）：9-17.

[25]華磊，郁梅，林瑤瑤.基于多特征融合的三維網(wǎng)格質(zhì)量評價方法[J].激光雜志，2020，41（1）：100-107.HUA Lei，YU Mei，LIN Yaoyao.3D mesh quality assessment method based on multiple feature fusion[J].Laser Journal，2020，41（1）：100-107.

[26]史卓，孔謙，玉珂.基于二面角逆差值Loop細(xì)分的漸進(jìn)傳輸方法[J].圖學(xué)學(xué)報(bào)，2019，40（1）：92-98.SHI Zhuo，KONG Qian，YU Ke.Progressive transmission method based on dihedral reverse interpolation loop subdivision[J].Journal of Graphics，2019，40（1）：92-98.

[27]馬天，李嬌嬌，李占利，等.質(zhì)點(diǎn)彈簧模型在牙齦軟組織形變仿真上的改進(jìn)與應(yīng)用[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2020，32（2）：325-333.MA Tian，LI Jiaojiao，LI Zhanli，et al.Improvement and application of mass spring model in simulation of gingival soft tissue deformation[J].Journal of Computer Aided Design & Computer Graphics，2020，32（2）：325-333.