保持特征的高質(zhì)量三角網(wǎng)格簡化方法

張 霞，段黎明＋ ，劉 璐

（1．重慶大學 機械工程學院，重慶 400044；2．重慶大學 光電技術(shù)及系統(tǒng)教育部重點實驗室ICT研究中心，重慶 400044）

0 引言

在逆向工程中，常采用三角網(wǎng)格模型來描述物體。復(fù)雜的三角網(wǎng)格模型由幾十萬、幾百萬甚至上億個三角形組成，如此龐大的數(shù)據(jù)量對計算機的分析、顯示、存儲與傳輸構(gòu)成了巨大的挑戰(zhàn)。采用一些相對簡單的模型代替原始模型可以解決這些問題，如何做到既能簡化復(fù)雜的三角網(wǎng)格模型又不丟失模型的細節(jié)特征，成為近些年國內(nèi)外學者廣泛關(guān)注的問題。

目前，國內(nèi)外針對三角網(wǎng)格模型的簡化已提出了許多算法，常用的簡化方法可分為幾何元素刪除法、網(wǎng)格重新劃分法和幾何元素折疊法。幾何元素刪除法包括頂點刪除和三角形刪除［1－2］，這兩種方法不斷地從網(wǎng)格中刪除頂點或三角形，同時對模型中形成的空洞進行三角化，但重新三角化增加了簡化操作的復(fù)雜性。網(wǎng)格重新劃分法［3］是根據(jù)一定規(guī)則產(chǎn)生新網(wǎng)格的所有頂點，再對它進行三角剖分，從而形成一個頂點更少、拓撲關(guān)系更簡單的逼近網(wǎng)格，但該方法簡化不光滑模型時效果較差，且計算量和誤差都較大。幾何元素折疊法包括邊折疊和三角形折疊［4－13］，這兩種方法不需要對折疊區(qū)域重新三角化，具有更好的穩(wěn)定性且簡化速度快。Garland等［4］用局部二次誤差度量（Quadric Error Metric，QEM）來衡量邊折疊的代價，該方法計算簡單且運行速度較快，故在模型簡化領(lǐng)域被廣泛運用，但該算法容易形成誤差累積，且沒有考慮網(wǎng)格的細節(jié)特征，在簡化網(wǎng)格的同時也會丟失網(wǎng)格的幾何特征。劉曉利等［5］簡單地引入了頂點的尖特征度，并對Garland的方法進行了改進，該方法較好地保留了網(wǎng)格特征，但尖特征度的取法過于簡單，而且閾值和懲罰系數(shù)需要預(yù)先根據(jù)經(jīng)驗設(shè)定。Zhou等［6］將點的曲率和邊長的乘積定義為誤差準則，該方法有效地保持了拓撲結(jié)構(gòu)，但簡化過程中忽略了網(wǎng)格的質(zhì)量和邊界的影響。易兵等［7］將張量投票理論與二次誤差結(jié)合，該方法能較好地保留模型的整體特征和細節(jié)特征，但對由尖銳特征和平坦區(qū)域組成的模型進行簡化時效果不是很明顯。

除了邊折疊方法外，三角形折疊作為邊折疊算法的延續(xù)，由于其簡化速度比邊折疊算法更快而得到了更加廣泛的應(yīng)用。Hamann［8］和 Gieng［9］先后提出兩種類似的基于三角形折疊的網(wǎng)格簡化算法，這兩種算法能較好地保持外形，但具有復(fù)雜度較高、誤差的衡量標準缺乏有效性等不足。Pan等［10］將三角形折疊與QEM算法結(jié)合起來，給出了一種傳遞簡化誤差的方法，該方法速度快、效果較好，但三角形簡化時新頂點的位置不確定，同時忽略了三角形個體形狀、面積等因素，從而導致局部區(qū)域過度簡化和狹長三角形的產(chǎn)生。周元峰等［11］對Pan的方法進行修改，提出了體積平方度量下的簡化方法，該方法對重要特征區(qū)域的保留效果不佳。此外，Chen等［12］對QEM算法進行了改進，各三角形折疊誤差的閾值采用平均誤差確定，生成的簡化網(wǎng)格的質(zhì)量較好，但簡化網(wǎng)格比較均勻，特別是在低分辨率的情況下，往往會丟失網(wǎng)格的幾何特征。劉湘云等［13］提出一種基于概率值簡化三角網(wǎng)格模型的算法，加快了簡化速度，但卻存在分段區(qū)間不唯一的問題。

