三角網格頂點重要度的自適應Loop細分算法

王艷艷，惠麗峰，羅曉鋒，張榮國

1.內蒙古科技大學高等職業技術學院，內蒙古包頭014010

2.內蒙古科技大學礦業工程學院，內蒙古包頭014010

3.太原科技大學計算機學院，太原030024

1 引言

在CG、幾何造型等領域中，物體表面通常是用三角形網格模型來描述的。在多數情況下，需要使用三維激光掃描儀對大物體、寬場景進行數據采集。為了適應計算機對這些數據的實時顯示、傳輸、分析、編輯、重建、存儲等要求，必須對這類模型數據進行處理。一類是簡化網格模型：在保持物體特征和視覺效果的前提下，減少該模型的頂點數、邊數、三角面片數；另一類是自適應細分：通過控制誤差來局部細分網格，力求以較少的網格來獲得性能良好的曲面。對三角網格進行簡化和細分是CG研究領域的兩大熱點。

經過多年的發展，細分算法已經成為圖形學領域的一種標準造型技術。現有的細分模式有：Loop[1]、Catmull、Clark[2]、3[3]、混合細分[4]模式等，文獻[5]提出了一種廣泛的Loop細分方法。自適應細分算法是傳統細分算法的一種改進，它主要研究如何確定自適應細分準則，消除裂縫以及修正頂點幾何屬性等。對于這些問題的解決，國外Ashish Am resh等人對三角網格自適應細分[6]作了探索，文獻[7]提出了一種增量自適應細分，該方法可以根據用戶的需求只對選定的區域進行細分；國內有華中科技大學的胡等對四邊形的自適應細分[8]作了研究；另外，文獻[9-11]也在自適應細分方面作了大量的研究。

到目前為止，很多三角形網格的自適應細分方法[5，10-14]已被提出，但這些算法都不可避免會產生一些退化三角形，使得部分面片處于不同層，破壞了整體細分曲面的連續性。本文將域平均平面的距離[15]作為尺度，并根據文獻[16]求平均平面網格簡化方法中常用到的頂點重要度作為判斷頂點是否參與細分的標準，用頂點到其1-鄰的方法對其進行改進。經過大量的實驗發現，該方法計算簡單，處理速度快，其時間性能優于其他算法。

2 Loop細分模式

它是一種基于三角網格1-4面分裂的、逼近的細分模式，生成的曲面是盒式樣條曲面的推廣，在正則曲面上是C2連續，在奇異點處是C1連續。

此細分模式的各種頂點細分模板如圖1所示。

圖1 Loop細分模板示意圖

（1）內部奇頂點的計算公式為：

（2）內部偶頂點的計算公式為：

設V0，V1，…，Vk-1是頂點V的1-鄰接頂，k為頂點V的價，β的定義如下：

（3）邊界奇、偶頂點，可分別用圖1（c）、（d）的模板來計算。

3 新的自適應細分算法

經過大量實驗發現，對空間網格形狀影響越大的頂點越容易被細分，對網格形狀影響越小的頂點就越不容易被細分。本文以頂點到其平均平面的距離作為細分準則，這樣頂點細分就轉換為判斷頂點重要度的問題了。

定義1 （頂點的星型域）在空間三角形網格中，把頂點V（內點）和其1-鄰域上的頂點構成的封閉區域稱為V的星型鄰域，記為Star(V)。對于點V為邊界點的情況，稱由V，V1，V2，…，Vi組成的三角形區域為點V的半星型鄰域Starhalf(V)，將V的星型鄰域和半星型鄰域統稱為Star(V)。

定義2 （平均平面）對于頂點V的星型鄰域，必存在一個平面，使得點V的所有鄰域點Vi到此平面的距離和最小，則稱它為Star(V)的平均平面，記為SStar(V)。

3.1 頂點重要度的改進

根據定義可知，頂點V的平均平面是存在的，但要將這個平面表示出來是非常困難的。鑒于此，計算頂點到其平均平面的距離時，用與此頂點相連較長三條邊的端點構成的平面來代替平均平面，因而頂點的重要度得以改進。

3.1.1 平均平面

