一種改進的二次誤差測度簡化算法①

張文新，溫佩芝，黃 佳，朱立坤，邵其林

（桂林電子科技大學 計算機科學與工程學院，廣西 桂林 541004）

在計算機圖形學、三維動漫、反求工程等應(yīng)用中，三維幾何數(shù)字化模型通常用多邊形網(wǎng)格表示［1］。由于三角網(wǎng)格模型數(shù)學表示簡單，通用性和靈活性較好，得到了廣泛的應(yīng)用［2－3］。隨著三維激光掃描技術(shù)的發(fā)展，所獲得的三維數(shù)字化模型越來越精細、數(shù)據(jù)量越來越大，這些三維數(shù)字模型往往需要數(shù)百萬的三角面片才能準確表達物體的細節(jié)特征。如果將這些模型通過互聯(lián)網(wǎng)傳輸或在Web環(huán)境中展示，將是一個極具挑戰(zhàn)性的難題，因而成為計算機應(yīng)用及互聯(lián)網(wǎng)領(lǐng)域的研究熱點。在計算機處理速度和網(wǎng)絡(luò)帶寬有限的情況下，在Web中進行高分辨率的三維數(shù)字模型展示是不現(xiàn)實的，因此，對復(fù)雜度高的三維數(shù)字化模型進行簡化是Web3D展示最關(guān)鍵的技術(shù)。網(wǎng)格模型簡化的目的是將多邊形網(wǎng)格模型用一個近似模型表示，同時要盡可能保留原始模型的特征，包括幾何特征和視覺特征，但模型的數(shù)據(jù)量要遠小于原始模型。近年來，國內(nèi)外很多學者對網(wǎng)格模型簡化做了大量研究，提出了一系列簡化算法，如頂點刪除算法［4］、網(wǎng)格重新劃分算法［5］、邊折疊算法［6］、區(qū)域合并算法［7］、小波變換算法［8］、包絡(luò)網(wǎng)格算法［9］等。其中，邊折疊作為最重要的簡化算法之一，在幾何數(shù)字化網(wǎng)格模型簡化算法研究方面得到了廣泛應(yīng)用。

邊折疊算法由Hoppe［6］在1993年首先提出，采用全局能量函數(shù)最優(yōu)化方法簡化模型，把距離能量、表示能量和彈簧能量引入全局優(yōu)化方程中。實驗證明，該方法簡化生成的網(wǎng)格模型效果是所有簡化算法中最好的［10］。但由于其優(yōu)化過程是非線性的，計算復(fù)雜，很難滿足實時繪制要求。為此，Garland等［11］提出一種基于二次誤差測度（quadric error metric，簡稱QEM）的邊折疊網(wǎng)格簡化方法，該方法以新頂點到被折疊邊的2個頂點關(guān)聯(lián)平面的距離平方和作為誤差度量，簡化生成的網(wǎng)格模型質(zhì)量較高，且計算簡單、運行速度較快。劉曉利等［12］在QEM簡化算法的基礎(chǔ)上，引入頂點的尖特征度，并將其加入到誤差測度中，保留了網(wǎng)格模型的特征信息，但由于只在二次誤差測度中加入了一個懲罰項，且需要根據(jù)經(jīng)驗設(shè)定閾值和懲罰系數(shù)。李基拓等［13］提出一種利用質(zhì)點－彈簧模型優(yōu)化網(wǎng)格形狀的邊折疊算法，該方法需要作原始模型曲面和簡化模型曲面雙映射處理，操作比較繁瑣。周元峰等［14］提出一種基于體積平方度量的三角形折疊網(wǎng)格簡化方法，在極小化誤差目標函數(shù)中引入幾何形狀因子和法向約束因子，取得了較好的簡化效果。為此，在QEM簡化算法的基礎(chǔ)上，把頂點曲率和局部區(qū)域面積引入二次誤差測度中，增大曲率變化較大區(qū)域的頂點誤差代價，進而改變邊折疊的順序，使得簡化網(wǎng)格模型的特征區(qū)域得以保留。

1 基于QEM算法的網(wǎng)格模型簡化方法

1.1 邊折疊操作的概念

對邊（vi，vj）進行折疊操作是將頂點vi、vj移動到一個新頂點vn，且刪除以（vi，vj）為邊的三角形，其他鄰接三角形需要進行相應(yīng)的調(diào)整，如圖1所示。

圖1 邊折疊操作Fig.1 The edge collapse operator

1.2 誤差測度的計算

