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

馬 天，李嬌嬌，李 赟

(西安科技大學 計算機科學與技術(shù)學院，陜西 西安 710054)

0 引 言

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

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

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

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

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

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

1 Loop細分規(guī)則

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

圖1 Loop細分過程

圖2 Loop細分規(guī)則

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

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

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

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

3 細分判定改進

3.1 頂點光滑度判定

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

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

(1)

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

圖3通過設定光滑閾值來選取自適應細分區(qū)域，光滑閾值為所有頂點的頂點光滑度的平均值，即

圖3 頂點1-鄰域三角面片及其法向量

(2)

式中θi為細分前每個頂點的頂點光滑度；N為細分前模型的頂點個數(shù)。

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

3.2 改進細分算法

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

改進細分算法如下

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

Step 2.計算頂點光滑度，設定光滑閾值。

Step 3.將每個頂點的頂點光滑度與初始設定的光滑閾值進行比較。

Step 3.1.若頂點光滑度大于光滑閾值，則將該頂點標記為true。

Step 3.2.若一條邊上2個頂點都為True，則該邊標記為True。

Step 3.3.若一個三角面片上3個頂點都為True，則該面標記為True。標記為True表示該元素需要進行細分。

Step 4.對標記為True的三角面進行Loop細分。

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

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

Step 4.3.將新生成的頂點、邊、面標記為False，表示完成對原始三角面片的一次細分操作。

Step 5.當所有頂點、邊、面都標記為False時，說明此時的細分曲面滿足了細分需求，完成細分操作，生成細分曲面。

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

(3)

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

4 實驗結(jié)果及分析

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

實驗基于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開源庫，將文中改進的基于頂點光滑度的三角網(wǎng)格自適應細分算法應用在牙齦軟組織的形變仿真上。

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

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

圖4 下頜牙齒模型

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

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

圖5 牙齒平移時細分后頂點個數(shù)對比

圖6 牙齒平移時細分后面片個數(shù)對比

圖7 牙齒旋轉(zhuǎn)時細分后頂點個數(shù)對比

圖8 牙齒旋轉(zhuǎn)時細分后面片個數(shù)對比

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

表1 牙齒平移牙齦曲面網(wǎng)格細分效率對比

表2 牙齒旋轉(zhuǎn)牙齦曲面網(wǎng)格細分效率對比

4.3 視覺效果分析

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

圖9 1號牙齒(磨牙)平移牙齦細分效果對比

圖10 1號牙齒(磨牙)旋轉(zhuǎn)牙齦細分效果對比

圖11 2號牙齒(前磨牙)平移牙齦細分效果對比

圖12 2號牙齒(前磨牙)旋轉(zhuǎn)牙齦細分效果對比

圖13 3號牙齒(切牙)平移牙齦細分效果對比

圖14 3號牙齒(切牙)旋轉(zhuǎn)牙齦細分效果對比

5 結(jié) 論

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

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

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