陳雨，張建偉，譚詩瀚

（四川大學(xué)視覺合成圖形圖像技術(shù)國防重點學(xué)科實驗室，成都 610065）

0 引言

虛擬環(huán)境沉浸感和逼真度是衡量虛擬現(xiàn)實技術(shù)的重要因素，在游戲、仿真等實際應(yīng)用場景中，三維模型結(jié)構(gòu)復(fù)雜且種類繁多，所以三維場景的實時繪制一直是計算機圖形學(xué)研究的重點。在實際應(yīng)用場景中，模型的精細(xì)度不是越高越好，而是根據(jù)實際應(yīng)用需求，達(dá)到模型視覺效果和系統(tǒng)處理時間的平衡才是最重要的。如果三維模型的精度太高，則繪制時需要處理的數(shù)據(jù)量過大，會加重計算機CPU 和GPU 的負(fù)擔(dān)，輕則渲染延遲，重則可能導(dǎo)致系統(tǒng)癱瘓。

在飛行模擬仿真中，機場三維模型精度要求較高，導(dǎo)致需要處理的模型數(shù)據(jù)量龐大，因此，在場景切換時會出現(xiàn)較長時間的渲染延遲現(xiàn)象，所以如何平衡現(xiàn)有資源實現(xiàn)場景的高效繪制成為了一個亟待解決的問題。當(dāng)某一模型距離視點較遠(yuǎn)時，此時大量的渲染高精度模型就是浪費計算性能，因此，根據(jù)視距，在對渲染效果影響不大的情況下，合理地調(diào)度不同細(xì)節(jié)層次的模型，達(dá)到渲染效果和渲染性能的平衡才是最重要的。而構(gòu)建機場多分辨率模型的關(guān)鍵是根據(jù)實際需求選取合適的模型簡化技術(shù)，所以，本文主要是針對機場三維模型簡化技術(shù)的研究。

1 三維模型簡化算法

網(wǎng)格簡化通過減少模型點、邊和面的數(shù)量，減少繪制時模型數(shù)據(jù)的存儲、傳輸和處理，以此提高三維場景實時繪制的效率。一般三維模型采用幾何結(jié)構(gòu)和紋理結(jié)構(gòu)來進(jìn)行表示，幾何結(jié)構(gòu)多采用三角面片表示，所以，在本文中主要研究基于三角網(wǎng)格的簡化。

目前，網(wǎng)格簡化方法一般可以分為三類：元素刪除法、網(wǎng)格重繪法和元素折疊法[1]。元素刪除主要是對網(wǎng)格幾何點、線和面的刪除，該方法在刪除時需要考慮對模型的幾何特性和拓?fù)浣Y(jié)構(gòu)的影響，時間復(fù)雜度較高。網(wǎng)格重繪法有頂點聚類法，主要思想是利用包圍盒對模型所在空間進(jìn)行劃分，然后合并同一小空間中的頂點。該方法雖然速度很快，但是對于細(xì)節(jié)特征較多的模型誤差很大，且容易造成原模型的三角形退化，拓?fù)浣Y(jié)構(gòu)難以保持。元素折疊法分為了邊折疊和三角形折疊，相比于上兩者，簡化速度更快、適應(yīng)性更高。三角形折疊對建筑物簡化效果較差，為了達(dá)到更好的簡化效果，本文采取基于邊折疊的簡化方式。

邊折疊算法中有兩個關(guān)鍵步驟使得模型的幾何網(wǎng)格變動最小、效果最好，一個是最小折疊代價邊的選擇，一個是新頂點位置的確定。所以，邊折疊誤差的度量十分的重要，它是保證模型視覺效果的關(guān)鍵。本文通過對網(wǎng)格簡化方法的詳細(xì)研究，在基于二次誤差度量的基礎(chǔ)上，根據(jù)機場三維模型的局部特征區(qū)域，提出了一種機場三維模型的網(wǎng)格簡化方法，提高了機場模型簡化的質(zhì)量，滿足了用戶對視覺效果需求的同時，平衡了現(xiàn)有系統(tǒng)的性能。

1.1 邊折疊算法

邊折疊算法由Hoppe 等人提出，其基本思想是將三角網(wǎng)格中一條滿足條件的邊，簡化為一個頂點，同時將與該邊兩個端點相鄰的所有頂點和新頂點相連，并刪除所有退化的邊和面[1]。

邊折疊算法根據(jù)折疊后的新頂點不同分為了半邊折疊算法和全邊折疊算法。半邊折疊的新頂點是原折疊邊頂點的其中一個，全邊折疊的新頂點是通過誤差度量計算新生成的。兩者各有各的優(yōu)勢，前者因新頂點就是原頂點，所以存儲開銷減少了、算法計算量也降低了；后者結(jié)合誤差度量，生成的新頂點可以使邊折疊的代價最小，能更好的保持視覺效果，因此本文選取的是基于全邊折疊的。

