于 萍， 張彩明

（1. 淄博師范高等?？茖W(xué)校信息科學(xué)系，山東 淄博 255130；2. 山東大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，山東 濟(jì)南 250101）

地形可視化是是虛擬地理環(huán)境中不可缺少的組成部分，目前國(guó)內(nèi)外研究地形繪制主要基于層次細(xì)節(jié)（Level of Detail, LOD）模型技術(shù)。但在已有的大多數(shù)LOD算法[1-3]中，均隱含著一個(gè)相同的假設(shè)條件，即假定地形表面各處的高程值和顏色等物理屬性，在系統(tǒng)運(yùn)行過程中是固定不變的。然而汽車等運(yùn)載工具在松軟的地表上行駛會(huì)留下清晰的輪胎印跡、炸彈在地面上爆炸會(huì)產(chǎn)生彈坑。像這種地形表面各處的高程值和顏色等物理屬性在系統(tǒng)運(yùn)行過程中不斷變化的動(dòng)態(tài)地形并不滿足假設(shè)條件。并且動(dòng)態(tài)地形的實(shí)時(shí)可視化對(duì)構(gòu)建高逼真度的仿真環(huán)境具有重大的現(xiàn)實(shí)意義，也是視景仿真領(lǐng)域必須解決的重大問題。

利用LOD繪制大規(guī)模地形主要考慮3方面技術(shù)：數(shù)據(jù)組織方式，方便LOD模型生成并避免T-連接和裂縫的產(chǎn)生；誤差判據(jù)，減少每幀需要繪制的三角形數(shù)目提高算法效率并保證地形有較強(qiáng)的真實(shí)感；性能優(yōu)化，幀間連貫性、視錐剔除、三角形條帶化等技術(shù)優(yōu)化算法性能提高算法效率。其中，誤差判據(jù)決定了當(dāng)前視點(diǎn)下，不同分辨率的地形模型需要繪制的三角形結(jié)點(diǎn)。因此，誤差判據(jù)決定著每幀需要繪制的三角形結(jié)點(diǎn)個(gè)數(shù)，取值的大小直接決定著渲染地形的真實(shí)度和算法效率，是LOD中的關(guān)鍵技術(shù)。對(duì)于動(dòng)態(tài)地形，在地形發(fā)生動(dòng)態(tài)形變（即地形的高程值和顏色等屬性發(fā)生變化）時(shí)，更希望通過誤差判據(jù)能較好的體現(xiàn)地形形變效果，增強(qiáng)形變地形的真實(shí)感。目前對(duì)于誤差判據(jù)的研究大致可以分為兩類。

一類是考慮視點(diǎn)因素[1-4]。與視點(diǎn)相關(guān)的誤差計(jì)算，常使用屏幕空間誤差方法。其主要有兩種方法：基于距離及視向的屏幕空間誤差計(jì)算法[5-6]和只基于距離的屏幕空間誤差計(jì)算法[4,7]。通過理論分析和實(shí)驗(yàn)結(jié)果的對(duì)比指出：基于距離及視向的屏幕空間誤差計(jì)算法和只基于距離的屏幕空間誤差計(jì)算法，采用相同的屏幕誤差閾值對(duì)同一分辨率地表網(wǎng)格模型進(jìn)行視點(diǎn)相關(guān)的簡(jiǎn)化時(shí)，兩種簡(jiǎn)化方法的簡(jiǎn)化率相差不大。因此，只基于距離的屏幕空間誤差計(jì)算，因其計(jì)算簡(jiǎn)單得到廣泛的應(yīng)用[7-9]。

另一類考慮地形粗糙度因素[10-11]。地形粗糙度反映的是地形局部起伏劇烈程度的特征量，是較好的體現(xiàn)地形真實(shí)感的重要因素。對(duì)于較平坦的區(qū)域，可以用較低分辨率的三角網(wǎng)格表示；對(duì)于起伏較大的區(qū)域，需要用較高分辨率的三角網(wǎng)格表示。文獻(xiàn)[10]采用局部誤差計(jì)算方法，結(jié)點(diǎn)誤差由結(jié)點(diǎn)周圍5個(gè)結(jié)點(diǎn)的誤差和結(jié)點(diǎn)本身誤差的最大值表示，會(huì)有一定程度“跳躍”感的產(chǎn)生。文獻(xiàn)[11]提出的粗糙度計(jì)算方法需要從葉子頂點(diǎn)開始向上遞歸計(jì)算所有非葉子頂點(diǎn)的誤差，在地形發(fā)生動(dòng)態(tài)形變時(shí)，也會(huì)增加算法的耗費(fèi)時(shí)間，降低算法效率。