1997年Garland等［11］提出了三維網(wǎng)格模型的二次誤差測度簡化算法，以邊折疊操作生成的新頂點到被折疊邊的2個頂點關(guān)聯(lián)平面的距離平方和作為誤差測度度量，根據(jù)邊折疊后的簡化模型與原始模型之間的誤差，即折疊代價Δv＝vTQv衡量和判斷一條邊能否被折疊簡化。對于三維空間頂點v＝［vxvyvz1］T與其關(guān)聯(lián)的三角形平面的集合P（v），誤差代價Δv定義為：

其中p＝［abcd］T表示三維空間中的平面方程ax＋by＋cz＋d＝0，且a2＋b2＋c2＝1。式（1）可變換為：

其中Kp為一個4×4的對稱矩陣，令頂點v的二次誤差測度矩陣。對于邊（vi，vj）→vn，折疊代價為Δvn＝vnT（Qi＋Qj）vn，用Qn＝Qi＋Qj表示新頂點vn的二次誤差測度矩陣，可快速計算邊折疊所造成的誤差，同時更新相應(yīng)的邊折疊順序。

新頂點的最佳位置可通過求式（2）的極小值確定，即?Δv／?x＝?Δv／?y＝?Δv／?z＝0，通過線性方程組求解頂點vn：

若方程組（4）有唯一解，則vn可由式（5）得到，

如果矩陣不可逆，QEM試圖沿著邊（vi，vj）找到一個最優(yōu)的頂點。若找不到合適的頂點，則算法會在vi、vj和（vi，vj）／2中尋找一個合適的點。實驗證明，QEM算法對三維網(wǎng)格模型的簡化效果明顯，且運行速度快，但該方法簡化生成的網(wǎng)格是均勻的，特別是在低分辨率的情況下，簡化生成的網(wǎng)格模型損失了原始模型的細節(jié)特征，引起細節(jié)部分的失真。為了能在簡化網(wǎng)格模型中更好地保持原始模型的細節(jié)特征區(qū)域，提出一種改進的基于邊折疊網(wǎng)格簡化方法，根據(jù)網(wǎng)格模型在折痕、拐點等特征區(qū)域網(wǎng)格曲率較大、三角面片較小的特點，將頂點曲率和局部區(qū)域面積引入二次誤差測度計算中，給出類似QEM算法的誤差標準，并用該誤差標準指導(dǎo)網(wǎng)格模型進行邊折疊操作。

2 改進的QEM算法

邊折疊包括2個重要的因素：1）確定邊折疊的順序；2）確定邊折疊后新頂點的位置。這2個因素決定了邊折疊簡化后的網(wǎng)格模型質(zhì)量。為了更好地指導(dǎo)邊折疊的順序，將頂點的曲率引入二次誤差測度中，通過增大頂點曲率變化較大區(qū)域的誤差測度值，改變邊折疊的順序，使得原始網(wǎng)格模型的細節(jié)特征在簡化網(wǎng)格模型中得以保留。另外，為了使簡化后的網(wǎng)格模型三角面片分布更加合理均勻，在重點特征區(qū)域用較多三角面片表示，在平坦區(qū)域用較少三角面片表示，引入了另一個誤差約束量——局部區(qū)域面積。

2.1 頂點曲率的計算

由于三維幾何數(shù)字化網(wǎng)格模型通常由一系列的三角面片組成，三角面片是二階不可微的曲面，理論上不存在曲率的概念，但可看作光滑表面的分段近似，這里所說的曲率是指一個近似曲率［15］。研究表明，人的視覺對幾何數(shù)字化網(wǎng)格模型的折痕、拐點等關(guān)鍵特征比較敏感，因此，在進行網(wǎng)格模型簡化時應(yīng)盡量保留這些部位。一般情況下，在三維幾何數(shù)字化網(wǎng)格模型平坦區(qū)域，曲率較?。辉谌S幾何數(shù)字化網(wǎng)格模型折痕、拐點等特征區(qū)域，曲率較大。若一個頂點的曲率越大，說明該頂點越能代表網(wǎng)格模型的細節(jié)特征。對于這些頂點推遲其邊折疊的順序，使得原始網(wǎng)格模型的主要特征信息得以保留。

對于任意一個三角網(wǎng)格t0，取其3個頂點分別為vi－1，vi，vi＋1，那么t0的單位法向量可用下式計算：

為了得到頂點vi的曲率，需計算頂點vi的法向量。頂點法向量可通過計算與該點關(guān)聯(lián)的所有三角網(wǎng)格的法向量進行面積加權(quán)平均得到［16－17］，

其中：k為與頂點vi相關(guān)三角面片的個數(shù)；Si為第i個三角網(wǎng)格的面積。得到頂點的法向量后，可計算該頂點的曲率為

其中α（nvi，ni）為頂點法向量nvi與三角網(wǎng)格單位法向量ni的夾角。

