格網劃分與四叉樹相結合的海量建筑物數據組織與調度

劉恒飛，劉紀平，王 勇，王想紅

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

格網劃分與四叉樹相結合的海量建筑物數據組織與調度

劉恒飛1，2，劉紀平2，王 勇2，王想紅2

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

針對三維GIS中海量建筑物數據，提出基于經緯線格網劃分與四叉樹空間索引相結合的數據組織方式，采用基于視點相關LOD、數據緩存和多線程的建筑物數據動態調度策略進行了實踐應用，試驗結果表明此方法是可行、高效的。

格網劃分;四叉樹;視點相關LOD;數據緩存;多線程

一、引 言

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

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

在分析已有成果的基礎上，本文對海量建筑物數據的組織與調度進行了系統的研究與實踐。在建筑物數據組織方面，提出了基于格網劃分與空間索引的建筑物數據組織模型;在建筑物數據調度方面，采用基于視點相關LOD［7］的建筑物數據動態調度策略;在此基礎上進行了實踐驗證，結果表明采用的組織與調度方法是合理、高效的。

二、基于格網劃分與四叉樹空間索引的建筑物數據組織模型

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

圖1 海量建筑物數據組織結構圖

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

1.大范圍建筑物數據的經緯線格網分割

利用經緯線格網結構簡單、計算高效的優點，對較大范圍內的建筑物數據進行組織。以該范圍的最小經緯度為原點，選取適當的經緯度間隔劃分成格網，并利用行列號對格網進行編碼，根據建筑物的地理坐標將屬于同一經緯線格網范圍的建筑物數據組織在一起。這樣就建立起大范圍建筑物數據的組織結構，利用式(1)和式(2)可以快速實現經緯度和行列號的轉換。

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

2.經緯線格網內部的四叉樹空間索引建立

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

圖2 四叉樹空間索引圖

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

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

3)如果沒有，則查找出四個子區域內的建筑物數據;

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

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

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

3.單個建筑物模型的LOD數據組織

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

圖3 單個建筑物數據組織結構圖

三、基于視點相關LOD的建筑物數據動態調度策略

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

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

圖4 建筑物數據調度流程圖

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

四、試驗結果及分析

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

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

表1 試驗結果數據表

圖5 運行效果圖

五、結束語

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

［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中大規模場景數據獲取、組織及調度方法的研究與實現［D］.大連：大連理工大學，2003.

［3］ 楊衛軍.海量三維城市模型的調度與場景管理［D］.武漢：武漢大學，2005.

［4］ 于鳳友.空間數據組織管理的研究與應用［D］.大連：大連理工大學，2003.

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

［6］ 劉紀平.海量空間數據組織與管理初探［J］.中國圖象圖形學報，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。