謝劍薇， 劉 濤， 于鳳坤

（裝備學院 信息裝備系，北京101416）

隨著“數(shù)字地球”（digital earth，DE）［1］和“全球信息網(wǎng)格”（global information grid，GIG）概念的相繼提出，建立具有多分辨率、海量數(shù)據(jù)的大規(guī)模虛擬地形場景在全球范圍受到越來越多的關(guān)注?！皵?shù)字地球”強調(diào)對地球的真三維描述，因此，基于全球三維地形的實時繪制技術(shù)成為面向“數(shù)字地球”的虛擬現(xiàn)實系統(tǒng)的關(guān)鍵技術(shù)之一，即如何在計算機上對數(shù)字地形模型（digital terrain models，DTM）中的地形數(shù)據(jù)進行實時三維顯示、模擬仿真［2］。

減少視景體以外場景的繪制是加快全球海量地形數(shù)據(jù)可視化的有效途徑之一。根據(jù)可見性評估的依據(jù)，可見性剔除算法可分為3類：背面剔除（back face culling）、視域剔除（view frustum culling）和遮擋剔除（occlusion culling）［3］。由于基于全球地形數(shù)據(jù)實時繪制涉及數(shù)據(jù)量非常龐大，一般采用視域剔除算法，即計算當前視域內(nèi)的地形；然后根據(jù)節(jié)點評價準則，對地形進行剖分，得到多分辨率地形可見節(jié)點集。由于節(jié)點之間分辨率不同導致邊界出現(xiàn)裂縫，因此在繪制之前進行不同分辨率節(jié)點之間的無縫處理。本文全球地形數(shù)據(jù)采用四叉樹邏輯存儲結(jié)構(gòu)。

1 地形數(shù)據(jù)組織

由于地理空間采用經(jīng)緯度方式自然分割，因此地形數(shù)據(jù)很適合采用四叉樹結(jié)構(gòu)進行存儲。全球地形數(shù)據(jù)以如下四叉樹［4－5］形式進行組織，如圖1所示。所有地形數(shù)據(jù)均放在全球范圍內(nèi)進行定位，四叉樹的第1層分別對應東西兩半球地形數(shù)據(jù)，然后每一節(jié)點按照地理區(qū)域均勻分割為4個子節(jié)點，如此繼續(xù)，一直分割到所需要的精度。全球地形數(shù)據(jù)以這樣的邏輯四叉樹進行存儲，每個節(jié)點的地理位置是確定的，用經(jīng)緯度表示。每個節(jié)點包含特定范圍地形數(shù)據(jù)，采用規(guī)整網(wǎng)格進行地形數(shù)據(jù)的存儲。通過實驗，每個節(jié)點中數(shù)字高程模型（digital elevation model，DEM）數(shù) 據(jù) 采 用33×33采樣點，數(shù)字正射影像（digital orthophoto map，DOM）數(shù)據(jù)采用256×256采樣點，在這種情況下每一幀數(shù)據(jù)量大小滿足實時顯示的需求，同時以影像為紋理，與地形數(shù)據(jù)匹配效果好。

圖1 全球地形數(shù)據(jù)四叉樹邏輯結(jié)構(gòu)

2 全球地形數(shù)據(jù)快速可見性判定

本文采用基于四叉樹的全球地形快速可見性判定的基本思想是：通過球面解算實現(xiàn)數(shù)據(jù)過濾，減少了圖形繪制的數(shù)據(jù)量。將地球看作一個空間的球面，用相機視域與其求交，剔除視域以外的部分；對視域以內(nèi)的部分，則依據(jù)節(jié)點評價準則，對地形進行剖分，得到一個多分辨率地形可見節(jié)點集，以保證每一幀地形的繪制數(shù)據(jù)量保持基本恒定。

2.1 可見區(qū)域的計算

首先根據(jù)給定的相機參數(shù)（包括視點、觀察方向以及相機內(nèi)參數(shù)），針對球模型計算出可見范圍?？梢妳^(qū)域的計算方法如下：

1）根據(jù)當前相機位置、相機觀察方向、視域和焦距確定相機觀察視域4條錐線的方程，并計算各條錐線與球面的交點；

2）根據(jù)相鄰2條錐線與球面相交的情況，計算相機各個錐面與球面相交的空間圓弧以及相交圓弧的相關(guān)信息（包括圓弧半徑、圓心位置以及圓弧起始點與結(jié)束點）；

3）合并各段圓弧，得到相機視錐與球面相交的輪廓線；

4）根據(jù)輪廓線各段圓弧的角度和對其進行相應采樣，得到一組采樣點集合；

5）將采樣點投影到測量平面坐標，并順序相連，得到一個多邊形區(qū)域，該區(qū)域即為可見區(qū)域。多邊形區(qū)域的頂點坐標用經(jīng)緯度坐標表示。

2.2 多分辨率地形可見節(jié)點集的生成

