基于海量存儲的三維地理信息系統(tǒng)應(yīng)用與研究

宋 娟，張 宏

(哈爾濱理工大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，黑龍江 哈爾濱 150080)

0 引 言

近年來，GIS軟件的3D功能不斷加強。國外3DGIS軟件典型代表包括ESRI公司的ArcView的3D Analyst和GEONOVA公司的DILAS。前者支持多維矢量轉(zhuǎn)換和全球多分辨率數(shù)據(jù)的3D無縫可視化，后者支持LOD的3D建模、關(guān)系數(shù)據(jù)庫存儲與管理。由于顯存和系統(tǒng)內(nèi)存容量有限，實際應(yīng)用中大規(guī)模地形數(shù)據(jù)采取最近最少利用(least recent use,LRU)原則的分頁方式。針對大規(guī)模地形與紋理數(shù)據(jù)動態(tài)可視化的瓶頸，文中提出了多重紋理映射的大規(guī)模地形繪制方法，實現(xiàn)了規(guī)則網(wǎng)格區(qū)域分割的分層(LOD)分塊和四隊列分頁數(shù)據(jù)庫調(diào)度、基于視域的LRU算法內(nèi)存釋放、多線程并行處理的場景優(yōu)化策略。

1 四叉樹結(jié)構(gòu)的LOD瓦片組織算法

海量地形3D可視化，采用高精度的DEM作為基礎(chǔ)數(shù)據(jù)，往往能達到幾百萬個三角形面，渲染每一幀不可能一次性顯示，系統(tǒng)幀率無法達到實時渲染的要求。為解決大規(guī)模數(shù)據(jù)和系統(tǒng)顯示速率的瓶頸，對海量地形和紋理數(shù)據(jù)采用基于四叉樹結(jié)構(gòu)的LOD簡化[1-3]，使紋理映射高效集成到地形3D可視化中，遍歷簡單，減少選中地形子塊的時間。

1.1 四叉樹分層分塊的LOD算法

該系統(tǒng)預(yù)處理方法采用地形和紋理多分辨率建模，構(gòu)建金字塔模型[4]；按照四叉樹算法構(gòu)建LOD地形和紋理樹[5]；對紋理片與地形片進行有效壓縮；創(chuàng)建外存的金字塔模型數(shù)據(jù)庫。多分辨率金字塔用網(wǎng)格表示統(tǒng)一區(qū)域，相鄰層精度為1∶4。按正常的視覺現(xiàn)象，透視投影規(guī)律：視點距地面較遠時，繪制較少的三角形；較近時，繪制較多的三角形。采用四叉樹算法將原始地形劃分為多網(wǎng)格模型，再分別進行遞歸分割，直到最后一級分塊為最高分辨率。

1.1.1 分塊四叉樹

采用等間隔劃分方法對大規(guī)模數(shù)據(jù)金字塔模型進行分層分塊處理，根據(jù)由上而下的方法進行簡化。以地形圖為基礎(chǔ)，進一步進行規(guī)則格網(wǎng)劃分。例如一幅1∶2 000圖幅的大小為1 000×800，根據(jù)需要把部分單圖幅按2×2等分，即500×400，部分按照4×4等分，即250×200。以左上角為原點，四叉樹場景結(jié)構(gòu)劃分如圖1所示。

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

模型每節(jié)點有兩個LOD級別：本身所在的粗糙網(wǎng)格模型級別和四等分后的子塊級別。分層分塊策略，一次讀寫訪問一節(jié)點，且動態(tài)調(diào)度中只訪問需要的節(jié)點。很大程度上縮短了數(shù)據(jù)訪問時間又能表示多分辨率數(shù)據(jù)；與四叉樹結(jié)構(gòu)相結(jié)合，具備了快速數(shù)據(jù)索引的功能。

四叉樹層與瓦片的層對應(yīng)，節(jié)點編號是層號和網(wǎng)格坐標，拓撲關(guān)系如圖2所示。上下層父子關(guān)系、同一層鄰接關(guān)系。鄰接包括角鄰接、邊鄰接，上下層包括向上繼承、向下分解。

圖2 瓦片拓撲關(guān)系和網(wǎng)格坐標系

1.1.2 塊結(jié)構(gòu)與LOD建模編程實現(xiàn)

采用hash map的數(shù)據(jù)結(jié)構(gòu)，索引作為鍵，指針內(nèi)容作為值。采用塊結(jié)構(gòu)保存，如下：

struct Chunk