針對上述算法的不足，本文提出一種根據(jù)頂點投影確定三角形的折疊點，并控制三角形折疊后所產(chǎn)生的體積誤差、三角形法向量的角度誤差和三角形面積的方法。該方法不僅有效地保持了模型特征，還將模型簡化產(chǎn)生的誤差控制在一定范圍內(nèi)。

1 方法描述

采用三角形折疊簡化三角網(wǎng)格模型時，如何確定三角形的折疊點和三角形的折疊順序等問題，決定了簡化后能否得到較優(yōu)的簡化模型。為敘述方便，首先引入一些基本概念。

1．1 基本概念

頂點vi的一階鄰域三角形（First Order Triangle，F(xiàn)OT）是指與頂點vi直接相鄰的三角形。頂點vi的所有一階鄰域三角形的集合記為｛FOT｝vi。如圖1所示，｛FOT｝v0＝｛T1，T2，T3，T4，T5｝。

三角形Ti的一階鄰域三角形是指三角形Ti各頂點的一階鄰域三角形，但不包括Ti本身。三角形Ti的所有一階鄰域三角形的集合記為｛FOT｝Ti。如圖1所示，｛FOT｝T2＝ ｛T1，T3，T4，…，T9，T10｝。

1．2 折疊點的確定

本文進行簡化的基本操作是三角形折疊。如圖2所示，圖2a中三角形Ti＝ （vi1，vi2，vi3）執(zhí)行折疊操作后，簡化為圖2b中的情形，即三角形Ti的三個頂點vi1，vi2和vi3折疊為一個頂點vi0?？刂普郫B點vi0的位置可以較好地保持原始模型的幾何特征，如何確定折疊點vi0成為本文研究的重點。

本文充分利用三角形的一階鄰域信息，通過頂點在三角形的一階鄰域三角形中的投影確定折疊點的位置，從而簡化網(wǎng)格模型。該方法避免了投影面的復(fù)雜計算過程，所涉及的一階鄰域三角形個數(shù)也不多，可以快速定位，大大縮短了處理時間，此外，還很好地增強了局部特征。以圖2為例，當折疊三角形Ti時，對于折疊點vi0的確定本文采用如下方案：首先，利用式（1）計算頂點vi1在折疊點vi0中的分量值v′i1，式（1）表示了v′i1的計算方法，分量值v′i2和v′i3的計算方法與此相同；其次，根據(jù)式（2）計算三角形Ti的折疊點vi0。

式（1）中：PTj表示頂點vi1在三角形Tj（三角形Ti的一階鄰域三角形集合中的元素）所在平面的投影點，STj表示三角形Tj的面積，λ1和λ2分別表示投影點和頂點vi1的影響系數(shù)，λ1和λ2的取值范圍為0～1．0，且λ1＋λ2＝1。本文中λ1和λ2的取值由大量實驗分析得到，實驗表明兩者的取值對簡化模型的影響類似于圖3所列的模型，實驗中均方根誤差值（Root Mean Square Error，RMSE）由 Metro［14］測量得到，實驗還表明λ1和λ2取0．4～0．6時，簡化模型的誤差相對較小。在本文所有實驗中，λ1＝0．6，λ2＝0．4。

與計算v′i1的方法一樣，分別計算頂點vi2和vi3在折疊點vi0中所對應(yīng)的分量值v′i2和v′i3。最后，采用式（2）計算三角形Ti的折疊點vi0。

式中：γ1，γ2和γ3分別表示頂點vi1，vi2和vi3的重要度，

