劉恒飛，劉紀(jì)平，王 勇，王想紅

(1.蘭州交通大學(xué)數(shù)理與軟件工程學(xué)院，甘肅蘭州730070;2.中國測繪科學(xué)研究院，北京100830)

格網(wǎng)劃分與四叉樹相結(jié)合的海量建筑物數(shù)據(jù)組織與調(diào)度

劉恒飛1，2，劉紀(jì)平2，王 勇2，王想紅2

(1.蘭州交通大學(xué)數(shù)理與軟件工程學(xué)院，甘肅蘭州730070;2.中國測繪科學(xué)研究院，北京100830)

針對三維GIS中海量建筑物數(shù)據(jù)，提出基于經(jīng)緯線格網(wǎng)劃分與四叉樹空間索引相結(jié)合的數(shù)據(jù)組織方式，采用基于視點相關(guān)LOD、數(shù)據(jù)緩存和多線程的建筑物數(shù)據(jù)動態(tài)調(diào)度策略進(jìn)行了實踐應(yīng)用，試驗結(jié)果表明此方法是可行、高效的。

格網(wǎng)劃分;四叉樹;視點相關(guān)LOD;數(shù)據(jù)緩存;多線程

一、引 言

建筑物數(shù)據(jù)是三維GIS的重要組成部分，它不僅逼真地描述了現(xiàn)實世界，而且在空間分析、城市規(guī)劃、輔助決策中有著重要應(yīng)用。但是，由于建筑物數(shù)據(jù)相對于地形、影像空間數(shù)據(jù)具有更復(fù)雜的結(jié)構(gòu)、更龐大的數(shù)據(jù)量，而且現(xiàn)有計算機(jī)軟硬件條件根本無法滿足海量建筑物數(shù)據(jù)的一次性調(diào)度與顯示。因此如何對海量建筑物數(shù)據(jù)進(jìn)行合理、高效的組織與調(diào)度，為其后續(xù)應(yīng)用提供良好支持，在三維GIS中具有重要意義。

目前對海量建筑物數(shù)據(jù)組織與調(diào)度的研究，主要是在參考地形、影像空間數(shù)據(jù)的組織與調(diào)度基礎(chǔ)上進(jìn)行的，采用格網(wǎng)劃分、空間索引［1］或兩者結(jié)合的方式對建筑物數(shù)據(jù)進(jìn)行組織，利用LOD、多線程、緩存等技術(shù)進(jìn)行建筑物數(shù)據(jù)的調(diào)度。翟巍［2］提出了基于地形格網(wǎng)劃分與基于規(guī)則劃分四叉樹的建筑物子場景空間索引相結(jié)合的建筑物數(shù)據(jù)組織方式，但仍不能很好地解決建筑物空間數(shù)據(jù)的冗余問題;楊衛(wèi)軍［3］采用空間索引與BSP樹相結(jié)合的方式對建筑物數(shù)據(jù)進(jìn)行組織，雖然解決了數(shù)據(jù)冗余問題，但單純的空間索引方式會影響數(shù)據(jù)的更新與查找效率;于鳳友［4］、唐桂文［5］、劉紀(jì)平［6］等也都對空間數(shù)據(jù)的組織與調(diào)度進(jìn)行了詳細(xì)的研究并提出了具體的解決方案，對建筑物數(shù)據(jù)的組織與調(diào)度提供了有價值的指導(dǎo)與建議。

在分析已有成果的基礎(chǔ)上，本文對海量建筑物數(shù)據(jù)的組織與調(diào)度進(jìn)行了系統(tǒng)的研究與實踐。在建筑物數(shù)據(jù)組織方面，提出了基于格網(wǎng)劃分與空間索引的建筑物數(shù)據(jù)組織模型;在建筑物數(shù)據(jù)調(diào)度方面，采用基于視點相關(guān)LOD［7］的建筑物數(shù)據(jù)動態(tài)調(diào)度策略;在此基礎(chǔ)上進(jìn)行了實踐驗證，結(jié)果表明采用的組織與調(diào)度方法是合理、高效的。

二、基于格網(wǎng)劃分與四叉樹空間索引的建筑物數(shù)據(jù)組織模型