{

int chunkIndex;//塊索引

int swIndex,seIndex,neIndex,nwIndex;//4個子節(jié)點索引

int lod_level;//節(jié)點層

int xIndex,yIndex;//節(jié)點塊所在層的位置

int min_h,max_h;//塊的最小和最大高程

int mesh_pos;//三角網(wǎng)數(shù)據(jù)位置

}

利用遞歸思想實現(xiàn)四叉樹LOD模型建立的過程如下：

void UpdateQuadTr(int nXCenter,int nZCenter,int nSize,int lod_level,int xIndex,int yIndex)

{

……

//判斷地形子節(jié)點是否需要分割，若是，則執(zhí)行以下代碼

m_bQuadMat [chunkIndex][nXCenter+ nZCenter* m_nMapSize]=true;

UpdateQuadTr(nXCenter-nSize/2,nZCenter-nSize/2,nSize/2,lod_level+1,xIndex,yIndex); //分割西南節(jié)點

UpdateQuadTr(nXCenter+nSize/2,nZCenter-nSize/2,nSize/2,lod_level+1,xIndex,yIndex); //分割東南節(jié)點

UpdateQuadTr(nXCenter+nSize/2,nZCenter+nSize/2,nSize/2,lod_level+1,xIndex,yIndex); //分割東北節(jié)點

UpdateQuadTr(nXCenter-nSize/2,nZCenter+nSize/2,nSize/2,lod_level+1,xIndex,yIndex); //分割西北節(jié)點

}

1.2 地形數(shù)據(jù)庫管理策略

在紋理疊加到地形的過程中，根據(jù)地形和紋理數(shù)據(jù)的大小，根據(jù)不同層不同塊分辨率大小及粗糙程度，對紋理和地形不斷進行LOD處理、計算并疊加。不同層由不同分辨率塊與紋理片組成。把同時打包紋理的地形塊保存為三維模型寫入磁盤，表示多段數(shù)據(jù)塊的組合體，以常用的“.ive”格式，把場景樹保存為二進制文件，按不同層次數(shù)據(jù)塊存儲。

每數(shù)據(jù)層有一特定的標識名。命名方式如下：

FILENAME=地名+數(shù)據(jù)類型+數(shù)據(jù)層+行文件夾+數(shù)據(jù)文件

地塊模型命名為name _root/subtile(數(shù)據(jù)類型)_L(層)_r(行號)_c(列號).ive，如beijing_subtile_L3_X0_Y1.ive。由于系統(tǒng)中每個文件夾容納的文件數(shù)量有限，通過對層做分級，可避免文件夾文件過多。分級后，在外存中，3D地形紋理庫存儲管理圖如圖3所示。

圖3 地形紋理數(shù)據(jù)庫存儲管理圖

構(gòu)建3D地形庫，有效組織特定區(qū)域相關(guān)的數(shù)據(jù)[6]。通過地理坐標關(guān)聯(lián)視域范圍的數(shù)據(jù)，統(tǒng)一分配空間位置索引，快速調(diào)度3D庫中的地形紋理數(shù)據(jù)，提高紋理地形節(jié)點的訪問效率和場景裁剪效率，達到整個大規(guī)模地形的無縫渲染漫游。

2 動態(tài)調(diào)度策略算法

2.1 動態(tài)調(diào)度內(nèi)存釋放方法

三維場景實時瀏覽時，根據(jù)視點的位置，計算視域內(nèi)塊的索引，根據(jù)空間索引快速計算與上一步建立的四叉樹各塊中心點的距離，并根據(jù)事先指定的空間閾值判斷是否需要加載或卸載數(shù)據(jù)，并根據(jù)視點的變化，不斷調(diào)整內(nèi)存中模型的細節(jié)層次(LOD)級別。

2.1.1 基于視域的LRU算法

LRU頁面置換算法在管理內(nèi)存時移出短時間內(nèi)不用的數(shù)據(jù)塊，提高了空間利用率。采取虛擬頁存儲管理，將所需空間劃分為多個頁面，內(nèi)存中存放當(dāng)前所需頁面，其余頁面放入外存。基于視點的加載過程如圖4所示。

圖4 基于視點的數(shù)據(jù)加載卸載

文中在LRU算法[7]的基礎(chǔ)上，采用基于可視范圍的數(shù)據(jù)內(nèi)存釋放算法，內(nèi)存達到上限時，計算下一幀視域外的地形塊，根據(jù)優(yōu)先級高低將地形數(shù)據(jù)從內(nèi)存緩沖區(qū)卸載。