式（3）中：m為頂點vi1的一階鄰域三角形的總數(shù)，n表示三角形Ti的法向量，nj（j＝1，2，…，m）表示頂點vi1的各一階鄰域三角形的法向量。如圖2a所示，｜nj－n｜的長度越大，則該一階鄰域三角形相對于三角形Ti的變化就越明顯。γ2和γ3的計算方法與γ1相同。

1．3 折疊順序的確定

根據(jù)上述確定折疊點的方法計算出三角網(wǎng)格模型中各三角形的折疊點后，由各三角形的折疊點可以計算折疊后其一階鄰域三角形的最大面積、法向量的角度誤差和簡化模型與初始模型間的體積誤差。在本文提出的方法中，因為計算三角形的最大面積和法向量的角度誤差是為了確定體積誤差，所以采用以體積誤差控制為主、以三角形的最大面積和法向量的角度誤差控制為輔的策略，來確定三角形的折疊順序。

1．3．1 體積誤差

體積誤差是在某一三角形折疊后，簡化模型與初始模型間的體積變化值。通過體積誤差可以有效控制原始模型的體積變化，使得簡化模型從幾何尺寸方面盡可能逼近原始模型。如圖4所示，三角形Ti折疊為點vi0時，產(chǎn)生的體積誤差Vi表示以vi0為頂點、以三角形Ti及其一階鄰域三角形為底面的所有四面體的體積之和，

式中：vi0表示三角形Ti的折疊點，折疊點vi0的坐標記為（xi，yi，zi，1），設(shè)三角形Tj所在的平面方程為ajx＋bjy＋cjz＋dj＝0，其中aj2＋bj2＋cj2＝1，令PTj＝ （aj，bj，cj，dj），STj表示三角形Tj的面積。

式（4）是一個帶符號的體積計算式，其正負情況反映了簡化模型相對于初始模型的凹凸情況。簡化后，網(wǎng)格模型的體積誤差可能出現(xiàn)一部分為正、一部分為負，甚至網(wǎng)格模型有變化但體積誤差為零的情形，因此具有無法準確地度量簡化模型體積變化的缺陷。本文采用平方體積累加的方法計算體積誤差，可避免上述現(xiàn)象的發(fā)生，計算方法如下：

1．3．2 最大面積

最大面積是指某一三角形折疊后，發(fā)生變形的一階鄰域三角形中最大三角形的面積。確定三角形折疊順序時之所以考慮最大面積值，是因為模型中可能存在的局部平緩區(qū)域被折疊后會產(chǎn)生過小誤差，從而很容易出現(xiàn)過度簡化現(xiàn)象，導致該區(qū)域產(chǎn)生過大三角形。通過限制最大面積，可將簡化模型中各三角形的面積控制在一定范圍內(nèi)，因而很好地解決了上述問題。如圖4所示，三角形Ti折疊為點vi0時，產(chǎn)生的最大面積Si采用式（6）表示。

式中：S′i1，S′i2，S′i3，…，S′in分別表示三角形Ti的各一階鄰域三角形在Ti折疊后的面積。

1．3．3 角度誤差

某一三角形折疊后其一階鄰域三角形的形狀和位置會發(fā)生變化，如圖4所示，三角形Ti折疊為點vi0時，Ti的一階鄰域三角形 Δvi1vi4vi5，Δvi2vi5vi6，Δvi2vi6vi7，Δvi3vi7vi8，Δvi3vi8vi9，Δvi1vi9vi4變化為Δvi0vi4vi5，Δvi0vi5vi6，Δvi0vi6vi7，Δvi0vi7vi8，Δvi0vi8vi9，Δvi0vi9vi4。三角形Ti折疊后其一階鄰域三角形的法向量所發(fā)生的最大角度變化值稱為角度誤差，記為αi，

式中：ni0，ni1，…，nin表示三角形Ti折疊前其一階鄰域三角形的單位法向量，n′i0，n′i1，…，n′in表示三角形Ti折疊后其一階鄰域三角形的單位法向量。對角度誤差的有效控制可避免模型簡化時出現(xiàn)三角形的旋轉(zhuǎn)角度過大甚至翻轉(zhuǎn)的現(xiàn)象。

1．4 方法的基本步驟

本文提出的基于三角形折疊的網(wǎng)格簡化方法步驟如下：