得到三角網(wǎng)格模型中每個頂點的曲率，并把曲率加入誤差測度中。若一個頂點的曲率越大，表示該頂點的位置越能表現(xiàn)模型的細節(jié)特征，將曲率大的邊放入堆底，曲率小的邊放入堆頂，根據(jù)折疊代價的大小進行邊折疊操作。

2.2 局部區(qū)域面積加權(quán)

QEM算法簡化后的網(wǎng)格模型三角面片分布比較均勻，不能很好地突顯原始網(wǎng)格模型的重要特征。希望簡化的網(wǎng)格模型在特征區(qū)域三角面片相對較多，在平坦區(qū)域三角面片相對較少，這樣才能更好地表現(xiàn)原始模型的整體面貌。因此，為了在簡化模型后有效保持原始模型的特征，并使三角面片分布更加合理，把局部區(qū)域面積引入折疊代價計算中，以改變邊折疊的順序，從而達到更好的簡化效果。

如圖2所示，頂點v的鄰接三角形為t0，t1，t2，t3，t4，t5，所有鄰接三角形的面積之和稱為頂點v的局部區(qū)域面積SLR。網(wǎng)格模型中任一頂點的局部區(qū)域面積可表示為

其中：k為頂點v鄰接三角形的個數(shù)；Si為第i個鄰接三角形的面積。

圖2 局部區(qū)域面積示意圖Fig.2 The schematic diagram of local region area

在計算邊折疊代價時，把頂點曲率和局部區(qū)域面積添加到式（2）中，將式（2）得到的代價乘以頂點的曲率，然后除以該頂點的鄰接局部區(qū)域面積，把得到的新代價作為邊折疊最后代價：

對于新頂點位置的確定，QEM算法中通過求式（2）的極小值確定，其求解過程不但復(fù)雜而且?guī)缀我饬x不明確。對此，采用半邊折疊操作，根據(jù)一條邊的2個頂點的折疊代價大小確定保留哪一個頂點。由于半邊收縮操作未引入新的頂點，無需增加額外的存儲開銷，從而可提高簡化速度。

2.3 算法描述

首先采用堆排序的方式對邊序列按照折疊誤差的大小進行排序，并存儲在待折疊邊的誤差隊列中，然后每次從堆中取出誤差最小的邊進行簡化操作。算法步驟為：

1）讀入原始網(wǎng)格模型，計算每個網(wǎng)格模型頂點的二次誤差矩陣Q；

2）計算三角網(wǎng)格模型中每個頂點的曲率cvn，結(jié)合頂點相鄰三角網(wǎng)格的局部區(qū)域面積SLR（vn），計算網(wǎng)格中頂點的二次誤差測度矩陣Q（vn）＝

3）計算每條邊的折疊代價Δvn，依據(jù)折疊代價的大小將所有的邊排序后放入堆中，折疊代價最小的置于堆頂，折疊代價最大的置于堆底；

4）從堆中取出折疊代價最小的邊進行折疊操作，同時刪除該邊及與該邊關(guān)聯(lián)的三角網(wǎng)格，并更新所有相關(guān)幾何元素的狀態(tài)；

5）重復(fù)上述過程直到達到簡化要求，否則轉(zhuǎn)步驟4）。

3 實驗結(jié)果分析

為了證明本算法的性能，在Microsoft Visual C＋＋、2.94GHz Intel（R）2、2GB內(nèi)存PC機上實現(xiàn)該算法，采用OPENGL圖形庫渲染模型，然后將本算法與QEM算法的簡化效果進行對比，實例為小鹿模型和人臉模型。圖3（a）為小鹿的原始網(wǎng)格模型，包含10 648個三角面片；圖3（b）為人臉原始模型，包含13 472個三角面片。圖4為利用QEM算法和本算法對小鹿模型進行簡化得到的模型，簡化模型剩余三角面片分別為2000個、800個、300個。

從圖4（a）～（c）可看出，利用QEM算法得到的簡化模型網(wǎng)格分布均勻，在平坦區(qū)域也占用較多的網(wǎng)格，既造成了網(wǎng)絡(luò)浪費，也未能很好突出模型的特征。經(jīng)大規(guī)模簡化后，QEM算法簡化的模型鹿角和嘴部開始出現(xiàn)模糊現(xiàn)象，圖4（c）簡化到只剩300個三角面片時，造成了視覺上的退化。與QEM算法相比，本算法能在一定程度上保持模型重要特征，并使得簡化后的模型網(wǎng)格分布比較合理，用較多的三角面片表示曲率變化較大區(qū)域，而在平坦區(qū)域用較少三角面片表示，如圖4（d）中在鹿角、鹿嘴、鹿鼻等特征區(qū)域保留了較多的三角面片。這樣，本算法在低分辨率的情況下，仍能保留簡化后模型的幾何特征，圖4（f）比圖4（c）更能突顯鹿角和鹿嘴的細節(jié)特征。