1.2 二次誤差度量算法（QEM）

網(wǎng)格模型簡化的根本目的是在減少模型面片數(shù)的同時，確保模型整體的幾何特征基本不變、主要特征區(qū)域保持。因此需要結(jié)合實際應(yīng)用需求來控制幾何誤差，針對不同領(lǐng)域提升模型簡化的質(zhì)量。

目前，比較常用的幾何誤差度量有二次誤差度量、體積誤差度量[2]和豪斯多夫距離度量[3]。二次誤差度量是Garland[4]提出的，相比于后兩者，二次誤差算法計算簡單、效率高，因此二次誤差及其改進(jìn)算法是目前使用最為普遍的。

二次誤差以頂點到其一階鄰域三角面片的距離作為邊折疊簡化的折疊代價。該算法可以分為初始化和迭代：初始化時，首先為模型中的頂點都分配一個二次誤差矩陣，然后通過點的二次誤差矩陣計算出相關(guān)邊的誤差矩陣，最后計算出折疊后新頂點的最佳位置及邊的折疊代價；迭代時，依次選擇代價最小的邊進(jìn)行折疊操作，同時更新新頂點的位置和新邊的折疊代價，不斷迭代簡化至達(dá)到設(shè)置的簡化率。

1.2.1 點的折疊代價計算

定義：模型中一頂點v，v的初始誤差矩陣為Qv，頂點v所關(guān)聯(lián)的三角形集合為Face（v），則頂點v到其一階鄰域三角面片的距離平方和為：

其中：P=[a,b,c,d]T，表示由方程ax+by+cz+d=0所定義的平面，且a2+b2+c2=1。Kp是一個4x4 的對稱矩陣，表示如下：

1.2.2 邊的折疊代價計算

定義：邊（u，v），該邊折疊到新頂點m后，點m的二次誤差矩陣也即為邊（u，v）的二次誤差矩陣，等于Qm=Qu+QV，此時邊（u,v）的折疊代價為：

Δ(m)可用下面的式子表示：

1.2.3 新頂點的位置計算

在該算法中，折疊代價大小取決于新生成的頂點m的位置。新頂點m存在一個最佳的位置，使得Δ(m)達(dá)到局部最小。因誤差函數(shù)是個二次函數(shù)，所以可以通過對式子（1）偏導(dǎo)求最小值，解得m 的最佳位置，式子如下：

關(guān)于新頂點m 的位置：

若系數(shù)矩陣（2）可逆，則方程的解即為新頂點m的最佳位置；

若系數(shù)矩陣（2）不可逆，則新頂點m的位置可以選擇三點（包括點u、點v或邊（u,v）的中點）中折疊代價最小的所對應(yīng)的頂點。

2 算法改進(jìn)

基于二次誤差度量的網(wǎng)格簡化算法側(cè)重于考慮點對模型簡化前后導(dǎo)致的形變量大小，沒有考慮模型的局部特征和網(wǎng)格的幾何特性，導(dǎo)致簡化出來的網(wǎng)格均勻，丟失一些重要的細(xì)節(jié)特征，特別是在簡化率（刪除的三角面片數(shù)/原模型的三角面片數(shù)）比較大的時候。因此，王曉哲等人[5]基于二次誤差度量，提出了一種半自動化的網(wǎng)格簡化算法，用戶通過對感興趣的區(qū)域可以添加權(quán)值來自定義簡化效果，但是這樣可能會導(dǎo)致模型簡化效果不佳，因為一般用戶是不能預(yù)判權(quán)值所對應(yīng)的簡化效果。段黎明等人[6]提出了網(wǎng)格細(xì)分方法，將體積誤差和三角形平展度加入到了誤差度量中，但是該方法可能會導(dǎo)致過共頂點的現(xiàn)象，降低模型網(wǎng)格簡化的質(zhì)量。李少卿等人[7]在二次誤差度量的基礎(chǔ)上加入了對頂點的約束，并對生成新面片的旋轉(zhuǎn)方向進(jìn)行角度誤差控制，提高了模型特征區(qū)域頂點的誤差度量。

為了提高機場三維模型的簡化質(zhì)量，本文在基于二次誤差度量的邊折疊算法上，提出了一種顧及局部特征的機場三維模型邊折疊算法，算法通過預(yù)先對機場三維模型的重要局部區(qū)域的頂點進(jìn)行標(biāo)記，在折疊代價計算時添加頂點權(quán)重來改變簡化序列，對機場的特征區(qū)域加以保留，提高模型簡化的質(zhì)量，滿足用戶需求。

2.1 新誤差度量機制的計算

