姜藝諾，王 偉，田 澤

(1.西安工程大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院， 西安 710048； 2.集成電路與微系統(tǒng)設(shè)計(jì)航空科技重點(diǎn)實(shí)驗(yàn)室，西安 710068)

1 引言

隨著計(jì)算機(jī)科學(xué)技術(shù)及數(shù)字媒體的發(fā)展，三維模型精確度得以提高。在一些3D仿真應(yīng)用場景中，如軍事模擬作戰(zhàn)、導(dǎo)彈發(fā)射追蹤，這些復(fù)雜場景的構(gòu)建可能需要數(shù)萬個三角形網(wǎng)絡(luò)，復(fù)雜的模型給計(jì)算機(jī)的存儲、傳輸、渲染過程帶來了巨大的挑戰(zhàn)。同樣，由于導(dǎo)彈發(fā)射車模型存在大量的三角面片，導(dǎo)致仿真應(yīng)用場景中模型加載不流暢、渲染時間過長，從而直接影響系統(tǒng)性能[1]。在保證模型特征的情況下，較低內(nèi)存的占用、快速的數(shù)字傳輸和高效的物理計(jì)算是首選和必要的，因此需要相對簡單的模型代替原有模型。自20世紀(jì)70年代初，國內(nèi)外學(xué)者提出了許多網(wǎng)格模型簡化算法，目前一般可分為4類：頂點(diǎn)聚類法[2]；頂點(diǎn)刪除法[3]；邊折疊法[4-6]；三角形折疊法[8-9]。其中，頂點(diǎn)聚類法是將三維模型劃分為一定數(shù)量的子空間，簡化后的子空間頂點(diǎn)聚類都會被新頂點(diǎn)代替，之后再刪除與原頂點(diǎn)相關(guān)聯(lián)的三角形面片或者重疊的邊，該算法計(jì)算速度較快，但對面積較大的平面簡化程度較低，同時會造成模型細(xì)節(jié)特征丟失的現(xiàn)象，生成模型質(zhì)量不高。頂點(diǎn)刪除法通過迭代方式刪除網(wǎng)格中小于閾值的頂點(diǎn)進(jìn)行簡化，該方法簡單高效，但簡化過程需要重新三角化，使模型表面過于粗糙。

邊折疊算法首先由Hoppe[4]提出，該算法是一種針對任意二維流形的三角形網(wǎng)格模型簡化方法，是一個全局能量函數(shù)的非線性優(yōu)化，它需要大量的計(jì)算以及長時間的運(yùn)行，執(zhí)行效率較低。1997年，針對Hoppe算法存在的缺點(diǎn)，Galand提出一種基于二次誤差度量(quadric error metrics，QEM)的邊折疊算法[5]，利用局部二次誤差度量的方法來計(jì)算邊緣折疊的誤差，將新頂點(diǎn)到與該點(diǎn)相鄰的平面的距離的平方作為度量誤差，該算法計(jì)算簡單，運(yùn)行速度較快。楊曉東等[6]在邊折疊的基礎(chǔ)上引入局部面積度量的方法來改變模型特征和平坦區(qū)域上頂點(diǎn)折疊的次序，更好的突出了模型的特點(diǎn)。Sadia Tariq等[7]在邊折疊的基礎(chǔ)上，通過簡化同一模型多個副本文件加快算法運(yùn)行時間，并將頂點(diǎn)紋理信息加入誤差矩陣中，提高了模型的簡化質(zhì)量。

三角形折疊算法和邊折疊算法的思想大致相同，Zhou 等[8]首先計(jì)算出折疊點(diǎn)到相鄰曲面距離的平方和，按照最小化折疊代價順序?qū)θ切握郫B實(shí)現(xiàn)模型簡化，由于算法以三角形折疊為中心，在簡化率相同的情況下，其折疊速度明顯優(yōu)于邊折疊。車力等[9]將三角形折疊與多視覺感知相結(jié)合并借此定義三角形折疊誤差度量函數(shù)，可以很好地保持算法的邊界特征，并有效改善模型質(zhì)量，但由于多次計(jì)算不同視點(diǎn)誤差造成算法耗時較長。

