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

（桂林電子科技大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，廣西 桂林 541004）

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

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

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

1.1 邊折疊操作的概念

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

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

1.2 誤差測(cè)度的計(jì)算

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

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

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

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

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

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

2 改進(jìn)的QEM算法

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

2.1 頂點(diǎn)曲率的計(jì)算

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

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

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

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

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

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

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

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

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

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

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

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

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

2.3 算法描述

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

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

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

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

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

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

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

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

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

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

圖4 小鹿的簡(jiǎn)化模型Fig.4 The simplified models of deer

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

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

4 結(jié)束語(yǔ)

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

［1］潘志庚，龐明勇.幾何網(wǎng)格簡(jiǎn)化研究與進(jìn)展［J］.江蘇大學(xué)學(xué)報(bào)，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)格模型簡(jiǎn)化［J］.軟件學(xué)報(bào)，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)格簡(jiǎn)化算法［J］.軟件學(xué)報(bào)，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］劉曉利，劉則毅，高鵬東，等.基于尖特征度的邊折疊簡(jiǎn)化算法［J］.軟件學(xué)報(bào)，2005，16（5）：669－675.

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

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

［15］張果，劉旭敏，關(guān)永.一種基于近似曲率的邊折疊簡(jiǎn)化算法［J］.計(jì)算機(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.