袁松鶴，靳海亮，耿文軒

(河南理工大學(xué),河南 焦作 454000)

隨著數(shù)字地球的不斷發(fā)展，全球地形數(shù)據(jù)的組織與管理受到越來越多的關(guān)注。如何構(gòu)建一個(gè)具有高度真實(shí)感的地形可視化場(chǎng)景成為一個(gè)非常關(guān)鍵的問題。由于受計(jì)算機(jī)內(nèi)存容量的限制，系統(tǒng)所能管理的數(shù)據(jù)量、顯示效果的逼真性和交互響應(yīng)的實(shí)時(shí)性是評(píng)價(jià)一個(gè)可視化系統(tǒng)是否實(shí)用的3個(gè)重要指標(biāo)。面對(duì)幾百個(gè)TB的數(shù)據(jù)，更甚至PB級(jí)的數(shù)據(jù)，不可能將全部海量數(shù)據(jù)一次性全部加入內(nèi)存，此時(shí)必須尋求針對(duì)于外存的數(shù)據(jù)組織與存儲(chǔ)策略[1]。目前，最常用的是基于外存(Out-of-Core)的方法，當(dāng)外存中的數(shù)據(jù)需要繪制時(shí)再進(jìn)行實(shí)時(shí)的讀取。Out-of-Core方法的思想是在1998年P(guān)ajarola[2]等提出的，將分塊后的地形數(shù)據(jù)按編碼規(guī)則進(jìn)行排序存儲(chǔ)在外存中。Vitter[3]在2001年在分塊的基礎(chǔ)上提出層次設(shè)計(jì)，大大提高了性能。Lindstrom等[4-5]在前人基礎(chǔ)上在外存上建立文件，實(shí)現(xiàn)與內(nèi)存的映射關(guān)系，加快數(shù)據(jù)的調(diào)度效率。

本文針對(duì)海量地形數(shù)據(jù)的組織與調(diào)度方面的問題，采用規(guī)則格網(wǎng)數(shù)字高程模型(Digital Elevation Model)構(gòu)建四叉樹多分辨率模型，并提出一種高效的數(shù)據(jù)檢索方式。另外本文在實(shí)時(shí)繪制階段，針對(duì)與需要繪制的地形數(shù)據(jù)構(gòu)建連續(xù)LOD模型。為大規(guī)模地形數(shù)據(jù)的繪制提出一種針對(duì)于外存的實(shí)時(shí)繪制方法。

1 基于四叉樹的海量地形數(shù)據(jù)組織方式

1.1 基于四叉樹海量地形數(shù)據(jù)表示

近年來計(jì)算機(jī)軟、硬件等技術(shù)有了飛速發(fā)展，但要實(shí)現(xiàn)地形可視化的數(shù)據(jù)量過于龐大，無法一次性的對(duì)這些地形數(shù)據(jù)進(jìn)行處理。由于傳統(tǒng)的地形數(shù)據(jù)組織與調(diào)度方式不但占用計(jì)算機(jī)大量的內(nèi)存，而且渲染幀率也無法滿足視覺需要。本文將采用四叉樹結(jié)構(gòu)來管理地形數(shù)據(jù)，鑒于四叉樹組織方式的靈活性，通過四叉樹結(jié)構(gòu)來管理地形幾何數(shù)據(jù)，從而構(gòu)建出多分辨率層次結(jié)構(gòu)。

首先將研究區(qū)域地形數(shù)據(jù)劃分為大小相同的m行m列，每個(gè)子塊邊長(zhǎng)為2n+1，左上角為第0行第0列，對(duì)于最后邊和最下邊不滿足大小相同要求的塊，以無效數(shù)據(jù)填充。根據(jù)分塊后的地形數(shù)據(jù)在原始地形中所處的行、列位置進(jìn)行編號(hào)，其編號(hào)為i-j，表示處于第i行、第j列的數(shù)據(jù)。地形分塊的數(shù)據(jù)文件格式如表1所示。

表1 地形塊文件格式

將分塊后的地形數(shù)據(jù)以四叉樹的數(shù)據(jù)結(jié)構(gòu)進(jìn)行組織[6]。一棵四叉樹，每2×2個(gè)點(diǎn)合成為一個(gè)上層點(diǎn)。如圖1所示，設(shè)第r行的初始分辨率為r0，則第L層的分辨率rL為

rL=r0x2L.

(1)

圖1 四叉樹分層結(jié)構(gòu)

