面向Web的機械產品三維模型簡化算法研究

齊洪方，汪 耀

(1.武漢華夏理工學院智能制造學院，湖北 武漢 430223；2.武漢理工大學機電工程學院，湖北 武漢 430070)

1 引言

隨著信息技術的不斷發(fā)展，分布式制造的時代已經(jīng)到來，面向Web的機械產品三維CAD模型在線瀏覽需求越來越大。采用三維模型的在線瀏覽方式，用戶無需安裝大型三維軟件，在瀏覽器中即可查看三維產品模型。

基于WebGL技術的機械產品三維模型Web顯示，不僅可以實現(xiàn)3D模型的顯示渲染，而且相對于其它Web3D技術而言，具有無需下載安裝任何插件或函數(shù)庫、兼容性好、支持跨平臺顯示和渲染效果逼真且速度快的特點。由于WebGL技術基于OpenGL ES 2.0，通過多個三角面片來描述一個三維模型實體[1]，隨著三維實體模型的復雜程度不斷增加，用來描述三維實體模型的面片數(shù)據(jù)也會隨之增加，因此，為保證Web環(huán)境下三維模型數(shù)據(jù)傳遞和瀏覽器顯示的流暢性，需要對三維模型數(shù)據(jù)進行簡化，以保證瀏覽器能直接、快速的讀取并顯示。

本文選擇OBJ格式作為通用三維模型格式，針對不同軟件導出的OBJ文件內部數(shù)據(jù)格式不統(tǒng)一的問題，進行三維模型數(shù)據(jù)的預處理，在三維模型數(shù)據(jù)預處理的基礎上，提出基于半邊折疊的三維模型簡化算法，該算法利用定點領域三角形的平均面積、定點領域三角形的法向量變化和折疊邊的邊長計算折疊代價值，并按值的大小進行排序，將折疊代價值最小的邊折疊成一個點，并不斷重復計算折疊代價值、排序和折疊簡化這一過程，直到達到設定的簡化要求。

2 三維模型格式預處理

OBJ是一種被普遍公認的模型數(shù)據(jù)交換格式[2]。OBJ文件通過保存面片信息的形式保存著模型所有幾何信息，文件中每一行都通過一個關鍵字(Keyword)開頭，用來區(qū)別這一行的數(shù)據(jù)類型，例如：某一行數(shù)據(jù)開頭是字母v，則表示這一行數(shù)據(jù)為頂點坐標。OBJ模型文件中常用的關鍵字及含義見表1。

表1 OBJ模型常用關鍵字

OBJ文件數(shù)據(jù)一般都由頂點坐標數(shù)據(jù)、頂點法向量數(shù)據(jù)、面片索引數(shù)據(jù)和紋理坐標數(shù)據(jù)四部分組成。

但是不同三維CAD軟件導出的OBJ文件在數(shù)據(jù)內容方面存在差異。例如：SolidWorks得到的OBJ文件包含頂點坐標、頂點法向量和頂點索引，但不包含三維模型Web顯示所需的紋理坐標數(shù)據(jù)；Pro/E得到的OBJ文件包含四部分數(shù)據(jù)，但其紋理坐標數(shù)據(jù)以三維坐標形式存在，不符合Web環(huán)境下對模型進行紋理貼圖的二維坐標數(shù)據(jù)要求；還有部分三維CAD軟件以模型中的三角面為基本單元，造成頂點坐標數(shù)據(jù)、頂點法向量數(shù)據(jù)和面片索引數(shù)據(jù)重復出現(xiàn)的現(xiàn)象。綜合以上，不同三維CAD軟件導出的OBJ文件的差異主要集中在：是否有紋理坐標數(shù)據(jù)、紋理坐標數(shù)據(jù)是否為二位坐標數(shù)據(jù)和點坐標數(shù)據(jù)、頂點法向量數(shù)據(jù)和面片索引數(shù)據(jù)是否重復三個問題。本文借鑒文獻[2]的方法，通過紋理坐標處理和數(shù)據(jù)化零為整處理，將不同三維CAD軟件導出的OBJ模型轉化為OBJ模型的標準格式，如表2中實例所示。

