基于二次誤差度量的大型網(wǎng)格模型簡化算法

李紅波，劉昱晟，吳 渝，羅 璇

（重慶郵電大學(xué) 網(wǎng)絡(luò)智能研究所，重慶400065）

0 引 言

在計(jì)算機(jī)圖形學(xué)中，三維模型通常使用三維網(wǎng)格表現(xiàn)。由于較大的網(wǎng)格模型受到存儲成本和計(jì)算效率的限制，很難將其直接應(yīng)用到實(shí)際工作當(dāng)中。解決該問題的一個有效方式就是對原有網(wǎng)格進(jìn)行簡化，在盡可能保持網(wǎng)格模型外觀特征的前提下，減少原模型的三角面片數(shù)量。但是對于尺寸超出內(nèi)存容量的大型網(wǎng)格模型，無法將其一次讀入內(nèi)存進(jìn)行簡化。此外，受限于CPU處理速度，大型網(wǎng)格的簡化一般耗時很長。因此，面向大型網(wǎng)格模型的簡化成為近幾年來計(jì)算機(jī)圖形學(xué)領(lǐng)域的研究熱點(diǎn)之一［1］。

對于常規(guī)網(wǎng)格模型，Garland提出一種邊折疊算法，即二次誤差度量算法 （quadric error metric，QEM）。顧耀林等［2］、孫永鋒等［3］、唐慧等［4］、張果等［5］、Tang等［6］與黨建武等［7］對其進(jìn)行了進(jìn)一步的研究。在常規(guī)算法的基礎(chǔ)上，Cignoni提出了基于八叉樹的外存網(wǎng)格模型數(shù)據(jù)結(jié)構(gòu)，以邊折疊的方式對網(wǎng)格進(jìn)行了有效簡化，但其數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)與實(shí)現(xiàn)較為復(fù)雜。Hoppe對網(wǎng)格模型分割為多塊可以一次讀入內(nèi)存的子模型塊，并分別對每個子塊依次進(jìn)行簡化，對分割邊界處的三角形進(jìn)行保留，在所有子模型塊簡化結(jié)束后將其重組，并再進(jìn)行一次簡化以消除拼接處的冗余三角形。該算法在每次子模型合并時都需要額外進(jìn)行簡化，增加了開銷。馮潔等［8］在網(wǎng)格分割的基礎(chǔ)上，改進(jìn)了邊權(quán)的計(jì)算方法，減小了模型簡化產(chǎn)生的誤差。

本文在上述研究的基礎(chǔ)上，提出一種改進(jìn)的大型網(wǎng)格簡化算法。算法在QEM算法的基礎(chǔ)上進(jìn)行了改進(jìn)，在權(quán)值的計(jì)算中加入了頂點(diǎn)法向量夾角與邊長因子，更準(zhǔn)確地反映出了模型的細(xì)節(jié)特征，并利用邊折疊的優(yōu)勢，引入基于八叉樹的模型劃分策略，在實(shí)現(xiàn)了子模型的簡化的前提下，有效避免了子模型重組過程中的額外簡化步驟。

1 經(jīng)典QEM算法

QEM算法是一種邊折疊算法，該算法將邊折疊后生成的頂點(diǎn)到該邊折疊前兩端點(diǎn)相關(guān)平面距離的平方和作為誤差測度，算法計(jì)算量小，簡化速度快，簡化質(zhì)量較高，因此本文選擇以該算法為基礎(chǔ)。

1.1 有效頂點(diǎn)對的選擇

一個頂點(diǎn)對（vi，vj）若滿足下列條件之一，則被稱為有效頂點(diǎn)對：

（1）（vi，vj）是一條邊；

（2）vi－vj＜t，其中t為閾值。

其中，條件 （2）表明，當(dāng)兩不相連頂點(diǎn)距離小于閾值t時，這兩個頂點(diǎn)就有可能進(jìn)行折疊。這樣會改變原有模型的拓?fù)浣Y(jié)構(gòu)，導(dǎo)致模型中兩個不相連的部分連接在一起，或者模型中的孔洞消失。若不希望產(chǎn)生這樣的結(jié)果，可將閾值t設(shè)置為0，此時算法即簡化為普通的邊折疊算法。

有效頂點(diǎn)對為邊時的折疊如圖1所示。

1.2 二次誤差測度

為了衡量刪除每條邊的代價，需要定義每個頂點(diǎn)的誤差。對每個頂點(diǎn)v建立一個4×4的誤差矩陣Q，將頂點(diǎn)v＝［vx，vy，vz，1］Τ的誤差定義為二次型Δv＝vΤQv（誤差矩陣Q的建立方法見下節(jié)）。