得到上述的可見區(qū)域后，需要根據(jù)視點以及地形模型對其進行剖分，以得到一個既能滿足視覺質(zhì)量，又能保證數(shù)據(jù)量盡可能小的多分辨率地形節(jié)點集。因此節(jié)點評價準則必須使生成的網(wǎng)格盡量減少幾何形變，在保證實時性的前提下，使畫面質(zhì)量接近全分辨率時的地形［6］。在建立節(jié)點評價準則時，一般要考慮視距與地形本身粗糙程度的影響［7］。本文節(jié)點評價函數(shù)的建立，主要考慮視距的影響，這是因為在后續(xù)過程中會對節(jié)點內(nèi)數(shù)據(jù)進行相應調(diào)整，使得繪制數(shù)據(jù)量滿足實時繪制的需求，所以沒有必要再進行地形粗糙度的判定以進一步減小繪制的數(shù)據(jù)量。

2.2.1 視距標準

從人體視覺仿生角度出發(fā)，希望距離視點近的景物能夠很精確地顯示，距離稍遠的則不用很精確，因此采用距視點距離作為地形節(jié)點剖分依據(jù)。但是目前幾乎所有的視線相關(guān)的距離計算方法，都局限于在距離計算中添加一個不同的視線因子，只是經(jīng)驗公式，且忽略了深度（Z軸）的影響［8］。為此本文采用如下節(jié)點評價標準：計算可見區(qū)域多邊形在當前相機參數(shù)的投影面積，根據(jù)投影面積確定當前節(jié)點是否有必要進行剖分，該評價準則充分考慮了視線方向的影響。多邊形投影面積計算公式為

式中：多邊形由頂點p0，p1，…，pn順時針組成；p′i是點pi的投影坐標；A是當前相機的投影矩陣。

式中：S是多邊形的投影面積；P′ix和P′iy表示點pi的投影坐標x與y值。

如果當前多邊形的投影面積大于給定閾值，則對該多邊形所在的節(jié)點進行細分；否則輸出該節(jié)點。投影面積閾值設置為256×256＝65 536，這樣使得地形數(shù)據(jù)投影尺度與DOM節(jié)點數(shù)據(jù)分辨率一致，可以得到最佳的視覺效果。

2.2.2 多分辨率地形可見節(jié)點集生成流程

在得到當前視點下的可見區(qū)域后，依據(jù)上述的視距標準對可見區(qū)域是否細分進行判斷，由此得到1個多分辨率地形可見節(jié)點集。具體算法流程見圖2所示。

圖2 多分辨率地形可見節(jié)點集生成流程

3 裂縫處理

在對地形進行渲染時，如果相鄰子塊節(jié)點的分辨率不一致，則在構(gòu)建三角形網(wǎng)格時，就會在相接的邊界上出現(xiàn)裂縫，這是地形繪制時必須解決的問題［9］。針對塊內(nèi)“裂縫”問題，不少學者研究采用限制相鄰節(jié)點層次差不超過1的方法消除裂縫，且只適用于少量靜態(tài)地形數(shù)據(jù)場合。但處理海量地形數(shù)據(jù)時，要不斷地對節(jié)點層次差進行判斷，計算量大、耗費CPU時間長［10］。為此本文提出一種新的方法來消除裂縫。本文地形數(shù)據(jù)采用規(guī)整網(wǎng)格結(jié)構(gòu)，由于觀察方向原因，網(wǎng)格各邊界投影長度會有很大差別。若根據(jù)投影長度對此規(guī)則網(wǎng)格進行重采樣，使得邊界采樣點的個數(shù)與投影長度成正比，網(wǎng)格內(nèi)部采樣點依據(jù)邊界情況均勻過渡，如此一來均勻網(wǎng)格變成了一種密度均勻變化的不規(guī)則網(wǎng)格，這樣不僅可以消除裂縫，而且大大減少繪制的復雜度，同時不會影響視覺效果。具體過程如圖3所示。

圖3 網(wǎng)格重采樣消除裂縫

從理論上說，由于相鄰數(shù)據(jù)節(jié)點的相鄰邊界無論分辨率是否相同，它們在屏幕上的投影長度都是相等的；所以，經(jīng)過重采樣簡化處理以后，相鄰數(shù)據(jù)塊的共同邊界的重采樣點分布情況也是相同的，這樣自然而然消除了裂縫。但實際上會出現(xiàn)圖4所示的情況，節(jié)點A右邊界采樣步長為2，節(jié)點B左邊界采樣步長為2，節(jié)點C左邊界采樣步長為4，使得節(jié)點A與節(jié)點B之間出現(xiàn)裂縫。這是由于邊界重采樣步長只能是2的整數(shù)冪，使得重采樣不能完全根據(jù)實際投影長度來進行，當相鄰數(shù)據(jù)塊共同邊界的重采樣投影長度不一致時就產(chǎn)生了裂縫。在這種情況下采用分辨率向面積大的數(shù)據(jù)節(jié)點看齊的方法，即比較一個數(shù)據(jù)節(jié)點的相鄰節(jié)點，如果相鄰邊的分辨率（邊界重采樣步長）不同，則比較2個數(shù)據(jù)節(jié)點的面積，調(diào)整面積較小的數(shù)據(jù)節(jié)點的邊分辨率等于面積較大的數(shù)據(jù)節(jié)點的邊分辨率。針對圖4所示情況，即調(diào)整節(jié)點B的采樣步長為4，這樣節(jié)點A、B之間的裂縫就消除了。這樣做是犧牲了某些節(jié)點部分數(shù)據(jù)的分辨率，但是不會明顯降低顯示質(zhì)量。

