祁成武張宇婷舒振宇胡 超徐惠霞

1(浙江大學(xué)寧波理工學(xué)院信息科學(xué)與工程學(xué)院 寧波 315100)

2(浙江萬里學(xué)院數(shù)學(xué)研究所 寧波 315100)

基于最小面積差的三維模型簡化算法

祁成武1張宇婷1舒振宇1胡 超1徐惠霞2

1(浙江大學(xué)寧波理工學(xué)院信息科學(xué)與工程學(xué)院 寧波 315100)

2(浙江萬里學(xué)院數(shù)學(xué)研究所 寧波 315100)

文章提出了一種基于面積誤差度量下的三維網(wǎng)格模型簡化方法。該方法通過極小化誤差目標(biāo)函數(shù)來簡化三角網(wǎng)格模型。算法首先對邊遍歷，計算每條邊的最小面積差；然后對面積差最小的邊進(jìn)行折疊；最后通過求解折疊邊的最小面積差，確定新點(diǎn)的坐標(biāo)。實(shí)驗(yàn)結(jié)果表明，該算法不僅可以反映局部表面幾何變化，還可使模型仍具有較高保真度。最后用實(shí)例說明了該方法的有效性。

三維模型簡化；QEM；最小面積差

1 引 言

在三維計算機(jī)圖形學(xué)中，一般采用多邊形模型來完成單個物體或整個三維環(huán)境的繪制。而三角網(wǎng)格模型依靠其運(yùn)算快速、數(shù)學(xué)表達(dá)簡單和便捷等特點(diǎn)脫穎而出，已成為當(dāng)前圖形軟件三維建模的基本單元，在圖形領(lǐng)域得到了廣泛的應(yīng)用[1]。但是，一個三維物體或場景的高精度三角面片的表示有時需要上百萬甚至上億個三角面片，這對于當(dāng)前的計算機(jī)，特別是顯示、傳輸和存儲系統(tǒng)帶來了很大的挑戰(zhàn)。在這種情況下，通常需要在模型的精度和計算機(jī)的計算能力之間進(jìn)行折衷。即保持模型在可允許的誤差范圍內(nèi)變化，運(yùn)用適當(dāng)?shù)暮喕夹g(shù)來減少原始模型幾何元素的數(shù)量，從而達(dá)到顯示和處理的要求和質(zhì)量。近年來，國內(nèi)外學(xué)者提出了很多網(wǎng)格模型簡化算法。這些算法使得大規(guī)模三維模型的處理、傳輸和渲染成為可能，具有重要的意義。本文提出了一種以三維網(wǎng)格模型最小面積變化值為目標(biāo)的三維模型簡化算法。實(shí)驗(yàn)結(jié)果表明，該算法能夠在簡化過程中較好地保持面積不變，具有一定的理論意義和實(shí)用價值。

現(xiàn)有的網(wǎng)格模型算法大多以特征值、體積和誤差等作為簡化的目標(biāo)。它們主要是在保持網(wǎng)格模型的形狀或外觀基本不變的前提下，盡量減少網(wǎng)格模型的細(xì)節(jié)信息及多邊形數(shù)目，從而提高網(wǎng)格模型的顯示、傳輸和計算效率。

在過去的十年里，學(xué)者們提出了很多簡化算法。其中一類算法[2-9]通過對網(wǎng)格模型進(jìn)行局部改變，每次改變先刪除一部分三角面片，然后用數(shù)量更少的三角面片代替，從而完成對三維模型的簡化操作。這類方法主要考慮保持模型的逼近誤差和拓?fù)浣Y(jié)構(gòu)，但并不強(qiáng)調(diào)三角網(wǎng)格的取樣或質(zhì)量。Garland[10]給出了有關(guān)這些方法的詳細(xì)介紹。

還有一類簡化算法[11-15]通過一種稱為細(xì)分連接性的特殊結(jié)構(gòu)實(shí)現(xiàn)模型的簡化。這類算法通過不斷重復(fù)將一個均勻的細(xì)分操作符運(yùn)用到一個較為粗糙的基礎(chǔ)網(wǎng)格上來完成簡化操作。它的主要優(yōu)點(diǎn)是可以提供不同級別的細(xì)節(jié)層次，從而使得多分辨率表達(dá)成為可能。但是，其基礎(chǔ)網(wǎng)格的構(gòu)造和頂點(diǎn)取樣并不容易控制。