空間數(shù)據(jù)組織就是對空間數(shù)據(jù)進(jìn)行合理的規(guī)劃并建立空間索引，以求方便空間數(shù)據(jù)的管理和提高空間數(shù)據(jù)的檢索效率。地形、影像等空間數(shù)據(jù)的組織主要采用基于格網(wǎng)劃分或建立R樹、四叉樹等空間索引的方式。但由于建筑物數(shù)據(jù)其自身具有的不規(guī)則性，如果單純地采用格網(wǎng)劃分的方式進(jìn)行組織勢必會在格網(wǎng)邊界處產(chǎn)生大量的分割，如果只利用空間索引的方式又由于數(shù)據(jù)量大而難于維護(hù)。因此，本文結(jié)合二者的優(yōu)點對海量建筑物數(shù)據(jù)進(jìn)行組織，組織結(jié)構(gòu)如圖1所示。

圖1 海量建筑物數(shù)據(jù)組織結(jié)構(gòu)圖

在大范圍采用經(jīng)緯線格網(wǎng)劃分;在格網(wǎng)內(nèi)部建立四叉樹空間索引，利用四叉樹索引組織單個模型;單個模型組織其自身的LOD數(shù)據(jù)及模型信息數(shù)據(jù);每個LOD級別組織其包含的幾何和紋理數(shù)據(jù)。

1.大范圍建筑物數(shù)據(jù)的經(jīng)緯線格網(wǎng)分割

利用經(jīng)緯線格網(wǎng)結(jié)構(gòu)簡單、計算高效的優(yōu)點，對較大范圍內(nèi)的建筑物數(shù)據(jù)進(jìn)行組織。以該范圍的最小經(jīng)緯度為原點，選取適當(dāng)?shù)慕?jīng)緯度間隔劃分成格網(wǎng)，并利用行列號對格網(wǎng)進(jìn)行編碼，根據(jù)建筑物的地理坐標(biāo)將屬于同一經(jīng)緯線格網(wǎng)范圍的建筑物數(shù)據(jù)組織在一起。這樣就建立起大范圍建筑物數(shù)據(jù)的組織結(jié)構(gòu)，利用式(1)和式(2)可以快速實現(xiàn)經(jīng)緯度和行列號的轉(zhuǎn)換。

當(dāng)進(jìn)行檢索時，首先根據(jù)建筑物的位置計算其所在的格網(wǎng)，快速定位到所需要的建筑物數(shù)據(jù)的范圍，避免了如R樹、四叉樹等空間索引查找速度慢的缺點;當(dāng)涉及精確的建筑物數(shù)據(jù)要求時，例如選取單個建筑物或單個建筑物的某一級別LOD數(shù)據(jù)，則通過經(jīng)緯線格網(wǎng)內(nèi)部的空間索引對單個建筑物數(shù)據(jù)進(jìn)行處理。

2.經(jīng)緯線格網(wǎng)內(nèi)部的四叉樹空間索引建立

在對大范圍建筑物數(shù)據(jù)進(jìn)行經(jīng)緯線格網(wǎng)劃分的基礎(chǔ)上，對經(jīng)緯線格網(wǎng)內(nèi)部建立四叉樹空間索引，以組織格網(wǎng)內(nèi)部的單個建筑物數(shù)據(jù)。建立四叉樹空間索引的基本思路是：讓每個建筑物的MBR被一個最小區(qū)域完全包含，從而避免劃分線對建筑物的分割。如圖2所示，可以看出9、15和16分別都跨越了多個區(qū)域，要被一個最小區(qū)域完全包含，就只能是根節(jié)點所代表的區(qū)域，4、7跨越了兩個區(qū)域，要被一個最小區(qū)域完全包含，就只能是NW和NE區(qū)域。構(gòu)建索引步驟如下：

圖2 四叉樹空間索引圖

1)對地理空間進(jìn)行四分，判斷是否有建筑物與區(qū)域四分的劃分線相交;

2)如果有，則將此建筑物信息存儲在此區(qū)域的根節(jié)點上;

3)如果沒有，則查找出四個子區(qū)域內(nèi)的建筑物數(shù)據(jù);