輸入：原始模型中三角形數(shù)量為M，期望的簡化模型中的三角形數(shù)量為N。簡化時，體積誤差閾值為V0、最大面積閾值為s0、角度誤差閾值為α0。

步驟1 對于原始網(wǎng)格中的每一個三角形Ti，根據(jù)式（2）計算其折疊點vi0。

步驟2 根據(jù)每一個三角形Ti的折疊點vi0，采用式（5）～式（7）計算折疊后產(chǎn)生的體積誤差Vi、最大面積值si以及角度誤差αi。

步驟3 按照體積誤差由小到大將三角形順序加入誤差堆中。

步驟4 取出堆頂三角形，若Vi＜V0，si＜s0，αi＜α0，則折疊該三角形，刪除堆中該三角形及其一階鄰域三角形，并重新計算被折疊三角形的一階鄰域三角形的折疊點和折疊誤差，按照體積誤差大小將各三角形順序插入堆中，轉(zhuǎn)步驟6；若Vi＜V0，而si，αi中有一個或兩個不滿足條件，則不處理該三角形，轉(zhuǎn)步驟5；若Vi＞V0，則結(jié)束簡化操作。

步驟5 依次取出堆中的三角形，對各三角形進行判斷，若當前三角形滿足條件，則折疊該三角形，刪除堆中該三角形及其一階鄰域三角形，并重新計算被折疊三角形的一階鄰域三角形的折疊點和折疊誤差，按照體積誤差的大小將各三角形順序插入堆中，轉(zhuǎn)步驟6；若堆中無滿足條件的三角形時，則結(jié)束簡化操作。

步驟6 重復(fù)步驟4，直至當前三角形的體積誤差大于V0或簡化達到用戶要求時，簡化操作結(jié)束。

根據(jù)上述簡化步驟，基于三角形折疊的網(wǎng)格簡化流程如圖5所示。

2 實驗結(jié)果與討論

在Visual C＋＋60的環(huán)境下實現(xiàn)該方法，在2．53GHz Intel（R）Core（TM）i3CPU、1．92GB內(nèi)存的PC上運行該程序，并采用不同的模型來驗證該方法。如表1所示，原始球模型（包含189 298個三角形）的體積為4 060．775 5mm3，采用體積誤差控制簡化95%時，簡化球模型的體積為4 062．484 4 mm3，體積變化為0．042 1%；而當不采用體積誤差控制簡化95%時，簡化球模型的體積為4 084．501 0 mm3，體積變化為0．580 9%。此外，從視覺效果上看，無體積誤差控制的簡化模型遠不及采用體積誤差控制的簡化模型。

法向量角度誤差控制對簡化模型的影響如圖6所示。圖6a為皮帶輪的原始模型（包含772331個三角形），圖6b為采用法向量角度誤差控制簡化95%時所得的簡化模型，圖6c為不采用法向量角度誤差控制簡化95%時所得的簡化模型，模型特征區(qū)域因大量三角形旋轉(zhuǎn)過大而造成表面不光滑，且平面處也有許多因三角形過度旋轉(zhuǎn)而產(chǎn)生的瑕疵，嚴重影響了視覺效果。

表1 體積誤差控制對球模型簡化的影響

如圖7和圖8所示，將本文的簡化模型與文獻［6］中描述的基于QEM的三角形折疊簡化方法得到的模型進行比較，從簡化模型的網(wǎng)格質(zhì)量進行評價，發(fā)現(xiàn)采用文獻［6］的方法簡化得到的輪轂簡化模型因部分三角形旋轉(zhuǎn)過大而產(chǎn)生嚴重缺陷，如圖7c所示。采用文獻［6］的方法簡化90%時得到的茶壺簡化模型產(chǎn)生了三角形冗余的現(xiàn)象，如圖8c所示。而采用本文的簡化方法得到的簡化模型沒有出現(xiàn)上述兩種情形，如圖7b和圖8b所示。實例中輪轂?zāi)Ｐ筒捎帽疚姆椒ê喕瘯r，各閾值設(shè)定為V0＝5 mm3，s0＝12mm2，α0＝7°；茶壺模型簡化時，各閾值設(shè)定為V0＝8mm3，s0＝15mm2，α0＝5°。大量實驗表明：體積誤差閾值設(shè)置在5～10mm3，最大面積閾值設(shè)置在10～20mm2，角度誤差閾值設(shè)置在5～10°可取得較好的簡化效果，也能夠滿足各個簡化比例的要求。