另外一些算法與網(wǎng)格重劃有關(guān)。先輸入一個三角形網(wǎng)格，然后重新取樣，得到的新網(wǎng)格形狀分布不同但仍近似于同一網(wǎng)格曲面，并滿足某些質(zhì)量要求。運(yùn)用這種思路的算法[16-19]通常根據(jù)局部運(yùn)算符來進(jìn)行簡化(例如頂點(diǎn)或邊折疊)。還有一些方法[20-24]先將原始網(wǎng)格全局參數(shù)化，然后再在全部的參數(shù)空間中進(jìn)行重取樣，從而實(shí)現(xiàn)三維模型的簡化。這些方法達(dá)到了很好的效果，但也具有計算量大和數(shù)值不穩(wěn)定的缺點(diǎn)。一種改進(jìn)的思路是用局部參數(shù)化方法[25,26]來替代，如 Sifri等[27]與 Peyré 等[28]提出的基于測地路徑的網(wǎng)格重劃方法。算法結(jié)果使得三維網(wǎng)格模型表面上頂點(diǎn)達(dá)到一致性分布或者自適應(yīng)分布。Shu 等[29]通過結(jié)合紅綠細(xì)分技術(shù)，并構(gòu)造三維網(wǎng)格模型上的Voronoi 圖以及對偶 Delaunay 三角化，實(shí)現(xiàn)了對三維模型的高精度簡化。Alliez 和 Gotsman[30]給出了關(guān)于這些方法的綜述。

2 基于最小面積差的三維模型簡化

2.1 二次誤差度量(Quadric Error Metrics，QEM)算法[6]簡介

QEM 算法以新頂點(diǎn)到其相關(guān)平面的距離平方和最小為目標(biāo)，反復(fù)進(jìn)行邊折疊，最終達(dá)到簡化目的。邊折疊操作如圖1 所示，將一條邊的兩個端點(diǎn) s 和 t 折疊為一個新的頂點(diǎn) m，同時刪除褪化的三角形，這里 m 的位置并不一定是中點(diǎn)，此即一次邊折疊操作。

圖1 邊折疊過程Fig.1. The process of edge collapse

在三維空間中，令 v＝(x, y, z, 1)表示齊次坐標(biāo)下的頂點(diǎn)，則一個平面可以用方程 pv＝0 表示。其中，p＝(a, b, c, d)T，a, b, c 滿足 a2+b2+ c2＝1，是該平面單位法向量的三個分量；d 是固定距離。定義由邊折疊引起頂點(diǎn) v＝(vx, vy, vz, 1)T位置移動導(dǎo)致的二次誤差為：

其中，planes(v)表示頂點(diǎn) v 周圍 1-鄰域內(nèi)所有三角面片所在的平面集合；為 v 的二次誤差度量矩陣。因?yàn)槊總€初始頂點(diǎn)為周圍 1-鄰域內(nèi)三角形的交點(diǎn)，所以初始頂點(diǎn)的二次誤差為。當(dāng)有邊折疊操作為了讓產(chǎn)生的二次誤差最小，最佳的新頂點(diǎn)位置和二次誤差分別為：

該算法具有高效且平均誤差低等優(yōu)點(diǎn)。

2.2 加入面積差因素的 QEM 算法

在 QEM 算法中，可以發(fā)現(xiàn)有兩個關(guān)鍵的邊折疊因素：一個是如何對折疊邊排序，另一個是如何選擇新頂點(diǎn)的位置。這兩個因素決定了折疊簡化后是否能得到優(yōu)化的新網(wǎng)格。