動(dòng)態(tài)地形可視化需要在地形發(fā)生形變后能較好的體現(xiàn)地形局部形變效果，但又需滿足地形實(shí)時(shí)繪制的要求。為此，本文利用局部地形的粗糙度構(gòu)造約束條件，加入視點(diǎn)因素后形成帶約束的嵌套誤差判據(jù)方法。不但可以很好地體現(xiàn)地形的形變效果，刻畫局部地形細(xì)節(jié)，還能隱式的避免T-連接和裂縫的產(chǎn)生，同時(shí)降低較平坦區(qū)域冗余三角形的產(chǎn)生。從而在保證動(dòng)態(tài)地形有較強(qiáng)真實(shí)感的前提下，減少每幀中需要繪制的三角形結(jié)點(diǎn)個(gè)數(shù)，提高算法效率。

1 帶約束誤差判據(jù)的可視化算法

本文算法采用基于DAG的三角形二叉樹存儲(chǔ)結(jié)構(gòu)，利用帶約束的誤差判據(jù)計(jì)算誤差，用較少的冗余三角形有效避免T-連接和裂縫的產(chǎn)生。同時(shí)利用延遲判斷的幀間連貫性，減少每幀的繪制時(shí)間提高算法效率。

1.1 基于DAG的三角形二叉樹

本文用三角形二叉樹[3,8,10]結(jié)構(gòu)存儲(chǔ)需繪制的三角形信息。將初始平面的正方形區(qū)域劃分為兩個(gè)等腰直角三角形，并把他們定義為位于二叉樹的最頂層。對(duì)于頂層三角形，連接直角頂點(diǎn)和其斜邊的中點(diǎn)，三角形被平分為兩個(gè)子三角形，定義這兩個(gè)子三角形位于下一精細(xì)層，并稱頂層三角形為其父親。遞歸執(zhí)行該操作，可生成層次結(jié)構(gòu)的三角形二叉樹。在三角形二叉樹的構(gòu)造過程中，實(shí)際上還隱含著嚴(yán)格的頂點(diǎn)引入次序。這種引入次序可用頂點(diǎn)的有向非循環(huán)圖DAG(Directed Acyclic Graph) 來描述。

1.2 帶約束的誤差判據(jù)

只基于距離的屏幕空間誤差計(jì)算，雖然計(jì)算簡(jiǎn)單應(yīng)用廣泛，但沒有考慮地形本身的起伏狀況。并且為避免T-連接和裂縫的產(chǎn)生，通常會(huì)增加冗余三角形。為此，利用局部地形的粗糙度，構(gòu)造約束因子在體現(xiàn)地形本身起伏程度的同時(shí)降低冗余三角形個(gè)數(shù)。

1）約束因子

為了減少冗余三角形個(gè)數(shù)體現(xiàn)局部地形細(xì)節(jié)，利用地形粗糙度構(gòu)造約束因子。考慮到動(dòng)態(tài)地形運(yùn)行中發(fā)生的形變，需要實(shí)時(shí)計(jì)算誤差函數(shù)，為減少實(shí)時(shí)計(jì)算量，本文提出基于方差的局部粗糙誤差函數(shù)。所謂局部粗糙度是指誤差中方差不是計(jì)算整個(gè)地形的方差，而是以結(jié)點(diǎn)為中心包含周圍結(jié)點(diǎn)的局部區(qū)域方差。主要考慮頂點(diǎn)附近局部區(qū)域的高程值對(duì)該頂點(diǎn)高程值的方差累計(jì)效果。取局部地形M×N，點(diǎn)i處構(gòu)造局部粗糙誤差函數(shù)公式如下：

其中，Z(x,y)為局部地形頂點(diǎn)(x,y)的高程值，Zi為該頂點(diǎn)的高程值，n=M×N。利用局部粗糙誤差函數(shù)，構(gòu)造值域在(0,1)區(qū)間內(nèi)的頂點(diǎn)約束因子ki，具體計(jì)算公式如下：