利用多分辨率金字塔模型對(duì)地形數(shù)據(jù)進(jìn)行組織管理，在進(jìn)行地形繪制時(shí)，離視點(diǎn)近的區(qū)域采用分辨率高的數(shù)據(jù)進(jìn)行表示，離視點(diǎn)遠(yuǎn)的區(qū)域采用較低的分辨率進(jìn)行繪制，從而構(gòu)建地形數(shù)據(jù)LOD模型，并且利用四叉樹的索引方式進(jìn)行地形數(shù)據(jù)的組織管理。如圖2、圖3所示：第0層的數(shù)據(jù)為四叉樹的根節(jié)點(diǎn)，覆蓋地形的整個(gè)區(qū)域，但分辨率最低。從樹的根節(jié)點(diǎn)往下，每一層所代表的地形范圍不變，但地形數(shù)據(jù)的分辨率逐漸變大，樹中的每個(gè)節(jié)點(diǎn)都對(duì)應(yīng)地形中的一塊。四叉樹結(jié)構(gòu)一般由一個(gè)根結(jié)點(diǎn)、若干個(gè)非葉結(jié)點(diǎn)和葉結(jié)點(diǎn)組成，如果某個(gè)結(jié)點(diǎn)的4個(gè)子結(jié)點(diǎn)指針不為空，則為非葉結(jié)點(diǎn)，否則為葉結(jié)點(diǎn)，如果結(jié)點(diǎn)的父結(jié)點(diǎn)指針為空，則該結(jié)點(diǎn)為根結(jié)點(diǎn)。

圖2 對(duì)應(yīng)的四叉樹結(jié)構(gòu)

圖3 四叉樹分割

1.2 改進(jìn)的四叉樹瓦片索引

在對(duì)原始地形數(shù)據(jù)進(jìn)行分層操作時(shí)，主要工作是對(duì)數(shù)據(jù)的重采樣，利用四叉樹數(shù)據(jù)結(jié)構(gòu)來對(duì)各層數(shù)據(jù)進(jìn)行存儲(chǔ)。傳統(tǒng)的基于瓦片金字塔模型的四叉樹結(jié)構(gòu)對(duì)于數(shù)據(jù)的存儲(chǔ)采用分層方式，對(duì)于每一層的數(shù)據(jù)按從左到右的順序依次編碼存儲(chǔ)。

根據(jù)相應(yīng)的改進(jìn)方法，每個(gè)節(jié)點(diǎn)數(shù)據(jù)只在樹中存儲(chǔ)一次，有效地避免存儲(chǔ)空間的浪費(fèi)。構(gòu)造一種地形塊內(nèi)無數(shù)據(jù)冗余的外存模型，并進(jìn)行索引文件的生成。為了避免在新節(jié)點(diǎn)插入時(shí)進(jìn)行內(nèi)存的重新分配內(nèi)存，首先生成滿四叉樹結(jié)構(gòu)，這樣可以加快節(jié)點(diǎn)插入的進(jìn)度，最后釋放掉空的節(jié)點(diǎn)所占內(nèi)存空間[7]。一般根據(jù)經(jīng)驗(yàn)值四叉樹的深度4～7之間為最佳。

為了實(shí)現(xiàn)對(duì)外存中高程點(diǎn)數(shù)據(jù)的快速查詢，故將索引文件常駐內(nèi)存，而且索引文件所占內(nèi)存較小，只需構(gòu)造完整的索引方式，就可實(shí)現(xiàn)對(duì)外存地形數(shù)據(jù)的有序查找。本文將地形數(shù)據(jù)按照逐層從上到下從左到右的方式進(jìn)行存儲(chǔ)。在第0層存儲(chǔ)數(shù)據(jù)點(diǎn)0123，從第0層到第1層新增頂點(diǎn)為45678，故為了減少數(shù)據(jù)的重復(fù)存儲(chǔ)，本層只存儲(chǔ)新增數(shù)據(jù)點(diǎn)，同理，第3層也只存儲(chǔ)新增數(shù)據(jù)點(diǎn)，依次實(shí)現(xiàn)數(shù)據(jù)的完整存儲(chǔ)。

對(duì)存儲(chǔ)的數(shù)據(jù)點(diǎn)進(jìn)行編號(hào)(L-N-i-j),L代表此數(shù)據(jù)點(diǎn)所在的層號(hào)，N代表該頂點(diǎn)在該層新增數(shù)據(jù)點(diǎn)的序號(hào)。i表示此點(diǎn)在該層的橫坐標(biāo)，j表示此點(diǎn)在該層的縱坐標(biāo)。坐標(biāo)系的建立選擇從左上角開始，從左到右，從上到下，每個(gè)數(shù)據(jù)塊左上角起始坐標(biāo)為(0,0)，故該點(diǎn)的索引號(hào)為(L-N-0-0)。如圖4所示，數(shù)據(jù)點(diǎn)19的索引號(hào)為(2-10-1-3)。根據(jù)式(2)、式(3)即可在地形文件中找到所要讀取的數(shù)據(jù)：

