宋 娟，張 宏

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

0 引 言

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

1 四叉樹結構的LOD瓦片組織算法

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

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

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

1.1.1 分塊四叉樹

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

圖1 四叉樹結構劃分

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

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

圖2 瓦片拓撲關系和網格坐標系

1.1.2 塊結構與LOD建模編程實現

采用hash map的數據結構，索引作為鍵，指針內容作為值。采用塊結構保存，如下：

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;//三角網數據位置

}

利用遞歸思想實現四叉樹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 地形數據庫管理策略

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

每數據層有一特定的標識名。命名方式如下：

FILENAME=地名+數據類型+數據層+行文件夾+數據文件

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

圖3 地形紋理數據庫存儲管理圖

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

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

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

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

2.1.1 基于視域的LRU算法

LRU頁面置換算法在管理內存時移出短時間內不用的數據塊，提高了空間利用率。采取虛擬頁存儲管理，將所需空間劃分為多個頁面，內存中存放當前所需頁面，其余頁面放入外存?；谝朁c的加載過程如圖4所示。

圖4 基于視點的數據加載卸載

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

2.1.2 動態(tài)調度實現

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

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

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

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

3D場景漫游中，計算和渲染視域內的網格數據[8-10]，在很大程度上降低了運行時間復雜度，高效地實現了大規(guī)模地形數據的構建與繪制。

2.2 四隊列多線程調度機制

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

2.2.1 緩沖區(qū)機制

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

2.2.2 四隊列調度

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

2.2.3 多線程處理

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

圖6 數據調度處理流程

主線程：地形數據獲取，LOD簡化，視域剔除，實現實時繪制和渲染。

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

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

3 3DGIS平臺應用

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

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

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

4 結束語

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

參考文獻:

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

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

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

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

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

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

[12] 宋 敏,申閆春.基于空間數據庫VRGIS的研究與應用[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] 姜翰青,王博勝,章國鋒,等.面向復雜三維場景的高質量紋理映射[J].計算機學報,2015,38(12):2349-2360.