顧及局部特征的機(jī)場三維模型邊折疊算法

陳雨，張建偉，譚詩瀚

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

0 引言

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

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

1 三維模型簡化算法

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

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

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

1.1 邊折疊算法

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

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

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

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

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

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

1.2.1 點(diǎn)的折疊代價(jià)計(jì)算

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

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

1.2.2 邊的折疊代價(jià)計(jì)算

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

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

1.2.3 新頂點(diǎn)的位置計(jì)算

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

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

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

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

2 算法改進(jìn)

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

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

2.1 新誤差度量機(jī)制的計(jì)算

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

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

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

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

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

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

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

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

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

圖1

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

圖2

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

4 結(jié)語

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