劉恒飛，劉紀(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)

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

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

一、引 言

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

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

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

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

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

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

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

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

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

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

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

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

圖2 四叉樹空間索引圖

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

基于上述研究，依托中國測繪科學(xué)研究院政府地理信息中心的三維可視化平臺(tái)，編程實(shí)現(xiàn)此建筑物數(shù)據(jù)的組織與調(diào)度方法。采用真實(shí)建模的建筑物數(shù)據(jù)(約500個(gè)，三角形數(shù)目約6 000個(gè))、全球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)行試驗(yàn)。對(duì)比不渲染建筑物數(shù)據(jù)與渲染不同LOD級(jí)別建筑物數(shù)據(jù)時(shí)的幀速率，試驗(yàn)結(jié)果如表1所示，效果如圖5所示。

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

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

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

五、結(jié)束語

本文在深入研究已有建筑物、地形、影像空間數(shù)據(jù)組織與調(diào)度方法的基礎(chǔ)上，采用對(duì)大范圍建筑物數(shù)據(jù)進(jìn)行經(jīng)緯線格網(wǎng)劃分與經(jīng)緯線格網(wǎng)內(nèi)部建立四叉樹空間索引的方式對(duì)建筑物數(shù)據(jù)進(jìn)行組織;結(jié)合視點(diǎn)相關(guān)LOD、數(shù)據(jù)緩存與多線程等方法進(jìn)行建筑物數(shù)據(jù)的動(dòng)態(tài)調(diào)度;并在實(shí)際應(yīng)用中證明此方法在海量建筑物數(shù)據(jù)的組織與調(diào)度方面是可行、有效的。但仍存在一些問題，例如在經(jīng)緯線格網(wǎng)劃分時(shí)仍存在少量的建筑物數(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)度方法的研究與實(shí)現(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ù)存儲(chǔ)和調(diào)度的研究［J］.測繪科學(xué)，2008，33(3)：110-113.

［6］ 劉紀(jì)平.海量空間數(shù)據(jù)組織與管理初探［J］.中國圖象圖形學(xué)報(bào)，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—)，男，黑龍江雞東人，碩士生，研究方向?yàn)槿SGIS。