offset(n)begin=

(2)

offset(n)end=(3n+1)X(3n+1)-1.

(3)

圖4 數(shù)據(jù)索引結(jié)構(gòu)

2 地形數(shù)據(jù)的調(diào)度

本文采用視點(diǎn)與視線相結(jié)合的方式進(jìn)行LOD的選擇，對(duì)目標(biāo)瓦片進(jìn)行由粗到細(xì)、層層推進(jìn)的策略。對(duì)于在視域外的節(jié)點(diǎn)的判斷和剔出，傳統(tǒng)的裁剪算法是解一個(gè)方程組[]，將與視錐體的6個(gè)裁剪面進(jìn)行比較，這樣會(huì)消耗大量的處理時(shí)間，導(dǎo)致渲染的速度非常慢，本文通過求取視錐與水平面的交面來作為視錐體裁剪面，進(jìn)行第一次可見性的剔出。通過引入節(jié)點(diǎn)包圍圓實(shí)現(xiàn)兩次數(shù)據(jù)的選取。

2.1 地形節(jié)點(diǎn)評(píng)價(jià)

由于通過視錐體交面獲得的地形塊根據(jù)視覺原理不能采用全分辨率模式進(jìn)行繪制。必須采用LOD原理對(duì)地形模型進(jìn)行簡(jiǎn)化。本文通過計(jì)算視點(diǎn)、視線與節(jié)點(diǎn)的位置關(guān)系，建立一個(gè)節(jié)點(diǎn)評(píng)價(jià)系統(tǒng)，決定節(jié)點(diǎn)是否進(jìn)行分割[8]。

首先計(jì)算地形的靜態(tài)誤差(簡(jiǎn)化模型與原始模型頂點(diǎn)間的高程差)。為了防止簡(jiǎn)化過度、簡(jiǎn)化模型精度不準(zhǔn)確等問題，將頂點(diǎn)間的依賴關(guān)系考慮在內(nèi)。由于相鄰層間節(jié)點(diǎn)誤差會(huì)出現(xiàn)傳遞，故在地形模型中父節(jié)點(diǎn)間的靜態(tài)誤差(粗糙度)不小于其子節(jié)點(diǎn)間的靜態(tài)誤差(粗糙度)。因此選取本身節(jié)點(diǎn)與子節(jié)點(diǎn)中的最大值作為當(dāng)前節(jié)點(diǎn)誤差，如圖5所示。

圖5 節(jié)點(diǎn)靜態(tài)誤差

根據(jù)視點(diǎn)到節(jié)點(diǎn)的距離，及節(jié)點(diǎn)與視線方向位置關(guān)系，采用屏幕誤差來衡量一個(gè)LOD層次。最終的節(jié)點(diǎn)評(píng)價(jià)算式為

(4)

式中：δ為節(jié)點(diǎn)靜態(tài)誤差;H為屏幕垂直高度;θ為視點(diǎn)的下視角;α為視點(diǎn)的垂直張角;D為視點(diǎn)到節(jié)點(diǎn)的距離;β為視線與視點(diǎn)到節(jié)點(diǎn)的方向向量之間的夾角。通過式(4)求取屏幕誤差來確定節(jié)點(diǎn)的分割情況。

2.2 連續(xù)LOD模型動(dòng)態(tài)構(gòu)建

對(duì)于采用視覺原理相關(guān)的LOD[9]技術(shù)的地形可視化系統(tǒng)，要求不同的區(qū)域由不同分辨率的地形數(shù)據(jù)來表示。根據(jù)視錐體裁剪與地形節(jié)點(diǎn)評(píng)價(jià)來構(gòu)建LOD模型。判斷某一時(shí)刻與視錐體相交的地形塊，分別為地形塊2、4構(gòu)建LOD模型。將屏幕誤差與所設(shè)置的誤差閾值進(jìn)行比較，判斷節(jié)點(diǎn)剖分情況。然后對(duì)剖分后的子節(jié)點(diǎn)，根據(jù)節(jié)點(diǎn)包圍圓的方法判斷該子節(jié)點(diǎn)是否可見，若可見進(jìn)行繪制，否則不參與繪制。

判斷地形數(shù)據(jù)是否在可視范圍內(nèi)，以及可視范圍內(nèi)的瓦片是否滿足分辨率要求的算法步驟如下：