網(wǎng)格折疊簡化實(shí)質(zhì)上可認(rèn)為是一個優(yōu)化問題。解決該問題的常用方法是定義目標(biāo)函數(shù)，簡化后的網(wǎng)格是目標(biāo)函數(shù)的最優(yōu)解，因此網(wǎng)格簡化的關(guān)鍵是如何建立該目標(biāo)函數(shù)。顯然，目標(biāo)函數(shù)應(yīng)是表達(dá)新舊兩個網(wǎng)格間差別的函數(shù)：通過極小化目標(biāo)函數(shù)得到新頂點(diǎn)的位置，并使新舊兩個網(wǎng)格間差別在某種意義下達(dá)到最小[31]。

2.2.1 定義面積差

本文的目標(biāo)函數(shù)采用網(wǎng)格的平方面積變化作為衡量模型間差別的標(biāo)準(zhǔn)：使得三維網(wǎng)格簡化前后的面積改變趨向于最小，同時又保持模型的特征基本不變。

圖2 表明了在確定折疊邊為 O1O2后，對邊O1O2的邊折疊并確立新點(diǎn) C 的過程。其中，S1為含點(diǎn) O1的三角面片的面積和；S2為含點(diǎn) O2的三角面片的面積和；SC為含新點(diǎn) C 的三角面片的面積和。 要使邊折疊前后模型表面積變化越小，即使的值越小。

圖2 邊折疊過程Fig.2. The process of edge collapse

2.2.2 子算法一：確定折疊邊

(1)按模型邊順序遍歷所有邊；

(2)對每條邊計算其最小面積差；

(3)得到最小的最小面積差，并以該邊為折疊邊；

(4)邊折疊后得到邊的順序、折疊邊的最小面積差及新點(diǎn)坐標(biāo)；

(5)一次邊折疊結(jié)束。

2.2.3 子算法二：確定邊折疊后新點(diǎn)的位置

圖3 為確定邊折疊后新點(diǎn)的最佳位置示意圖。

圖3 確定邊折疊后新點(diǎn)的最佳位置Fig.3. The optimal location of the new point after edge collapsing

如圖3(1)中所示，可得

3 實(shí)驗(yàn)與討論

3.1 實(shí)驗(yàn)結(jié)果

本節(jié)給出的實(shí)例是在 Intel(R) Core(TM)2 Duo CPU，2.00 G 內(nèi)存 PC 上用 Visual Studio 2012 實(shí)現(xiàn)的。本文提出的網(wǎng)格簡化算法基于三角形網(wǎng)格折疊，比較的模型實(shí)例是模型 Eight。

圖4 給出了本文算法在 Eight 模型上的簡化效果圖。從圖4 可以看出，本文算法選擇邊折疊前后面積變化小的邊開始折疊。同時也可以看出，該模型數(shù)據(jù)有著明顯的簡化效果，證明了該算法的可行性和有效性。

3.2 面積對比

圖4 本文算法在 Eight 模型上的簡化效果圖Fig.4. The effect of the simpli fi ed Eight model by using our method

圖5 Seahorse 模型簡化 90% 對比圖Fig.5. The comparison results of the 90% simpli fi ed Seahorse model by using our method and the QEM algorithm

圖6 Seahorse 模型簡化 80% 對比圖Fig.6. The comparison results of the 80% simpli fi ed Seahorse model by using our method and the QEM algorithm

為對比模型簡化后的表面積維持效果，本文在模型 Seahorse(5042 個頂點(diǎn)，9999 個三角面片)上進(jìn)行了算法實(shí)驗(yàn)和比較 ，結(jié)果見圖5 和圖6。該模型的點(diǎn)較為均勻，可以看出在采集點(diǎn)的時候?qū)儆诰鶆蚍植疾杉姆椒?。圖5 和圖6 顯示，較為平整的面主要集中在 Seahorse 模型的肚子部位。從圖5 和圖6 中的(2)小圖，即本文算法簡化后的效果圖，可以發(fā)現(xiàn)，Seahorse 肚子上明顯點(diǎn)減少了，而圖5 和圖6 中的(3)小圖中，Seahorse的肚子上點(diǎn)無明顯減少。

從表1 可以看出，對三維網(wǎng)格模型進(jìn)行相同比例的簡化后，本文方法產(chǎn)生的表面積誤差要遠(yuǎn)小于 QEM 算法。