2.1.2 動態(tài)調(diào)度實現(xiàn)

大規(guī)模地形3D場景瀏覽，有效采用數(shù)據(jù)庫分頁技術(shù)。分頁調(diào)度劃分空間頁面，頁面為地形基本調(diào)度單位，場景瀏覽時動態(tài)加載。整個地形按照四叉樹構(gòu)建原則進行劃分，自頂而下、逐級建立各級R+樹空間索引。空間索引方法是為了加速場景遍歷，最大限度地縮短數(shù)據(jù)加載與卸載的響應(yīng)時間。

根據(jù)LOD技術(shù)，利用視角高度與瓦片尺寸的比，判定當(dāng)前顯示的瓦片是否需要進一步分解。為了利用GPU圖形處理能力，對每一地形瓦片，采用Chunlod網(wǎng)格(Mesh)模型算法，利用后臺線程加載網(wǎng)格數(shù)據(jù)，GPU對其進行批處理運算，調(diào)整地形幾何網(wǎng)格塊的LOD層。

地形動態(tài)調(diào)度和可視化流程如圖5所示。

圖5 地形數(shù)據(jù)動態(tài)調(diào)度和可視化流程

3D場景漫游中，計算和渲染視域內(nèi)的網(wǎng)格數(shù)據(jù)[8-10]，在很大程度上降低了運行時間復(fù)雜度，高效地實現(xiàn)了大規(guī)模地形數(shù)據(jù)的構(gòu)建與繪制。

2.2 四隊列多線程調(diào)度機制

通過上述調(diào)度策略，基本實現(xiàn)了大規(guī)模地形3D場景的實時瀏覽與交互。為進一步提高場景渲染效率，采用緩存區(qū)四隊列機制、多線程加載、區(qū)域索引的場景裁切和紋理共享。

2.2.1 緩沖區(qū)機制

緩沖區(qū)包括內(nèi)存和外存緩存。內(nèi)存緩存中，已加載的數(shù)據(jù)直接用于場景繪制，實現(xiàn)高速緩存。外存緩存用于預(yù)存儲數(shù)據(jù)。高速緩存大小設(shè)有上限，控制瓦片數(shù)。內(nèi)外存置換采用所述的LRU算法。漫游常在部分場景附近進行，剛渲染的數(shù)據(jù)不應(yīng)立即卸載。當(dāng)后臺線程需要獲得渲染數(shù)據(jù)時，先在緩沖區(qū)中查找，如未找到則在外存中繼續(xù)搜索。

2.2.2 四隊列調(diào)度

數(shù)據(jù)動態(tài)調(diào)度機制[11-12]：顯示當(dāng)前可視范圍時，預(yù)判斷下一步可能載入的數(shù)據(jù)；判斷在最近時間內(nèi)不可能出現(xiàn)在可視范圍內(nèi)的數(shù)據(jù)；正確地進行數(shù)據(jù)加載、卸載、預(yù)編譯和合并處理。保證場景瀏覽的穩(wěn)定性和暢通性。數(shù)據(jù)調(diào)度流程如圖6所示。

2.2.3 多線程處理

每一層單獨設(shè)置線程負責(zé)不同LOD數(shù)據(jù)的加載卸載，可提高大規(guī)模場景反復(fù)加載卸載的性能。原理如下：

圖6 數(shù)據(jù)調(diào)度處理流程

主線程：地形數(shù)據(jù)獲取，LOD簡化，視域剔除，實現(xiàn)實時繪制和渲染。

數(shù)據(jù)預(yù)調(diào)度線程：根據(jù)當(dāng)前視點計算可見域和預(yù)可見域，若需要的地形數(shù)據(jù)塊未在內(nèi)存中,載入隊列加入地形快索引，從外存庫動態(tài)讀取地形塊，且剔除不可見節(jié)點以避免資源浪費，同時進行預(yù)可見數(shù)據(jù)調(diào)度。

事件處理線程：接收事件，計算相機參數(shù)，設(shè)置相機視圖矩陣、漫游器、視口等。

3 3DGIS平臺應(yīng)用

地形/影像三維模型處理工具，實現(xiàn)多重紋理映射地形構(gòu)建金字塔模型，按層在本地存放組織，實現(xiàn)多重紋理映射。為減小渲染負擔(dān)，將多個原始影像分別預(yù)處理成不同分辨率紋理，使用OSG中Mipmap紋理映射技術(shù)[13-15]。2D紋理寬度高度是2的冪次方，單位為紋素(texel)。一般的，較小紋理圖像分辨率是下一層4個紋理片(單元)的平均值。

