LOD地形模型中數(shù)據(jù)調(diào)度研究

董文雪

摘 要：本文基于筆者對LOD實景模型的研究，以LOD地形數(shù)據(jù)的調(diào)度為研究對象，論文首先詮釋了基于四叉樹的LOD地形模型的概念，進而探討了地形數(shù)據(jù)組織與LOD預(yù)處理，在此基礎(chǔ)上，詳細探討了LOD地形數(shù)據(jù)的調(diào)度，相信對從事相關(guān)工作的同行能有所裨益。

關(guān)鍵詞：LOD 地形模型 數(shù)據(jù)調(diào)度

中圖分類號：TP391 文獻標識碼：A 文章編號：1672-3791（2014）08（b）-0036-02

地形的可視化是3維地理信息系統(tǒng)中的一個重要研究問題，近年來，圖形硬件技術(shù)飛速發(fā)展，基本能夠滿足小范圍場景實時交互繪制的需求，但仍然無法滿足大規(guī)模3維場景的應(yīng)用需要。從目前的研究情況看，主要從兩個環(huán)節(jié)尋求改進：一是從外存儲器到內(nèi)存階段，通過數(shù)據(jù)的有效組織、內(nèi)外存之間的合理調(diào)度縮短讀取數(shù)據(jù)的時間；二是在內(nèi)存中繪制階段，采用多分辨率模型等技術(shù)縮短繪制時間。大規(guī)模的3維場景涉及到大量的空間數(shù)據(jù)，不可能一次性調(diào)入內(nèi)存，只能根據(jù)場景繪制的需要在內(nèi)、外存之間動態(tài)調(diào)度。這種動態(tài)調(diào)度的思想是很容易理解的，但實現(xiàn)起來又有很多問題需要研究，特別是為了實現(xiàn)場景繪制的實時交互，需要設(shè)計合理高效的數(shù)據(jù)組織結(jié)構(gòu)，并對數(shù)據(jù)調(diào)度過程進行控制和優(yōu)化。這些數(shù)據(jù)如何存儲，采用怎樣的數(shù)據(jù)結(jié)構(gòu)進行組織，對于系統(tǒng)最終描述場景的真實感和動態(tài)效果有著重要的影響，這也正是本文要研究的內(nèi)容。

1 基于四叉樹的 LOD地形模型

1.1 數(shù)據(jù)模型

從3維場景可視化角度而言，目前在地形的數(shù)字表達上普遍采用 DEM方法。DEM常用的數(shù)據(jù)結(jié)構(gòu)有：規(guī)則網(wǎng)格（Grid）、不規(guī)則三角網(wǎng)（TIN）以及兩者的混合結(jié)構(gòu)。其中，規(guī)則網(wǎng)格數(shù)據(jù)結(jié)構(gòu)由于其頂點呈規(guī)則分布，只需要記錄數(shù)據(jù)的基本信息和每個格網(wǎng)點的高程值，結(jié)構(gòu)簡單、操作方便、便于簡化，非常適合于大規(guī)模地形數(shù)據(jù)的組織和管理。

在地形場景繪制時，為了提高顯示速度，目前使用比較廣泛的是利用細節(jié)層次（LOD）技術(shù)生成同一地區(qū)的多分辨率模型，根據(jù)視點的變化，在滿足顯示精度要求的前提下，選擇不同分辨率的模型，達到“距離越近看得越清，距離越遠越模糊”的效果。金字塔就是一種多分辨率層次模型，它可以直接提供不同分辨率的地形數(shù)據(jù)而無需實時重采樣。

1.2 地形數(shù)據(jù)的四叉樹表示

本文中，多分辨率模型采用基于四叉樹的數(shù)據(jù)結(jié)構(gòu)構(gòu)建。首先，四叉樹結(jié)構(gòu)與地理坐標有天然的統(tǒng)一；其次，四叉樹與紋理鑲嵌技術(shù)可以很好地集成在一起。但采用四叉樹結(jié)構(gòu)帶來兩個問題：一是用四叉樹劃分的地形節(jié)點數(shù)必須是2n（如無特殊說明，在本文中，每個數(shù)據(jù)塊為一個節(jié)點）；二是不同層數(shù)據(jù)塊之間交界處會出現(xiàn)地形表面的不連續(xù)。第一個問題可以通過重采樣增加或減少地形格網(wǎng)來避免；第二個問題可以使用限制四叉樹的方法或改變高分辨率模型頂點高程值的方式加以解決。采用四叉樹細節(jié)層次模型時，先對地形數(shù)據(jù)做不同精度的等間距格網(wǎng)采樣，采樣結(jié)果構(gòu)成四叉樹的一層節(jié)點，樹中每個節(jié)點對應(yīng)地形的一塊區(qū)域，對于樹中任意相鄰的層，位于上一層的節(jié)點采樣精度是下一層的一半，任意一個非葉子節(jié)點都有4個子節(jié)點，而且子節(jié)點的采樣區(qū)域恰好將父節(jié)點四等分。利用這一特性，我們可以通過選擇位于不同層的節(jié)點來實現(xiàn)對特定區(qū)域不同分辨率的表示。