本文的改進(jìn)算法在邊折疊時，將誤差度量分為了兩部分，一是基于二次誤差的基礎(chǔ)誤差度量；二是對機場三維模型特征區(qū)域的自定義誤差度量。

飛行模擬仿真主要是用于飛行員的模擬訓(xùn)練，在整個場景中需要渲染的模型有：機場三維模型、飛機模型、車輛模型和天空場景等等。其中，最重要的是機場三維模型的繪制，特別是機場模型中的滑行道、跑道和標(biāo)識牌，所以在模型簡化時，需要對重要區(qū)域進(jìn)行保留或者減少簡化。

改進(jìn)算法在讀入.obj 模型文件時，根據(jù)在3dsMax中設(shè)置的區(qū)域名，識別頂點是否屬于重要特征區(qū)域，若是則對頂點進(jìn)行標(biāo)記。在折疊代價計算時，對于邊若有一個頂點被標(biāo)記了，則給邊的折疊代價加權(quán)值w，增加該邊的折疊代價，改變簡化序列的順序，使模型重要局部區(qū)域的特征得以保持。

2.2 權(quán)值w的設(shè)置

對于初始權(quán)值w的設(shè)定，若是直接給出權(quán)值常數(shù)系數(shù)，則可能會導(dǎo)致重要局部區(qū)域的簡化效果不佳，因為一般無法預(yù)知設(shè)置的權(quán)值所對應(yīng)的簡化效果，可能過小，使得對折疊代價排序的影響微不足道，如將權(quán)值設(shè)置為10，但如果二次誤差的數(shù)量級為104，則簡化序列不受影響。所以本文中權(quán)值w的初始值參考了待簡化的機場模型的二次誤差范圍，即先計算得到所有點的二次誤差值，記錄其中的最大值和最小值，取最大誤差和最小誤差的中值作為初始的權(quán)值。

在邊折疊的迭代中，邊的折疊不僅使得一階鄰域中受影響的頂點的二次誤差Q需要重新計算，而且頂點的權(quán)值w也需要重新計算，使得權(quán)值一直傳遞下去?？紤]到機場模型的應(yīng)用需求是對于這些重要局部區(qū)域盡量保留，同時為減少計算量，所以對重要區(qū)域內(nèi)的點賦予初始權(quán)值w 后，權(quán)值不再改變，使其點相關(guān)的邊折疊代價一直很大，不被折疊。

3 實驗結(jié)果分析

本實驗是在主頻3.40GHz，內(nèi)存8GB 的硬件環(huán)境下完成，高精度機場三維模型由3dsMax 構(gòu)建并導(dǎo)出.obj 格式，以Microsoft Visual Studio 為編程平臺實現(xiàn)該算法。

為了驗證本算法的具有較好的性能，實驗對比了QEM 算法與本文算法的簡化結(jié)果。由于機場三維模型數(shù)據(jù)量太大，實驗時選取了部分模型進(jìn)行實驗，選取的模型為天府機場部分機場建筑物和機場滑行道，如圖1 所示，選取的原始高精度機場模型中包含了113336 個頂點、147775 個三角面片，其中，網(wǎng)格模型中有顏色的網(wǎng)格為機場建筑物部分，其余白色網(wǎng)格為滑行道部分。

圖1

當(dāng)簡化率設(shè)置為0.2 時，圖2（a）為使用了QEM 算法簡化的模型，簡化后包含了98558 個頂點，118219 個三角面片；圖2（b）為使用本文算法簡化的模型，簡化后包含了98558 個頂點，118219 個三角面片。

圖2

從簡化結(jié)果可以看出，本文的算法有效地對機場三維模型進(jìn)行了簡化，相比于普適性的QEM 算法，本文算法可以對機場重要局部區(qū)域滑行道保留更多的細(xì)節(jié)特征，更符合飛行模擬仿真的實際需求。

4 結(jié)語

本文基于二次誤差的邊折疊算法，提出了一種顧及局部特征的機場三維模型邊折疊算法。該算法不僅能夠有效地簡化機場三維模型，還能根據(jù)飛行模擬仿真的應(yīng)用需求，較好地保留機場重要局部區(qū)域。在現(xiàn)有系統(tǒng)性能的基礎(chǔ)上，平衡了渲染質(zhì)量和渲染效率之間矛盾，滿足了用戶需求。根據(jù)不同領(lǐng)域應(yīng)用需求來優(yōu)化簡化算法，不斷提高模型的簡化質(zhì)量已是未來的發(fā)展趨勢。為了更好地提升機場實時渲染效率，在由本文簡化算法生成的機場多分辨率模型的基礎(chǔ)上，還會進(jìn)一步研究根據(jù)不同視點預(yù)調(diào)度不同層次的模型。