將刪除有效頂點(diǎn)對（vi，vj），生成新頂點(diǎn)珔v的過程記為（vi，vj）→珔v。則需要為新生成頂點(diǎn)珔v建立一個頂點(diǎn)誤差矩陣珚Q，在這里簡單的令珚Q＝Qi＋Qj，其中Qi、Qj分別為頂點(diǎn)vi、vj的頂點(diǎn)誤差矩陣。

1.3 頂點(diǎn)誤差矩陣Q的計(jì)算

令p＝ ［a b c d］Τ表示平面

則可將頂點(diǎn)誤差定義為頂點(diǎn)到其關(guān)聯(lián)平面距離的平方和

式 （1）給出的誤差矩陣可以被重寫為

式中：Kp——矩陣

基礎(chǔ)二次誤差Kp用來確定空間中任意點(diǎn)到平面p的平方距離。將所有與頂點(diǎn)v相連的平面計(jì)算出Kp，取其和即可得到誤差矩陣Q。

2 基于改進(jìn)QEM算法的大型網(wǎng)格簡化算法

QEM算法在模型的簡化效果上較為理想，簡化速度也很快，但仍存在不足：經(jīng)典QEM算法以網(wǎng)格模型間的幾何誤差作為權(quán)值，并未考慮模型的外觀誤差，因而產(chǎn)生的網(wǎng)格非常均勻，在簡化過程中，原模型的某些細(xì)節(jié)特征將會丟失。因此，在經(jīng)典的QEM算法基礎(chǔ)上，引入頂點(diǎn)法向量來減小模型簡化過程中帶來的外觀誤差。

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

不同于常見頂點(diǎn)法向量的定義［9］，在網(wǎng)格模型中，將一個頂點(diǎn)v的頂點(diǎn)法向量定義為

式中：Np——與頂點(diǎn)v相鄰三角面的面法向量，Sp——該三角面的面積，Ap——該三角面在頂點(diǎn)v處夾角的弧度。

引入三角面面積的目的是正確反映出三角面片面積與頂點(diǎn)法向量的關(guān)系：頂點(diǎn)法向量應(yīng)傾向于面積更大的三角面片；引入三角面片在頂點(diǎn)處夾角的目的是避免在簡化過程中生成過于細(xì)長的三角面。通過以上兩處的改進(jìn)，使得頂點(diǎn)法向量能夠更真實(shí)地反映出頂點(diǎn)的彎曲程度。

在確定頂點(diǎn)法向量的計(jì)算方式后，就可以確定有效頂點(diǎn)對（vi，vj）中兩點(diǎn)頂點(diǎn)法向量夾角，令

將新生成頂點(diǎn)的誤差定義為

式中：li，j——有效頂點(diǎn)對 （vi，vj）的空間 距離。ci，j取值 范圍為 ［－1，1］，Nvi和Nvj夾角越大，則ci，j越小，1－ci，j越大，說明有效頂點(diǎn)對（vi，vj）鄰域內(nèi)的幾何變化較大，該頂點(diǎn)對的權(quán)值應(yīng)較高，應(yīng)將其刪除優(yōu)先級向后推。

2.2 改進(jìn)的八叉樹網(wǎng)格劃分算法

一種常用的網(wǎng)格劃分策略［10］是將原網(wǎng)格模型用一組平面均勻分割為若干子模型，若分割邊界上三角面片的3個頂點(diǎn)不在同一個子網(wǎng)格中，則需要對此三角面片重新進(jìn)行三角剖分，以使每個子網(wǎng)格中的三角面片都是完整的。由此可見這種策略在簡化過程中增加了面片三角剖分和簡化的步驟，因此需要更多的處理時間。

經(jīng)典網(wǎng)格劃分策略如圖3所示。

本文在以上網(wǎng)格劃分策略的基礎(chǔ)上進(jìn)行了改進(jìn)，步驟如下：

（1）找出網(wǎng)格模型中的最大點(diǎn)與最小點(diǎn)，計(jì)算出網(wǎng)格中點(diǎn)；

（2）以x軸、y軸和z軸為分割邊界，從中點(diǎn)將網(wǎng)格劃分為8個象限，將每個象限內(nèi)的數(shù)據(jù)存儲為獨(dú)立的網(wǎng)格模型，并建立從子網(wǎng)格模型中頂點(diǎn)索引到父網(wǎng)格模型中頂點(diǎn)索引的映射；

（3）依次判斷每個子網(wǎng)格的數(shù)據(jù)量，若大于內(nèi)存容量則轉(zhuǎn)向步驟 （2）繼續(xù)迭代劃分；

