姜藝諾，王 偉，田 澤

(1.西安工程大學 計算機科學學院， 西安 710048； 2.集成電路與微系統(tǒng)設計航空科技重點實驗室，西安 710068)

1 引言

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

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

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

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

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

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

(1)

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

(2)

(3)

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

(4)

解得：

(5)

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

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

(6)

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

圖1 三角形折疊法

3 約束因子的構建

3.1 體積比

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

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

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

設A為三角形的頂點坐標矩陣，|A|為對應坐標矩陣的行列式，則△v1v2v3與原點所圍成的四面體的體積可由式(7)計算：

(7)

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

(8)

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

3.2 網(wǎng)格顯著度

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

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

(9)

(10)

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

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

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

(11)

式中：KG為頂點的高斯曲率;KH為頂點的平均曲率，兩者均通過文獻[16]中計算方法求得。

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

(12)

(13)

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

(14)

(15)

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

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

4 TCPGF算法

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

4.1 折疊代價的計算

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

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

(16)

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

(17)

4.2 新頂點的確定

(18)

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

vi0=(v1+v2+v3)/3

(19)

圖4 三角形重心

4.3 算法步驟

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

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

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

步驟5：若達到需求的簡化率或者隊列為零，則轉到步驟6，否則轉到步驟4；

步驟6：算法終止。

4.4 算法合理性分析

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

5 實驗結果及分析

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

為了驗證改進算法的合理性，實驗采用多種距離誤差以及算法時間開銷作為指標，與文獻[5-6]中模型簡化算法對比。

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

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

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

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

圖6 組件一模型簡化結果對比

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

圖7 組件二模型簡化結果對比

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

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

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

5.2 幾何誤差分析比較

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

定義Hausdorff 距離為：

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

(20)

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

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

Metro誤差比較工具由Cignoni[17]等在論文中提出設計，是至今評價誤差的主要量化標準，使用Metro測量出的誤差對比如表1所示。

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

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

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

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

5.3 時間開銷分析比較

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

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

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

6 結論

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