第二個模型實(shí)例是模型 RockerArm(500 個頂點(diǎn)，1000 個三角面片)。與第一個的區(qū)別在于，該模型數(shù)據(jù)較小，可以考察在較小模型下，本文算法的面積誤差有效性能否保持。

對 RockerArm 模型分別運(yùn)用本文算法與QEM 算法，其模型簡化對比如圖7 所示，網(wǎng)格簡化表面積維持率比較如表2 所示。

表1 Seahorse 模型簡化表面積維持率比較Table1. A comparison between the retention rate of the surface area after simplifying the model of Seahorse from using the QEM and our method

圖7 RockerArm 模型簡化對比圖Fig.7. The comparison results of the RockerArm model

從表2 可以看出，對網(wǎng)格進(jìn)行相同比例的簡化后，本文方法產(chǎn)生的表面積誤差要遠(yuǎn)小于QEM 算法。

同時，當(dāng)模型數(shù)據(jù)很少時，本文算法對模型的特征保持率較低。但從另一面來講，運(yùn)用到實(shí)際中，如果模型較小，那其需要簡化的概率也極小。一般只有當(dāng)模型數(shù)據(jù)非常大時，才需要運(yùn)用到簡化算法。

3.3 距離誤差對比

本文在 Seahorse 模型(5042 個頂點(diǎn)，9999 個三角面片)上對本文算法和 QEM 算法簡化結(jié)果的Hausdorff 距離進(jìn)行了對比。

為了比較兩種方法在簡化過程中網(wǎng)格模型的 Hausdorff 距離作為誤差標(biāo)準(zhǔn)進(jìn)行比較，Hausdorff 距離由下式定義，定義如下：

其中，d(pA, pB)為點(diǎn)與點(diǎn)之間的距離。

從表3 可以看出，運(yùn)用這兩種算法分別對網(wǎng)格進(jìn)行相同比例的簡化后，本文算法產(chǎn)生的平方體積誤差要大于采用 QEM 算法的所產(chǎn)生的平方體積誤差。雖然如此，但是從 Hausdorff 距離的比較結(jié)果來看，在簡化比率不是很大的情況下，本文算法具有較好的簡化效果。

3.4 運(yùn)行時間對比

使用模型 RockerArm 來進(jìn)行運(yùn)行時間對比。QEM 作為模型簡化中常用的方法，其主要原因就是其簡化效率高，而簡化后模型表面特征保持良好。本文算法與 QEM 網(wǎng)格簡化運(yùn)行時間比較如表4 所示。

從表4 可以看出，本文算法和 QEM 算法的運(yùn)行時間較為接近。說明本文算法具有較好的運(yùn)算效率和可操作性。

表2 RockerArm 模型簡化表面積維持率比較Table2. A comparison of the retention rate of the surface area after simplifying the RockerArm by using the QEM algorithm and our method

表3 Seahorse 模型簡化的 Hausdorff 距離比較Table3. A comparison of the Hausdorff distances after simplifying the model of Seahorse by using the QEM algorithm and our method

表4 網(wǎng)格簡化運(yùn)行時間比較Table4. A comparison of the running time of mesh simpli fi cation by using the QEM algorithm and our method

4 結(jié) 論

本文提出了一種基于面積誤差度量下的三維網(wǎng)格模型簡化方法。該方法通過極小化誤差目標(biāo)函數(shù)來簡化三角網(wǎng)格模型：首先對模型中所有邊進(jìn)行遍歷，并對每條邊計算其最小面積差，折疊其中最小結(jié)果的邊，之后通過求解最小面積差，確定新點(diǎn)的坐標(biāo)。從代碼編寫后生成的效果圖可以看出，改進(jìn)后的算法不僅可以反映局部表面幾何變化，同時模型仍具有較高保真度。本文最后用實(shí)例說明本文方法的有效性。

