郝娟兒，唐莉萍，曾培峰

（東華大學(xué)a.信息科學(xué)與技術(shù)學(xué)院；b.計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，上海 201620）

基于曲率和面積的二次誤差測(cè)度網(wǎng)格簡(jiǎn)化算法

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

（東華大學(xué)a.信息科學(xué)與技術(shù)學(xué)院；b.計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，上海 201620）

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

網(wǎng)格簡(jiǎn)化；邊收縮；二次誤差測(cè)度；離散曲率

目前在計(jì)算機(jī)圖形學(xué)和幾何造型中，三維物體模型的表面通常以三角網(wǎng)格的形式表示.對(duì)于大規(guī)模的物體模型，為刻畫(huà)出物體的表面細(xì)節(jié)特征，相應(yīng)的三維模型往往需要數(shù)量相當(dāng)龐大的三角網(wǎng)格構(gòu)建得到.巨大的數(shù)據(jù)量給計(jì)算機(jī)的處理和存儲(chǔ)、網(wǎng)絡(luò)數(shù)據(jù)傳輸以及實(shí)時(shí)顯示都會(huì)帶來(lái)很大的困難，因此，有必要對(duì)三角網(wǎng)格模型進(jìn)行簡(jiǎn)化.

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

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

1 QEM算法研究及分析

QEM算法的基本思想是用二次誤差測(cè)度描述簡(jiǎn)化誤差，通過(guò)對(duì)模型原始邊界內(nèi)部每個(gè)頂點(diǎn)計(jì)算相應(yīng)的誤差測(cè)度矩陣，得到每條邊的邊收縮代價(jià)，每次簡(jiǎn)化都選擇收縮代價(jià)最小的邊進(jìn)行操作，直至達(dá)到預(yù)期的簡(jiǎn)化要求.

1.1 邊收縮操作

對(duì)邊 （v1，v2）進(jìn)行邊收縮操作，記為 （v1，v2）→，如圖1所示.將一條邊（v1，v2）簡(jiǎn)化為一個(gè)頂點(diǎn)，其收縮操作過(guò)程如下：

（1）去除原始網(wǎng)格中所有與頂點(diǎn)v1和頂點(diǎn)v2相關(guān)聯(lián)的三角網(wǎng)格；

（2）將頂點(diǎn)v1和v2移至新的位置；

（3）將與頂點(diǎn)v1和v2相關(guān)的邊和三角網(wǎng)格的信息添加到頂點(diǎn)的信息中.

重復(fù)以上邊收縮過(guò)程，直到簡(jiǎn)化模型中的三角網(wǎng)格達(dá)到預(yù)期的數(shù)量或一定的簡(jiǎn)化比例要求.從圖1可以看出，一般情況下進(jìn)行一次邊收縮操作可以減少1個(gè)頂點(diǎn)、2個(gè)三角形和3條邊.

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

1.2 二次誤差測(cè)度

模型簡(jiǎn)化的重點(diǎn)在于選取合適的邊進(jìn)行收縮，使得邊收縮最小程度地影響模型的視覺(jué)效果.一條邊的收縮與否是通過(guò)評(píng)價(jià)這條邊收縮后對(duì)模型所帶來(lái)的誤差的大小，即收縮代價(jià)決定的.每次收縮都選取收縮代價(jià)最小的邊操作，這樣得到的簡(jiǎn)化模型與原始模型的誤差最小.

文獻(xiàn)［3］算法在將三角網(wǎng)格中的兩個(gè)頂點(diǎn)收縮為一個(gè)新頂點(diǎn)時(shí)，首先計(jì)算它的二次誤差測(cè)度，即計(jì)算該頂點(diǎn)到與原始網(wǎng)格中被收縮的兩個(gè)頂點(diǎn)相關(guān)聯(lián)的三角網(wǎng)格間距離的平方和，并據(jù)此求解方程得到新頂點(diǎn)的坐標(biāo)位置.

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

定義頂點(diǎn)v的二次誤差測(cè)度矩陣［3］為

對(duì)于邊 （vi，vj）收縮為新頂點(diǎn)，將收縮代價(jià)定義為并用Q′i＋Q′j來(lái)表示新頂點(diǎn)的二次誤差測(cè)度矩陣［3］.

2 QEM改進(jìn)算法

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

2.1 離散法向量和曲率估計(jì)

2.1.1 法向量和曲率

在微分曲面中，曲面的法向量是曲面的一階微分量，曲面的曲率是曲面的二階微分量.作為曲面信息的重要度量指標(biāo)，曲面的法向量和曲率可以量化地表示三角網(wǎng)格模型表面的細(xì)節(jié)特征信息，如邊界、折痕、拐點(diǎn)和尖銳邊等彎曲程度較大區(qū)域的特征.