若地形起伏較大，則fi的值較大，此時(shí)ki的值較大接近1。若地形較為平坦，則fi的值較小，此時(shí)ki的值較小。但地形平坦到接近平地時(shí)，會(huì)出現(xiàn)fi的值小于1，甚至為0的情況，此時(shí)ki的值反而較大，不能準(zhǔn)確表示地形的粗糙程度。為此，在分母上修正fi為fi+1+ξ，以保證分母fi和ki的值不為0，其中ξ為接近0的極小數(shù)。如公式（3）所示。

2）帶約束的誤差判據(jù)球

與視點(diǎn)相關(guān)的誤差計(jì)算考慮的是?ABC在引入斜邊AD后所產(chǎn)生的頂點(diǎn)空間誤差，用引入斜邊前后高程值差的絕對(duì)值表示δD=|ZD-(ZB+ZC) /2|。由此得到的只基于距離的屏幕空間誤差計(jì)算公式為：

其中，λ表示對(duì)象空間中的單位長(zhǎng)度，τ表示屏幕的空間誤差；p，e分別為結(jié)點(diǎn)、視點(diǎn)在三維對(duì)象空間中的位置；d為視點(diǎn)到屏幕平面的距離；δ表示與結(jié)點(diǎn)相對(duì)應(yīng)的對(duì)象空間誤差。

在給定屏幕空間誤差閾值τ后，可以得到結(jié)點(diǎn)原始誤差判據(jù)球半徑為：

該式可看作在三維空間中以頂點(diǎn)i為球心,半徑為ri的球面, 稱之為頂點(diǎn)i的原始誤差據(jù)球。但 只基于視點(diǎn)考慮的誤差判據(jù)球沒有考慮地形局部粗糙程度，會(huì)產(chǎn)生一定的冗余三角形。為減少較平坦地區(qū)冗余三角形的產(chǎn)生，同時(shí)保留局部起伏較大區(qū)域的層次細(xì)節(jié)，利用地形局部粗糙度構(gòu)造的約束因子ki約束誤差判據(jù)球。得到：

但利用帶約束的誤差判據(jù)球，在繪制地形時(shí)不可避免的會(huì)出現(xiàn)T-連接和裂縫。所謂T-連接是指一個(gè)三角形或多個(gè)三角形共享另一個(gè)三角形的一條邊的一部分。T-連接容易在繪制時(shí)產(chǎn)生地形裂縫，即使不產(chǎn)生裂縫，在繪制時(shí)T-連接出現(xiàn)的地方也會(huì)產(chǎn)生不連續(xù)的點(diǎn)，給人不真實(shí)的感覺。為此，利用嵌套誤差判據(jù)球?qū)⒏鱾€(gè)頂點(diǎn)間的包圍關(guān)系隱式的包含在誤差評(píng)價(jià)函數(shù)中，從而使所有需要分裂的子結(jié)點(diǎn)在繪制前其父結(jié)點(diǎn)早已分裂。因此，對(duì)與非葉子頂點(diǎn)需計(jì)算其嵌套誤差判據(jù)球，確保孩子頂點(diǎn)要求分裂時(shí)父結(jié)點(diǎn)都已經(jīng)分裂。修改后頂點(diǎn)的帶約束嵌套誤差判據(jù)球，球心仍是該頂點(diǎn)的空間位置，半徑計(jì)算公式如下：

其中，ri為由式（6）所確定的頂點(diǎn)i的帶約束誤差判據(jù)球半徑，pi、pj分別為頂點(diǎn)i及其孩子頂點(diǎn)j的空間位置，Ci為DAG中頂點(diǎn)i的孩子集合，Rj為頂點(diǎn)j的嵌套誤差判據(jù)球半徑，稱式（7）所定義的誤差判據(jù)球?yàn)轫旤c(diǎn)的嵌套誤差判據(jù)球。

3）動(dòng)態(tài)形變后的誤差計(jì)算

若地形在實(shí)時(shí)繪制階段發(fā)生動(dòng)態(tài)性變，為盡可能的減少實(shí)時(shí)繪制中算法的計(jì)算量，本文采用與靜態(tài)地形不同的處理方法。給每個(gè)發(fā)生形變的頂點(diǎn)增加一位表示地形形變的標(biāo)志位，當(dāng)實(shí)時(shí)繪制中地形發(fā)生動(dòng)態(tài)形變時(shí)，通過改變標(biāo)志位狀態(tài)來確定發(fā)生形變的地形區(qū)域頂點(diǎn)。對(duì)形變區(qū)域的頂點(diǎn)重新計(jì)算其嵌套誤差判據(jù)球，并利用預(yù)處理時(shí)生成的DAG計(jì)算其祖先的嵌套誤差判據(jù)球。在計(jì)算形變區(qū)域的頂點(diǎn)的祖先嵌套誤差判據(jù)球時(shí)，并不需要計(jì)算所有的祖先結(jié)點(diǎn)，當(dāng)重新計(jì)算的祖先結(jié)點(diǎn)的嵌套誤差判據(jù)球沒有改變時(shí)，即可停止其它祖先結(jié)點(diǎn)的誤差計(jì)算。

