三角網格模型簡化算法的研究現狀

張茹　胡世昌

摘要：模型的精細程度在計算機圖形的真實感顯示中非常重要，而龐大的數據量對計算機的存儲、顯示和傳輸帶來了巨大的挑戰，因此三維模型的簡化算法越來越受到學者的關注，文中對三角網格算法展開了系統的研究，總結歸納了元素折疊法和誤差度量的基本思想及其優缺點，并展望了模型簡化領域未來的研究方向。

關鍵詞：三角網格；網格簡化；邊折疊；三角形折疊

中圖分類號：TP391.4 文獻標識碼：A 文章編號：1007-9416（2018）01-0128-02

隨著三維激光掃描技術的發展，三角網格模型的獲取精度大幅度提高。龐大的網格數據雖可以保持物體的細節特征，卻給計算機的存儲、顯示和傳輸帶來了困難。為減輕計算機處理數據的壓力，方法之一就是簡化模型。計算機圖形學中的三維模型常采用多邊形網格進行描述，空間中三個點確定一個平面，因此三角形是多邊形網格中最常用到的多邊形，所以，此次網格模型簡化研究中，我們僅針對三角網格模型。

1 三角網格簡化相關算法

目前網格簡化方法一般可以分為三類：元素刪除法、網格重繪法和元素折疊法。元素刪除法包括點刪除和三角形刪除，根據網格模型的幾何性質和拓撲關系來刪除頂點，但該方法對原網格模型的特征保持較差。網格重繪法是在原網格模型的基礎上重新繪制頂點數更少的模型，但這種方法對于細節特征較多的模型，計算量和誤差都較大。相比來說，元素折疊法具有更高的穩定性和簡化速度，其主要分為邊折疊和三角形折疊，下面將對這兩種方法進行論述。

1.1 邊折疊

邊折疊算法首先由Hoppe[1]提出，其基本思想是將三角網格中一條滿足條件的邊，簡化為一個頂點，同時將與該邊兩個端點相鄰的所有頂點都和新頂點相連，并刪除所有退化的邊和面，如圖1所示，可通過三個步驟來完成一次邊折疊操作：

（1）將頂點移動至新頂點；（2）將所有與頂點相關的邊連接到頂點；（3）刪除頂點以及所有失效的邊和三角形。

如圖1所示，一次非邊界邊折疊操作可減少三條邊、兩個三角形、一個頂點；如圖2所示，一次邊界邊折疊操作可減少兩條邊、一個三角形、一個頂點。對于封閉的模型來說，所有的邊都由兩個三角面片包含，但是對于不封閉的模型而言，有些邊只被一個三角面片包含，稱之為邊界邊。邊界邊往往含有模型的邊界特征，因此在討論模型簡化算法時要注意將邊界邊和非邊界邊分開討論。

1.2 三角形折疊

Hamann[2]提出一種基于三角形折疊的網格簡化算法，三角形折疊操作與邊折疊操作類似，將邊折疊中的邊換成了三角形，折疊過程如圖3所示：將三角形折疊成一個頂點，并將與該三角形三個頂點相連的所有頂點都與新頂點相連，刪除與此三角形有公共邊的三角形。

如圖3所示，一次非邊界三角形折疊操作減少六條邊、四個三角形、兩個頂點；如圖4所示，一次邊界三角形折疊操作減少五條邊、三個三角形、兩個頂點。

從幾何元素數量上分析，一次三角形折疊減少的數量是一次邊折疊的兩倍，因此，在簡化率相同的情況下，三角形折疊具體更高的簡化速度。

2 新頂點位置的確定

新頂點的位置直接影響到簡化后模型的形狀，確定新頂點無疑是簡化方法中的一個難點，Garland，等[3]通過二次誤差矩陣（Quadric Error Metrics，QEM）來確定邊折疊點的位置，該方法雖然計算簡單，但得到的模型過于均勻；張霞，等[4]運用頂點投影法來確定三角形折疊點的位置，充分利用了折疊區域的幾何信息，但存在簡化誤差閾值不易控制，忽視網格連續性的問題；段黎明，等[5]在√3網格細分法的基礎上確定三角形折疊后的坐標，在簡化比例較大時能較好地保持網格特征和連續性，但對于一些特征三角形比較集中的模型，容易出現過共頂點的現象。每種方法都有其不足之處，這就促使著我們去深入研究，不斷的改進，以取得更好的效果。