三維空間中三角網(wǎng)格模型是由邊和頂點(diǎn)相連接而成的分段線(xiàn)性曲面，沒(méi)有確切的解析表示，無(wú)法用傳統(tǒng)的曲面解析方法計(jì)算.它是一種離散的曲面表示形式，沒(méi)有連續(xù)的法向量和曲率.對(duì)于該網(wǎng)格曲面，通常通過(guò)計(jì)算其頂點(diǎn)處的離散法向量和離散曲率作為曲面在頂點(diǎn)處彎曲程度的近似［8］.

三角網(wǎng)格的數(shù)據(jù)分析需要存儲(chǔ)兩種數(shù)據(jù)結(jié)構(gòu)：一種是頂點(diǎn)數(shù)據(jù)結(jié)構(gòu)，存儲(chǔ)網(wǎng)格中各頂點(diǎn)的坐標(biāo)；另一種是三角網(wǎng)格數(shù)據(jù)結(jié)構(gòu)，存儲(chǔ)指向組成每個(gè)三角網(wǎng)格的頂點(diǎn)數(shù)據(jù)的頂點(diǎn)索引數(shù)據(jù).基于后者可以計(jì)算得到離散法向量和曲率.

2.1.2 離散法向量

假設(shè)一個(gè)三角網(wǎng)格的3個(gè)頂點(diǎn)分別為vj－1，v，vj，那么該網(wǎng)格的單位法向量為

遍歷三角網(wǎng)格數(shù)據(jù)結(jié)構(gòu)，用式（3）得到所有三角網(wǎng)格的單位法向量.然后根據(jù)各三角網(wǎng)格的單位法向量估算各個(gè)頂點(diǎn)的法向量.頂點(diǎn)法向量通過(guò)對(duì)與該頂點(diǎn)相關(guān)聯(lián)的所有三角網(wǎng)格的法向量進(jìn)行加權(quán)平均得到.考慮與頂點(diǎn)相關(guān)聯(lián)的各個(gè)三角網(wǎng)格面積對(duì)頂點(diǎn)法向量結(jié)果的影響，本文將各三角網(wǎng)格的面積也作為估算頂點(diǎn)法向量時(shí)的權(quán)值.若一個(gè)頂點(diǎn)為v，與它相關(guān)聯(lián)三角網(wǎng)格數(shù)量為m，記m為頂點(diǎn)v的維度，則頂點(diǎn)v的單位法向量為

其中：Sj表示第j個(gè)三角網(wǎng)格的面積.

這樣，可得到三角網(wǎng)格模型中每個(gè)頂點(diǎn)的單位法向量，并作為頂點(diǎn)的屬性和頂點(diǎn)坐標(biāo)一起存入三角網(wǎng)格數(shù)據(jù)結(jié)構(gòu)中.

2.1.3 離散曲率

對(duì)于三角網(wǎng)格模型的每個(gè)頂點(diǎn)，離散曲面在頂點(diǎn)處沿不同的方向彎曲程度不同.因此，刻畫(huà)曲面在某一個(gè)點(diǎn)附近的彎曲程度，可以用曲面上經(jīng)過(guò)該點(diǎn)的不同曲線(xiàn)的曲率進(jìn)行評(píng)價(jià).

利用式（5）得到和頂點(diǎn)v相鄰的各個(gè)邊方向的離散曲率.根據(jù)曲率的大小，可以判斷網(wǎng)格模型的關(guān)鍵特征.

2.2 邊收縮后的頂點(diǎn)

本文網(wǎng)格簡(jiǎn)化的基本操作為半邊收縮.半邊收縮操作不生成新的頂點(diǎn)，收縮后的頂點(diǎn)為原兩個(gè)頂點(diǎn)中的一個(gè)，即簡(jiǎn)化模型中的頂點(diǎn)是原始模型的一個(gè)子集.一條邊的兩個(gè)頂點(diǎn)保留哪個(gè)需通過(guò)比較這條邊兩個(gè)頂點(diǎn)的收縮代價(jià)大小確定.這樣既能減少計(jì)算新頂點(diǎn)的時(shí)間開(kāi)銷(xiāo)，又可以節(jié)省存儲(chǔ)新頂點(diǎn)的空間開(kāi)銷(xiāo).

2.3 曲率面積加權(quán)誤差測(cè)度

根據(jù)計(jì)算得到與每個(gè)頂點(diǎn)關(guān)聯(lián)的各邊的離散曲率和相鄰三角網(wǎng)格的面積，結(jié)合QEM算法的原理，求出每個(gè)頂點(diǎn)曲率面積加權(quán)的二次誤差測(cè)度矩陣，并用計(jì)算得到的邊收縮代價(jià)指導(dǎo)簡(jiǎn)化過(guò)程中的半邊收縮順序.模型中曲率較大的頂點(diǎn)構(gòu)成重要特征相關(guān)的邊，這些邊加權(quán)之后相應(yīng)的邊收縮代價(jià)較大，在邊收縮隊(duì)列中的順序就靠后.由于推遲了與重要特征相關(guān)的三角網(wǎng)格的收縮，模型的重要特征得以保留.