如圖7所示，紋理使用多幅分辨率不同的遙感影像(10 m分辨率的普通遙感影像、1 m分辨率的城區(qū)高分辨率遙感影像)疊加拼接而成。場景中明顯地展現(xiàn)了不同分辨率紋理的效果，很好地實現(xiàn)了多幅遙感影像的無縫拼接，可在盡量減少大規(guī)模數(shù)據(jù)且保證較高的加載渲染效率的條件下，使場景研究主題更突出。

圖7 三維地理信息系統(tǒng)

4 結(jié)束語

針對Mipmap紋理的大規(guī)模三維地形可視化技術(shù)進行了研究，并應(yīng)用于3DGIS平臺?；谒牟鏄浞謱臃謮K的LOD算法，建立多分辨率金字塔模型并進行有效的組織管理；引入四叉樹空間索引的動態(tài)調(diào)度機制，對場景中地形數(shù)據(jù)進行紋理映射，并進行動態(tài)調(diào)度可視化；通過場景裁剪和紋理共享，實現(xiàn)地形場景的快速優(yōu)化。加快了存取速度，降低了裁剪計算的復(fù)雜度，實現(xiàn)了高效渲染。該課題開發(fā)的3DGIS平臺為一個基礎(chǔ)應(yīng)用架構(gòu)，并未充分利用2D矢量數(shù)據(jù)的拓撲關(guān)系，網(wǎng)絡(luò)分析、鄰域分析、緩沖區(qū)分析等空間分析應(yīng)用功能需進一步完善。

參考文獻:

[1] 岳利群,夏 青,柳佳佳,等.全球海量地形數(shù)據(jù)組織管理方法的研究[J].測繪科學(xué),2009,34(3):121-123.

[2] 戴晨光,張永生,鄧雪清.一種用于實時可視化的海量地形數(shù)據(jù)組織與管理方法[J].系統(tǒng)仿真學(xué)報,2005,17(2):406-409.

[3] 王璐錦,唐澤圣,唐 龍.基于三角形二叉樹的地表模型動態(tài)簡化算法[J].清華大學(xué)學(xué)報:自然科學(xué)版,2002,42(1):92-95.

[4] 張恒國,王合龍,吳清香.基于ROAM算法的數(shù)字地面模型研究與實現(xiàn)[J].信息技術(shù),2008,32(1):95-97.

[5] 杜 瑩,武玉國,王曉明,等.全球多分辨率虛擬地形環(huán)境的金字塔模型研究[J].系統(tǒng)仿真學(xué)報,2006,18(4):955-958.

[6] MINOUX C.Enabling virtual-globe browsing on memory-constrained platforms visualization and exploration of geospatial data[R].[s.l.]:[s.n.],2007.

[7] SUN M,LYU G L,LEI C.Large-scale vector data displaying for interactive manipulation in 3D landscape map[R].[s.l.]:[s.n.],2008.

[8] BLOW J.Terrain rendering at high levels of detail[C]//Game developers conference.[s.l.]:[s.n.],2000:119-124.

[9] DAI C G,ZHANG Y S,YANG J Y.Rendering 3D vector data using the theory of stencil shadow volume[R].[s.l.]:[s.n.],2008.

[10] 申閆春,王 銳,翟春麗.海量地形的GIS特征數(shù)據(jù)實時渲染算法研究[J].計算機仿真,2011,28(10):223-227.

[11] 馬柳青,宋關(guān)福,郭 會,等.一種海量地形影像數(shù)據(jù)的快速漫游算法[J].地球信息科學(xué)學(xué)報,2009,11(5):604-609.

[12] 宋 敏,申閆春.基于空間數(shù)據(jù)庫VRGIS的研究與應(yīng)用[J].測繪與空間地理信息,2012,35(8):47-52.

[13] BHATFACHARJEE S,PATIDAR S,NARAYANAN P J.Real-time rendering and manipulation of large terrains[C]//Proceedings of 6th Indian conference on computer vision,graphics an image processing.Washington DC,USA:IEEE Computer Society,2008:551-559.

[14] 黃超超,凌永順,呂相銀.地形紋理映射方法研究[J].計算機仿真,2005,22(1):209-212.

[15] 姜翰青,王博勝,章國鋒,等.面向復(fù)雜三維場景的高質(zhì)量紋理映射[J].計算機學(xué)報,2015,38(12):2349-2360.