格网划分与四叉树相结合的海量建筑物数据组织与调度

刘恒飞，刘纪平，王 勇，王想红

(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。