表2 OBJ標準格式實例

3 半邊折疊算法原理

在保證原始模型幾何形狀不發(fā)生改變的前提下，采用適當?shù)乃惴p少網(wǎng)格模型的面片數(shù)或頂點數(shù)，可以提高計算機圖形繪制速度。常用的網(wǎng)格模型簡化算法有頂點刪除簡化算法[3]，邊折疊簡化算法[4-5]，采樣簡化算法[6]，頂點聚類簡化算法[7-9]和多邊形合并簡化算法[10]等。這些算法各有各的特點，在不同的網(wǎng)格簡化情形得到相應應用，其中Hoppe提出的基于邊折疊思想進行模型簡化的算法簡單高效是目前最常用的模型簡化方法之一。邊折疊算法示意圖如圖1所示，在對v1v2進行折疊時，利用能量優(yōu)化確定新頂點v’的位置，由于邊折疊算法在每一次折疊過程中將產生一個新的頂點同時刪除原有的兩個頂點，這樣在新頂點產生的時候就需要進行頂點索引更新，這一過程將增加一定的計算量和存儲量。

圖1 邊折疊算法示意圖

半邊折疊算法示意圖如圖2所示，在進行邊uv的折疊時，u點將被刪除，同時所有與頂點u相關的頂點將與頂點v相連，即v點起到了代替u點的作用。與邊折疊算法不同，半邊折疊算法在每一次執(zhí)行半邊折疊的過程中不會產生一個新的頂點，僅刪除了一個原有的頂點，避免了計算新頂點位置帶來的運輸量和存儲量。本文選擇半邊折疊算法作為三維模型簡化算法，可以有效提升模型簡化效率。

圖2 半邊折疊算法示意圖

4 三維模型數(shù)據(jù)簡化

通常邊折疊算法有能量函數(shù)法和二次誤差測量簡化算法，Hope[4]提出的基于能量優(yōu)化的方法來確定折疊順序和新頂點位置的網(wǎng)格模型簡化算法，通過構建計算網(wǎng)格簡化誤差的數(shù)學模型，來不斷尋找使能量方程值最小的簡化點。該算法能夠實現(xiàn)質量很高的模型簡化，但其缺點在于優(yōu)化過程計算量大，自動化程度不高，耗費了大量的計算時間，不利于Web環(huán)境下三維模型的顯示；而Garland提出的二次誤差測量簡化算法[5]通過計算頂點到相關平面距離的平方和作為誤差測度，并使用二次誤差測度作為邊折疊代價，相對Hope提出的算法而言計算較快，也能生成較好質量的模型，但相對Web環(huán)境其同樣存在著計算量較大的問題。綜合上述分析，本文在保證模型顯示精度的前提下，為了盡可能的減小計算量，在計算折疊代價時主要考慮了頂點領域三角形平均面積、頂點領域三角形的法向量變化和折疊邊的邊長三個方面因素。

4.1 頂點領域三角形的平均面積

為了保證模型顯示的精度，在模型簡化過程中應盡可能避開模型特征較為顯著的區(qū)域。在網(wǎng)格模型的表達中，若頂點領域三角形的平均面積越小，則說明該區(qū)域的三角網(wǎng)格密度越集中，表示該區(qū)域的模型特征越顯著；若頂點領域三角形的平局面積越大，則說明該區(qū)域的三角網(wǎng)格密度越稀疏，表示該區(qū)域的模型特征越不顯著。因此，頂點的領域三角形的平均面積在一定程度上反映著該頂點處的模型特征的顯著程度，如圖3所示。

圖3 領域三角形

圖3中，圖(a)和圖(b)兩個模型在頂點v1處的領域三角形總面積一樣，但三角形數(shù)量不同，其中圖(b)的網(wǎng)格更加密集。當對邊(v1，v2)進行折疊操作時，與v1相連的所有頂點都將連接v2上。顯然圖(b)中的網(wǎng)格在折疊后對模型特征的影響會更大。所以圖(b)中的邊(v1，v2)比圖(a)中邊(v1，v2)具有更高的重要度，通過點的領域三角形的平均面積表示，如式(1)所示。