3 誤差度量

模型簡化的根本目的在于保持模型細節基本不變的情況下盡可能減少面片的數量，一條邊或者三角形能否被折疊是由其誤差的大小來決定的，合理的誤差度量方法可以有效的控制簡化后模型的質量，使模型外觀在一個能夠接受的范圍內。

3.1 二次誤差度量

二次誤差度量是用新頂點到折疊邊所關聯平面的距離平方和作為誤差標準，只考慮了模型簡化前后的距離誤差，沒有考慮到模型的細節特征，使網格過于均勻，但其簡化速度快，且在簡化率較低時效果較好，因此后來的很多算法都是在此基礎上加以改進的。

3.2 體積誤差度量

體積誤差是模型簡化前后的體積變化值，誤差越小代表簡化算法越好，但三維空間中各個面的法向量的存在，使得算出來的體積變化可正可負，其正負情況反映了簡化模型相對于初始模型的凹凸情況，但也可能出現網格模型變化了但體積誤差為零的情況，因此后人多使用體積的平方誤差度量方法，如文獻[4]。

3.3 頂點重要度

頂點的重要度亦是我們需要考慮的一個因素，當我們觀察物體時，對棱角、棱邊、輪廓等關鍵細節較敏感，對平坦區域的感知力較弱，頂點處的起伏變化越大，去除該點后對網格模型的影響就越大，即頂點的重要度越大。在模型同等的簡化率時，我們就要首先考慮刪除頂點重要度低的點，保留頂點重要度高的點。

董艷，等[6]將頂點的重要度作為權重引入折疊代價中，從而影響邊的折疊順序，取得較好的結果，但仍有簡化效率不高的缺點。

這里只介紹了幾種常用的誤差度量方法，除此之外，還有點的曲率[7]、局部區域平均面積等[8]，更多有效的方法有待我們去發掘和驗證。

4 結語

模型簡化一般要遵循兩個原則，最少的頂點數和最小的誤差。不斷提高模型簡化質量和速度是我們一直努力的方向，在此基礎上，我們可以從以下幾個方面進一步研究：

（1）我們經常見到的模型都是帶有顏色、紋理等屬性的，這些簡化算法是否對所有帶屬性的模型具有較好的簡化質量。（2）從視點出發，不同分辨率的模型是否能夠隨視點的遠近自適應的變換并有較高的轉換效率。（3）三角網格模型是用多個三角形面片來逼近模型，相對來說二次曲面有更好的表達曲面的能力，用二次曲面代替部分三角網格來逼近模型是否有更高的效率和質量。

參考文獻

[1]Hoppe H， DeRose T， Duchamp T， McDonald J， Stuetzle W. Mesh optimization. Proc. of the Computer Graphics，1993，（27）：19-26.

[2]Hamann B. A data reduction scheme for triangulated surface[J].Computer Aided Geometric Design，1994，（2）：197-214.

[3]Garland M， Heckbert PS. Surface simplification using quadric error metrics. Proc. of the Computer Graphics，1997，（31）：209-216.

[4]張霞，段黎明，劉璐.保持特征的高質量三角網格簡化方法[J].計算機集成制造系統，2014，（3）：486-493.

[5]段黎明，邵輝，等.高效率的三角網格模型保特征簡化方法[J].光學精密工程，2017，（2）：460-468.

[6]董艷，張志毅，楊客.基于頂點重要度的保形網格簡化方法研究[J].計算機工程與設計，2013，（5）：1889-1895.

[7]Zhou M D，Michael Y W.Engineered model simplification for simulation based structural design[J]. Computer Aided Design and Applications，2012，（1）：87-94.

[8]賈琪.基于改進二次誤差測度的網格簡化算法研究[D].秦皇島：燕山大學，2014.