比較上述幾種折疊算法，三角形折疊算法具有幾何意義較為直觀、算法效率較高等特點(diǎn)。為了解決QEM簡化算法會造成模型幾何特征丟失的缺點(diǎn)，提出保持幾何特征的三角形折疊(triangle collapse preserving geometric features，TCPGF)算法，將三角形折疊引入到QEM算法中，并加入體積比及網(wǎng)格顯著度因子來構(gòu)建幾何特征誤差度量函數(shù)，在保持模型簡化時間差別不大的前提下進(jìn)一步提升模型質(zhì)量，較好的保證模型的原始特征。

2 二次誤差度量算法與三角形折疊

給初始模型中任意一個三角形Ti設(shè)置一個4×4的誤差矩陣Kp，v為模型的任意頂點(diǎn)，包含頂點(diǎn)v的三角形集合用Ci表示。設(shè)一個平面p的方程表示為ax+by+cz+d=0，其中a、b、c、d為常數(shù)，不同時為0。然后，將該平面縮寫為p=[a,b,c,d]T，且a2+b2+c2=1。則頂點(diǎn)v=(x,y,z,1)T到Ci的平方和為：

(1)

根據(jù)平面p=[a,b,c,d]T可知，每個三角形平面可以計(jì)算出大小為4×4的對稱矩陣Kp，如式(2)所示：

(2)

(3)

QEM算法旨在使新折疊點(diǎn)引起的折疊誤差盡可能小。因此，計(jì)算該方程(3)中偏導(dǎo)數(shù)，并將其設(shè)為0。由此得到了一個線性方程如(4)所示：

(4)

解得：

(5)

若方程(4)可以求解，而且方程左側(cè)的矩陣是可逆的，則從方程中可以得到新折疊點(diǎn)的位置，如式(5)所示。若不可逆，則將三角形的重心作為新的折疊點(diǎn)。三角形折疊法如圖1所示。

QEM算法簡化的幾何基本元素是三角形，其累加性較好，本文中將邊折疊延伸為三角形折疊，并更新折疊代價：

(6)

由于QEM算法沒有考慮模型局部形態(tài)，測度標(biāo)準(zhǔn)過于單一，基于以上原因，為了使簡化后的模型準(zhǔn)確表達(dá)出原始模型的特征，下文將引入體積比和網(wǎng)格顯著度，并將兩者統(tǒng)稱為約束因子，給出了一種類似于QEM的誤差標(biāo)準(zhǔn)，能夠有效地控制三角形的簡化順序。

圖1 三角形折疊法

3 約束因子的構(gòu)建

3.1 體積比

體積作為一種常見的誤差函數(shù)控制變量，旨在從幾何尺度方面盡可能逼近原始模型[10-11]。本文中體積比指模型中三角形與原點(diǎn)圍成的體積在簡化前后的比值，并用該值來量化模型簡化前后模型體積變化情況。

定義常見的三角形網(wǎng)絡(luò)T，T=(t1,t2,t3,…,tn)，其頂點(diǎn)集合為V，V=(v1,v2,v2,…,vi)，與三角形3個頂點(diǎn)鄰接的三角形被稱為鄰域三角形，如圖2所示。被折疊的△v1v2v3三個頂點(diǎn)坐標(biāo)分別為v1(x1,y1,z1)、v2(x2,y2,z2)和v3(x3,y3,z3)，由定義可知其鄰域三角形為△v1v6v2，△v1v5v6，△v1v5v4，△v1v3v4，△v2v6v7，△v2v7v3，△v3v7v8，△v3v4v8。

圖2 三角折疊引起的體積變化

設(shè)A為三角形的頂點(diǎn)坐標(biāo)矩陣，|A|為對應(yīng)坐標(biāo)矩陣的行列式，則△v1v2v3與原點(diǎn)所圍成的四面體的體積可由式(7)計(jì)算：

(7)