圖4 裂縫消除前后的多分辨率地形模型

為了避免重采樣所占用的時間開銷，采用模式文件存儲各種可能產(chǎn)生的網(wǎng)格情況，在地形數(shù)據(jù)繪制時，直接調(diào)用模式文件繪制相應的不規(guī)則網(wǎng)格。節(jié)點網(wǎng)格重采樣方法不僅能夠?qū)崿F(xiàn)各不同分辨率節(jié)點之間的無縫拼接，而且使得繪制數(shù)據(jù)的冗余量大大減少，在保證輸出圖形效果的同時，大大提高了繪制速度。

4 算法實驗結(jié)果

通過實驗測試，基于四叉樹的全球地形實時繪制方法可以在計算機上實現(xiàn)全球地形的實時瀏覽，平均達到50幀／s以上的高速漫游。測試環(huán)境為：CPU為P4 2.8G，2G內(nèi)存，750G硬盤，操作系統(tǒng)Windows XP，顯示器分辨率1 024×768，GEFORCE6200（512 M顯存）顯卡。表1是不同視點情況下一幀圖形繪制數(shù)據(jù)量（三角形個數(shù)）測試結(jié)果，由測試數(shù)據(jù)可看到每幀數(shù)據(jù)量基本恒定，其中視點位置用大地坐標系表示，觀察方向用方位角、俯仰角和滾動角來表示，所有角度表示用度為單位，表1測試視點位置的經(jīng)緯度固定，為（116.662 0°，40.353 6°），觀察方向固定，為（90°，－30°，0°），視點高度不同；表2是采用節(jié)點網(wǎng)格重采樣方法與直接利用規(guī)整網(wǎng)格繪制數(shù)據(jù)量的比對 結(jié) 果，視 點 位 置（116.662 0°，40.353 6°，20 000m），方位角為90°，滾動角為0°，俯仰角有變化。

表1 不同視點下繪制數(shù)據(jù)量的比較

表2 不同方法繪制三角形數(shù)目的比較

5 結(jié) 論

基于四叉樹的全球地形實時繪制方法計算球模型與相機錐面的相交區(qū)域，得到可見區(qū)域，計算方法簡單；以投影面積為節(jié)點評價準則，對可見區(qū)域進行剖分得到1個多分辨率地形可見節(jié)點集。依據(jù)節(jié)點邊界的投影長度進行網(wǎng)格重采樣，在消除裂縫的同時，大大減少繪制冗余數(shù)據(jù)量，使得每一幀地形繪制的數(shù)據(jù)量保持相對恒定。算法應用到數(shù)字地球平臺中，可以實現(xiàn)基于全球地形數(shù)據(jù)的實時瀏覽。

（

）

［1］承繼成，郭華東，薛勇.數(shù)字地球?qū)д摚跰］.北京：科學出版社，2007：1－5.

［2］凌實.大規(guī)模地形LOD模型簡化與實時繪制方法研究［D］.合肥：合肥工業(yè)大學，2009：1－13.

［3］COHEN D，CHRYSANTHOU Y L，SILVA C T，et al.A survey of visibility for walkthrough appli－cations［J］.IEEE Transaction on Visualization and Computer Graphics，2003（3）：412－431.

［4］邢偉，孫延奎，唐澤圣.與視點相關(guān)的多分辨率地表模型簡化算法［J］.清華大學學報：自然科學版，2004，44（l）：29－32.

［5］龍熙華，靳玉萍，宋勇利.大規(guī)模地形真實感渲染技術(shù)研究［J］.計算機工程，2012，38（7）：260－262.

［6］吳忠.四叉樹LOD算法優(yōu)化及在地形仿真中的應用［D］.武漢：華中科技大學，2006：7－15.

［7］李穎，陳業(yè)斌.基于四叉樹的三維地形繪制算法［J］.安徽工業(yè)大學學報：自然科學版，2008，25（1）：80－82.

［8］婁高鳴，李小奇，侯健，等.一種基于四叉樹的動態(tài)多分辨率LOD大規(guī)模三維地形繪制研究［J］.裝備制造技術(shù)，2009（8）：53－55.

［9］于卓，梁曉輝，馬上，等.一種支持大規(guī)模多種精度地形的實時繪制算法［J］.計算機研究與發(fā)展，2010，47（6）：988－995.

［10］原慶紅，韓燮.基于視點的分塊LOD大規(guī)模地形生成算法研究［J］.微電子學與計算機，2011，28（6）：41－45.