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

董文雪

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

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

中圖分類號(hào)：TP391 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1672-3791（2014）08（b）-0036-02

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

1 基于四叉樹(shù)的 LOD地形模型

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

從3維場(chǎng)景可視化角度而言，目前在地形的數(shù)字表達(dá)上普遍采用 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)由于其頂點(diǎn)呈規(guī)則分布，只需要記錄數(shù)據(jù)的基本信息和每個(gè)格網(wǎng)點(diǎn)的高程值，結(jié)構(gòu)簡(jiǎn)單、操作方便、便于簡(jiǎn)化，非常適合于大規(guī)模地形數(shù)據(jù)的組織和管理。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.2 裂縫消除的方法

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

4 結(jié)論

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

參考文獻(xiàn)

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

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

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

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

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

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