2 地形數(shù)據(jù)組織與 LOD預(yù)處理

采用金字塔模型需要對空間數(shù)據(jù)進行預(yù)處理，即對數(shù)據(jù)進行分層分塊。其基本思想是：首先將整個場景按照四叉樹結(jié)構(gòu)進行細節(jié)分層，每個LOD層又分為多個格網(wǎng)數(shù)為2n的正方形塊，然后對每一個數(shù)據(jù)塊按照四叉樹結(jié)構(gòu)進行組織。地形數(shù)據(jù)組織與處理包括三部分：DEM數(shù)據(jù)文件合并、DEM數(shù)據(jù)重采樣與分層、DEM數(shù)據(jù)分塊。紋理數(shù)據(jù)的處理方法與地形數(shù)據(jù)類似，本文不詳加討論。

2.1 數(shù)據(jù)文件合并

地形數(shù)據(jù)的來源和獲取途徑有多種，通常我們得到的大規(guī)模的DEM并非只是一個文件，而是一個由多個彼此之間相交或相接的DEM文件構(gòu)成的集合，數(shù)據(jù)文件可能多達幾百乃至上千個。如果不事先對數(shù)據(jù)文件進行合并，在后續(xù)的分級處理中，就要對每一個文件分別進行處理，要將原始的多個DEM文件處理成為具有不同細節(jié)層次、不同覆蓋范圍的多級DEM，其工作量之大可想而知。因此，需要將各個分散的DEM數(shù)據(jù)文件進行合并，考慮機器的處理能力，當數(shù)據(jù)量非常大時，可以分為幾個部分進行處理。

2.2 地形數(shù)據(jù)重采樣與分層

構(gòu)建地形數(shù)據(jù)金字塔模型各層數(shù)據(jù)時，是從底層即最高分辨率數(shù)據(jù)開始的，然后依次確定上一層數(shù)據(jù)的分辨率。從上到下，分辨率呈倍數(shù)遞增關(guān)系，下一層網(wǎng)格分辨率是上一層的2倍，這樣可以很方便地使用四叉樹索引技術(shù)進行快速定位。由于比例尺和分辨率不是一一對應(yīng)關(guān)系，DEM金字塔模型的各層數(shù)據(jù)可以通過其對應(yīng)的比例尺數(shù)據(jù)內(nèi)插處理得到。

2.3 地形數(shù)據(jù)分塊

數(shù)據(jù)分塊就是把 DEM數(shù)據(jù)分層后的各級LOD數(shù)據(jù)按照分塊要求重新進行塊的劃分。由于采用Grid數(shù)據(jù)結(jié)構(gòu)，DEM數(shù)據(jù)分塊比較容易實現(xiàn)。分塊時必須綜合考慮空間數(shù)據(jù)量、應(yīng)用要求和應(yīng)用平臺的軟硬件條件等，分塊過大，可能超出機器的處理能力；分塊過小，造成文件的個數(shù)太多，繪制時要頻繁地打開和關(guān)閉文件，不利于數(shù)據(jù)的管理和調(diào)度，所以選擇適當?shù)姆謮K大小就要取一個折中的解決方案。另外，采用四叉樹劃分時，DEM塊行與列的網(wǎng)格數(shù)需限制為2n×2n（n為不小于2的整數(shù)），本文選擇地形塊縱橫向格網(wǎng)數(shù)為16。在DEM分為小塊的同時進行文件合并，合并到一定大小時應(yīng)建立一個新的文件，文件命名要能反映出數(shù)據(jù)所在層數(shù)和與其他文件數(shù)據(jù)的相對位置。

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

在大規(guī)模3維場景中空間數(shù)據(jù)的組織階段，我們已為數(shù)據(jù)的實時調(diào)度做好了準備，但這時仍要考慮幾個問題：一是如何利用四叉樹技術(shù)實現(xiàn)地形塊的快速索引；二是如何消除不同分辨率地形節(jié)點拼接處的裂縫問題。endprint

3.1 地形數(shù)據(jù)塊的快速索引