若初始網(wǎng)格中頂點(diǎn)v鄰域三角形個數(shù)為m，則鄰域各三角形頂點(diǎn)坐標(biāo)矩陣為Ai(k=1,2,3,…,m)?！鱲1v2v3折疊后生成的頂點(diǎn)為v0后，設(shè)折疊后頂點(diǎn)v0的鄰域三角形個數(shù)為n，同理每個鄰域三角形坐標(biāo)矩陣記為Bi(k=1,2,3,…,n)。則刪除點(diǎn)v后模型體積比(volumetric ratio，VR)由式(8)計(jì)算:

(8)

為了使簡化后的模型保持原有特征，僅僅依靠體積比來約束誤差函數(shù)是不夠的，對于模型簡化來講，網(wǎng)格的細(xì)節(jié)特征也是需要考慮的重要因素之一，下面將對誤差函數(shù)加新的約束條件，合理化目標(biāo)函數(shù)。

3.2 網(wǎng)格顯著度

從視覺方面來講，二維圖像的顯著度是指圖像上能夠吸引觀看者興趣、捕捉到注意力的某些特征，一般包括圖像的紋理、顏色、亮度等信息，并且可以量化出來。而在三維模型中，網(wǎng)格顯著度一般基于網(wǎng)格特征計(jì)算，比較常見的有高斯曲率、主曲率、平均測地線距離等等[12]。Lee等[13]首先提出了計(jì)算機(jī)圖形學(xué)中網(wǎng)格顯著度的概念，將圖像中的顯著度引入到三維網(wǎng)格中。

為了提取網(wǎng)格顯著度，需要對網(wǎng)格噪聲進(jìn)行處理，因此濾波算法的選取極為重要。本文中使用雙邊濾波來計(jì)算網(wǎng)格顯著度。雙邊濾波是一種線性的過濾方法，與高斯濾波相比，雙邊濾波將像素值相似度和空間鄰近度進(jìn)行一種折衷處理，以像素為單位進(jìn)行操作，可以在達(dá)到濾波效果的同時，保證圖像邊緣結(jié)構(gòu)[14]。雙邊濾波器公式化描述如下：

(9)

(10)

式中：c(ξ,x)為空間距離相似度高斯權(quán)重；s(f(ξ),f(x))為像素相似度高斯權(quán)重；k(x)用來對雙邊濾波結(jié)果單位化。

由于高斯曲率和平均曲率對特定曲面敏感度不足，為了準(zhǔn)確反應(yīng)網(wǎng)格面幾何屬性，本文中的像素值不采用平均曲率代替，而使用周繼來等[15]的方法，使用頂點(diǎn)曲度代替。網(wǎng)格顯著度計(jì)算步驟如下：

1) 計(jì)算三維網(wǎng)格的頂點(diǎn)曲度:

(11)

式中：KG為頂點(diǎn)的高斯曲率;KH為頂點(diǎn)的平均曲率，兩者均通過文獻(xiàn)[16]中計(jì)算方法求得。

2) 計(jì)算基于三維網(wǎng)格頂點(diǎn)曲度的雙濾波空間距離權(quán)重αc以及特征保持度權(quán)重βs：

(12)

(13)

3) 計(jì)算三角形網(wǎng)格顯著度值：

(14)

(15)

式中：P為頂點(diǎn)的一層鄰域；C(x)為頂點(diǎn)曲度。根據(jù)大量實(shí)驗(yàn)，取σdist為v一階鄰域內(nèi)三角形邊長的平均值，圖3為導(dǎo)彈發(fā)射車組件網(wǎng)格顯著度圖像，根據(jù)圖像可知，模型中的顏色較深部位代表網(wǎng)格顯著度較高的區(qū)域，同時也說明該區(qū)域模型幾何特征較明顯。顏色較淺代表顯著度較低的部位，該區(qū)域網(wǎng)格變化較為平緩，特征度相對較低。

圖3 組件一、二網(wǎng)格顯著度圖像

4 TCPGF算法

導(dǎo)彈發(fā)射車模型結(jié)構(gòu)復(fù)雜，建模精度較高，部件連接復(fù)雜。針對以上特點(diǎn)，在QEM算法基礎(chǔ)上加入體積比以及網(wǎng)格顯著度這兩個約束因子建立新的折疊誤差函數(shù)。由于TCPGF算法是根據(jù)三角形的折疊代價大小進(jìn)行三角形折疊操作的，故如何計(jì)算折疊代價，直接影響到折疊三角形的選擇以及新頂點(diǎn)的確定。