隨著三維打印等技術(shù)的出現(xiàn)，更多的實(shí)際應(yīng)用場合為了追求三維效果，開始使用三維模型，三維模型簡化也會有越來越多的應(yīng)用機(jī)會。從目前國內(nèi)外研究及應(yīng)用來看，雖然已經(jīng)有大量網(wǎng)格簡化的相關(guān)研究工作，但是還沒有一種適合所有應(yīng)用的網(wǎng)格簡化，絕大多數(shù)算法都是針對具體問題提出的。另外不管哪種網(wǎng)格簡化算法都有其優(yōu)劣性，也許在不久的將來，隨著硬件軟件的更新?lián)Q代，能實(shí)現(xiàn)一種智能算法，可以判斷模型簡化的傾向性并能將多種經(jīng)典的簡化算法融合在一起，同時仍能保持高速運(yùn)算。

[1] 丁大偉, 邵新宇, 邱浩波, 等. 多邊形網(wǎng)格模型簡化算法綜述 [J]. 機(jī)械設(shè)計與制造, 2007, 9: 181-183.

[2] Schroeder WJ, Zarge JA, Lorensen WE. Decimation of triangle meshes [C] // Proceedings of the 19th Annual Conference on Computer Graphics and Interactive Techniques, 1992: 65-70.

[3] Cohen J, Varshney A, Manocha D, et al. Simpli fi cation envelopes [C] // Proceedings of the 23rd Annual Conference on Computer Graphics and Interactive Techniques, 1996: 119-128.

[4] Hoppe H. Progressive meshes [C] // Proceedings of the 23rd Annual Conference on Computer Graphics and Interactive Techniques, 1996: 99-108.

[5] El-Sana J, Varshney A. Controlled simplification of genus for polygonal models [C] // Proceedings of the 8th Conference on Visualization, 1997: 403-410.

[6] Garland M, Heckbert PS. Surface simplification using quadric error metrics [C] // Proceedings of the 24th Annual Conference on Computer Graphics and Interactive Techniques, 1997: 209-216.

[7] Lindstrom P, Turk G. Fast and memory efficient polygonal simplification [C] // Proceedings of the Conference on Visualization, 1998: 279-286.

[8] Kobbelt L, Campagna S, Seidel H. A general framework for mesh decimation [C] // Proceedings of Graphics Interface, 1998: 43-50.

[9] Zelinka S, Garland M. Permission grids: practical, error-bounded simpli fi cation [J]. ACM Transactions on Graph, 2002, 21(2): 207-229.

[10] Garland M. Multiresolution modeling: survey & future opportunities [C] // State of the Art Reports, 1999: 111-131.

[11] Eck M, DeRose T, Duchamp T, et al. Multiresolu-tion analysis of arbitrary meshes [C] // Proceedings of the 22nd Annual Conference on Computer Graphics and Interactive Techniques, 1995: 173-182.

[12] Lee AWF, Sweldens W, Schr?der P, et al. MAPS: multiresolution adaptive parameterization of surfaces [C] // Proceedings of the 25th Annual Conference on Computer Graphics and Interactive Techniques, 1998: 95-104.

[13] Kobbelt LP, Vorsatz J, Labsik U, et al. A shrink wrapping approach to remeshing polygonal surfaces [J]. Computer Graphics Forum, 1999, 18(3): 119-130.

[14] Guskov I, Vidimce K, Sweldens W, et al. Normal meshes [C] // Proceedings of the 27th Annual Conference on Computer Graphics and Interactive Techniques, 2000: 95-102.

[15] Hormann K, Labsik U, Greiner G. Remeshing triangulated surfaces with optimal parameterizations [J]. Computer-Aided Design, 2001, 33(11): 779-788.

[16] Turk G. Retiling polygonal surfaces [J]. ACM SIGGRAPH Computer Graphics, 1992, 26(2): 55-64.

[17] Hoppe H, DeRose T, Duchamp T, et al. Mesh optimization [C] // Proceedings of the 20th Annual Conference on Computer Graphics and Interactive Techniques, 1993: 19-26.

[18] Frey PJ, Borouchaki H. Geometric surface mesh optimization [J]. Computing and Visualization in Science, 1998, 1(3): 113-121.

[19] Frey PJ. About surface remeshing [C] // Proceedings of the 9th International Meshing Roundtable, 2000: 123-136.

