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

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

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

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

1 拓?fù)潢P(guān)系重構(gòu)

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

圖 1 半邊拓?fù)浜?jiǎn)化結(jié)構(gòu)Fig.1 Simplified structure of half topology

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

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

2 簡(jiǎn)化算法描述

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

2.1 邊折疊簡(jiǎn)化

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

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

對(duì)于折疊代價(jià)的計(jì)算， 引用Garland[2]二次誤差測(cè)度折疊簡(jiǎn)化算法， 將點(diǎn)到平面距離的平方作為誤差測(cè)度， 具體步驟如下：

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

2) 計(jì)算二項(xiàng)式頂點(diǎn)初始代價(jià)Δ(v)=vTQv;

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

點(diǎn)到平面距離的平方

d2(v)=Q(v)=

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

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

2.2 改進(jìn)算法

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

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

Garland二次誤差算法是對(duì)整個(gè)網(wǎng)格進(jìn)行簡(jiǎn)化， 網(wǎng)格模型由n個(gè)三角面片組成， 經(jīng)分層后得到m個(gè)層， 由圖 3 可以看出， 切片厚度較大時(shí)， 小的三角面片沒有被切中， 造成模型特征的丟失， 切片厚度較小時(shí)， 層數(shù)增多， 降低算法的效率. 因而， 使用基于切片厚度因子加權(quán)的網(wǎng)格簡(jiǎn)化， 需考慮一個(gè)權(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)在模型拓?fù)渲亟〞r(shí)可以快速構(gòu)建出網(wǎng)格模型， 三角形頂點(diǎn)、 邊和面的簡(jiǎn)化要充分考慮該頂點(diǎn)到相鄰三角形平面的距離， 通過(guò)分析距離和最終分層切片的厚度關(guān)系是否影響到外部輪廓特征來(lái)決定簡(jiǎn)化操作. 將點(diǎn)到相鄰平面距離的平方(d2)作為誤差測(cè)度， 引入切片厚度因子Z， 改變折疊代價(jià)， 從而減少階梯面的形成， 達(dá)到更好地保留模型表面細(xì)微特征的要求.

誤差測(cè)度公式為

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

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

2.4 邊界處理

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

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

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

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

表 1 算法比較

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

圖 4 牛模型簡(jiǎn)化效果Fig.4 Simplified effect of cow model

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

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

圖 5 兔子模型簡(jiǎn)化效果Fig.5 Simplified effect of bunny model

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

4 結(jié) 論

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

[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)格模型保特征簡(jiǎn)化方法[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]呂書明， 張明磊， 孫樹立. 基于簡(jiǎn)化和細(xì)分技術(shù)的三角形網(wǎng)格拓?fù)鋬?yōu)化方法[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)， 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í)二次誤差簡(jiǎn)化算法[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)， 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)格簡(jiǎn)化方法[J]. 計(jì)算機(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ìn)的二次誤差測(cè)度簡(jiǎn)化算法[J]. 桂林電子科技大學(xué)學(xué)報(bào)， 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é)合邊折疊和局部?jī)?yōu)化的網(wǎng)格簡(jiǎn)化算法[J]. 計(jì)算機(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)格模型簡(jiǎn)化算法[J].計(jì)算機(jī)工程與設(shè)計(jì)， 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.