如圖9所示，通過采用Metro對圖7和圖8所示的簡化模型進行幾何相似度分析，結(jié)果發(fā)現(xiàn)兩種方法所得簡化模型的RMSE值比較接近，但本文提出的簡化方法略優(yōu)于文獻［6］的簡化方法。

如圖10所示，通過對Garland提供的實驗?zāi)Ｐ停?］分別采用本文的方法（V0＝8mm3，s0＝20 mm2，α0＝8°）和文獻［6］及文獻［11］的方法進行比較，cow的原始模型（包含5804個三角形）分別經(jīng)三種方法簡化80%后，從包含特征較多的cow的頭部對特征的保持效果分析，文獻［6］的方法遠遠不如本文所提出的簡化方法，如圖10b和圖10c所示，而文獻［11］的方法主要考慮了模型特征的保持和網(wǎng)格質(zhì)量的優(yōu)化，但它對特征的保持效果與本文的特征保持效果相比還有待改進，如圖10d所示。

此外，從本文所提方法的時間復(fù)雜度上分析。由于該方法要處理含有大量三角形的網(wǎng)格模型，設(shè)計合理的數(shù)據(jù)結(jié)構(gòu)不僅使該方法能處理數(shù)據(jù)量大的模型，而且還具有較快的速度。本方法用到的數(shù)據(jù)結(jié)構(gòu)包括頂點表、三角形表和每個頂點的一階鄰域三角形表。在頂點表中記錄了每個頂點的坐標；在三角形表中記錄了構(gòu)成該三角形的三個頂點的ID號、該三角形折疊點的坐標和該三角形的三個折疊誤差值；在每個頂點的一階鄰域三角形表中，記錄了構(gòu)成該頂點的各一階鄰域三角形的ID號。分析時間時，首先假設(shè)輸入模型M包含n個三角形，目標簡化模型M′包含m個三角形，一次迭代中移除三角形的數(shù)目限定為常數(shù)k，最大的頂點的度限定為常數(shù)p。其次將方法簡單的劃分為兩個階段，第一階段為初始化階段，包括每個三角形折疊點的計算、折疊誤差的計算和對三角形進行堆排序；第二階段為迭代的折疊簡化。在初始化階段，因為計算所有三角形折疊點的時間復(fù)雜度為O（n），所有三角形折疊誤差的時間復(fù)雜度為O（n），對所有三角形進行堆排序的時間復(fù)雜度為O（nlogn），所以初始化的時間復(fù)雜度為O（nlogn）。又因為簡化階段第i次迭代的時間復(fù)雜度為O（log（n－ki）），所以簡化階段總的時間復(fù)雜度為：

logn＋log（n－k）＋log（n－2k）＋log（n－3k）＋…＋logm＜logn?。璴ogm！＝O（nlogn－mlogm）。

綜上可知，本文所提方法的時間復(fù)雜度為O（nlogn），與 文 獻 ［6］中 方法的時間復(fù)雜度（O（nlogn））一致，不同模型分別采用本文和文獻［6］的方法簡化時，具體運行時間如表2所示，雖然兩者的時間復(fù)雜度都為O（nlogn），但由于兩種方法所采用的誤差準則的差異，造成實際的運行時間存在微小的差異，但相比本文簡化后網(wǎng)格的質(zhì)量和特征保持的效果來說，這些時間的開銷是值得的，另外，本文的方法還與文獻［11］進行了時間對比，可以看出，本文所提出的方法在時間上也優(yōu)于文獻［11］。

表2 采用本文方法簡化三角網(wǎng)格模型的運行時間

3 結(jié)束語

