三角網(wǎng)格頂點(diǎn)重要度的自適應(yīng)Loop細(xì)分算法

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

1.內(nèi)蒙古科技大學(xué)高等職業(yè)技術(shù)學(xué)院，內(nèi)蒙古包頭014010

2.內(nèi)蒙古科技大學(xué)礦業(yè)工程學(xué)院，內(nèi)蒙古包頭014010

3.太原科技大學(xué)計(jì)算機(jī)學(xué)院，太原030024

1 引言

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

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

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

2 Loop細(xì)分模式

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

此細(xì)分模式的各種頂點(diǎn)細(xì)分模板如圖1所示。

圖1 Loop細(xì)分模板示意圖

（1）內(nèi)部奇頂點(diǎn)的計(jì)算公式為：

（2）內(nèi)部偶頂點(diǎn)的計(jì)算公式為：

設(shè)V0，V1，…，Vk-1是頂點(diǎn)V的1-鄰接頂，k為頂點(diǎn)V的價(jià)，β的定義如下：

（3）邊界奇、偶頂點(diǎn)，可分別用圖1（c）、（d）的模板來計(jì)算。

3 新的自適應(yīng)細(xì)分算法

經(jīng)過大量實(shí)驗(yàn)發(fā)現(xiàn)，對空間網(wǎng)格形狀影響越大的頂點(diǎn)越容易被細(xì)分，對網(wǎng)格形狀影響越小的頂點(diǎn)就越不容易被細(xì)分。本文以頂點(diǎn)到其平均平面的距離作為細(xì)分準(zhǔn)則，這樣頂點(diǎn)細(xì)分就轉(zhuǎn)換為判斷頂點(diǎn)重要度的問題了。

定義1 （頂點(diǎn)的星型域）在空間三角形網(wǎng)格中，把頂點(diǎn)V（內(nèi)點(diǎn)）和其1-鄰域上的頂點(diǎn)構(gòu)成的封閉區(qū)域稱為V的星型鄰域，記為Star(V)。對于點(diǎn)V為邊界點(diǎn)的情況，稱由V，V1，V2，…，Vi組成的三角形區(qū)域?yàn)辄c(diǎn)V的半星型鄰域Starhalf(V)，將V的星型鄰域和半星型鄰域統(tǒng)稱為Star(V)。

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

3.1 頂點(diǎn)重要度的改進(jìn)

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

3.1.1 平均平面

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

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

3.1.2 頂點(diǎn)的重要度

網(wǎng)格模型上的點(diǎn)可分為內(nèi)部頂點(diǎn)和邊界頂點(diǎn)，它們的重要度與該點(diǎn)在空間網(wǎng)格上的曲率相對應(yīng)，曲率越大，對空間網(wǎng)格形狀的保持就越重要，這樣的頂點(diǎn)也就越容易細(xì)分；否則，反之。

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

圖2 內(nèi)部頂點(diǎn)V的重要度

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

圖3 邊界頂點(diǎn)V的重要度

邊界線V1Vi直線方程為：

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

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

上述的改進(jìn)方法會造成一定程度的誤差，但誤差可限制在為數(shù)不多的三角形范圍內(nèi)。對數(shù)據(jù)源密度非常高的網(wǎng)格模型來說，對應(yīng)的三角面片非常小。本文的細(xì)分方法可以在一定程度上減少對最終顯示效果影響不大的冗余計(jì)算，重點(diǎn)突顯三維圖形的主要特征和拓?fù)浣Y(jié)構(gòu)，適宜對顯示速度有較高要求的情景。

3.2 算法步驟

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

（1）遍歷全部頂點(diǎn)，計(jì)算各個(gè)頂點(diǎn)的價(jià)。

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

（3）由三角形所含死點(diǎn)的個(gè)數(shù)，確定三角形的邊的類型和面的類型。

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

（5）新面的生成。對死面不進(jìn)行分裂生成新面?；蠲娴姆至逊绞接址譃閮煞N：

①當(dāng)三條邊都為活邊時(shí)，將該面分裂成4個(gè)小三角形；

②當(dāng)只有一條死邊時(shí)，死邊上不插入新點(diǎn)。另外兩條邊頂點(diǎn)處重要度決定了新的三角形生成方式。

（6）采用Loop細(xì)分模板更新所有偶點(diǎn)的位置。

（7）判斷是否進(jìn)行下次細(xì)分，直到滿足需求。

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

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

圖4 汽車模型自適應(yīng)細(xì)分結(jié)果圖

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

圖5 人體模型自適應(yīng)細(xì)分結(jié)果圖

圖6 地形模型自適應(yīng)細(xì)分結(jié)果圖

表1 兩種方法的實(shí)驗(yàn)結(jié)果對比

通過表1可以看出，本文算法在三次細(xì)分過程中產(chǎn)生的三角面片數(shù)都要多于文獻(xiàn)[8]中的算法，但是隨著細(xì)分次數(shù)增多，三角面片數(shù)的增加，本文算法的時(shí)效性就越發(fā)地顯現(xiàn)出來，這是因?yàn)楸疚乃惴ㄍㄟ^距離來判定頂點(diǎn)是否參與細(xì)分，省去了反復(fù)計(jì)算頂點(diǎn)法矢的過程，加快了對數(shù)據(jù)量非常龐大的模型進(jìn)行處理，時(shí)間效率比較高。

5 結(jié)論

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

[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，F(xiàn)arin 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]胡和平.自適應(yīng)Catmull-Clark細(xì)分算法[J].華中科技大學(xué)學(xué)報(bào)，2002，10（10）：56-58.

[9]李桂清，吳壯志，馬維銀.自適應(yīng)細(xì)分技術(shù)研究進(jìn)展[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2006，18（12）：1789-1799.

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

[11]鐘大平，周來水，周海.自適應(yīng)混合細(xì)分算法研究[J].機(jī)械科學(xué)與技術(shù)，2004，23（9）：1090-1092.

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

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

[14]王艷艷，張榮國，王蓉，等.向量線性相關(guān)的三角網(wǎng)格自適應(yīng)Loop細(xì)分方法[J].工程圖學(xué)學(xué)報(bào)，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]羅鹍，黃魁東，連明明.基于頂點(diǎn)刪除的三角網(wǎng)格模型簡化新方法[J].微電子學(xué)與計(jì)算機(jī)，2009（5）：142-144.

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