面向VR建模的網(wǎng)格簡化算法優(yōu)化研究

張文靜，劉茵，張孟，李明亮

（1.北京農(nóng)業(yè)職業(yè)學(xué)院信息技術(shù)系，北京，102442；2.河北地質(zhì)大學(xué)信息工程學(xué)院，河北石家莊，050031; 3.河北省智能傳感物聯(lián)網(wǎng)技術(shù)工程研究中心，河北石家莊，050031）

0 引言

隨著VR技術(shù)的飛速發(fā)展，三維模型逐漸精細(xì)化，文件的數(shù)據(jù)量過于龐大，這使虛擬現(xiàn)實系統(tǒng)的實時響應(yīng)機(jī)制緩慢，不利于進(jìn)行人機(jī)交互[1]。為了優(yōu)化虛擬現(xiàn)實系統(tǒng)引入網(wǎng)格簡化思想。網(wǎng)格簡化的關(guān)鍵是找到并刪除對模型外觀影響較小的三角面片，保留明顯反映模型外觀特征的三角面片。Garland提出了二次誤差測度的概念（QEM算法）來控制簡化誤差[2]，但此種方法無法保留模型原始信息，簡化質(zhì)量不高；而Hoppe則提出了漸進(jìn)網(wǎng)格(Progressive Mesh，PM)算法進(jìn)行迭代簡化[3]，但該算法計算量大、對機(jī)器性能要求太高，普適性不高。本文將PM算法簡化思想與二次誤差測度方法相結(jié)合，提出一種新的可保留模型外觀特征的簡化方法。

1 PM算法簡介

PM算法主要內(nèi)容為漸進(jìn)網(wǎng)格思想。通過遞歸迭代實現(xiàn)邊塌縮與點分裂的過程，通過不斷地進(jìn)行邊塌縮操作使網(wǎng)格簡化，并在簡化過程中記錄原始頂點和新頂點的位置信息，以及頂點間連接關(guān)系的變動情況。

Hoppe在其思想中提出邊塌縮概念：三角網(wǎng)格中有一條三角形邊uv，u和v分別是三角邊的兩個端點，A和B是以uv為公共邊的兩個三角形。當(dāng)邊uv為塌縮邊時，用頂點v來替換頂點u，并使其它鄰居頂點與新頂點連接，然后把頂點u及相關(guān)信息刪除。這就完成了一次目標(biāo)三角邊塌縮。進(jìn)行一次三角邊塌縮，可以刪除一個頂點、三條邊和兩個三角形面片。通過反復(fù)選擇刪減，最終就會得到一定要求的簡化網(wǎng)格。

2 基于邊塌縮的改進(jìn)算法

2.1 誤差公式的選擇與新頂點的確定

本文采用Garland提出的二次誤差測度方法(QEM方法)作為基礎(chǔ)誤差控制。在模型的三角面片網(wǎng)格中，質(zhì)量最好的網(wǎng)格面片為等邊三角形，一個三角形正則度越高，越接近等邊三角形。為了優(yōu)化簡化網(wǎng)格質(zhì)量，避免在網(wǎng)格簡化過程中出現(xiàn)狹長三角形，本研究在二次誤差測度的基礎(chǔ)上引入三角形正則度作為調(diào)節(jié)因子，來調(diào)節(jié)塌縮誤差。三角形的正則度表示為:

其中l(wèi)1、l2、l3分別為三角形由短到長的三條邊，當(dāng)re=1時，三角形正則度最好，此時該三角形為等邊三角形。當(dāng)re=0時，三角形的正則度最差，此時三角形退化成為了一條直線。根據(jù)三角形正則度的判定，將誤差調(diào)節(jié)因子設(shè)為邊塌縮后，選取的新頂點鄰域中所有生成三角形的正則度的平均值，即

基于二次誤差測度與三角形正則度判定，確定一個新的誤差計算方法，即

式(3)中Q為傳統(tǒng)的三角形邊二次誤差，當(dāng)邊塌縮后生成的三角形的正則度越大時，簡化誤差越小，那么其在簡化過程中的優(yōu)先級越高。對于新頂點的選取，本研究選擇塌縮邊e的兩個頂點中使Error最小的頂點作為三角邊塌縮后的新頂點。相比于傳統(tǒng)的邊折疊方法，無需計算塌縮后新頂點的位置，減少了算法的計算量，不會導(dǎo)致網(wǎng)格拓?fù)浣Y(jié)構(gòu)錯誤。

