基于曲率和面積的二次誤差測度網格簡化算法

郝娟兒，唐莉萍，曾培峰

（東華大學a.信息科學與技術學院；b.計算機科學與技術學院，上海 201620）

基于曲率和面積的二次誤差測度網格簡化算法

郝娟兒a，唐莉萍a，曾培峰b

（東華大學a.信息科學與技術學院；b.計算機科學與技術學院，上海 201620）

在經典的二次誤差測度（QEM）簡化算法基礎上，將離散曲率和面積引入到邊收縮代價計算中，提出了一種基于離散曲率和面積的二次誤差測度網格簡化改進算法.該算法既考慮了離散曲面在各頂點附近的彎曲程度，又考慮了曲面的幾何形狀特征.為保留模型的原始邊界特征，規定不對其邊界進行簡化.試驗結果表明，改進算法在網格簡化過程中保持了原有算法運行速度快的優點，且簡化模型能合理地分配網格，并更好地保持了原始模型的重要特征.

網格簡化；邊收縮；二次誤差測度；離散曲率

目前在計算機圖形學和幾何造型中，三維物體模型的表面通常以三角網格的形式表示.對于大規模的物體模型，為刻畫出物體的表面細節特征，相應的三維模型往往需要數量相當龐大的三角網格構建得到.巨大的數據量給計算機的處理和存儲、網絡數據傳輸以及實時顯示都會帶來很大的困難，因此，有必要對三角網格模型進行簡化.

三角網格簡化的目的是在保持原始三維模型重要幾何特征的前提下，通過一定的規則減少三維物體模型表面的三角網格.現有的網格簡化算法［1］有頂點刪除算法、頂點聚類算法、重新三角化網格算法、區域合并算法和邊收縮算法等.其中，邊收縮算法是近年網格簡化算法研究中非常重要的一類算法，由 HOPPE［2］首先提出，通過對一個全局能量函數進行優化控制實現簡化過程.該算法是一個非線性優化過程，需要的數據量大，計算過于復雜，運行速度慢.1997年，GARLAND等［3］提出了二次誤差測度（quadric error metrics，QEM）算法，其以新頂點到與被收縮邊的兩個頂點相關聯的平面的距離平方和作為誤差測度，用局部二次誤差測度計算邊收縮代價，這種方法相對簡單、運行速度快，且充分考慮了模型的幾何相似性，能保持較高的模型整體相似度，但其沒有考慮模型的細節特征，產生的簡化網格是均勻的，經大規模簡化后會出現模型表面的重要幾何特征丟失的現象，進而引起細節部分的失真.為保持模型關鍵特征，文獻［4－6］提出采用兩個頂點的法向量間夾角判定關鍵特征，以此提高簡化模型的視覺效果.文獻［7］通過采用視覺重要度和幾何誤差建立一個簡化代價函數來指導簡化，但其數學含義不清晰，實際簡化效果無法確定.

本文通過對已有方法的研究和分析，結合模型特征提出一種基于離散曲率和網格面積的QEM改進算法.將三角網格模型頂點的離散曲率引入到二次誤差測度的計算中，對曲率變化較大的區域增加誤差測度值，推遲其邊收縮順序，在簡化過程中使模型的重要幾何特征得以保留.同時，將三角網格面積也作為二次誤差測度計算的權值，以保證簡化生成的新三角網格的質量.

1 QEM算法研究及分析

QEM算法的基本思想是用二次誤差測度描述簡化誤差，通過對模型原始邊界內部每個頂點計算相應的誤差測度矩陣，得到每條邊的邊收縮代價，每次簡化都選擇收縮代價最小的邊進行操作，直至達到預期的簡化要求.

1.1 邊收縮操作

對邊 （v1，v2）進行邊收縮操作，記為 （v1，v2）→，如圖1所示.將一條邊（v1，v2）簡化為一個頂點，其收縮操作過程如下：

（1）去除原始網格中所有與頂點v1和頂點v2相關聯的三角網格；

（2）將頂點v1和v2移至新的位置；

（3）將與頂點v1和v2相關的邊和三角網格的信息添加到頂點的信息中.