1.3 幀間連貫性

視點(diǎn)連續(xù)移動(dòng)時(shí)，相鄰幀間地形的層次細(xì)節(jié)模型具有很大的連貫性，需繪制的三角形變化不大。因而利用幀間的連貫性[8-9]，對(duì)實(shí)時(shí)顯示的地形進(jìn)行處理。從前一幀中顯示的三角形二叉樹的結(jié)點(diǎn)出發(fā)，根據(jù)當(dāng)前視點(diǎn)的變化情況，判定下一幀需要繪制的結(jié)點(diǎn)。對(duì)視點(diǎn)離開其嵌套判定誤差球的頂點(diǎn)進(jìn)行合并操作，對(duì)視點(diǎn)進(jìn)入其嵌套判定誤差球的頂點(diǎn)進(jìn)行分裂操作，對(duì)其它前一幀中顯示的頂點(diǎn)可直接顯示?？紤]到ΔABC，如圖1所示，E表示視點(diǎn)位置，當(dāng)E進(jìn)入半徑為r的誤差判據(jù)球區(qū)域內(nèi)時(shí)，ΔABC才需要分裂，當(dāng)E離開半徑為R的誤差判據(jù)球區(qū)域時(shí)，ΔABC才需要合并。而當(dāng)視點(diǎn)E在兩個(gè)誤差判據(jù)球間移動(dòng)時(shí)，ΔABC無需進(jìn)行視距與誤差判據(jù)球的判斷可直接顯示。因此，本文利用延遲因子，預(yù)測(cè)出頂點(diǎn)在當(dāng)前視點(diǎn)移動(dòng)速度下，最長(zhǎng)延遲分裂或合并的次數(shù)。對(duì)上一幀中顯示的頂點(diǎn)，若其延遲因子遞減后非零則無需判斷可直接顯示。從而無需判斷上一幀中所有顯示的頂點(diǎn)，以減少實(shí)時(shí)繪制時(shí)的計(jì)算量，提高算法效率。若地形在實(shí)時(shí)繪制階段發(fā)生動(dòng)態(tài)性變，除了重新計(jì)算形變區(qū)域的頂點(diǎn)嵌套誤差判據(jù)球外，還需重新計(jì)算形變區(qū)域各個(gè)頂點(diǎn)的延遲因子。并在計(jì)算后對(duì)形變區(qū)域的各個(gè)結(jié)點(diǎn)重新判斷，確定頂點(diǎn)是否需要判斷。

圖1 延遲示意圖

2 實(shí)現(xiàn)和分析

在PC機(jī)上實(shí)現(xiàn)了算法，并利用實(shí)驗(yàn)地形數(shù)據(jù)進(jìn)行了相關(guān)實(shí)驗(yàn)。實(shí)驗(yàn)硬件環(huán)境為：Intel P4 2.0GHz, 256M RAM, nVIDI2 A GeForce2 400 顯卡；軟件環(huán)境為：Windows 2000, VC6.0和OpenGL。

1）靜態(tài)地形誤差和效果圖比較

利用實(shí)驗(yàn)地形數(shù)據(jù)[13]中的crater、island、maui 3個(gè)地形，分別對(duì)文獻(xiàn)[3]、文獻(xiàn)[11]和本文方法進(jìn)行了比較。實(shí)驗(yàn)中局部粗糙度因子取3×3局部地形高程值。對(duì)每個(gè)地形數(shù)據(jù)分別就其某視點(diǎn)下渲染的三角形個(gè)數(shù)和全局高程差進(jìn)行了對(duì)比，如圖2、圖3所示。由圖2可以看出在地形渲染過程中本文算法所需繪制的三角形個(gè)數(shù)在多數(shù)情況下能明顯的低于文獻(xiàn)[3,11]。由圖3可以看出全局高程差3種計(jì)算方法相差不大。

