大規(guī)模地形真三維可視化系統(tǒng)設(shè)計與實現(xiàn)

摘要:對已有算法進(jìn)行了綜合及改進(jìn)，對地形繪制中的四叉樹剖分控制#65380;DEM分塊#65380;紋理自動分塊#65380;地形數(shù)據(jù)的數(shù)據(jù)庫存儲#65380;視見體剪裁#65380;誤差控制#65380;裂縫拼接等方面進(jìn)行了深入研究，提出了改進(jìn)方法，并結(jié)合OpenGL立體顯示技術(shù)，基于微機平臺實現(xiàn)了一個簡潔#65380;快速的大規(guī)模真三維立體地形實時繪制原型系統(tǒng)，達(dá)到了很好的效果。實驗結(jié)果表明，該算法實現(xiàn)簡單#65380;內(nèi)存開銷較少#65380;CPU耗費小，具有較低的時間#65380;空間開銷，適于大規(guī)模地形的真三維實時可視化。

關(guān)鍵詞:地形可視化;連續(xù)細(xì)節(jié)層次;真三維;實時漫游;視區(qū)剪裁

中圖分類號:TP317.4文獻(xiàn)標(biāo)志碼:A

文章編號:1001－3695(2008)02－0603－04

0引言

地形三維可視化技術(shù)近年來一直是相關(guān)領(lǐng)域的熱點研究問題，在三維仿真和虛擬地理環(huán)境中占有十分重要的地位。隨著遙感技術(shù)#65380;衛(wèi)星技術(shù)的發(fā)展，獲取高分辨率的數(shù)字高程數(shù)據(jù)以及影像紋理數(shù)據(jù)成為可能，也使地形高程數(shù)據(jù)和紋理數(shù)據(jù)異常龐大，超出了一般圖形系統(tǒng)的實時渲染和內(nèi)存管理能力，對地形的實時繪制也提出了更高的要求。因此地形三維可視化技術(shù)研究的關(guān)鍵問題就是三維地形模型的管理#65380;調(diào)度與實時渲染，以達(dá)到提高地形實時顯示速度和最大程度提高視覺效果的最佳平衡。國內(nèi)外在這方面進(jìn)行了很多研究[1~11]。本文對前人算法進(jìn)行了深入的研究和比較，提出了一種基于規(guī)則網(wǎng)格的#65380;視點相關(guān)(view－dependent)的連續(xù)LOD地形模型的生成和實時繪制算法。在此算法中，采用地形小塊(block)來組織數(shù)據(jù)，建立了視參數(shù)(視點位置#65380;視線方向#65380;地形起伏程度等)相關(guān)的誤差評價函數(shù)，實現(xiàn)了視點相關(guān)的連續(xù)LOD地形模型的實時生成與繪制，并針對地形LOD算法中的幾個關(guān)鍵技術(shù)進(jìn)行了改進(jìn)，提出的繪制算法在PC上達(dá)到了很好的效果。該算法的主要特點包括:a)給出了影像紋理自動分塊原則和方法，實現(xiàn)紋理的自動分塊，而不是以往研究的手工分塊;b)實現(xiàn)了基于Oracle OCI，解決了大規(guī)模地形數(shù)據(jù)(DEM和影像紋理)數(shù)據(jù)庫存儲和調(diào)度問題，保證了數(shù)據(jù)的安全性，而不是以往研究的文件管理方式;c)提出的簡化扇形視見體剪裁方法，使視見體剪裁計算簡單而快速;d)DEM子塊單獨構(gòu)建LOD，塊內(nèi)分辨率任意，提出向左向下原則，簡化了DEM子塊間裂縫拼接方法;e)基于立體透視投影原理，實現(xiàn)了地形真三維(3.0維)可視化，而不是以往研究的偽三維(2.5維)。

1基于四叉樹動態(tài)多分辨率三維地形的實現(xiàn)

1.1基于四叉樹結(jié)構(gòu)的地形LOD模型算法

基于四叉樹結(jié)構(gòu)的LOD模型構(gòu)造算法實質(zhì)是通過遞歸的方法對地形進(jìn)行從頂向下的四叉樹劃分[9]。在劃分過程中實時計算節(jié)點誤差。如果該節(jié)點誤差大于限定的閾值，則對該節(jié)點所在區(qū)域繼續(xù)進(jìn)行劃分，直到所有節(jié)點的誤差小于給定的閾值。基于四叉樹結(jié)構(gòu)的LOD算法數(shù)據(jù)結(jié)構(gòu)如圖1所示。

