切片厚度加權(quán)的二次誤差測度網(wǎng)格簡化算法

武 帥， 黃慶學(xué)， 李宏杰， 張 弛

(1. 太原科技大學(xué) 電子信息工程學(xué)院, 山西 太原 030024； 2. 太原重型機械裝備協(xié)同創(chuàng)新中心, 山西 太原 030024；3. 山西省互聯(lián)網(wǎng)+3D打印協(xié)同創(chuàng)新中心, 山西 太原 030024； 4. 太原理工大學(xué) 機械工程學(xué)院， 山西 太原 030024)

STL(Stereolithography)是快速成型系統(tǒng)應(yīng)用的標準文件類型之一， 是利用三角網(wǎng)格來顯示三維模型. 目前廣泛使用的三維數(shù)據(jù)獲得方式有3種： 三維建模、 激光掃描和人像DIY. 隨著衛(wèi)星、 掃描儀、 圖像儀器等先進技術(shù)的不斷完善和發(fā)展， 人們可以得到越來越復(fù)雜， 越來越精細的模型， 而高精度、 強復(fù)雜的模型所需的三角面片數(shù)量越多， 對系統(tǒng)的要求也就越高， 因此對三角網(wǎng)格進行簡化是必不可少的， 這也是快速重建的核心.

在上述研究的基礎(chǔ)上， 本文提出一種切片厚度加權(quán)的二次誤差測度網(wǎng)格簡化算法. 采用半邊拓撲結(jié)構(gòu)進行模型重構(gòu)， 減少模型頂點數(shù)及三角面片數(shù)， 提高計算性能， 在二次誤差測度算法的基礎(chǔ)上， 引入切片厚度加權(quán)， 準確反映模型表面的細微特征.

1 拓撲關(guān)系重構(gòu)

在實際的應(yīng)用中高復(fù)雜度的網(wǎng)格模型會帶來諸多不變， 比如： 在動漫電影中， 網(wǎng)格越多， 最終呈現(xiàn)的速度就越慢； 在表達遠近物體時， 遠處的模型需要模糊一點， 顯示模型的全部網(wǎng)格不僅顯得多余， 還增加了系統(tǒng)的內(nèi)存， 影響計算性能； 在虛擬世界中， 場景的連續(xù)轉(zhuǎn)換更是對網(wǎng)格有極高的要求， 為了解決這些問題， 要充分利用網(wǎng)格的簡化與重建， 降低網(wǎng)格復(fù)雜度， 提高響應(yīng)速度.

圖 1 半邊拓撲簡化結(jié)構(gòu)Fig.1 Simplified structure of half topology

利用半邊數(shù)據(jù)結(jié)構(gòu)實現(xiàn)網(wǎng)格模型的簡化需要獲取三維模型網(wǎng)格頂點、 面以及半邊數(shù)據(jù)， 對每一個頂點存儲一個外向半邊(半邊起點)， 對每一個面存儲一個邊界半邊， 對每一個半邊確定半邊的終點、 半邊所屬的面、 半邊所在面的下一個半邊、 半邊對應(yīng)相反的半邊以及相反半邊所在面的上一個半邊.

半邊結(jié)構(gòu)在點、 線、 面鄰接關(guān)系方面有良好的特性， 對網(wǎng)格簡化操作有很好的效果， 只需要簡單的定位就可以進行重構(gòu)， 效率更高， 減少了三角形的頂點數(shù)和三角面片數(shù)， 大大地縮短了時間， 提高了計算性能.

2 簡化算法描述

三角網(wǎng)格的簡化是把用三角形網(wǎng)格表示的模型用一個近似模型來代替， 讓近似模型基本保持原模型的大致形狀與結(jié)構(gòu)， 但頂點數(shù)目和三角形數(shù)目明顯少于原始模型. 誤差測度是通過量化模型輸入、 輸出之間的差異， 控制網(wǎng)格簡化的方向和力度， 使最終生成的模型誤差在用戶允許誤差范圍之內(nèi)， 因而其在網(wǎng)格簡化中被廣泛使用.

2.1 邊折疊簡化