（4）處于劃分邊界上的邊和頂點(diǎn)都分別加入相鄰的多個子網(wǎng)格。但對每個子網(wǎng)格，不處理劃分邊界上的邊及子網(wǎng)格外的頂點(diǎn)，邊界上的邊收縮依靠子模型的邊折疊算法完成，處理方法如圖5所示。在每個子網(wǎng)格中的邊折疊后，處在劃分邊界上的邊自然的進(jìn)行了伸展。

圖5 邊界處理

依靠子模型邊折疊處理劃分邊界上的邊會產(chǎn)生極小的誤差，但是對于較大的網(wǎng)格模型，劃分邊界上的邊所占比例很小，幾乎不會影響最終的簡化效果。

2.3 算法流程

改進(jìn)算法的流程如下：

（1）按2.2節(jié)網(wǎng)格劃分算法對模型進(jìn)行迭代劃分，記錄劃分信息；

（2）對每個子網(wǎng)格模型中的每個原始頂點(diǎn)計(jì)算頂點(diǎn)誤差矩陣Q；

（3）選出所有的有效頂點(diǎn)對；

（4）對每個有效頂點(diǎn)對（vi，vj）計(jì)算出最優(yōu)生成點(diǎn)珔v的坐標(biāo)，并計(jì)算出誤差Δ珔v；

（5）將所有有效頂點(diǎn)對按誤差大小存入小根堆中；

（6）從小根堆堆頂取出誤差最小的有效頂點(diǎn)對，將頂點(diǎn)vi、vj合并為珔v；

（7）根據(jù)與vi、vj相連邊和三角面片信息生成與珔v相連的邊與三角面片，并將與vi、vj相連的邊和三角面片標(biāo)記為無效。

（8）重新計(jì)算與vi、vj相關(guān)的有效頂點(diǎn)對誤差；

（9）重復(fù)步驟 （6）至步驟 （8），直到被簡化網(wǎng)格模型滿足精度條件；

（10）根據(jù)原劃分信息將子網(wǎng)格模型進(jìn)行拼接。

2.4 算法復(fù)雜度

Garland指出，經(jīng)典QEM算法的初始化時間復(fù)雜度及簡化時間復(fù)雜度均為O（nlogn）。本文算法在初始化及簡化過程中增加了頂點(diǎn)法向量夾角與邊長的計(jì)算，這個過程的時間復(fù)雜度為O（n），模型劃分與拼接也會消耗一部分時間，這個過程的時間復(fù)雜度同樣是O（n），因此本文算法的時間復(fù)雜度沒有改變，仍為O（nlogn）。

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

為驗(yàn)證本文算法的正確性和有效性，在Intel Core i5－2320 3.00GHz的CPU，4GB內(nèi)存，Windows 7操作系統(tǒng)，Visual Studio 2010＋OpenGL的計(jì)算機(jī)上進(jìn)行實(shí)驗(yàn)。對Horse、Bunny、Dragon和Lucy等4個經(jīng)典模型，分別使用經(jīng)典QEM算法結(jié)合八叉樹分割算法的網(wǎng)格簡化算法，與本文提出的改進(jìn)QEM算法結(jié)合八叉樹分割算法的網(wǎng)格簡化算法進(jìn)行對比。部分簡化效果如圖6和圖7所示。

圖6 Bunny模型簡化效果對比

對比發(fā)現(xiàn)，對Bunny模型，使用經(jīng)典QEM算法的網(wǎng)格簡化算法在簡化到99%時，兔子左耳部分已經(jīng)缺失，但表面變化比較小的軀干部分卻使用了較多的三角面片，而使用改進(jìn)QEM算法的網(wǎng)格簡化算法的耳朵部分仍十分完整，軀干部分僅用較少的三角面片就表現(xiàn)的比較準(zhǔn)確。對Lucy模型，使用經(jīng)典QEM算法的網(wǎng)格簡化算法在簡化到99%時，模型手部已經(jīng)退化，無法分辨出手指，而使用改進(jìn)QEM算法的網(wǎng)格簡化算法的手指輪廓十分清晰；當(dāng)簡化到99.9%時，使用經(jīng)典QEM算法簡化出的模型已經(jīng)出現(xiàn)多處退化，而本文算法仍能保持一個較好外觀。通過觀察，簡化模型在子模型合并邊界上的三角面片分布十分均勻，沒有拼接痕跡。

圖7 Lucy模型簡化效果對比

表1為各經(jīng)典模型使用不同算法簡化后的數(shù)據(jù)?？梢钥闯觯疚乃惴ㄓ捎诰邆浔Ａ裟Ｐ图?xì)節(jié)特征的優(yōu)點(diǎn)，簡化后模型的Hausdorff距離較使用經(jīng)典QEM算法的簡化算法更小。上文中已提到，本文算法時間復(fù)雜度的數(shù)量級與經(jīng)典QEM算法的相同，從表中也可看到，使用本文算法增加的簡化時間是可以接受的。