4.1 折疊代價的計(jì)算

將體積比VR(Ti)以及網(wǎng)格顯著度約束因子B(Ti)作為參數(shù)添加到式(6)中進(jìn)行新折疊誤差的計(jì)算。三角形T0折疊后引起的局部體積比值越高，顯著度越高，表示該網(wǎng)格局域?qū)儆谔卣髅黠@區(qū)域，則應(yīng)延遲折疊該區(qū)域三角形，更新折疊誤差矩陣如下所示：

Qt′=(VR(Ti) +B(Ti))Qt

(16)

式中：VR(Ti)與B(Ti)分別根據(jù)式(7)—(15)求得。那么新的折疊誤差標(biāo)準(zhǔn)為：

(17)

4.2 新頂點(diǎn)的確定

(18)

vi0即是三角形折疊的最佳位置。若該方程無解，則將三角形的重心作為新頂點(diǎn)的位置，如圖4所示，重心即三角形三條中線的交點(diǎn)，是三角形最佳平衡點(diǎn)，坐標(biāo)根據(jù)三角形3個頂點(diǎn)坐標(biāo)的幾何均值求得，即：

vi0=(v1+v2+v3)/3

(19)

圖4 三角形重心

4.3 算法步驟

本文中提出的基于三角形折疊的網(wǎng)格簡化方法采用堆排序的方法按照折疊誤差的大小進(jìn)行排序，模型特征越明顯的部位網(wǎng)格顯著度越高，折疊后引起的體積變化較大，因此每次簡化就要延遲該三角形的折疊，即每次在堆中提取誤差最小的三角形進(jìn)行簡化。

步驟3：計(jì)算每一個三角形的折疊誤差，并按照折疊誤差從小到大排列三角形，將其加入誤差堆隊(duì)列中；

步驟4：將折疊誤差最小的三角形從隊(duì)列中取出并折疊，更更新所有相關(guān)信息，若折疊誤差為0，則將其插入到誤差為零的三角形隊(duì)列后；

步驟5：若達(dá)到需求的簡化率或者隊(duì)列為零，則轉(zhuǎn)到步驟6，否則轉(zhuǎn)到步驟4；

步驟6：算法終止。

4.4 算法合理性分析

文中提出的保持幾何特征約束算法在設(shè)計(jì)過程中采用QEM進(jìn)行三角形折疊方法，一次可以同時簡化2個三角形，相當(dāng)于兩次邊折疊的效果，具有更快的迭代速度。但仍然存在簡化后網(wǎng)格過于均勻的缺點(diǎn)，故引入了體積比以及網(wǎng)格顯著度兩個參數(shù)，與二次誤差度量方法結(jié)合，合理維持局部網(wǎng)格形狀變化，彌補(bǔ)了經(jīng)典QEM算法無法保持模型細(xì)節(jié)、簡化網(wǎng)格過于均勻等缺點(diǎn)，使算法在時間開銷與現(xiàn)存算法差別較小的前提下向優(yōu)化的方向發(fā)展。QEM算法是公認(rèn)簡化效果好、適用性高的算法，將仿真結(jié)果與QEM算法(文獻(xiàn)[5])和在其基礎(chǔ)上改進(jìn)的算法(文獻(xiàn)[6])進(jìn)行對比，保證了該算法的合理性與可行性。

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

所有實(shí)驗(yàn)在處理器為Intel(R) Core(TM) i7-8565U CPU @ 1.80GHz 1.99 GHz、操作系統(tǒng)為Window 10、安裝內(nèi)存為8 GB的計(jì)算機(jī)平臺上，通過Visual Studio平臺上實(shí)現(xiàn)。導(dǎo)彈發(fā)射車三維模型數(shù)據(jù)來源于集成電路與微系統(tǒng)設(shè)計(jì)航空科技重點(diǎn)實(shí)驗(yàn)室(1)集成電路與微系統(tǒng)設(shè)計(jì)航空科技重點(diǎn)實(shí)驗(yàn)室設(shè)立于2015年，主要研究方向包括：智能計(jì)算機(jī)基礎(chǔ)理論、新型機(jī)載網(wǎng)絡(luò)理論及芯片設(shè)計(jì)技術(shù)，積累了大量實(shí)驗(yàn)設(shè)備、關(guān)鍵技術(shù)，是航空領(lǐng)域核心集成電路前沿陣地以及人才培養(yǎng)和專業(yè)發(fā)展的綜合平臺。，由3DMAX軟件制作，將其導(dǎo)出為.obj文件并在此基礎(chǔ)上進(jìn)行實(shí)驗(yàn)。