二次誤差測度準則存在于多種網(wǎng)格簡化算法中， 該算法生成的網(wǎng)格質(zhì)量較好， 簡化速度也較快， 其中邊折疊簡化方法使用較多， 這是一種幾何元素刪除法， 研究的重點是如何選擇新頂點， 也就是如何保證簡化誤差最小. 邊折疊簡化方法是按照一定的準則對網(wǎng)格模型中的邊計算折疊誤差， 根據(jù)折疊代價由小到大的順序進行折疊操作， 折疊簡化的核心是從網(wǎng)格中選定一對頂點v1,v2， 將兩者合為一個新的頂點v′， 然后將與v1,v2相連的邊連接到新的頂點v′上， 將關(guān)聯(lián)的三角面片刪除， 最終得到簡化模型， 如圖 2 所示.

圖 2 邊折疊操作Fig.2 Edge collapse

對于折疊代價的計算， 引用Garland[2]二次誤差測度折疊簡化算法， 將點到平面距離的平方作為誤差測度， 具體步驟如下：

1) 將頂點定義為v=[x,y,z,1]T， 并為每個頂點定義一個4×4矩陣Q;

2) 計算二項式頂點初始代價Δ(v)=vTQv;

3) 頂點v1,v2的有效收縮點v′的選擇以及邊折疊代價Δ(v)=v′T(Q1+Q2)v′，其中：Q1,Q2為折疊前v1,v2的初始矩陣；v′為折疊后的新頂點.

點到平面距離的平方

d2(v)=Q(v)=

∑(pTv)2=∑(vTp)(pTv)=

∑vT(ppT)v=vT(∑Kp)v,

2.2 改進算法

Garland二次誤差算法中誤差測度Q是對所有三角面片進行求和得到的， 誤差測度標準過于單一， 沒有很好地反映出模型重構(gòu)后表面的細微特征， 因此不少學(xué)者在這方面提出了自己的方案. 張文新等[9]提出將頂點曲率和三角形面積引入二次誤差測度中， 較好地保留模型的細節(jié)特征. 劉峻等[10]提出將邊折疊與局部優(yōu)化進行結(jié)合的網(wǎng)格簡化算法， 將頂點近似曲率引入到二次誤差測度中， 對三角網(wǎng)格進行局部優(yōu)化處理， 減少了狹長三角形的數(shù)量， 但幾何誤差有一定的限制. 李紅波等[11]提出采用八叉樹劃分模型， 在經(jīng)典二次誤差測度的基礎(chǔ)上， 引入頂點法向量夾角與邊長作為權(quán)值的模型簡化， 較好地保留了模型表面的細微特征， 但時間復(fù)雜度基本沒有改變. V.Ungvichian等[12]提出的使用主曲率和方向進行網(wǎng)格簡化， 在簡化到較低分辨時， 模型的部分細節(jié)特征丟失嚴重. JL Tseng等[13]提出的基于擴展形狀算子的三維曲面網(wǎng)格簡化， 在二次誤差測度算法上加以改進， 雖然其細節(jié)特征保持能力較強， 但是簡化模型的狹長三角形較多.

在二次誤差測度網(wǎng)格簡化算法中， 邊折疊的順序和新頂點的位置是由原始模型三角面片的二次型誤差決定的， 因此在每個三角面片的二次型誤差上乘上權(quán)值將會改變邊折疊的順序， 影響新頂點的位置.

Garland二次誤差算法是對整個網(wǎng)格進行簡化， 網(wǎng)格模型由n個三角面片組成， 經(jīng)分層后得到m個層， 由圖 3 可以看出， 切片厚度較大時， 小的三角面片沒有被切中， 造成模型特征的丟失， 切片厚度較小時， 層數(shù)增多， 降低算法的效率. 因而， 使用基于切片厚度因子加權(quán)的網(wǎng)格簡化， 需考慮一個權(quán)因子Z， 滿足隨模型表面輪廓變化而變化.

Z=Zmin+(Zmax-Zmin)sinα,

式中：α為單位法向量與切平面Z軸的夾角；Zmin為最小切片厚度；Zmax為最大切片厚度.

圖 3 分層切片F(xiàn)ig.3 Slicing

2.3 算法描述

采用半邊數(shù)據(jù)結(jié)構(gòu)在模型拓撲重建時可以快速構(gòu)建出網(wǎng)格模型， 三角形頂點、 邊和面的簡化要充分考慮該頂點到相鄰三角形平面的距離， 通過分析距離和最終分層切片的厚度關(guān)系是否影響到外部輪廓特征來決定簡化操作. 將點到相鄰平面距離的平方(d2)作為誤差測度， 引入切片厚度因子Z， 改變折疊代價， 從而減少階梯面的形成， 達到更好地保留模型表面細微特征的要求.