重復以上邊收縮過程，直到簡化模型中的三角網格達到預期的數量或一定的簡化比例要求.從圖1可以看出，一般情況下進行一次邊收縮操作可以減少1個頂點、2個三角形和3條邊.

圖1 邊收縮操作Fig.1 Edge collapse

1.2 二次誤差測度

模型簡化的重點在于選取合適的邊進行收縮，使得邊收縮最小程度地影響模型的視覺效果.一條邊的收縮與否是通過評價這條邊收縮后對模型所帶來的誤差的大小，即收縮代價決定的.每次收縮都選取收縮代價最小的邊操作，這樣得到的簡化模型與原始模型的誤差最小.

文獻［3］算法在將三角網格中的兩個頂點收縮為一個新頂點時，首先計算它的二次誤差測度，即計算該頂點到與原始網格中被收縮的兩個頂點相關聯的三角網格間距離的平方和，并據此求解方程得到新頂點的坐標位置.

三維空間坐標系中的平面可以用方程ax＋by＋cz＋d＝0（a2＋b2＋c2＝1）表示，根據平面方程的系數，可將平面簡記為p＝［a，b，c，d］T.設v為網格上的一個頂點，其坐標記為［vxvyvz1］T，P（v）表示與頂點v相關聯的三角網格的集合，p為P（v）中的一個三角網格，用p∈P（v）表示.那么，任意一個頂點到三角網格集合P（v）中各三角網格距離的平方之和為

定義頂點v的二次誤差測度矩陣［3］為

對于邊 （vi，vj）收縮為新頂點，將收縮代價定義為并用Q′i＋Q′j來表示新頂點的二次誤差測度矩陣［3］.

2 QEM改進算法

曲率可以描述三角網格模型的重要局部特征.網格模型中的拐點、折痕、尖銳邊等關鍵特征區域內的網格曲率較大，平坦區域曲率較小.因此，本文將曲率引入頂點的二次誤差測度矩陣中，進而影響與該頂點相關聯的各個邊的收縮代價值.在對原始模型進行簡化時，本文選擇推遲曲率較大區域的收縮順序，保證邊收縮操作主要往曲率較小的方向進行，使得模型的關鍵特征得以保留.同時將三角網格的面積引入二次誤差測度矩陣中，在曲率相同的情況下，優先保留面積較大的頂點，提高三角網格模型質量.這樣簡化模型能夠依照曲率的變化合理地分配網格數量，在彎曲程度較大的區域使網格分布稠密，在平坦區域使網格分布稀疏，可更加有效地保持較多的關鍵細節特征，在視覺效果上與原始模型相近.

2.1 離散法向量和曲率估計

2.1.1 法向量和曲率

在微分曲面中，曲面的法向量是曲面的一階微分量，曲面的曲率是曲面的二階微分量.作為曲面信息的重要度量指標，曲面的法向量和曲率可以量化地表示三角網格模型表面的細節特征信息，如邊界、折痕、拐點和尖銳邊等彎曲程度較大區域的特征.

三維空間中三角網格模型是由邊和頂點相連接而成的分段線性曲面，沒有確切的解析表示，無法用傳統的曲面解析方法計算.它是一種離散的曲面表示形式，沒有連續的法向量和曲率.對于該網格曲面，通常通過計算其頂點處的離散法向量和離散曲率作為曲面在頂點處彎曲程度的近似［8］.

三角網格的數據分析需要存儲兩種數據結構：一種是頂點數據結構，存儲網格中各頂點的坐標；另一種是三角網格數據結構，存儲指向組成每個三角網格的頂點數據的頂點索引數據.基于后者可以計算得到離散法向量和曲率.

2.1.2 離散法向量

假設一個三角網格的3個頂點分別為vj－1，v，vj，那么該網格的單位法向量為

遍歷三角網格數據結構，用式（3）得到所有三角網格的單位法向量.然后根據各三角網格的單位法向量估算各個頂點的法向量.頂點法向量通過對與該頂點相關聯的所有三角網格的法向量進行加權平均得到.考慮與頂點相關聯的各個三角網格面積對頂點法向量結果的影響，本文將各三角網格的面積也作為估算頂點法向量時的權值.若一個頂點為v，與它相關聯三角網格數量為m，記m為頂點v的維度，則頂點v的單位法向量為

