面向Web的機(jī)械產(chǎn)品三維模型簡化算法研究

齊洪方，汪 耀

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

1 引言

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

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

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

2 三維模型格式預(yù)處理

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

表1 OBJ模型常用關(guān)鍵字

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

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

表2 OBJ標(biāo)準(zhǔn)格式實(shí)例

3 半邊折疊算法原理

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

圖1 邊折疊算法示意圖

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

圖2 半邊折疊算法示意圖

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

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

4.1 頂點(diǎn)領(lǐng)域三角形的平均面積

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

圖3 領(lǐng)域三角形

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

(1)

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

4.2 頂點(diǎn)領(lǐng)域三角形的法向量變化

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

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

(2)

4.3 折疊邊的邊長

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

d(u，v)=u-v

(3)

其中，u-v為點(diǎn)u，v之間的歐式距離。

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

4.4 折疊代價計算

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

(4)

5 基于折疊代價的半邊折疊算法設(shè)計

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

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

圖5 半邊折疊算法流程

6 算法實(shí)驗(yàn)

6.1 實(shí)驗(yàn)環(huán)境

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

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

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

圖6 模型簡化對比

7 結(jié)論

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