4)對四個子區(qū)域遞歸上述步驟，直至達(dá)到劃分閾值;

5)將建筑物信息存儲在所屬最小區(qū)域中。

利用四叉樹機(jī)制對經(jīng)緯線格網(wǎng)內(nèi)部的建筑物數(shù)據(jù)建立空間索引，可以很好地解決冗余問題，而且空間索引的更新也相對于R樹空間索引方便，同時避免了R樹空間索引中包圍盒的重疊，方便了數(shù)據(jù)的管理，縮短了檢索時間。

3.單個建筑物模型的LOD數(shù)據(jù)組織

單個建筑物模型含有模型的信息文件(存儲模型的地理位置信息、幾何變換信息及屬性信息)和多個LOD級別的模型數(shù)據(jù)，組織上采用樹狀層次結(jié)構(gòu)，如圖3所示。單個建筑物模型組織管理其自身的模型信息文件和多個LOD模型數(shù)據(jù)，每個LOD模型數(shù)據(jù)組織管理該級別的幾何數(shù)據(jù)和紋理數(shù)據(jù)。通過這種樹狀的層次結(jié)構(gòu)，就可以將單個建筑物的不同類型的數(shù)據(jù)分門別類，進(jìn)行合理的組織。

圖3 單個建筑物數(shù)據(jù)組織結(jié)構(gòu)圖

三、基于視點相關(guān)LOD的建筑物數(shù)據(jù)動態(tài)調(diào)度策略

空間數(shù)據(jù)調(diào)度就是確定在什么時間，采用什么方式，調(diào)入還是調(diào)出空間數(shù)據(jù)的一個過程。由于海量的建筑物數(shù)據(jù)需要在內(nèi)外存之間進(jìn)行切換，因此需要采用合理、高效的方式與方法對建筑物數(shù)據(jù)進(jìn)行調(diào)度，以提高數(shù)據(jù)調(diào)度的效率，減少調(diào)度的延遲時間。因此，結(jié)合上述的建筑物數(shù)據(jù)組織模型，本文采用基于視點相關(guān)LOD技術(shù)并利用數(shù)據(jù)緩存和多線程，實現(xiàn)建筑物數(shù)據(jù)的動態(tài)調(diào)度。

利用視點相關(guān)LOD，根據(jù)人眼在觀察事物時的規(guī)律(對較遠(yuǎn)的場景獲取的信息相對較少，對較近的場景獲取的信息相對較多、較精細(xì))對詳細(xì)程度不同的數(shù)據(jù)進(jìn)行選擇與排除，動態(tài)地加載與卸載建筑物數(shù)據(jù)。利用數(shù)據(jù)緩存對內(nèi)存中的建筑物數(shù)據(jù)進(jìn)行統(tǒng)一管理，由于數(shù)據(jù)緩存中保存當(dāng)前使用的建筑物數(shù)據(jù)，因此可以減少調(diào)度的數(shù)據(jù)量同時避免建筑物數(shù)據(jù)的重復(fù)調(diào)度。利用多線程，將建筑物數(shù)據(jù)從外存到內(nèi)存的I/O操作放入后臺線程中進(jìn)行，防止在同一線程中由于I/O操作而產(chǎn)生的調(diào)度延遲，同時可以提高調(diào)度效率。結(jié)合本文采用的建筑物數(shù)據(jù)組織模型，調(diào)度流程如圖4所示。

圖4 建筑物數(shù)據(jù)調(diào)度流程圖

在建筑物數(shù)據(jù)調(diào)度的過程中，先依據(jù)當(dāng)前視點的高度與視野范圍，結(jié)合建筑物數(shù)據(jù)的組織方式，選擇需要調(diào)入與調(diào)出的不同詳細(xì)程度的建筑物數(shù)據(jù);再根據(jù)數(shù)據(jù)緩存中已有的建筑物數(shù)據(jù)，確定實際要調(diào)入的建筑物數(shù)據(jù)并將數(shù)據(jù)緩存中需要調(diào)出的建筑物數(shù)據(jù)進(jìn)行卸載;然后利用后臺線程進(jìn)行建筑物數(shù)據(jù)的I/O操作，當(dāng)I/O操作完成時將所需數(shù)據(jù)存入數(shù)據(jù)緩存并返回，否則只返回數(shù)據(jù)緩存中已有的建筑物數(shù)據(jù);最終得到所需的不同細(xì)節(jié)層次的建筑物數(shù)據(jù)。