誤差測度公式為

Q′(v)=(∑Z·Qi)(v).

算法實現(xiàn)的一般步驟如下： ① 讀取三維網(wǎng)格模型數(shù)據(jù)， 并構(gòu)建半邊數(shù)據(jù)結(jié)構(gòu)； ② 提取模型Z軸最高點和最低點的坐標值； ③ 按照最低點坐標值進行排序； ④ 計算各邊的二次誤差矩陣； ⑤ 計算邊折疊代價并構(gòu)造新頂點； ⑥ 將折疊代價按照從小到大的順序進行排列； ⑦ 簡化掉折疊代價的最小邊； ⑧ 判斷最終簡化是否達到要求， 若達到， 則簡化結(jié)束， 若沒有達到， 返回第⑦步.

2.4 邊界處理

模型簡化時要先確定三角網(wǎng)格模型的邊界， 在半邊數(shù)據(jù)結(jié)構(gòu)中， 一個邊應(yīng)當對應(yīng)兩個半邊， 如果某一條邊只對應(yīng)一個半邊， 則可以判定該邊是一個邊界邊. 根據(jù)邊界邊尋找正確的邊界面. 以面為特征， 構(gòu)建STL模型的面法向量索引矩陣， 使得模型的邊界得以很好的保持.

3 實驗結(jié)果分析

在一臺普通的PC(2.60 GHz CPU， 4.00 GB內(nèi)存， Windows 7系統(tǒng))上對本文算法進行驗證， 測試幾個STL文件格式的實例. 分別使用Garland網(wǎng)格簡化算法、 文獻[9]簡化算法與本文的改進QEM網(wǎng)格簡化算法進行對比.

表 1 給出了Garland算法與本文算法在運行方面的比較.

表 1 算法比較

圖 4 所示的是對頂點數(shù)為3 474， 面片數(shù)為5 804 的牛模型的簡化.

圖 4 牛模型簡化效果Fig.4 Simplified effect of cow model

圖 4(a) 所示的是牛的原始模型， 圖4(b)～(d)所示的是采用Garland算法對牛模型的簡化， 圖 4(e)～(g) 所示的是采用文獻[9]算法對牛模型的簡化， 圖 4(h)～(j) 所示的是采用本文算法對牛模型的簡化， 簡化剩余的三角面片數(shù)分別為3 000， 1 484以及618.

圖 5 所示的是對頂點數(shù)為35 016， 面片數(shù)為69 451的兔子模型的簡化. 由于兔子模型三角面片數(shù)較多不易觀察， 對每一個簡化算法使用光照顯示. 圖5(a)所示的是兔子的原始模型， 圖5(b)～(d) 所示的是采用Garland算法對兔子模型的簡化， 圖5(e)～(g)所示的是采用文獻[9]算法對兔子模型的簡化， 圖5(h)～(j)所示的是采用本文算法對兔子模型的簡化， 簡化剩余的三角面片數(shù)分別為34 635， 13 800以及3 412.

圖 5 兔子模型簡化效果Fig.5 Simplified effect of bunny model

從圖 5 可以看出， 在相同的簡化條件下， 本文算法比Garland簡化算法能更好地反映模型的細節(jié)特征， 相比文獻[9]簡化算法效率更高. 在經(jīng)過大規(guī)模的簡化后， 本文算法仍能保持模型的整體形狀. 圖4中在大規(guī)模簡化條件下， 可以看到采用Garland簡化算法牛的兩個角部分特征丟失， 采用文獻[9]簡化算法雖然細節(jié)特征有所保持， 但會出現(xiàn)少量狹長的三角面片， 采用本文算法三角面片分布較合理， 在平坦的地方三角面片較少， 在變化大的地方三角面片較多； 圖5中在大規(guī)模簡化條件下， 可以看到采用Garland簡化算法兔子的眼睛部位有點模糊， 采用文獻[9]簡化算法兔子的腳部分細節(jié)特征不完整， 這些信息在分辨率低時就很容易丟失， 采用本文算法細節(jié)特征基本還可以較好地體現(xiàn)出來.

4 結(jié) 論

從實驗結(jié)果可以看出， 與Garland算法相比， 采用半邊數(shù)據(jù)結(jié)構(gòu)使得模型在簡化時可以直接確定鄰接關(guān)系， 使得拓撲重構(gòu)的速度更快； 采用點到相鄰平面距離的平方作為誤差測度， 引入切片厚度加權(quán)來簡化模型， 可以較好地反應(yīng)模型的細節(jié)特征， 降低算法運行時間， 同時保持了模型較好的視覺效果， 提高了計算性能.