第1步：判斷地形數(shù)據(jù)是否在視錐體內(nèi)，如果在，轉(zhuǎn)到第2步；否則，算法結(jié)束。

第2步：將節(jié)點(diǎn)屏幕誤差與誤差閾值進(jìn)行比較，若節(jié)點(diǎn)屏幕誤差小于誤差閾值，將其插入到繪制鏈表，否則，按照四叉樹剖分規(guī)則剖分地形塊，得到對(duì)應(yīng)的4個(gè)子節(jié)點(diǎn),將4個(gè)子節(jié)點(diǎn)插入到測(cè)試鏈表1。

第3步：判斷測(cè)試鏈表1是否為空。如果為空，算法結(jié)束；否則，轉(zhuǎn)到第4步。

第4步：利用節(jié)點(diǎn)包圍圓逐個(gè)判斷測(cè)試鏈表1中的節(jié)點(diǎn)是否在可見區(qū)內(nèi)，如果在，將其插入到測(cè)試鏈表2；否則，將其舍棄。

第5步：將測(cè)試鏈表1進(jìn)行清空，轉(zhuǎn)到第6步。

第6步：對(duì)測(cè)試鏈表2中的瓦片數(shù)據(jù)進(jìn)行逐個(gè)判斷，看是否滿足分辨率的要求。如果滿足，將其插入到繪制鏈表；否則，按照四叉樹剖分規(guī)則剖分地形塊，得到對(duì)應(yīng)的4個(gè)子節(jié)點(diǎn),將4個(gè)子節(jié)點(diǎn)插入到測(cè)試鏈表1。

第7步：將測(cè)試鏈表2進(jìn)行清空，轉(zhuǎn)到第3步。

2.3 基于多線程的數(shù)據(jù)調(diào)度策略

本文利用基于視景體與地形求交的視景體裁切方法來計(jì)算地形的可見區(qū)，引入數(shù)據(jù)預(yù)取策略，來實(shí)現(xiàn)數(shù)據(jù)的實(shí)時(shí)動(dòng)態(tài)調(diào)度，同時(shí)利用多線程技術(shù)[10]，將繪制線程和數(shù)據(jù)調(diào)度線程并行化處理。此方法有效地提高了所有數(shù)據(jù)加載完成的時(shí)間，便于每一幀的實(shí)時(shí)繪制。

2.3.1 基于視域擴(kuò)展的數(shù)據(jù)預(yù)取策略

在根據(jù)視覺原理及視點(diǎn)運(yùn)動(dòng)預(yù)測(cè)的前提下，提出如圖6所示的地形子塊數(shù)據(jù)預(yù)取調(diào)度方案。

圖6 數(shù)據(jù)預(yù)加載策略

圖6中每一個(gè)小方格代表地形字塊，藍(lán)色線框是可視區(qū)域，紅色線框是預(yù)加載區(qū)域，小的三角形是視域區(qū)域，大的三角形是視閾擴(kuò)展。

在第1幀中將地形覆蓋區(qū)域分為視域、視域擴(kuò)展、可視區(qū)域、調(diào)度區(qū)域以及預(yù)加載區(qū)域。視域?yàn)楦鶕?jù)視覺原理當(dāng)前用戶能夠觀察到的區(qū)域，即視錐范圍；將地形分塊區(qū)域與視域相交的部分當(dāng)作可視區(qū)域，并將可視區(qū)域包含的分塊集合用集合M表示，這些地形塊數(shù)據(jù)將在構(gòu)建地形LOD模型時(shí)使用；將以R為半徑的所涉及的半圓區(qū)域作為視域擴(kuò)展區(qū)域，需加載的地形塊數(shù)據(jù)量就由視域擴(kuò)展區(qū)域的大小決定；將地形分塊區(qū)域與視域擴(kuò)展相交的部分稱作調(diào)度區(qū)域，并將調(diào)度區(qū)域包含的分塊集合用集合N表示，這些數(shù)據(jù)將被載入到內(nèi)存中；假如N和N′分別表示相鄰兩幀調(diào)度區(qū)域包含的地形分塊集合，則預(yù)加載區(qū)域就是N′N=M對(duì)應(yīng)的地形分塊集合，表示當(dāng)前幀需要預(yù)先加載到內(nèi)存的地形數(shù)據(jù)，這些數(shù)據(jù)是對(duì)下一幀的預(yù)測(cè)，并不需要立即繪制。

2.3.2 多線程的數(shù)據(jù)調(diào)度