調(diào)度程序首先必須獲得視景體投影的空間坐標，然后判斷視景體投影與哪些層的哪些數(shù)據(jù)塊覆蓋范圍發(fā)生交疊。如果可見區(qū)域在地形數(shù)據(jù)所表示的范圍內(nèi)，測試與可見區(qū)域交疊的頂層數(shù)據(jù)是否滿足分辨率要求，如果不滿足，由2倍率關(guān)系，根據(jù)頂層數(shù)據(jù)分辨率可迅速判斷出哪一層數(shù)據(jù)符合要求。由于數(shù)據(jù)分塊是規(guī)則的，因此并不需要對所有數(shù)據(jù)塊進行比較，只需要求出視景體梯形投影四個端點相對于全局場景起始點在X和Y方向上的坐標增量，再除以單塊的尺寸，便可以確定有哪些數(shù)據(jù)塊與可視區(qū)域發(fā)生交疊。當視點在場景中的位置或觀察方向發(fā)生變化時，視景體投影與數(shù)據(jù)塊的相交關(guān)系相應(yīng)發(fā)生變化，因此調(diào)度程序需要不斷地在內(nèi)、外存儲器之間執(zhí)行數(shù)據(jù)調(diào)度。因為地形數(shù)據(jù)已經(jīng)分塊，只需將視點附近區(qū)域的數(shù)據(jù)塊常駐內(nèi)存，將進入到可視范圍的新的數(shù)據(jù)塊調(diào)入，同時釋放那些“不可見數(shù)據(jù)塊”所占用的內(nèi)存空間。這樣就維持了內(nèi)存中數(shù)據(jù)載入和刪除的動態(tài)平衡，極大減少了內(nèi)存的負擔，使大規(guī)模3維地形實時漫游變得可行。

3.2 裂縫消除的方法

進行地形LOD模型繪制時，如果相鄰塊的分辨率不一樣，就會產(chǎn)生裂縫。目前，常用的消除裂縫的方法有兩種：一是強制相鄰網(wǎng)格進行分裂，如圖1（a）所示，在接邊處將低分辨率模型作適當分裂，使相鄰節(jié)點具有相同的邊界。這種方法在每一節(jié)點處都可能造成大量的分裂操作，產(chǎn)生大量不必要的三角形。第二種方法是將高分辨率模型頂點移動到相鄰低分辨率模型的邊界點上，如圖1（b）所示，這種方法計算簡單，但需要進行插值產(chǎn)生新的數(shù)據(jù)點來彌合裂縫，并且會產(chǎn)生T型連接，T型連接可能導(dǎo)致一些空洞小點，但一般情況下的繪制結(jié)果是可以接受的。本文采用第二種方法，在繪制時使用低分辨率模型一側(cè)邊上點的內(nèi)插高程來代替高分辨率模型產(chǎn)生裂縫的實際地面點高程。

4 結(jié)論

本文針對大規(guī)模地形可視化中地形數(shù)據(jù)組織方法進行了研究，采用本文所述方法，對某地區(qū)地形數(shù)據(jù)進行了組織和處理，實驗結(jié)果證明，可以滿足地形實時渲染的要求，消除了裂縫現(xiàn)象。但各層次細節(jié)的數(shù)據(jù)需要提前生成，預(yù)處理過程比較費時，而且靜態(tài)LOD文件中冗余存儲了各層次細節(jié)的地形數(shù)據(jù)，數(shù)據(jù)量比較大，要求硬盤有足夠的存儲空間。但考慮到預(yù)處理過程是一次性的，處理后的多層次細節(jié)數(shù)據(jù)一般不作改動，而且目前的硬盤容量都比較大，可以滿足地形和紋理數(shù)據(jù)的存儲需求，與對顯示速度的要求相比，這些問題還是可以接受的。至于LOD分層的問題，大多文獻依應(yīng)用需求和機器配置自己確定，到底什么情況下分多少層合適，目前還沒有公認的標準。另外，由于原始地形數(shù)據(jù)不一定滿足要求，可能需要重采樣，而且LOD分層時也需重采樣，重采樣引起的誤差對地形精度和顯示效果有多大影響，這都是目前正在研究和急需解決的問題。

參考文獻

[1] 劉少華，吳東勝，羅小龍，等.三維GIS數(shù)據(jù)模型在地層建模中的應(yīng)用研究及可視化[J].測繪信息與工程，2007（2）.

[2] 胡圣武，李鯤鵬.三維GIS關(guān)鍵技術(shù)的研究[J].地理空間信息，2008（3）.

[3] 魏波，湯軍.基于GIS的油田數(shù)字化管道的實現(xiàn)[J].測繪與空間地理信息，2008（4）.

[4] 謝榮安.GIS數(shù)據(jù)模型設(shè)計中的問題探討[J].地礦測繪，2004（4）.

[5] 林偉華，伍永剛，曾文，等.基于MAPGIS的市政設(shè)施數(shù)據(jù)模型研究[J].測繪科學，2008（4）.

[6] 石昊楠，孔金玲，董立新，等.面向?qū)ο蟮目臻g數(shù)據(jù)庫建庫探討[J].測繪標準化，2005（4）.endprint