本文通過運用頂點投影法確定了三角形折疊點的空間位置，不但計算量小，而且考慮了三角形本身及其鄰域?qū)φ郫B點的影響，同時由折疊點的位置預(yù)算折疊時所產(chǎn)生的相關(guān)幾何誤差，可確定網(wǎng)格模型簡化時的折疊順序。大量實驗結(jié)果表明，本文提出的新簡化方法在降低簡化誤差的同時還有效保持了原始模型的特征，獲得了高質(zhì)量的簡化模型，但在誤差允許的范圍內(nèi)，如何自適應(yīng)地設(shè)定最優(yōu)誤差控制閾值以滿足用戶指定的簡化比例，還有待進一步研究。

［1］ WILLIAM J S，JONATHAN A Z，WILLIAM E L．Decimation of triangle meshes［J］．Computer Graphics，1992，26（2）：65－70．

［2］ KALVIN A D，TAYLOR R H．Superfaces：Polygonal mesh simplification with bounded error［J］．IEEE Computer Graphics and Application，1996，16（3）：64－77．

［3］ TURK G．Retiling polygonal surfaces［J］．Computer Graphics，1992，26（2）：55－64．

［4］ GARLAND M，HECKBERT P S．Surface simplification using quadric error metrics［C］//Proceedings of the SIGGRAPH’97．Los Angeles，Cal．，USA：Computer Graphics，1997：209－216．

［5］ LIU Xiaoli，LIU Zeyi，GAO Pengdong，et al．Edge collapse simplification based on sharp degree［J］．Journal of Software，2005，16（5）：669－675（in Chinese）．［劉曉利，劉則毅，高鵬東，等．基于尖特征度的邊折疊簡化算法［J］．軟件學報，2005，16（5）：669－675．］

［6］ ZHOU Mingdong，MICHAEL Y W．Engineered model simplification for simulation based structural design［J］．Computer－Aided Design and Applications，2012，9（1）：87－94．

［7］ YI Bing，LIU Zhenyu，TAN Jianrong．New quadric metric for simplifying meshes to retain the feature edge［J］．Journal of Computer－Aided Design ＆ Computer Graphics，2012，24（4）：427－434（in Chinese）．［易 兵，劉振宇，譚建榮．邊界特征保持的網(wǎng)格模型分級二次誤差簡化算法［J］．計算機輔助設(shè)計與圖形學學報，2012，24（4）：427－434．］

［8］ HAMANN B．A data reduction scheme for triangulated surface［J］．Computer Aided Geometric Design，1994，11（2）：197－214．

［9］ GIENG T S，HAMANN B，JOY K I．Smooth hierarchical surface triangulations［C］//Proceedings IEEE Visualization 1997．Washington，D．C．，USA：IEEE，1997：379－386．

［10］ PAN Zhigeng，ZHOU Kun，SHI Jiaoying．A new mesh simplification algorithm based on triangle collapses［J］．Journal of Computer Science and Technology，2001，16（1）：57－63．

［11］ ZHOU Yuanfeng，ZHANG Caiming，HE Ping．Feature preserving mesh simplification algorithm based on square volume measure［J］．Chinese Journal of Computers，2009，32（2）：203－212（in Chinese）．［周元峰，張彩明，賀 平．體積平方度量下的特征保持網(wǎng)格簡化方法［J］．計算機學報，2009，32（2）：203－212．］

［12］ CHEN Jun，SHI Xiong．Real－time LOD algorithm based on triangle collapse optimization［C］//Proceedings of the 7th International Conference on Computational Intelligence and Security．Washington，D．C．，USA：IEEE，2011：312－315．

［13］ LIU Xiangyun，ZOU Beiji．A new algorithm for simplying triangle mesh model based on probability［J］．Journal of Central South University：Science and Technology，2005，36（1）：123－127（in Chinese）．［劉湘云，鄒北驥．一種依概率值簡化三角網(wǎng)格模型的新算法［J］．中南大學學報：自然科學版，2005，36（1）：123－127．］

［14］ CIGNONI P，ROCCHINI C，SCOPIGNO R．Metro：measuring error on simplified surfaces［J］．Computer Graphics Forum，1998，17（2）：167－174．