1.2地形數(shù)據(jù)的分塊

目前的計算機內(nèi)存容量仍然有限，大規(guī)模的地形數(shù)據(jù)不可能一次性地調(diào)入內(nèi)存。為此，筆者提出了一種基于數(shù)據(jù)分塊#65380;部分?jǐn)?shù)據(jù)常駐內(nèi)存#65380;塊內(nèi)分層簡化的處理策略。其基本思想是:首先將研究區(qū)地形數(shù)據(jù)劃分為大小相同的m行n列，每個子塊邊長為2n+1，命名為RowiColj( i，j分別為該子塊所在的行和列)，左下角為第0行第0列，對于最右側(cè)和最上側(cè)不滿足大小相同要求的塊，以無效數(shù)據(jù)(如-9 999)填充，如圖2中的灰色線填充部分;然后對每一個數(shù)據(jù)分塊按照四叉樹結(jié)構(gòu)進(jìn)行組織，以二進(jìn)制格式存儲到數(shù)據(jù)庫中。考慮到Intel的CPU內(nèi)存頁大小是4 KB，塊的大小取33×33較好，這樣在一定程度上提高了存儲效率，降低了內(nèi)存缺頁的次數(shù)，同時數(shù)據(jù)調(diào)度也不會太頻繁。

1.3影像紋理的自動分塊

由于影像數(shù)據(jù)占用較大的存儲空間，而且一般的計算機圖形渲染設(shè)備限制了單次裝載影像的大小，如目前的OpenGL渲染設(shè)備支持的單張影像的最大范圍為2 048×2 048，而在實際多數(shù)情況下地形影像的范圍遠(yuǎn)遠(yuǎn)大于這個限制數(shù)量的大小。需要對大范圍的影像紋理進(jìn)行分塊處理，即在平面空間上將影像分割成一系列規(guī)則的影像塊。

影像分塊分為規(guī)則分塊(一個影像塊對應(yīng)一個或多個DEM子塊)和不規(guī)則分塊(一個影像塊并不對應(yīng)整數(shù)個DEM子塊)。在實際應(yīng)用效率上，不規(guī)則分塊將造成大量紋理數(shù)據(jù)冗余，而且在紋理影像塊調(diào)度時計算繁瑣，因此，這里采用規(guī)則分塊中的一個影像塊對應(yīng)一個DEM子塊，漫游時可立即確定所應(yīng)調(diào)入的紋理影像塊。

通常情況下，影像紋理覆蓋范圍與地形并不是完全重合，因此在分塊時要進(jìn)行如下判斷，如圖3所示。

1.6LOD模型構(gòu)造中裂縫的處理

LOD模型構(gòu)造算法的另外一個重要特征是保證不同分辨率塊之間模型的無縫隙拼接，從而保證在模型漫游或可視化過程中不會產(chǎn)生漏洞，保證LOD模型結(jié)構(gòu)的有效性。地形是按照分塊存儲#65380;調(diào)度和渲染的，這樣就包括地形塊內(nèi)部和地形塊之間的兩種裂縫處理。

1)地形塊內(nèi)裂縫的處理對于同一地形塊內(nèi)的區(qū)域而言，由于不同的地形子塊間的分辨率不一樣，在相鄰精度等級相差一倍以上時，即在具有不同細(xì)節(jié)的地形間會出現(xiàn)裂縫現(xiàn)象。根據(jù)設(shè)計的四叉樹數(shù)據(jù)結(jié)構(gòu)，采用一定算法對縫隙進(jìn)行縫合，在渲染地形時進(jìn)行判斷，如果有縫隙則進(jìn)行一定的處理。這里采用垂直邊線進(jìn)行裂縫處理，對已經(jīng)劃分好的地形網(wǎng)格節(jié)點進(jìn)行第二次遍歷，遍歷時對相鄰節(jié)點精度進(jìn)行比較。如果相鄰的網(wǎng)格精度相差超過一倍，則在兩個網(wǎng)格之間增加一條邊線，如圖6所示。

2)相鄰地形塊之間裂縫的處理在構(gòu)建LOD模型中每個DEM子塊都是單獨進(jìn)行的，這樣可以有效提高LOD建模速度。當(dāng)相鄰兩個block具有不同分辨率層次時，具有較高分辨率層次的block具有更多的高程點，兩者共享邊上就會出現(xiàn)T連接，引起裂縫，如圖7所示。在對每個block構(gòu)建LOD模型時，已經(jīng)存儲了每個節(jié)點的分割狀態(tài)及高度，因此，算法采用后繪制的block，其左共享邊界向其前一列block看齊，下共享邊界向其下一行block看齊，即向左向下原則，從而解決相鄰地形塊之間裂縫問題，如圖7所示。