圖3 小鹿和人臉原始模型Fig.3 The original models of deer and face

圖4 小鹿的簡化模型Fig.4 The simplified models of deer

圖5為利用QEM算法和本算法對人臉模型進行簡化得到的簡化模型，剩余三角面片分別為3000個、1000個、500個。從這3組對比圖可看出，利用本算法得到的人臉簡化模型在眼睛、鼻子和嘴巴等特征區(qū)域網(wǎng)格分布較為稠密，有效地保持了較多的細節(jié)特征，在視覺效果上更接近原始模型。

圖5 人臉模型的簡化陰影圖比較Fig.5 The simplified models of face

4 結(jié)束語

針對大數(shù)據(jù)量的三維網(wǎng)格幾何模型在Web3D展示中的難點，提出了一種改進的二次誤差測度簡化算法，將頂點曲率和局部區(qū)域面積引入網(wǎng)格簡化誤差代價計算中。實驗表明，本算法在保留原算法運行速度快、效率高的同時，很好地保留了原始網(wǎng)格模型的細節(jié)特征，改善了三維幾何數(shù)字化模型簡化后在網(wǎng)絡(luò)展示中的細節(jié)模糊的狀況。由于數(shù)字化模型除了幾何信息外，還具有紋理、顏色等屬性，下一步將研究帶屬性的三角網(wǎng)格模型簡化的問題，進一步提升三維數(shù)字化模型Web3D的展示效果。

［1］潘志庚，龐明勇.幾何網(wǎng)格簡化研究與進展［J］.江蘇大學學報，2005，26（1）：67－71.

［2］Dong Wenlong，Li Jiankun，JayKuo C C.Fast mesh simplification for progressive transmission［C］／／Multimedia and Expo，2000IEEE International Conference on.New York：IEEE Computer Society Press，2000：1731－1734.

［3］盧威，曾定浩，潘金貴.支持外觀屬性保持的三維網(wǎng)格模型簡化［J］.軟件學報，2009，20（3）：713－723.

［4］William J S，Jonathan A Z，William E L.Decimation of triangle meshes［J］.Computer Graphics，1992，26（2）：65－70

［5］Turk G.Retiling polygonal surfaces［J］.Computer Graphics，1992，26（2）：55－64.

［6］Hoppe H.Progressive meshes［C］／／ACM Computer Graphics Procedings，Annual Conference Series，1996：99－108.

［7］Kalvin A D，Taylor R H.Superfaces：polygonal mesh simplication with bounded error［J］.IEEE Computer Graphics and Application，1996，16（3）：64－77.

［8］Lounsbery M，deRose T.Multiresolution analysis for surface of arbitrary topological type［R］.Washington：U－niversity of Washington，1994：47－64.

［9］張明敏，周昆，潘志庚.基于超包絡(luò)網(wǎng)絡(luò)的三角形網(wǎng)格簡化算法［J］.軟件學報，1999，10（6）：405－408.

［10］Cignoni P，Puppo E，Scopogno R.Representation and visualization of terrain surfaces at variable resolution［J］.The Visual Computer，1997，13：199－217.

［11］Garland M，Heckbert P S.Surface simplification using quadric error metrics［J］.Computer Graphics，1997，31（3）：209－216.

［12］劉曉利，劉則毅，高鵬東，等.基于尖特征度的邊折疊簡化算法［J］.軟件學報，2005，16（5）：669－675.

［13］李基拓，陸國棟.基于邊折疊和質(zhì)點彈簧模型的網(wǎng)格簡化優(yōu)化算法［J］.計算機輔助設(shè)計與圖形學學報，2006，18（3）：426－432.

［14］周元峰，張彩明，賀平.體積平方度量下的特征保持網(wǎng)格簡化方法［J］.計算機學報，2009，32（2）：203－212.

［15］張果，劉旭敏，關(guān)永.一種基于近似曲率的邊折疊簡化算法［J］.計算機應(yīng)用，2009，29（3）：729－731.

［16］Biermann H，Levin A，Zorin D.Piecewise smooth subdivision surfaces with normal control［C］／／Proceedings of SIGGRAPH 2000.Boston：Addison Wesley Professional，2000：113－120.

［17］Page D L，Koschan A，Sun Y，et al.Robust crease detection and curvature estimation of piecewise smooth surfaces from triangle mesh approximations using normal voting［C］／／Proceedings of the International Conference on Computer Vision and Pattern Recognition.San Francisco：Morgan Kaufmann，2001：162－167.