為了驗(yàn)證改進(jìn)算法的合理性，實(shí)驗(yàn)采用多種距離誤差以及算法時間開銷作為指標(biāo)，與文獻(xiàn)[5-6]中模型簡化算法對比。

5.1 不同簡化率下模型簡化效果對比

由于導(dǎo)彈發(fā)射車模型數(shù)據(jù)量太大，實(shí)驗(yàn)針對性選取了導(dǎo)彈發(fā)射車兩個特征明顯的部件作為仿真實(shí)驗(yàn)對象。如圖5所示的組件一(a)，組件二(b)。其原始模型分別含有1 674與4 004個三角形面片，其中組件一模型表面頂點(diǎn)分布較為均勻而且是連續(xù)的表面；而組件二幾何特征復(fù)雜，頂點(diǎn)分布不均勻且模型表面不連續(xù)。

圖5 組件一、組件二原始模型圖

為驗(yàn)證改進(jìn)模型簡化算法效果，圖6中(a)—(c)是使用文獻(xiàn)[5]算法、文獻(xiàn)[6]算法以及本文算法對組件一簡化15%的簡化結(jié)果，可以看出三者在視覺效果上沒有明顯差異。直到將模型簡化率提高至85%時，如圖6(g)—(i)所示。文獻(xiàn)[5]算法簡化后的模型雖然邊角特征未退化，但三角網(wǎng)格分布過于均勻，與原模型差別較大。采用文獻(xiàn)[6]算法后模型梯形邊角退化為尖銳的三角形，無法保持模型原始特征。相比較看，本文算法可以有效防止模型邊角特征退化。

圖6 組件一模型簡化結(jié)果對比

圖7給出了組件二分別采用文獻(xiàn)[5-6]和本文算法在簡化率15%、55%、85%下實(shí)驗(yàn)簡化結(jié)果，由于組件二頂點(diǎn)數(shù)比較多，使用3種算法將模型簡化15%時，如圖7(a)—(c)所示，很難從視覺方面比較的簡化效果。

圖7 組件二模型簡化結(jié)果對比

當(dāng)簡化率提升至85% 時，使用本文算法簡化的模型軸體區(qū)域保存仍然比較完整，軸桿頭尾特征明顯，沒有出現(xiàn)較大范圍的特征退化，使特征能夠較好的保留下來，并且網(wǎng)格顯著度高的區(qū)域較稠密，而使用文獻(xiàn)[5-6]對模型同樣簡化85% 時，軸體左端部位形變率較大，而且網(wǎng)格顯著度較低的區(qū)域網(wǎng)格仍較稠密。由此可見，加入體積比以及網(wǎng)格顯著度2種約束因子能夠有效地保持原始模型特征。

圖8為簡化率為85% 時局部細(xì)節(jié)放大圖(圖7圓圈標(biāo)識部位)。從圖中更能看出在分別使用文獻(xiàn)[5]算法以及文獻(xiàn)[6]算法后，組件二模型軸體兩端特征已退化，并產(chǎn)生較多的狹長三角形，而本文算法簡化結(jié)果無較多狹長三角形，也不會造成模型特征退化的現(xiàn)象。

圖8 簡化率85%時組件二局部對比

5.2 幾何誤差分析比較

TCPGF算法在保證誤差最小的原則下進(jìn)行實(shí)驗(yàn)，為了更好地衡量該算法的優(yōu)劣性，首先定量分析組件一、二在簡化率為15%、25%、35%、45%、55%、65%、75%、85%下的 Hausdorff 距離誤差；再通過誤差比較工具M(jìn)etro(v4.07)測量模型簡化率為15%和85%時的最大誤差和平均誤差，根據(jù)實(shí)驗(yàn)結(jié)果驗(yàn)證本文算法性能。

