基于四叉樹的全球地形實(shí)時繪制方法

謝劍薇， 劉 濤， 于鳳坤

（裝備學(xué)院 信息裝備系，北京101416）

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.2.1 視距標(biāo)準(zhǔn)

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

式中：多邊形由頂點(diǎn)p0，p1，…，pn順時針組成；p′i是點(diǎn)pi的投影坐標(biāo)；A是當(dāng)前相機(jī)的投影矩陣。

式中：S是多邊形的投影面積；P′ix和P′iy表示點(diǎn)pi的投影坐標(biāo)x與y值。

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

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

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

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

3 裂縫處理

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

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

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

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

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

4 算法實(shí)驗(yàn)結(jié)果

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

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

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

5 結(jié) 論

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

（

）

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

［2］凌實(shí).大規(guī)模地形LOD模型簡化與實(shí)時繪制方法研究［D］.合肥：合肥工業(yè)大學(xué)，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］邢偉，孫延奎，唐澤圣.與視點(diǎn)相關(guān)的多分辨率地表模型簡化算法［J］.清華大學(xué)學(xué)報：自然科學(xué)版，2004，44（l）：29－32.

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

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

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

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

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

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