2.2 邊界保持

傳統(tǒng)的二次誤差測度方法會對開放邊界網(wǎng)格的邊界特征產(chǎn)生較大的影響，所以對于三維網(wǎng)格的邊界頂點本研究采取了直接將邊界點作為邊塌縮后的新頂點位置的方法，能夠很好保證模型簡化后的整體質(zhì)量。而對于邊界邊的處理，在其塌縮誤差的基礎(chǔ)上加入一個閾值C0，使其塌縮代價變大，塌縮優(yōu)先級降低，較為方便簡單的保持模型邊界處的細(xì)節(jié)特征。

2.3 算法主要步驟

改進(jìn)算法主要步驟為:（1）輸入目標(biāo)簡化精度并初始化，計算誤差矩陣；（2）計算每條邊的塌縮誤差Error，并判斷是否需要進(jìn)行邊界處理；（3）選取塌縮代價最小的邊進(jìn)行塌縮簡化，并在最小堆內(nèi)更新數(shù)據(jù)；（4）若簡化后三角面片數(shù)大于所求目標(biāo)面數(shù)，則轉(zhuǎn)步驟3繼續(xù)進(jìn)行簡化，反之則算法結(jié)束。

由于本算法中第1、2步計算量較小，可在常規(guī)時間內(nèi)完成，所以本算法的時間復(fù)雜性主要與最小堆操作有關(guān)，即本算法的時間復(fù)雜度為O(nlogn)。

3 實驗結(jié)果

對本文優(yōu)化算法與QEM算法和PM算法進(jìn)行運行效率比較。實驗環(huán)境為Visual Studio 2019，基于Intel Core i5-4210U處理器，選取bunny模型。

表1 bunny模型不同簡化率下算法運行對比

由對比實驗可以看出，由于優(yōu)化算法時間復(fù)雜度為O(nlogn),QEM算法時間復(fù)雜度為O(n2)，所以優(yōu)化算法時間效率較QEM算法有了大幅度提升。而PM算法，由于其復(fù)雜的誤差控制方式，導(dǎo)致其運行時間明顯長，可知原始的PM算法并不滿足虛擬現(xiàn)實系統(tǒng)對算法運行高效率的要求。

然后將本文算法與QEM方法進(jìn)行模型簡化質(zhì)量的對比實驗，實驗環(huán)境同上文。圖1為bunny模型經(jīng)本文算法在不同簡化率下的簡化質(zhì)量對比。圖2展示的是在80%簡化率下模型細(xì)節(jié)的對比。

圖1 bunny模型本文算法簡化圖

圖2 bunny模型80%簡化后細(xì)節(jié)對比圖

對比知本文算法在模型簡化的同時能使網(wǎng)格模型保持較好的外部形態(tài)特征，刪減網(wǎng)格主要集中在兔子毛發(fā)等細(xì)節(jié)部位，對模型整體的形態(tài)幾乎沒有影響。由于引入了誤差調(diào)節(jié)因子和邊界處理，優(yōu)化算法簡化后的模型網(wǎng)格過渡更為平滑，對細(xì)節(jié)特征的保持也更為優(yōu)秀，這表明本文算法完成了在快速運行的基礎(chǔ)上保持良好的網(wǎng)格模型質(zhì)量的目標(biāo)。

4 結(jié)論

本論文得到北京農(nóng)業(yè)職業(yè)學(xué)院科技創(chuàng)新項目基于VR技術(shù)的360全景展示設(shè)計及實現(xiàn)(No.XY-YF-20-13)、北京市職業(yè)院校教師素質(zhì)提升計劃專業(yè)創(chuàng)新團(tuán)隊培養(yǎng)項目（設(shè)施農(nóng)業(yè)與裝備（智慧農(nóng)業(yè)）專業(yè)創(chuàng)新團(tuán)隊）支持。本文根據(jù)虛擬現(xiàn)實對網(wǎng)格模型質(zhì)量高、數(shù)據(jù)量小的要求，提出了一種可快速運行的、能夠較好保持三維網(wǎng)格特征的網(wǎng)格簡化算法。本文優(yōu)化算法滿足了虛擬現(xiàn)實系統(tǒng)對網(wǎng)格簡化算法運行速度快、簡化質(zhì)量高的要求，三維模型在簡化后不會影響到用戶的觀看體驗與交互體驗。