(1)

其中，num表示點vi的領域三角形中三角形的總個數(shù)，tj表示點vi領域三角形中的三角形，ARtj表示三角形tj的面積。

4.2 頂點領域三角形的法向量變化

人的視覺對三角面法向量方向的變化比較敏感[11]。邊折疊后頂點領域三角形的法向量變化越小，模型的視覺變化影響越小；頂點領域三角形的法向量變化越大，說明模型特征損失較大。如圖4所示的邊折疊后頂點領域三角形的法向量變化。

圖4 邊(U，V)折疊后的領域三角形的法向量變化

(2)

4.3 折疊邊的邊長

在網(wǎng)格模型簡化過程中，考慮頂點領域三角形的平均面積大小和法向量變化大小是為了在網(wǎng)格簡化過程中盡量避免模型特征顯著的區(qū)域被大量簡化，從而丟失了模型的原始特征。但如果太過注重模型特征區(qū)域的保留，而大量刪減非特征區(qū)域，就會造成簡化后的網(wǎng)格模型出現(xiàn)模型整體特征的丟失。為避免這種極端化模型簡化的出現(xiàn)，本文引入折疊邊的邊長這個影響因子。折疊邊的邊長可通過式(3)來求。

d(u，v)=u-v

(3)

其中，u-v為點u，v之間的歐式距離。

當網(wǎng)格中邊的長度越大，折疊此邊將引起更大的網(wǎng)格整體變動。因此，在模型簡化操作過程中，應優(yōu)先折疊邊長較小的邊。

4.4 折疊代價計算

對于網(wǎng)格中的任一條折疊邊，折疊代價由頂點領域三角形的平均面積、頂點領域三角形的法向量變化和折疊邊的邊長三個部分組成，邊折疊代價計算式如式(4)所示。

(4)

5 基于折疊代價的半邊折疊算法設計

本文采用的半邊折疊算法，首先，獲取模型網(wǎng)格數(shù)據(jù)并構建網(wǎng)絡拓撲結構。然后，根據(jù)折疊代價計算式(4)計算網(wǎng)格中每個頂點的對應邊的折疊代價值，并按值的大小進行排序；取出代價值最小的邊折疊成一個點，同時將原來與刪除點關聯(lián)的頂點相連到新頂點上刪除舊的邊；最后，更新折疊變化后受影響邊的折疊代價值，并再次排序。重復這一過程，當網(wǎng)格模型簡化到?jīng)]有符合設定條件的半邊時，就得到了簡化后的網(wǎng)格。其算法流程如圖6所示，具體算法步驟如下。

網(wǎng)格模型簡化過程中的閾值設定，因考慮到機械產品模型對顯示精度的要求，按照領域三角形法向量變化值為1-cos(10°)作為標準，即保證半邊折疊后，三維模型的形狀特征不會發(fā)生變化。

圖5 半邊折疊算法流程

6 算法實驗

6.1 實驗環(huán)境

在PC機(Intel i7、8G內存、Window10)上運行基于半邊折疊算法的三維模型簡化算法。簡化對象為bunny.obj的三維模型文件。

6.2 實驗及結果分析

從圖6可以看出，兩種算法簡化率達到85%之后，兔子的眼睛、耳朵等特征就開始明顯失真，當達到95%時，基本就不清晰了，但是本文算法與QEM算法相比較，特征部位的三角網(wǎng)格明顯較為密集。由此可見，本文算法能較好的反映原模型的特征，保證模型顯示的質量。

圖6 模型簡化對比

7 結論

本文主要研究Web環(huán)境下機械產品三維模型顯示的簡化算法。在OBJ文件數(shù)據(jù)規(guī)范化處理的基礎上，利用半邊折疊算法進一步優(yōu)化，以頂點領域三角形平均面積、頂點領域三角形的法向量變化以及折疊邊的邊長，計算折疊代價，通過對折疊代價排序與預先設定闕值進行簡化處理，減少模型的三角面片數(shù)量，較好的提升了機械產品三維模型在線瀏覽的流暢性，保證了機械產品三維模型的視覺效果，后續(xù)研究重點是對算法的進一步改進和完善。