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

宋 娟，張 宏

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

0 引 言

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

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

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

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

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

1.1.1 分塊四叉樹

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

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

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

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

圖2 瓦片拓?fù)潢P(guān)系和網(wǎng)格坐標(biāo)系

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

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

struct Chunk

{

int chunkIndex;//塊索引

int swIndex,seIndex,neIndex,nwIndex;//4個(gè)子節(jié)點(diǎn)索引

int lod_level;//節(jié)點(diǎn)層

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

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

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

}

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

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

{

……

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

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

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

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

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

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

}

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

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

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

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

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

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

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

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

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

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

2.1.1 基于視域的LRU算法

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

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

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

2.1.2 動(dòng)態(tài)調(diào)度實(shí)現(xiàn)

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

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

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

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

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

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

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

2.2.1 緩沖區(qū)機(jī)制

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

2.2.2 四隊(duì)列調(diào)度

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

2.2.3 多線程處理

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

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

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

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

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

3 3DGIS平臺(tái)應(yīng)用

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

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

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

4 結(jié)束語

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

參考文獻(xiàn):

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

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

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

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

[5] 杜 瑩,武玉國,王曉明,等.全球多分辨率虛擬地形環(huán)境的金字塔模型研究[J].系統(tǒng)仿真學(xué)報(bào),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ù)實(shí)時(shí)渲染算法研究[J].計(jì)算機(jī)仿真,2011,28(10):223-227.

[11] 馬柳青,宋關(guān)福,郭 會(huì),等.一種海量地形影像數(shù)據(jù)的快速漫游算法[J].地球信息科學(xué)學(xué)報(bào),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].計(jì)算機(jī)仿真,2005,22(1):209-212.

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