定義Hausdorff 距離為：

Dist(A,B)=max{min{d(pA,pB)}}

(20)

其中，d(pA,pB)為點(diǎn)pA與點(diǎn)pB之間的距離。

圖9和圖10給出了文獻(xiàn)[5]算法、文獻(xiàn)[6]算法以及本文算法的Hausdorff距離誤差對比結(jié)果。由圖9、圖10可知，當(dāng)簡化程度相同時，使用本文算法得到的組件一的Hausdorff距離誤差比文獻(xiàn)[5]算法降低了28%～37%，比文獻(xiàn)[6]降低了3%～28%；對于組件二模型，使用本文算法簡化的幾何誤差比文獻(xiàn)[5]降低13%～30%，比文獻(xiàn)[6]算法降低3%～18%，可以看出使用本文算法計(jì)算得出的模型誤差明顯小于其他2種算法，能夠更好地逼近原始模型。

Metro誤差比較工具由Cignoni[17]等在論文中提出設(shè)計(jì)，是至今評價誤差的主要量化標(biāo)準(zhǔn)，使用Metro測量出的誤差對比如表1所示。

圖9 不同算法下組件一模型Hausdorff距離誤差對比

圖10 不同算法下組件二模型Hausdorff距離誤差對比

表1 組件一、二簡化誤差對比

從表1對比數(shù)據(jù)分析可得，在簡化程度較高時，使用本文中方法簡化得到的平均誤差能夠穩(wěn)定在0.069 mm內(nèi)，均小于其他算法。隨著簡化率的升高，計(jì)算出的最大誤差值與其他2種算法相比差距也變大，這是因?yàn)樽畲笳`差一般產(chǎn)生在三角形面片密集的區(qū)域，而改進(jìn)的算法在計(jì)算簡化誤差時加入了網(wǎng)格顯著度因子，可以有效地控制防止模型顯著度較高區(qū)域被過度簡化，保留了特征點(diǎn)和邊，從而較好地保持模型初始特征以及拓?fù)湫浴?/p>

5.3 時間開銷分析比較

時間開銷是衡量模型簡化算法是否高效的重要指標(biāo)之一，本文挑選組件一、二模型簡化率分別為15%、55%、85%時算法所花費(fèi)的時間作為三組對比實(shí)驗(yàn)，實(shí)驗(yàn)數(shù)據(jù)如圖11、圖12所示。通過數(shù)據(jù)對比分析，可以得出結(jié)論：模型越復(fù)雜，其簡化耗費(fèi)時間越多，由于本文算法需要計(jì)算體積比以及網(wǎng)格顯著度，所以算法耗時增加，但得到的簡化模型質(zhì)量有較大的提高，且算法耗時差距在毫秒級別，故算法增加的時間開銷在可接受的范圍內(nèi)。

圖11 不同算法下組件一模型簡化耗時對比

圖12 不同算法下組件二模型簡化耗時對比

6 結(jié)論

提出了一種保持幾何特征的導(dǎo)彈發(fā)射車模型簡化算法，解決了傳統(tǒng)QEM算法簡化模型造成特征丟失、網(wǎng)格過于均勻的缺點(diǎn)。通過實(shí)驗(yàn)結(jié)果可知，改進(jìn)算法時間開銷較其他2種算法有所增加但差別較小，在可接受的范圍內(nèi)。在模型簡化率較高時，模型簡化平均誤差穩(wěn)定在0.069 mm內(nèi)，并且能夠生成質(zhì)量較高簡化模型，有效防止模型特征部位退化，對于提高虛擬戰(zhàn)場仿真場景模型加載速度以及人機(jī)交互流暢性具有重要作用和積極意義。下一步工作需要設(shè)計(jì)并行計(jì)算程序，采用GPU提高算法效率，同時在TCPGF算法的基礎(chǔ)上考慮紋理、光照等多維因素的影響，實(shí)現(xiàn)對帶有紋理模型的簡化。