面向VR建模的網格簡化算法優化研究

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

（1.北京農業職業學院信息技術系，北京，102442；2.河北地質大學信息工程學院，河北石家莊，050031; 3.河北省智能傳感物聯網技術工程研究中心，河北石家莊，050031）

0 引言

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

1 PM算法簡介

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

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

2 基于邊塌縮的改進算法

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

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

其中l1、l2、l3分別為三角形由短到長的三條邊，當re=1時，三角形正則度最好，此時該三角形為等邊三角形。當re=0時，三角形的正則度最差，此時三角形退化成為了一條直線。根據三角形正則度的判定，將誤差調節因子設為邊塌縮后，選取的新頂點鄰域中所有生成三角形的正則度的平均值，即

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

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

2.2 邊界保持

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

2.3 算法主要步驟

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

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

3 實驗結果

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

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

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

然后將本文算法與QEM方法進行模型簡化質量的對比實驗，實驗環境同上文。圖1為bunny模型經本文算法在不同簡化率下的簡化質量對比。圖2展示的是在80%簡化率下模型細節的對比。

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

圖2 bunny模型80%簡化后細節對比圖

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

4 結論

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