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

馬 天，李嬌嬌，李 赟

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

0 引 言

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

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

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

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

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

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

1 Loop細分規則

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

圖1 Loop細分過程

圖2 Loop細分規則

2 三角網格質量評價方法

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

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

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

3 細分判定改進

3.1 頂點光滑度判定

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

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

(1)

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

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

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

(2)

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

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

3.2 改進細分算法

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

改進細分算法如下

Step 1.初始狀態下將形變區域中所有頂點、邊、面都標記為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.計算每個三角網格上增加的新E-頂點的位置；更新原始三角網格頂點的位置作為新V-頂點。

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

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

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

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

(3)

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

4 實驗結果及分析

4.1 實驗環境及實驗數據

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

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

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

圖4 下頜牙齒模型

4.2 數值度量結果分析

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

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

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

圖7 牙齒旋轉時細分后頂點個數對比

圖8 牙齒旋轉時細分后面片個數對比

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

表1 牙齒平移牙齦曲面網格細分效率對比

表2 牙齒旋轉牙齦曲面網格細分效率對比

4.3 視覺效果分析

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

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

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

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

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

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

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

5 結 論

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

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

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