[1]Hoppe H, DeRose T, Duchamp T, et al. Mesh optimization[J]. ACM Siggraph Computer Graphics, 1993, 27： 19-26.

[2]Garland M, Heckbert P S. Surface simplification using quadric error metrics[C]. Proceedings of the 24th Annual Conference on Computer Graphics and Interative Techniques, 1997： 209-216.

[3]Ozaki H, Kyota F, Kanai T. Out-of-core framework for QEM-based mesh simplification[C]. Eurographics Symposium on Parallel Graphics & Visualization Eurographics Association, 2015： 87-96.

[4]Jia Q, Liu Y, Gu X. Edge collapse mesh simplification algorithm based on detail features preserving[J]. Journal of Computational Information Systems, 2014,10(7)： 2883-2890.

[5]段黎明， 邵輝， 李中明. 高效率的三角網(wǎng)格模型保特征簡化方法[J]. 光學(xué)精密工程， 2017, 25(2)： 460-468. Duan Liming, Shao Hui, Li Zhongming. Simplification method for feature preserving of efficient triangular mesh model[J]. Optics and Precision Engineering, 2017, 25(2)： 460-468. (in Chinese)

[6]呂書明， 張明磊， 孫樹立. 基于簡化和細分技術(shù)的三角形網(wǎng)格拓撲優(yōu)化方法[J]. 計算機輔助設(shè)計與圖形學(xué)學(xué)報， 2014, 26(8)： 1225-1231. Lü Shuming, Zhang Minglei, Sun Shuli. Topological optimization for triangular mesh based on simplification and subdivision[J]. Journal of Computer Aided Design and Computer Graphics, 2014, 26(8)： 1225-1231. (in Chinese)

[7]易兵， 劉振宇. 邊界特征保持的網(wǎng)格模型分級二次誤差簡化算法[J]. 計算機輔助設(shè)計與圖形學(xué)學(xué)報， 2012, 24(4)： 427-434. Yi Bing, Liu Zhenyu. New quadric metric for simplifying meshes to retain the feature edge[J]. Journal of Computer-Aided Design and Computer Graphics, 2012, 24(4)： 427-434. (in Chinese)

[8]張霞， 段黎明， 劉璐. 保持特征的高質(zhì)量三角網(wǎng)格簡化方法[J]. 計算機集成制造系統(tǒng)， 2014, 20(3)： 486-493. Zhang Xia, Duan Liming, Liu Lu. High quality triangular mesh simplification with feature-preserving[J]. Computer Integrated Manufacturing Systems, 2014, 20(3)： 486-493. (in Chinese)

[9]張文新， 溫佩芝， 黃佳， 等. 一種改進的二次誤差測度簡化算法[J]. 桂林電子科技大學(xué)學(xué)報， 2015, 35(1)： 59-63. Zhang Wenxin, Wen Peizhi, Huang Jia, et al. An improved quadric error metric mesh simplification algorithm[J]. Journal of Guilin University of Electronic Technology, 2015, 35(1)： 59-63. (in Chinese)

[10]劉峻， 范豪， 孫宇， 等. 結(jié)合邊折疊和局部優(yōu)化的網(wǎng)格簡化算法[J]. 計算機應(yīng)用， 2016, 36(2)： 535-540. Liu Jun, Fan Hao, Sun Yu, et al. Mesh simplification algorithm combined with edge collapse and local optimization[J]. Journal of Computer Applications, 2016, 36(2)： 535-540. (in Chinese)

[11]李紅波， 劉昱晟， 吳渝， 等. 基于二次誤差度量的大型網(wǎng)格模型簡化算法[J].計算機工程與設(shè)計， 2013, 34(9)： 3158-3162. Li Hongbo, Liu Yusheng, Wu Yu, et al. Simplification algorithm for large mesh models based on quadric error metrics[J]. Computer Engineering and Design, 2013, 34(9)： 3158-3162. (in Chinese)

[12]Ungvichian V, Kanongchaiyos P. Mesh simplification method using principal curvatures and directions[J]. Computer Modeling in Engineering & Sciences, 2011, 77(3)： 201-219.

[13]Tseng J, Lin Y. 3D Surface simplification based on extended shape operator[J]. Wseas Transactions on Computers, 2013, 12(8)： 320-330.