其中：Sj表示第j個三角網格的面積.

這樣，可得到三角網格模型中每個頂點的單位法向量，并作為頂點的屬性和頂點坐標一起存入三角網格數據結構中.

2.1.3 離散曲率

對于三角網格模型的每個頂點，離散曲面在頂點處沿不同的方向彎曲程度不同.因此，刻畫曲面在某一個點附近的彎曲程度，可以用曲面上經過該點的不同曲線的曲率進行評價.

利用式（5）得到和頂點v相鄰的各個邊方向的離散曲率.根據曲率的大小，可以判斷網格模型的關鍵特征.

2.2 邊收縮后的頂點

本文網格簡化的基本操作為半邊收縮.半邊收縮操作不生成新的頂點，收縮后的頂點為原兩個頂點中的一個，即簡化模型中的頂點是原始模型的一個子集.一條邊的兩個頂點保留哪個需通過比較這條邊兩個頂點的收縮代價大小確定.這樣既能減少計算新頂點的時間開銷，又可以節省存儲新頂點的空間開銷.

2.3 曲率面積加權誤差測度

根據計算得到與每個頂點關聯的各邊的離散曲率和相鄰三角網格的面積，結合QEM算法的原理，求出每個頂點曲率面積加權的二次誤差測度矩陣，并用計算得到的邊收縮代價指導簡化過程中的半邊收縮順序.模型中曲率較大的頂點構成重要特征相關的邊，這些邊加權之后相應的邊收縮代價較大，在邊收縮隊列中的順序就靠后.由于推遲了與重要特征相關的三角網格的收縮，模型的重要特征得以保留.

2.4 邊界的處理

在原始網格模型內部，由兩個頂點組成的邊被兩個三角面共享.如果網格中一條邊只有一個三角面與它相關聯，那么這條邊就為模型的邊界，與它對應的頂點稱為邊界點.對于有邊界的模型，在簡化過程應該盡可能保持其邊界特征.為保證邊界在簡化中不被退化，在簡化過程中對于原始網格中的邊界點應予以保留.在本文算法的程序實現過程中，通過為邊界點設置一個非常大的誤差測度權值，使邊界邊的收縮代價處于優先隊列的最后，保證不被收縮.這種處理方法簡單有效，能夠很好保留模型的邊界特征.

2.5 改進QEM算法流程

（1）讀入初始網格模型的頂點、三角網格數據.

（2）計算網格中每個頂點的離散法向量nv.根據每個頂點的離散法向量，計算出與頂點相鄰各邊的離散曲率Cj，并結合頂點各相鄰三角網格的面積Sj和三角網格對應矩陣Kpj，計算出網格中頂點的二次誤差測度矩陣為表述方便，記Sj×Cj，為第i個頂點的權重.

（3）根據網格中各頂點的二次誤差測度矩陣，計算每一條邊的收縮代價c，并將其放入優先隊列中.若 （v1，v2）→，其收縮代價為

（4）從優先隊列中取出收縮代價最小的邊進行邊收縮操作，刪除該邊及與該邊相關的三角網格，更新受影響區域點的鄰域，并計算新的邊收縮代價，然后更新優先隊列.

（5）重復上述過程，直到達到簡化要求.

3 試驗結果

應用本算法在VC＋＋6.0環境對來源于Internet的三維網格模型進行簡化試驗，然后將算法得到的簡化結果與文獻［3］算法結果進行比較.

圖2所示為對包含4 952個三角面和2 504個頂點的原始網格模型分別使用文獻［3］算法和本文算法，將其簡化為僅包含1 000個三角面的簡化模型.從圖2可以看出，本文算法得到的簡化模型，對于額頭和臉等平坦區域，使用的三角網格數量相對較少，而對于眼睛、鼻子、嘴巴等細節特征明顯的區域，使用的三角網格數量相對較多.