[20] Alliez P, Meyer M, Desbrun M. Interactive geometry remeshing [J]. ACM Transactions on Graphics, 2002, 21(3): 347-354.

[21] Alliez P, Cohen-Steiner D, Devillers O, et al. Anisotropic polygonal remeshing [J]. ACM Transactions on Graphics, 2003, 22(3): 485-493.

[22] Alliez P, Verdiere EC, Devillers O, et al. Isotropic surface remeshing [C] // International Conference on Shape Modeling and Applications, 2003: 49-58.

[23] Alliez P, Verdiere EC, Devillers O, et al. Centroidal Voronoi diagrams for isotropic surface remeshing [J]. Graphical Models, 2005, 67(3): 204-231.

[24] Gu X, Gortler SJ, Hoppe H. Geometry images [J]. ACM Transactions on Graphics, 2002, 21(3): 355-361.

[25] Surazhsky V, Gotsman C. Explicit surface remeshing [C] // Proceedings of the 2003 Eurographics/ACM SIGGRAPH Symposium on Geometry Processing, 2003: 20-30.

[26] Surazhsky V, Alliez P, Gotsman C. Isotropic remeshing of surfaces: a local parameterization approach [C] // Proceedings of the 12th International Meshing Roundtable, 2003: 215-224 .

[27] Sifri O, Sheffer A, Gotsman C. Geodesic-based surface remeshing [C] // International Meshing Roundtable, 2003: 189-199.

[28] Peyré G, Cohen L. Geodesic remeshing using front propagation [J]. International Journal of Computer Vision, 2006, 69(1): 145-156.

[29] Shu Z, Wang G, Dong C. Adaptive triangular mesh coarsening with centroidal Voronoi tessellations [J]. Journal of Zhejiang University Science A, 2009, 10(4): 535-545.

[30] Alliez P, Gotsman C. Recent advances in compression of 3D meshes [C] // Proceedings of the Symposium on Multiresolution in Geometric Modeling, 2003: 3-26.

[31] 周元峰, 張彩明, 賀平. 體積平方度量下的特征保持網(wǎng)格簡化方法 [J]. 計算機(jī)學(xué)報, 2009, 32(2): 205-206.

3D Model Simpli fi cation Algorithm Based on Minimum Surface Area Error

QI Chengwu1ZHANG Yuting1SHU Zhenyu1HU Chao1XU Huixia2
1( School of Information Science and Engineering, Ningbo Institute of Technology, Zhejiang University, Ningbo 315100, China )
2(Institute of Mathematics, Zhejiang Wanli University, Ningbo 315100, China )

A new algorithm for 3D mesh simplification based on minimum surface area error was presented in this paper. The algorithm simpli fi es 3D models by minimizing an error objective function. Firstly, the algorithm used the edge traversal algorithm for calculating the minimum area of each edge. Then the vertex coordinates of those new points were determined by fi nding the minimum surface area error. The results of our experiment show that our algorithm can not only re fl ect the local surface geometry changes, but also keep the model in a relatively high fi delity. Experimental results for the effectiveness of the algorithm were also presented.

3D model simpli fi cation; QEM; minimum surface area error

TP 391.72

A

2014-07-22

國家自然科學(xué)基金(11226328，61273332，61303144)；浙江省自然科學(xué)基金(LY13F020018)；寧波市自然科學(xué)基金(2013A610096)

祁成武，碩士研究生，研究方向?yàn)橛嬎銠C(jī)圖形學(xué)；張宇婷，本科生，研究方向?yàn)橛嬎銠C(jī)圖形學(xué)；舒振宇(通訊作者)，博士，副教授，研究方向?yàn)橛嬎銠C(jī)圖形學(xué)和計算機(jī)輔助幾何設(shè)計等，E-mail：shuzhenyu@163.com；胡超，博士，教授，博士生導(dǎo)師，三江學(xué)者特聘教授，研究方向?yàn)樽詣踊?、機(jī)器人控制和傳感器技術(shù)等；徐惠霞，博士，副教授，研究方向?yàn)橛嬎銠C(jī)輔助幾何設(shè)計。