設(x0，y0，z0)為頂點V的坐標，(xi，yi，zi)為頂點V的1-鄰域上所有點的坐標。利用公式（4）求出三條最長邊的端點Vi、Vj、Vk，已知它們坐標(xi，yi，zi)，(xj，yj，zj)，(xk，yk，zk)，利用這三個點的坐標可得平面的三點式方程：

將公式（5）轉化為平面的一般方程為：Amx+Bmy+Cmz+Dm=0，即為平均平面方程。

3.1.2 頂點的重要度

網格模型上的點可分為內部頂點和邊界頂點，它們的重要度與該點在空間網格上的曲率相對應，曲率越大，對空間網格形狀的保持就越重要，這樣的頂點也就越容易細分；否則，反之。

內部點的重要度可定義為頂點V(x0，y0，z0)到平均平面Amx+Bmy+Cmz+Dm=0的距離，如圖2所示。記為Degree(V)，當頂點V的星型鄰域上點確定時，DVS的值越大，相應頂點V處的曲率變化也越大。

圖2 內部頂點V的重要度

由于邊界頂點位置決定了邊界的形狀，因此其重要度不僅與邊界頂點處的曲率有關，還與其所在的邊界曲線的曲率有關。設V1、Vi為邊界頂點V的半星型鄰域上的兩個邊界頂點，V2、V3、V4，為這個鄰域上的內部頂點。V點周圍頂點所確定的平均平面為SStar(V)，DVS為點V到平面SStar(V)的距離，DVE為點V到邊界線V1Vi的距離，如圖3所示。

圖3 邊界頂點V的重要度

邊界線V1Vi直線方程為：

那么頂點V(x0，y0，z0)到此直線的距離[17]為：

其中ni=(Ai，Bi，Ci)，i∈n，M=A1x0+B1y0+C1z0+D1，N=Aix0+Biy0+Ciz0+Di。根據公式（6）、（7），邊界頂點的重要度就為：

上述的改進方法會造成一定程度的誤差，但誤差可限制在為數不多的三角形范圍內。對數據源密度非常高的網格模型來說，對應的三角面片非常小。本文的細分方法可以在一定程度上減少對最終顯示效果影響不大的冗余計算，重點突顯三維圖形的主要特征和拓撲結構，適宜對顯示速度有較高要求的情景。

3.2 算法步驟

為了清晰地說明本文算法，先來定義三對名詞。假設三角網格中的某個頂點的重要度小于給定的閾值，則此點為死點，反之為活點；只有當三角形一條邊上的兩個點都為死點時，該邊才為死邊，其余均為活邊；當一個三角形至少有兩條死邊時，這個三角形為死面，其余為活面。本文算法的具體步驟為：

（1）遍歷全部頂點，計算各個頂點的價。

（2）依據公式（6）或公式（8）計算出每個頂點的重要度，如果Degree(V)小于給定的閾值ε，則記為死點。

（3）由三角形所含死點的個數，確定三角形的邊的類型和面的類型。

（4）新（奇）點的生成。在活邊上按照Loop細分模式插入新點，采用Loop細分模板計算其插入位置。死邊上就不需要插入新點。

（5）新面的生成。對死面不進行分裂生成新面。活面的分裂方式又分為兩種：

①當三條邊都為活邊時，將該面分裂成4個小三角形；

②當只有一條死邊時，死邊上不插入新點。另外兩條邊頂點處重要度決定了新的三角形生成方式。

（6）采用Loop細分模板更新所有偶點的位置。

（7）判斷是否進行下次細分，直到滿足需求。

4 實驗結果和分析

為了驗證本文算法的有效性，利用C++和OPENGL圖形函數庫，在VC++6.0環境編程實現了相應算法，對原始面片數為914的汽車模型、面片數為3 121的人體模型及面片數為8 516地形模型進行了三次細分，如圖4～6所示。

圖4 汽車模型自適應細分結果圖