眼睛和嘴部是人體頭部模型的最重要特征，圖3和4所示分別為將模型簡化至2 000個三角網格時，對模型的右眼和嘴部這兩個重要特征區域分別采用文獻［3］算法和本文算法得到的簡化結果.從圖3和4可以看出，與文獻［3］算法相比，使用本文算法得到的簡化模型，在眼角和嘴角這些重要特征區域內，保留更多的三角網格，能更好地保持模型的重要幾何特征.

4 結 語

本文在二次誤差測度算法的基礎上，通過引入離散曲率和三角形面積作為權值計算頂點的二次誤差測度矩陣，得到相應的邊收縮代價，指導邊收縮順序.算法較好地保持了網格簡化過程中原始模型的重要幾何特征，使得最終的簡化模型能夠依照曲率的變化合理地分配網格數量，在彎曲程度較大的區域網格分布稠密，在平坦區域網格分布稀疏，因而有效地保持了較多的模型關鍵特征，在視覺效果上也與原始模型相近.

［1］HECKBERT P，GARLAND M.Survey of polygonal surface simplification algorithms ［R］. Multiresolution Surface Modeling Course SIGGRAPH'97，PA 15213.Pittsburgh：School of Computer Science，Carnegie Mellon University.1997.

［2］HOPPE H.Progressive meshes［C］//Proceedings of the 23rd Annual Conference on Computer Graphics and Interactive Techniques. New Orleans： Association for computing Machinery Press ACM Press，1996：99－108.

［3］GARLAND M，HECKBERT P.Surface simplification using quadric error metrics ［C］//Proceedings of the 24th Annual Conference on Computer Graphics and Interactive Techniques.Los Angeles：Association for computing Machinery Press，1997：209－216.

［4］周石琳，湯曉安，陳敏，等.基于多邊形頂點法矢量的網格模型簡化算法［J］.中國圖象圖形學報，2002，7（6）：601－605.

［5］CHEN B，NISHITA T.An efficient mesh simplification method with feature detection for unstructured meshes and web graphics［C］//Proceedings of IEEE Computer Graphics International 2003.Los Alamitos：IEEE Computer Society Press，2003：34－41.

［6］LU G，XU P，WEN X.Triangular mesh simplification algorithm based on vector angle［J］.Journal of Engineering Design，2005，4（2）：124－128.

［7］HUSSAIN M，OKADA Y，NIIJIMA K.Efficient and feature preserving triangular mesh decimation［J］.Journal of WSCG，2004，12（1/2/3）：167－174.

［8］LEE Y，MARSHALL D.Curvature based normalized 3D component facial image recognition using fuzzy integral［J］.Applied Mathematics and Computation，2008，205（2）：815－823.

［9］TAUBIN G.Estimating the tensor of curvature of a surface from a polyhedral approximation［C］//Proceedings of the 5th International Conference on Computer Vision.Los Alamitos：IEEE Computer Society Press，1995：902－907.

A Simplification Algorithm for Curvature and Area－Weighted Quadric Error Metrics Mesh

HAO Juan－era，TANG Li－pinga，ZENG Pei－fengb
（a.College of Information Science and Technology；b.College of Computer Science and Technology，Donghua University，Shanghai 201620，China）

Based on quadric error metrics（QEM），an improved mesh simplification algorithm is proposed.Discrete curvature and triangular area are used in the collapse cost calculation.Both curvature near vertices and surface geometric features are considered in the simplification computation.Meanwhile，edges of the mesh are not collapsed in order to reserve the feature of the object's boundary.The experimental result demonstrates that the proposed algorithm has the same efficiency comparing to the original algorithm，and meshes are distributed evenly in the simplification model，also important features of object are preserved.

mesh simplification；edge collapse；quadric error metrics；discrete curvature

TP 391

A

2011－05－25

郝娟兒（1986—），女，山西運城人，碩士，研究方向為圖形與圖像處理.E－mail：haojuan108＠126.com

唐莉萍（聯系人），女，副教授，E－mail：tanglp419＠gmail.com

1671－0444（2012）03－0318－05