2系統(tǒng)優(yōu)化關(guān)鍵技術(shù)

2.1視錐體裁剪

剪裁是地形簡化重要的一環(huán)，在特定視點下，地形大部分區(qū)域均位于視錐體之外，不需要繪制，應(yīng)在預(yù)處理階段剔除掉，因此，對視錐體外的數(shù)據(jù)進(jìn)行剪裁是提高顯示效率的關(guān)鍵之一。裁剪運算要占用較多的時間。傳統(tǒng)的裁剪算法是解一個方程組，將每個三角形與視景體的六個裁剪面進(jìn)行比較，判斷是否可見;當(dāng)處理的數(shù)據(jù)量很大時，會消耗大量的處理時間，導(dǎo)致渲染的速度非常慢。為了加快處理速度，忽略上#65380;下剪裁面和近剪裁面，將視景體投影到x－z平面上，建立扇形剪裁區(qū)域，將節(jié)點(格網(wǎng)塊)作為裁剪的最小單元進(jìn)行裁剪，對數(shù)據(jù)塊的節(jié)點進(jìn)行可見性測試。

首先以每個地形塊的幾何中心為圓心，半徑為r，為每個地形塊建立球形包圍區(qū)域，以該球表示當(dāng)前的地形塊來完成各種裁減操作。由于所有的地形塊大小相同，包圍球的大小也相同。判斷每個包圍球的球心在x－z平面上的投影是否落于扇形內(nèi)。如果是則繪制對應(yīng)的地形塊;否則分別計算球心到扇形兩條邊的距離，如果最小值小于r，則繪制對應(yīng)的地形塊(圖8)。

2.2背面剔除

背面剔除是在地形繪制前，剔除掉視方向背離的多邊形，只繪制面向視點的多邊形，從而減少繪制的多邊形數(shù)目。可通過計算視線方向和多邊形表面法向量的夾角來確定是否剔除。

視線方向和多邊形表面法向量的夾角可以轉(zhuǎn)換為向量間夾角的計算問題。設(shè)向量u和v的夾角為α(較小的那個角作為夾角)，為此，構(gòu)造角α的對邊向量u-v，從而u#65380;v和u-v向量構(gòu)成了一個三角形，如圖9所示。

2.3大規(guī)模數(shù)據(jù)的動態(tài)調(diào)度

大范圍的地形數(shù)據(jù)通常非常龐大，難以全部顯示，即使是利用一組LOD模型也難以做到。要實現(xiàn)形交互式渲染，每次只能讀取其模型的一部分來進(jìn)行;同時，隨著視點和視線變化，參與計算的這一部分細(xì)節(jié)的詳略程度也應(yīng)動態(tài)地作相應(yīng)改變[12]。維持這樣一個與視點相關(guān)#65380;視線相關(guān)的基于動態(tài)連續(xù)LOD模型的三維場景，需要一個動態(tài)視景更新機制來對數(shù)據(jù)進(jìn)行有效的組織與管理。地形數(shù)據(jù)經(jīng)過分塊處理后，建立如下實時顯示的分頁機制:視點始終位于數(shù)據(jù)頁的中點附近，在漫游過程中，隨著視點的移動，不斷更新數(shù)據(jù)頁中的數(shù)據(jù)塊，通過判斷視點的當(dāng)前位置(xe，ye)與數(shù)據(jù)頁幾何中心(xc，yc)間的兩個方向的偏移量:

當(dāng)Δx為正時，視點向x的正軸方向移動;反之則向負(fù)方向移動。如果當(dāng)Δy≥cellwidth(數(shù)據(jù)塊的寬度)時，將移動方向向上新的一行數(shù)據(jù)塊讀入數(shù)據(jù)頁中，同時將反方向的一行數(shù)據(jù)塊從數(shù)據(jù)頁中刪除，如圖11所示。同理，根據(jù)Δx與Δy進(jìn)行八個方向的移動，將移動方向上新的一行或一列數(shù)據(jù)讀入數(shù)據(jù)頁中，同時將反方向的另一行或另一列數(shù)據(jù)塊從數(shù)據(jù)頁中刪除。這樣，根據(jù)視點與數(shù)據(jù)頁幾何中心的偏移量大小情況，不斷更新數(shù)據(jù)頁中的內(nèi)容，實現(xiàn)大范圍的動態(tài)實時漫游。