2.4 邊界的處理

在原始網(wǎng)格模型內(nèi)部，由兩個(gè)頂點(diǎn)組成的邊被兩個(gè)三角面共享.如果網(wǎng)格中一條邊只有一個(gè)三角面與它相關(guān)聯(lián)，那么這條邊就為模型的邊界，與它對(duì)應(yīng)的頂點(diǎn)稱(chēng)為邊界點(diǎn).對(duì)于有邊界的模型，在簡(jiǎn)化過(guò)程應(yīng)該盡可能保持其邊界特征.為保證邊界在簡(jiǎn)化中不被退化，在簡(jiǎn)化過(guò)程中對(duì)于原始網(wǎng)格中的邊界點(diǎn)應(yīng)予以保留.在本文算法的程序?qū)崿F(xiàn)過(guò)程中，通過(guò)為邊界點(diǎn)設(shè)置一個(gè)非常大的誤差測(cè)度權(quán)值，使邊界邊的收縮代價(jià)處于優(yōu)先隊(duì)列的最后，保證不被收縮.這種處理方法簡(jiǎn)單有效，能夠很好保留模型的邊界特征.

2.5 改進(jìn)QEM算法流程

（1）讀入初始網(wǎng)格模型的頂點(diǎn)、三角網(wǎng)格數(shù)據(jù).

（2）計(jì)算網(wǎng)格中每個(gè)頂點(diǎn)的離散法向量nv.根據(jù)每個(gè)頂點(diǎn)的離散法向量，計(jì)算出與頂點(diǎn)相鄰各邊的離散曲率Cj，并結(jié)合頂點(diǎn)各相鄰三角網(wǎng)格的面積Sj和三角網(wǎng)格對(duì)應(yīng)矩陣Kpj，計(jì)算出網(wǎng)格中頂點(diǎn)的二次誤差測(cè)度矩陣為表述方便，記Sj×Cj，為第i個(gè)頂點(diǎn)的權(quán)重.

（3）根據(jù)網(wǎng)格中各頂點(diǎn)的二次誤差測(cè)度矩陣，計(jì)算每一條邊的收縮代價(jià)c，并將其放入優(yōu)先隊(duì)列中.若 （v1，v2）→，其收縮代價(jià)為

（4）從優(yōu)先隊(duì)列中取出收縮代價(jià)最小的邊進(jìn)行邊收縮操作，刪除該邊及與該邊相關(guān)的三角網(wǎng)格，更新受影響區(qū)域點(diǎn)的鄰域，并計(jì)算新的邊收縮代價(jià)，然后更新優(yōu)先隊(duì)列.

（5）重復(fù)上述過(guò)程，直到達(dá)到簡(jiǎn)化要求.

3 試驗(yàn)結(jié)果

應(yīng)用本算法在VC＋＋6.0環(huán)境對(duì)來(lái)源于Internet的三維網(wǎng)格模型進(jìn)行簡(jiǎn)化試驗(yàn)，然后將算法得到的簡(jiǎn)化結(jié)果與文獻(xiàn)［3］算法結(jié)果進(jìn)行比較.

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

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

4 結(jié) 語(yǔ)

本文在二次誤差測(cè)度算法的基礎(chǔ)上，通過(guò)引入離散曲率和三角形面積作為權(quán)值計(jì)算頂點(diǎn)的二次誤差測(cè)度矩陣，得到相應(yīng)的邊收縮代價(jià)，指導(dǎo)邊收縮順序.算法較好地保持了網(wǎng)格簡(jiǎn)化過(guò)程中原始模型的重要幾何特征，使得最終的簡(jiǎn)化模型能夠依照曲率的變化合理地分配網(wǎng)格數(shù)量，在彎曲程度較大的區(qū)域網(wǎng)格分布稠密，在平坦區(qū)域網(wǎng)格分布稀疏，因而有效地保持了較多的模型關(guān)鍵特征，在視覺(jué)效果上也與原始模型相近.

［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］周石琳，湯曉安，陳敏，等.基于多邊形頂點(diǎn)法矢量的網(wǎng)格模型簡(jiǎn)化算法［J］.中國(guó)圖象圖形學(xué)報(bào)，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—），女，山西運(yùn)城人，碩士，研究方向?yàn)閳D形與圖像處理.E－mail：haojuan108＠126.com

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

1671－0444（2012）03－0318－05