海量地形數據組織與調度策略研究

袁松鶴，靳海亮，耿文軒

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

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

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

1 基于四叉樹的海量地形數據組織方式

1.1 基于四叉樹海量地形數據表示

近年來計算機軟、硬件等技術有了飛速發展，但要實現地形可視化的數據量過于龐大，無法一次性的對這些地形數據進行處理。由于傳統的地形數據組織與調度方式不但占用計算機大量的內存，而且渲染幀率也無法滿足視覺需要。本文將采用四叉樹結構來管理地形數據，鑒于四叉樹組織方式的靈活性，通過四叉樹結構來管理地形幾何數據，從而構建出多分辨率層次結構。

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

表1 地形塊文件格式

將分塊后的地形數據以四叉樹的數據結構進行組織[6]。一棵四叉樹，每2×2個點合成為一個上層點。如圖1所示，設第r行的初始分辨率為r0，則第L層的分辨率rL為

rL=r0x2L.

(1)

圖1 四叉樹分層結構

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

圖2 對應的四叉樹結構

圖3 四叉樹分割

1.2 改進的四叉樹瓦片索引

在對原始地形數據進行分層操作時，主要工作是對數據的重采樣，利用四叉樹數據結構來對各層數據進行存儲。傳統的基于瓦片金字塔模型的四叉樹結構對于數據的存儲采用分層方式，對于每一層的數據按從左到右的順序依次編碼存儲。

根據相應的改進方法，每個節點數據只在樹中存儲一次，有效地避免存儲空間的浪費。構造一種地形塊內無數據冗余的外存模型，并進行索引文件的生成。為了避免在新節點插入時進行內存的重新分配內存，首先生成滿四叉樹結構，這樣可以加快節點插入的進度，最后釋放掉空的節點所占內存空間[7]。一般根據經驗值四叉樹的深度4～7之間為最佳。

為了實現對外存中高程點數據的快速查詢，故將索引文件常駐內存，而且索引文件所占內存較小，只需構造完整的索引方式，就可實現對外存地形數據的有序查找。本文將地形數據按照逐層從上到下從左到右的方式進行存儲。在第0層存儲數據點0123，從第0層到第1層新增頂點為45678，故為了減少數據的重復存儲，本層只存儲新增數據點，同理，第3層也只存儲新增數據點，依次實現數據的完整存儲。

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

offset(n)begin=

(2)

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

(3)

圖4 數據索引結構

2 地形數據的調度

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

2.1 地形節點評價

由于通過視錐體交面獲得的地形塊根據視覺原理不能采用全分辨率模式進行繪制。必須采用LOD原理對地形模型進行簡化。本文通過計算視點、視線與節點的位置關系，建立一個節點評價系統，決定節點是否進行分割[8]。

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

圖5 節點靜態誤差

根據視點到節點的距離，及節點與視線方向位置關系，采用屏幕誤差來衡量一個LOD層次。最終的節點評價算式為

(4)

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

2.2 連續LOD模型動態構建

對于采用視覺原理相關的LOD[9]技術的地形可視化系統，要求不同的區域由不同分辨率的地形數據來表示。根據視錐體裁剪與地形節點評價來構建LOD模型。判斷某一時刻與視錐體相交的地形塊，分別為地形塊2、4構建LOD模型。將屏幕誤差與所設置的誤差閾值進行比較，判斷節點剖分情況。然后對剖分后的子節點，根據節點包圍圓的方法判斷該子節點是否可見，若可見進行繪制，否則不參與繪制。

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

第1步：判斷地形數據是否在視錐體內，如果在，轉到第2步；否則，算法結束。

第2步：將節點屏幕誤差與誤差閾值進行比較，若節點屏幕誤差小于誤差閾值，將其插入到繪制鏈表，否則，按照四叉樹剖分規則剖分地形塊，得到對應的4個子節點,將4個子節點插入到測試鏈表1。