3地形真三維可視化的實現(xiàn)

3.1立體透視投影原理的數(shù)學(xué)描述

將不同的圖像分別放置入左右眼緩沖區(qū)，經(jīng)透視投影，將產(chǎn)生一個無論在幾何外觀上還是感覺上都非常好的立體效果。一個高質(zhì)量的立體圖像包括兩個立體部分，這兩部分都是透視投影，且它們的投影中心(攝像機)在位置上平行對稱，如圖12所示。

利用式(5)和(6)計算出來一對立體投影時，所有可能的三維點將投影到正視差區(qū)。左#65380;右攝像機的透視投影能很好地平衡視差效果，使合成結(jié)果更具有立體感。

3.2基于OpenGL真三維立體地形實現(xiàn)

在初始化每個顯示窗口時加載立體緩存支持(兩個前臺緩存和兩個后臺緩存)，分別設(shè)置左右眼的投影矩陣，并在后臺緩存中繪制場景;最后將后臺與前臺緩存互換，這樣后臺緩存上的圖像就被顯示出來，而原來的前臺緩存變?yōu)楹笈_緩存用于新的繪圖。整個繪圖過程就是這樣的循環(huán)往復(fù)過程。

將左右眼圖像分別寫入左右緩沖區(qū)中的偽代碼如下:

4結(jié)束語

根據(jù)上述算法，本文基于微機平臺實現(xiàn)了一個簡潔#65380;快速的大規(guī)模真三維立體地形實時繪制原型系統(tǒng)，并結(jié)合OpenGL立體顯示技術(shù)，實現(xiàn)了真三維立體地形，達(dá)到了很好的效果，如圖13所示。實驗運行環(huán)境:微機配置 CPU Pentium4 2.8 GHz#65380;內(nèi)存 512 MB#65380;nVIDIA QuadroFX 4500 512 MB立體圖像卡#65380;17英寸顯示器且分辨率設(shè)為 1 024×768像素#65380;顯存 128 MB;DEM數(shù)據(jù)原始采樣點數(shù)目為 2 800×2 200，影像數(shù)據(jù)原始采樣點數(shù)目為7 438×8 114(172 MB);在啟動光照和紋理模型的條件下，平均刷新速率為30 fps。

參考文獻(xiàn):

[1]萬定生，龔匯豐.一種基于四叉樹的大規(guī)模地形實時生成算法[J].計算機工程與應(yīng)用，2005，41(33):186－189.

[2]LINDSTROM P，PASCUCCI V. Visualization of large terrains made easy[C]//Proc of IEEE Visualization.2001:363－370.

[3]CLARK J H.Hierarchical geometric models for visible surface algorithms [J]. Communication of the ACM， 1996，19(10):547－554.

[4]GERSMER T. Top－down view－dependent terrain triangulation using the octagon metric[C]//Proc of Eurographics Symposium on Geometry Processing. 2003:1－11.

[5]EVANS W，KIRKPATRICK D， TOWNSEND G. Right－triangulated irregular networks[J]. Algorithmica，2001，30(2):264－286.

[6]BAO Xiao－h(huán)ong， PAJAROLA R. LOD－based clustering techniques for efficient large－scale terrain storage and visualization[C]//Proc of SPIE Conference on Visualization and Data Analysis. 2003:225－235.

[7]陳剛，夏青，萬剛. 地形RSG模型的動態(tài)構(gòu)網(wǎng)算法[J]. 測繪學(xué)報，2002，31(1):44－48.

[8]LINDSTROM P，KOLLER D，RIBARSKY W，et al. Real－time conti－nuous level of detail rendering of height fields[C]//Proc of ACM SIGGRAPH. 1996:109－118.

[9]殷宏，許繼恒，周良偉，等.基于限制四叉樹的大規(guī)模地形可視化及其實現(xiàn)[J]. 計算機應(yīng)用研究，2006，23(5):151－153.

[10]蘇虎，周美玉.一種大規(guī)模地形的實時繪制算法[J]. 武漢大學(xué)學(xué)報:工學(xué)版，2003，36(3):81－85.

[11]見英，葉榛.一種實時視景仿真中高度場地形繪制算法[J].系統(tǒng)仿真學(xué)報，2005，17(1):83－86.

[12]李清泉.三維空間數(shù)據(jù)的實時獲取#65380;建模與可視化[M].武漢:武漢大學(xué)出版社，2003:236－237.

“本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文”