大規模地形真三維可視化系統設計與實現

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

關鍵詞:地形可視化;連續細節層次;真三維;實時漫游;視區剪裁

中圖分類號:TP317.4文獻標志碼:A

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

0引言

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

1基于四叉樹動態多分辨率三維地形的實現

1.1基于四叉樹結構的地形LOD模型算法

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

1.2地形數據的分塊

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

1.3影像紋理的自動分塊

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

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

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

1.6LOD模型構造中裂縫的處理

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

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

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

2系統優化關鍵技術

2.1視錐體裁剪

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

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

2.2背面剔除

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

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

2.3大規模數據的動態調度

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

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

3地形真三維可視化的實現

3.1立體透視投影原理的數學描述

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

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

3.2基于OpenGL真三維立體地形實現

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

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

4結束語

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

參考文獻:

[1]萬定生，龔匯豐.一種基于四叉樹的大規模地形實時生成算法[J].計算機工程與應用，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－hong， 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模型的動態構網算法[J]. 測繪學報，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]殷宏，許繼恒，周良偉，等.基于限制四叉樹的大規模地形可視化及其實現[J]. 計算機應用研究，2006，23(5):151－153.

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

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

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

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