為了使數(shù)據(jù)調(diào)度與繪制同時(shí)進(jìn)行，采用多線程[11]來加速調(diào)度過程，主線程為每一個(gè)需要調(diào)度的地形塊開啟一個(gè)子線程。圖7是多線程的實(shí)現(xiàn)流程。

圖7 多線程處理機(jī)制

3 實(shí)驗(yàn)結(jié)果分析

為了檢測(cè)本算法的實(shí)用性，將其在PC機(jī)上用VC++6.0和OpenGL進(jìn)行測(cè)試，本文所利用的地形數(shù)據(jù)為在地理空間數(shù)據(jù)云所下載的DEM數(shù)據(jù)，實(shí)驗(yàn)所使用的硬件設(shè)備配置為：Inter(R) Core i5-3340 3.10 GHZ CPU,內(nèi)存4.0 GB，顯卡為Inter(R) HD，操作系統(tǒng)為Windows 7,屏幕分辨率為1 440 pixels×900 pixels。不同數(shù)據(jù)組織方式效果對(duì)比如表2所示。

在預(yù)處理階段，利用四叉樹結(jié)構(gòu)對(duì)地形高程數(shù)據(jù)進(jìn)行分塊多分辨率組織，采用本文的數(shù)據(jù)存儲(chǔ)方法，本實(shí)驗(yàn)地形的分塊大小為1025×1025，并將紋理數(shù)據(jù)進(jìn)行分塊編號(hào)索引處理，處理后的地形線框顯示如圖8、圖9所示。

表2 不同數(shù)據(jù)組織方式的效果對(duì)比列表

圖8 線框模式的三維地形圖

圖9 添加紋理的三維地形圖

4 結(jié) 論

本文針對(duì)海量地形數(shù)據(jù)無法一次性載入內(nèi)存進(jìn)行繪制的問題，采用經(jīng)典的四叉樹方法來進(jìn)行數(shù)據(jù)的組織，對(duì)于分塊的地形數(shù)據(jù)構(gòu)建層次分辨率模型，采用無冗余的數(shù)據(jù)存儲(chǔ)方式，降低內(nèi)存的消耗，減少計(jì)算量。在實(shí)時(shí)處理階段，引入視閾擴(kuò)展的數(shù)據(jù)預(yù)取策略，加快數(shù)據(jù)的調(diào)度速度，保證兩相鄰幀數(shù)之間的流暢。

[1] 陳懷友.大規(guī)模作戰(zhàn)仿真平臺(tái)可視化關(guān)鍵技術(shù)研究[D].哈爾濱：哈爾濱工程大學(xué),2010.

[2] PAJAROLA R. Large scale terrain visualization using the restricted quadtree triangulation[C]. In Visualization '98. Proceedings. 1998.

[3] VITTER J S. External Memory Algorithms and Data Structures: Dealing with Massive Data[J]. ACM Computing Surveys 33(2), 209-271.

[4] LINDSTROM P, PASCUCCI V. Visualization of Large Terrains Made Easy[C]. in Visualization, 2001. VIS '01. Proceedings. 2001.

[5] LINDSTROM P, PASCUCCI V.Terrain Simplification Simplified: A General Framework for View-Dependent Out-of-Core Visualization[C]. IEEE Transaction on Visualization and Computer Graphics, 8(3): 239-254. 2002.

[6] 張啟鑫.面向數(shù)字海洋應(yīng)用的全球地形數(shù)據(jù)組織與可視化技術(shù)研究[D].山東青島：中國海洋大學(xué),2015.

[7] 邱航. 虛擬戰(zhàn)場(chǎng)中復(fù)雜場(chǎng)景建模與繪制若干關(guān)鍵技術(shù)研究[D].成都：電子科技大學(xué),2011.

[8] 呂夢(mèng)雅.大規(guī)模戰(zhàn)場(chǎng)地形的實(shí)時(shí)可視化算法的研究[J].小型微型計(jì)算機(jī)系統(tǒng), 2010，31(8): 1578-1581.

[9] 王麗君.大規(guī)模戰(zhàn)場(chǎng)地形多分辨率建模及實(shí)時(shí)可視化的研究[D].河北秦皇島：燕山大學(xué),2009.

[10] 左志權(quán),陳媛.TB級(jí)地形數(shù)據(jù)實(shí)時(shí)漫游核心算法研究[J]. 中國圖像圖形學(xué)報(bào), 2010，15(9): 1411-1415.

[11] 靳海亮.海量三維地形數(shù)據(jù)實(shí)時(shí)繪制技術(shù)研究[M].北京：中國礦業(yè)大學(xué)出版社,2009.