四、試驗結(jié)果及分析

基于上述研究，依托中國測繪科學(xué)研究院政府地理信息中心的三維可視化平臺，編程實現(xiàn)此建筑物數(shù)據(jù)的組織與調(diào)度方法。采用真實建模的建筑物數(shù)據(jù)(約500個，三角形數(shù)目約6 000個)、全球0.2 m分辨率的影像數(shù)據(jù)及90 m分辨率的DEM數(shù)據(jù)，在測試用機(jī)(Intel Core2 CPU 2.8 GHz，2 GB內(nèi)存，NVIDIA GeForceG100顯卡)上進(jìn)行試驗。對比不渲染建筑物數(shù)據(jù)與渲染不同LOD級別建筑物數(shù)據(jù)時的幀速率，試驗結(jié)果如表1所示，效果如圖5所示。

試驗結(jié)果表明：采用本文的建筑物數(shù)據(jù)組織與調(diào)度方法，在渲染建筑物數(shù)據(jù)前后，幀速率并無明顯變化，而且平均幀速率達(dá)28幀/秒，完全滿足實施渲染的要求，證明此建筑物數(shù)據(jù)的組織與調(diào)度方法是可行、高效的。

表1 試驗結(jié)果數(shù)據(jù)表

圖5 運(yùn)行效果圖

五、結(jié)束語

本文在深入研究已有建筑物、地形、影像空間數(shù)據(jù)組織與調(diào)度方法的基礎(chǔ)上，采用對大范圍建筑物數(shù)據(jù)進(jìn)行經(jīng)緯線格網(wǎng)劃分與經(jīng)緯線格網(wǎng)內(nèi)部建立四叉樹空間索引的方式對建筑物數(shù)據(jù)進(jìn)行組織;結(jié)合視點相關(guān)LOD、數(shù)據(jù)緩存與多線程等方法進(jìn)行建筑物數(shù)據(jù)的動態(tài)調(diào)度;并在實際應(yīng)用中證明此方法在海量建筑物數(shù)據(jù)的組織與調(diào)度方面是可行、有效的。但仍存在一些問題，例如在經(jīng)緯線格網(wǎng)劃分時仍存在少量的建筑物數(shù)據(jù)冗余，有待進(jìn)一步研究。

［1］ GUTTMAN A.R-trees——A Dynamic Index Structure for Spatial Searching［C］∥Proc ACM SIGMOD Int Confon Management of Data.Boston：ACM，1984：47-57.

［2］ 翟巍.三維GIS中大規(guī)模場景數(shù)據(jù)獲取、組織及調(diào)度方法的研究與實現(xiàn)［D］.大連：大連理工大學(xué)，2003.

［3］ 楊衛(wèi)軍.海量三維城市模型的調(diào)度與場景管理［D］.武漢：武漢大學(xué)，2005.

［4］ 于鳳友.空間數(shù)據(jù)組織管理的研究與應(yīng)用［D］.大連：大連理工大學(xué)，2003.

［5］ 唐桂文.基于三維GIS的海量地形數(shù)據(jù)存儲和調(diào)度的研究［J］.測繪科學(xué)，2008，33(3)：110-113.

［6］ 劉紀(jì)平.海量空間數(shù)據(jù)組織與管理初探［J］.中國圖象圖形學(xué)報，1998，3(6)：500-503.

［7］ HOPPE H.Smooth View-dependent Level-of-detail Control and Its Application to Terrain Rendering［C］∥Proceedings of IEEE Visualization Research Triangle Park.North Carolina：［s.n.］，1998：35-42.

Building Massive Data Organization and Scheduling with the Combination of Grid Partition and Quadtree

LIU Hengfei，LIU Jiping，WANG Yong，WANG Xianghong

0494-0911(2010)11-0004-03

P208

B

2010-07-13

劉恒飛(1985—)，男，黑龍江雞東人，碩士生，研究方向為三維GIS。