圖2 3種地形下3種方法的三角形渲染個(gè)數(shù)對(duì)比

圖3 3種地形下3種方法的全局高程差對(duì)比

圖4 和圖5分別是某視點(diǎn)下，對(duì)較陡峭地形和較平坦地形的繪制效果圖，依次分別為全部三角形繪制，文獻(xiàn)[3]、文獻(xiàn)[11]和本文算法的比較，由圖4、圖5可以看出，雖然本文算法減少了繪制的三角形數(shù)目，但仍然能夠很好地體現(xiàn)地形地貌。

2）動(dòng)態(tài)形變性能和效果比較

對(duì)地形發(fā)生動(dòng)態(tài)形變的區(qū)域?qū)Ρ攘宋墨I(xiàn)[11]和本文方法。圖6為文獻(xiàn)[11]和本文方法渲染的地形形變效果圖，由圖可以看出本文方法能很好的用較少的三角形繪制地形的形變效果。圖7比較了兩種方法在形變時(shí)的平均幀速、三角形個(gè)數(shù)和全局高程差，由圖可以看出本文方法在繪制時(shí)間和繪制三角形個(gè)數(shù)上明顯優(yōu)于文獻(xiàn) [11]，而全局高程差兩種方法差不多。

圖6 動(dòng)態(tài)形變效果比較

圖7 動(dòng)態(tài)形變幀速、三角形個(gè)數(shù)和全局高程誤差比較

3 結(jié) 束 語

本文利用視點(diǎn)和地形本身粗糙因素，提出一種帶約束的誤差判據(jù)方法。該方法在隱式避免T-連接和裂縫生成的前提下，能有效地減少冗余的三角形結(jié)點(diǎn)個(gè)數(shù)，較好地提高算法效率，并且在地形發(fā)生形變時(shí)，能較好地體現(xiàn)地形的形變效果。實(shí)驗(yàn)結(jié)果表明，該方法在保證地形有較強(qiáng)真實(shí)感的前提下，能很好地減少三角形個(gè)數(shù)，提高算法效率。

[1]Lindstrom P, Koller D, Ribarsky W, et al. Real-time continuous level of detail rendering of height Fields [C]//Proceedings of SIGGRAPH’96, New Orleans, 1996: 109-118.

[2]Hoppe H. Smooth view-dependent level-of-detail control and its application to terrain rendering [C]//Proceedings of IEEE Visualization’98, New Caledonia,1998: 135-142.

[3]Duchaineau M, Wolinsky M, Sigeri D E, et al. Roaming terrain：real-time optimally adapting meshes [C]//Proceedings of IEEE Visualization’97, Phoenix, 1997:81-88.

[4]Lindstrom P, Pascucci V. Visualization of large terrains made easy [C]//Proceedings of IEEE Visualization’ 2001, san Diego, 2001: 363-370.

[5]趙友兵, 石教英, 周 驥, 等. 一種大規(guī)模地形的快速漫游算法[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2002,14(7): 624-628.

[6]陳少強(qiáng), 朱鐵穩(wěn), 李 琦, 等. 大規(guī)模多分辨率地形模型簡(jiǎn)化生成方法[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2005, (2): 273-278.

[7]王林旭, 李思昆, 潘曉輝. 動(dòng)態(tài)地形的實(shí)時(shí)可視化[J].計(jì)算機(jī)學(xué)報(bào), 2003, (11): 1524-1531.

[8]He Yefei, Cremer J, Papelis Y. Real-time extendibleresolution display of on-line dynamic terrain [C]//Proceedings of Graphies Interface, Calgary, Alberta.2002: 27-29.

[9]Chen Guojun, Zhang Jing. Dynamic terrain LOD with region pres ervation in 3D game engine [C]//Proceedings of the First Inte rnational Conference on E- Learning and Games, LNCS 3942, 2006: 711-715.

[10]R?ttger S, Heidrich W, Slusallek P, et al. Real-time generation of continuous lebels of detail for height fields [C]//Proceedings of the 6th International Conference in Central Europe on Computer Graphics and Visualization, 1998: 313-322.

[11]陳國(guó)軍, 崔保磊, 陳慶剛. 生成地形細(xì)節(jié)層次的粗糙度誤差判據(jù)[J]. 中國(guó)石油大學(xué)學(xué)報(bào), 2009, (10):168-172.

[12]DISCOE Ben Elevation file repository [EB/OL].http://www.vterrain.org/BT/index.html 2007-09-11.