表1 簡化效果實(shí)驗(yàn)數(shù)據(jù)

4 結(jié)束語

本文對國內(nèi)外經(jīng)典網(wǎng)格算法進(jìn)行研究與分析，在經(jīng)典QEM算法的基礎(chǔ)上，結(jié)合基于八叉樹的網(wǎng)格劃分策略進(jìn)行了改進(jìn)，使之能夠適用于大型網(wǎng)格模型。實(shí)驗(yàn)結(jié)果表明，該算法在未改變算法時間復(fù)雜度的前提下，能夠更好地保持模型細(xì)節(jié)特征，對于大型網(wǎng)格模型簡化的后續(xù)研究與應(yīng)用具有一定的參考價值。下一步工作是對簡化算法及網(wǎng)格劃分策略進(jìn)行更深入的研究，并引入分布式計(jì)算相關(guān)技術(shù)，提高子網(wǎng)格模型的簡化效率。

［1］ZHANG Yaping，XIONG hua，JIANG Xiaohong，et al.A survey of simplification and multiresolution techniques for massive meshes［J］.Journal of Computer－Aided Design and Computer Graphics，2010，22 （4）：559－568 （in Chinese）.［張亞萍，熊華，姜曉紅，等.大型網(wǎng)格模型簡化和多分辨率技術(shù)綜述 ［J］.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報，2010，22 （4）：559－568.］

［2］GU Yaolin，ZHAO Zhengming，WEI Jiangtao.Multiresolution mesh simplification algorithm with distance－weighted quadric error metric ［J］.Computer Engineering and Design，2007，28 （8）：1966－1968 （in Chinese）. ［顧耀林，趙爭鳴，魏江濤.距離加權(quán)的二次誤差測度多分辨率網(wǎng)格簡化 ［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2007，28 （8）：1966－1968.］

［3］SUN Yongfeng，LIU Xumin.Research on properties in process of triangle mesh simplification ［J］.Computer Engineering and Design，2008，29 （21）：5586－5587 （in Chinese）. ［孫永鋒，劉旭敏.三角網(wǎng)格簡化過程中屬性問題的研究 ［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2008，29 （21）：5586－5587.］

［4］TANG Hui，LUO Limin，ZHOU Zhengdong.A mesh simplification method based on curvature of curves ［J］.Journal of Image and Graphics，2008，13 （11）：2224－2230 （in Chinese）.［唐慧，羅立民，周正東.基于曲線曲率的網(wǎng)格簡化方法 ［J］.中國圖像圖形學(xué)學(xué)報，2008，13 （11）：2224－2230.］

［5］ZHANG Guo，LIU Xumin，GUAN Yong.Edge collapse simplification based on similar curvature ［J］.Journal of Computer Applications，2009，29 （3）：29－731 （in Chinese）. ［張果，劉旭敏，關(guān)永.一種基于近似曲率的邊折疊簡化算法 ［J］.計(jì)算機(jī)應(yīng)用，2009，29 （3）：729－731.］

［6］Tang Zhanhong，Yan Shutian.A New method of mesh simplification algorithm based on QEM ［J］.Information Technology Journal，2010，9 （2）：391－394.

［7］DANG Jianwu，LIU Yunwu， WANG Yangping，et al.Quadadric error metric mesh simplification algorithm based on discrete curvature ［J］.Journal of Computer Applications，2011，31 （4）：1010－1012 （in Chinese）. ［黨建武，劉云伍，王陽萍，等.基于離散曲率的二次誤差度量網(wǎng)格簡化算法［J］.計(jì)算機(jī)應(yīng)用，2011，31 （4）：1010－1012.］

［8］FENG Jie，ZHA Hongbin.Simplification and view－dependent LOD control for large 3Dmesh models ［J］.Journal of Computer－Aided Design and Computer Graphics，2006，18 （2）：186－193 （in Chinese）.［馮潔，查紅彬.大型三維網(wǎng)格模型的簡化及基于視點(diǎn)的LOD控制 ［J］.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報，2006，18 （2）：186－193.］

［9］WANG Fang，CONG Wenjing，ZHU Haitao.Research of simplification algorithm for modeling based on normal important degree of triangular facets ［J］.Computer and Digital Engineering，2011，39 （7）：6－8 （in Chinese）. ［王芳，叢文靜，祝海濤.基于頂點(diǎn)法向量重要度的模型簡化算法研究 ［J］.計(jì)算機(jī)與數(shù)字工程，2011，39 （7）：6－8.］

［10］Shamir A.Segmentation and shape extraction of 3Dboundary meshes ［C］／／Vienna：Proceedings of Eurographics，2006：137－149.