第3步：判斷測試鏈表1是否為空。如果為空，算法結束；否則，轉到第4步。

第4步：利用節點包圍圓逐個判斷測試鏈表1中的節點是否在可見區內，如果在，將其插入到測試鏈表2；否則，將其舍棄。

第5步：將測試鏈表1進行清空，轉到第6步。

第6步：對測試鏈表2中的瓦片數據進行逐個判斷，看是否滿足分辨率的要求。如果滿足，將其插入到繪制鏈表；否則，按照四叉樹剖分規則剖分地形塊，得到對應的4個子節點,將4個子節點插入到測試鏈表1。

第7步：將測試鏈表2進行清空，轉到第3步。

2.3 基于多線程的數據調度策略

本文利用基于視景體與地形求交的視景體裁切方法來計算地形的可見區，引入數據預取策略，來實現數據的實時動態調度，同時利用多線程技術[10]，將繪制線程和數據調度線程并行化處理。此方法有效地提高了所有數據加載完成的時間，便于每一幀的實時繪制。

2.3.1 基于視域擴展的數據預取策略

在根據視覺原理及視點運動預測的前提下，提出如圖6所示的地形子塊數據預取調度方案。

圖6 數據預加載策略

圖6中每一個小方格代表地形字塊，藍色線框是可視區域，紅色線框是預加載區域，小的三角形是視域區域，大的三角形是視閾擴展。

在第1幀中將地形覆蓋區域分為視域、視域擴展、可視區域、調度區域以及預加載區域。視域為根據視覺原理當前用戶能夠觀察到的區域，即視錐范圍；將地形分塊區域與視域相交的部分當作可視區域，并將可視區域包含的分塊集合用集合M表示，這些地形塊數據將在構建地形LOD模型時使用；將以R為半徑的所涉及的半圓區域作為視域擴展區域，需加載的地形塊數據量就由視域擴展區域的大小決定；將地形分塊區域與視域擴展相交的部分稱作調度區域，并將調度區域包含的分塊集合用集合N表示，這些數據將被載入到內存中；假如N和N′分別表示相鄰兩幀調度區域包含的地形分塊集合，則預加載區域就是N′N=M對應的地形分塊集合，表示當前幀需要預先加載到內存的地形數據，這些數據是對下一幀的預測，并不需要立即繪制。

2.3.2 多線程的數據調度

為了使數據調度與繪制同時進行，采用多線程[11]來加速調度過程，主線程為每一個需要調度的地形塊開啟一個子線程。圖7是多線程的實現流程。

圖7 多線程處理機制

3 實驗結果分析

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

在預處理階段，利用四叉樹結構對地形高程數據進行分塊多分辨率組織，采用本文的數據存儲方法，本實驗地形的分塊大小為1025×1025，并將紋理數據進行分塊編號索引處理，處理后的地形線框顯示如圖8、圖9所示。

表2 不同數據組織方式的效果對比列表

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

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

4 結 論

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

[1] 陳懷友.大規模作戰仿真平臺可視化關鍵技術研究[D].哈爾濱：哈爾濱工程大學,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] 張啟鑫.面向數字海洋應用的全球地形數據組織與可視化技術研究[D].山東青島：中國海洋大學,2015.

[7] 邱航. 虛擬戰場中復雜場景建模與繪制若干關鍵技術研究[D].成都：電子科技大學,2011.

[8] 呂夢雅.大規模戰場地形的實時可視化算法的研究[J].小型微型計算機系統, 2010，31(8): 1578-1581.

[9] 王麗君.大規模戰場地形多分辨率建模及實時可視化的研究[D].河北秦皇島：燕山大學,2009.

[10] 左志權,陳媛.TB級地形數據實時漫游核心算法研究[J]. 中國圖像圖形學報, 2010，15(9): 1411-1415.

[11] 靳海亮.海量三維地形數據實時繪制技術研究[M].北京：中國礦業大學出版社,2009.