從圖4～6可以看出，本文算法主要集中在對高曲率部分進行細分，汽車模型中，特別是對車輪和車體具有棱邊、棱角等具有尖銳特征的部位細分得最多；車窗、車頂和車門等平坦的部位細分較少。人體模型中，對脖頸截面、雙乳及肚臍部分細分較多，其他部分較少；地形模型中，對山脊部分細分多，而平地部分細分少。將本文算法和文獻[8]中的算法進行了實驗比較，表1在給定同一閾值的情況下對這兩種方法的實驗結果作了統計。

圖5 人體模型自適應細分結果圖

圖6 地形模型自適應細分結果圖

表1 兩種方法的實驗結果對比

通過表1可以看出，本文算法在三次細分過程中產生的三角面片數都要多于文獻[8]中的算法，但是隨著細分次數增多，三角面片數的增加，本文算法的時效性就越發地顯現出來，這是因為本文算法通過距離來判定頂點是否參與細分，省去了反復計算頂點法矢的過程，加快了對數據量非常龐大的模型進行處理，時間效率比較高。

5 結論

以與頂點相連較長三條邊的端點構成的平面近似為該頂點的平均平面，這與用網格面積法向加權求得的平均平面相比，前者就存在著很大的誤差。但目前三角網格模型的數據量都越來越龐大，精度也越來越高，在這樣的網格模型中，三角形的面積非常小，密度高且各三角形的形狀也比較接近，因此該方法產生的誤差可被限制在一定數量的三角形之內，對最終簡化結果的視覺影響不大，是可以采用的。以距離作為細分尺度，省去了反復計算三角形法矢量和面積的過程，大大減少了龐大數據模型的計算量，時間優越性能很高，但是細分后的三角面片數較多，這是本文算法的不足之處。以后的主要工作將集中在保持良好的細分效果情況下，既有高的時效性，又能最大化減少三角面片數。

[1]Loop C.Smooth subdivision surfaces based on triangles[D].Utah,USA:University of Utah，1987.

[2]Catmull E，Clark J.Recursively generated B-spline surfaces on arbitrary topological meshes[J].Computer Aided Design，1998，l0（6）：183-188.

[3]Doo D，Sabin M.Behaviour of recursive division surfaces near extraordinary points[J].Computer Aided Design，1978，10：356-360.

[4]Stam J，Loop C.Quad/triangle subdivision[J].Computer Graphics Forum，2003，22（1）：79-85.

[5]Ginkel I，Um lauf G.Analyzing a generalized loop subdivision scheme[J].Computing，2007，79（2/4）：353-363.

[6]Am resh A，Farin G，Razdan A.Adaptive subdivision schemes for triangular meshes[M]//Hierarchical and Geometric Methods in Scientific Visualization.Berlin：Springer-Verlag，2003.

[7]Pakdel H R，Samavati F F.Incremental adaptive loop subdivision[C]//Proceedings of ICCSA，2004：237-246.

[8]胡和平.自適應Catmull-Clark細分算法[J].華中科技大學學報，2002，10（10）：56-58.

[9]李桂清，吳壯志，馬維銀.自適應細分技術研究進展[J].計算機輔助設計與圖形學學報，2006，18（12）：1789-1799.

[10]吳劍煌，劉偉軍，王天然.面向三角網格的自適應細分[J].計算機工程，2006，32（12）：14-16.

[11]鐘大平，周來水，周海.自適應混合細分算法研究[J].機械科學與技術，2004，23（9）：1090-1092.

[12]李李，王亞平.裁剪曲面自適應三角化剖分[J].計算機應用，2006（S1）：2-13.

[13]趙宏慶，彭國華，葉正麟，等.自適應細分方法進行曲面造型[J].計算機應用研究，2006（9）：72-76.

[14]王艷艷，張榮國，王蓉，等.向量線性相關的三角網格自適應Loop細分方法[J].工程圖學學報，2009（1）：91-96.

[15]Schroeder W J，Zarge J A，Lorensen W E.Decimation of triangle meshes[J].ACM SIGGRAPH Computer Graphics，1992，26（2）：65-70.

[16]羅鹍，黃魁東，連明明.基于頂點刪除的三角網格模型簡化新方法[J].微電子學與計算機，2009（5）：142-144.

[17]王煥.點到空間直線距離公式的兩種簡潔證明[J].高等數學研究，2006，9（2）：38-39.