基于八叉树与R树的大规模矢量模型的快速索引与动态检索方法

Fast Index and Dynamic Retrieval Method of Large-Scale Vector Models Based on Octree and Rtree

摘要: 测绘技术的高速发展，使得地理空间三维模型的数据采集更为简单与高效，基于大规模三维模型的数据的空间分析是发掘三维模型价值的重要应用点。如何高效地检索所感兴趣的目标模型，是进行三维空间分析的基础。本文基于八叉树与R树构造O & R树，实现空间模型的快速索引，并在此基础上，通过序列化的二进制模型数据存储，实现了外存空间中三维模型坐标数据的快速检索。本文通过实际数据验证了方法的可行性，可为空间分析功能的开发提供三维模型的检索基础，并可为大规模三维GIS系统开发，以及相应专业系统开发提供借鉴。

Abstract: The rapid development of surveying and mapping technology has made the data collection of 3D geospatial models simpler and more efficient. Spatial analysis based on large-scale 3D models is an important application point for discovering the value of 3D models. How to efficiently retrieve the target model of interest is the basis for three-dimensional space analysis. This paper constructs an O & R tree based on the Octree and Rtree to realize the rapid indexing of the spatial model. On this basis, through the serialized binary model data storage, the fast retrieval of the coordinate data of the 3D models in the external storage space is realized. The feasibility of the method is verified by actual data, can provide a basis for retrieval of 3D models for the development of spatial analysis functions. This method can provide reference for the development of large-scale 3D GIS systems and the development of corresponding professional systems.

1. 引言

三维模型是我们在计算机虚拟世界中重建现实场景的重要手段 [1] ，随着测绘科学技术与计算机技术的高速发展，如：倾斜摄影 [2] 等技术，现在的三维模型获取正在变得容易，但是数据规模也是与日俱增，变得极其庞大 [3] 。计算机可视化技术的发展，使得三维可视化渲染能力变得更加强大，现在已经有诸多方法实现这些模型的动态渲染 [4] ，但是仅实现模型的渲染不足以满足我们对三维模型的诉求，基于模型的空间分析才能更进一步体现模型的价值，但是要基于这庞大的三维模型进行空间运算，快速且高效地模型索引与模型数据的检索是我们必须首先解决的问题。

模型索引是三维模型查找时至关重要的技术，在三维索引技术中，最常见的三维空间索引方法有网格、四叉树 [5] 和八叉树 [6] 等，这些数据结构可以将三维空间划分为不同的单元，从而使查询过程更高效；此外，基于图论的R树 [7] 索引，通过自适应地调整索引结构以适应不规则空间模型的索引方法，也是三维空间索引中至关重要的方法。但是这些索引方法在处理不规则空间模型的时候，往往因其结构原因，有着一些无法处理的局限，如八叉树会导致大量的重叠冗余数据，而R树在模型规模大量增加的时候，索引效率出现较大的降低。对此，复合索引的形式可以在避免某一索引弊端的时候 [8] ，发挥各自的优势。

空间索引可以帮助快速找到所需要的三维模型的编号，但是基于此编号快速找到对应模型的三角形，及模型的动态检索，亦是我们所需要关注的重要问题。常规的模型存储格式往往很难解决三角形的快速检索，如：OBJ、STL等模型，需要将模型的顶点与面信息都读取到内存，方可根据编号实现三角形的获取，这极大地限制了模型的快速检索；此外，一些常见的模型瓦片数据，如cesium提出来的3d tiles瓦片数据 [9] ，其对数据进行瓦片处理，并建立了各瓦片数据的空间包围盒，这给模型索引与检索提供了可能，但其所独有的数据投影格式，使得我们在进行数据获取的时候，还需要进行投影变换，给我们数据获取带来了较大的麻烦。

为了能够同时模型快速检索与高效的模型检索，本文融合八叉树与R树索引形成O & R树索引，从而实现模型的快速空间检索，此外，通过序列化的二进制形式的三角形坐标数据存储，形成可以快速检索三角形坐标的模型文件，从而实现三角形的高性能检索与快速动态检索。

2. 八叉树 + R树索引

2.1. 八叉树

八叉树(Octree)是一种常用的空间分割数据结构，被广泛应用于计算机图形学、物理模拟、自然语言处理等领域 [10] 。它的基本思想是将空间递归地划分为八个子空间，以此构成一棵树。通过不断的递归划分，最终可以将整个空间划分成许多小块，每个小块都代表一个叶子节点。在地理信息科学中，八叉树被广泛应用于空间数据检索等方面，可以加速对目标区域内的相关矢量面的查找，尤其适用于三维点云的快速检索，以及点云之间的集合运算。但是八叉树本身的规则划分的特性，无法适用于复杂的空间模型的划分，这使得其在以三角形为基础的不规则三维模型中应用中极其不便，为了能够覆盖所有模型，建立八叉树索引的时候，往往需要重复存储大量的模型数据，这使得树结构中存在大量的冗余数据，而且数据检测时会检测到大量的无关数据，从而使得数据检索效率大大降低。

2.2. R树

R树是一种高效的空间索引数据结构，被广泛应用于地理信息系统、数据库查询等领域 [11] 。其基本思想是将空间对象递归地划分为多个矩形区域，以此构建出一棵树。通过不断地递归划分，最终可以将整个空间划分成许多小块，每个小块都代表一个叶子节点。在地理信息系统中，R树被广泛应用于点、线和面等空间对象的索引和查询。通过使用R树，可以快速地查找给定范围内的所有空间对象，从而实现高效的地理信息查询。

上述八叉树适用于三维点云快速索引，但是，无法处理任意形态三维模型的空间索引，这使得八叉树的适用范围较为局限；相比八叉树，R树可弥补其缺陷，用于任意复杂模型的快速检索(如以三角形组成的空间曲面模型)，但是R树的结构较八叉树更为复杂，当模型规模增加的时候，R树的索引深度与重叠都会增大，而查找都是从根节点开始，访问的分支数与节点数都会大规模增加，使得索引的效率不尽人意。本文在实践中发现，当模型规模达到20万三角形时，R树索引构建与检索就需要耗费较多的时间。

2.3. 八叉树 + R树索引

为了兼容八叉树索引的高效，以及R树索引的适用性，本文将八叉树与R树组合形成O & R (Octree and Rtree)树索引，构建适用于大规模矢量模型的空间索引。O & R索引本质上可以看做一棵特殊的八叉树，该八叉树的叶子结点指向一棵与其对应索引空间相关联的R树(图1)，以在大范围空间内通过八叉树快速过滤，以提高检索效率，在局部通过R树精确检索，以减小检索过程中的冗余数据。

在此模型搜索结构中，八叉树的检索效率要远高于R树，因此，R树的快速检索是本索引成功的关键，R树的检索效率与面片规模增加并非呈线性关系，因此，本搜索结构需要解决R树搜索节点上所包含的最大面片数阈值的问题，亦即八叉树分解过程中，叶子节点上所包含的最大的面片数为多少的问题。在R树建立时，若其模数量小于此阈值，则树结构划分太过细碎，若模型数量大于此阈值，则R树检索效率大大降低，本文在此基于实验经验采用模型数量阈值为30,000。

3. 模型快速检索

当空间模型的规模达到一定程度的时候，已经不可能将其全部读取到内存空间中进行计算，一者需要大规模的时间进行数据读取，二者在计算机内存有限的情况下，内存空间将无法容纳所有的模型数据，因此需要一种能够在外存中快速检索模型的模型快速检索的策略，本文通过将模型以二进制形式存储在文件之中，然后在读取数据的时候，以文件指针快速定位到模型数据，从而实现数据的快速检索。

Figure 1. O & R tree

图1. O & R树

3.1. 模型存储

基于上述的O & R树，可以快速检索到所需要的模型面片的索引号，因此，只需要能够在模型面片的索引号的基础上，快速实现模型数据的检索即可实现目标区域处模型数据的快速检索。基于此考虑，需要模型数据以高度结构化的形式进行存储，同时考虑到文本文件形式的数据存储在读取的时候，以读行的形式亦无法快速实现数据定位，因此，本文采用一种二进制形式的三角形数据存储，具体存储步骤如下：

1) 获取三角形中的三个顶点的数据，将每个顶点所包含的x、y、z坐标数据皆转化为二进制数据形式，本文的坐标数据皆以双精度浮点形式进行存储，因此，每个坐标值将转化为8个字节的二进制数据；

2) 将每个三角形的数据，按照原始的三角形的点位顺序，并按照x、y、z的顺序，以二进制形式将数据输出到目标文件中，因为每个坐标值占用8个字节空间，每个顶点将占用24字节，每个三角形将占用72字节的数据空间。

基于此存储模式，每个三角形的占用空间一致，可满足结构化的数据存储要求。

3.2. 模型快速检索

基于此模型数据存储格式，采用文件指针的形式，可根据三角形的索引号快速定位到模型对应三角形数据的位置，由于每个三角形的存储空间为72字节，因此，对于索引号为n的三角形的空间起始位置为：

$L=\left(n-1\right)\times 72$

通过调节文件指针的起始位置，读取接下来的72字节的内容，按照每8个字节转换为双精度浮点数的规则，获得9个坐标值，即可获取目标三角形对应的数据。由于本文实验中采取C++语言实现，因此，此处采用fseek方法实现三角形数据定位，具体方法(图2)描述如下：

1) 首先通过文件指针打开一个文件，此时文件指针指向文件的首端；

2) 然后通过上述公式计算目标三角形对应的文件位置，通过fseek方法将文件指针移动到对应的位置；

3) 然后通过memcpy方法获取接下来的72字节内容；

4) 最后将此二进制内容解析为对应的三角形坐标值，即可获得目标三角形数据。

Figure 2. Fast retrieval of models

图2. 模型快速检索

4. 算法验证

通过上述技术方案，将中国南方某地区的倾斜摄影测量模型进行方法测试，考虑到本文方法并不需要瓦片组织形式的倾斜摄影模式，因此，本文所采用的测试模型为软件导出来的不进行瓦片划分的OBJ模型，即进行了二级划分，但是二级节点为仅包含一个综合模型的OBJ模型，而不再是层级结构的瓦片形式数据，在此结构中，模型包含共1,678,938个三角形。

基于此倾斜摄影模型本身的组织结构，本文在一个八叉树根节点的基础上，将这些模型分为21个二级子节点，然后，在限定每个叶子节点上不超过30,000个三角形的基础上，对每个二级节点在进行子节点划分，最终得到了204个八叉树叶子结点，即204个R树根节点。在此数据的基础上，本文通过计算向此倾斜模型上进行高程投射计算，针对不同规模的点数，本文对算法进行了时间统计，时间统计表1，根据统计结果可知，本文算法的单点检索，可以控制在3毫秒内，10,000个点的高程投射计算仅26秒多，极大满足了我们在工程项目中对于高程投射计算的要求。

Table 1. Relation table of calculating time and count of points

表1. 计算时间与计算点数关系表

根据此时间统计，本文绘制了其相关度曲线，曲线绘制如图3，可见计算时间与计算点数呈现线性正相关性，表明算法具有较强的鲁棒性。

Figure 3. Relation between calculating time and count of points

图3. 计算时间与计算点数的关系

5. 结论与展望

测绘技术的高速发展，使得在计算机世界中重建丰富的现实场景变得容易，但是，大规模模型在供三维展示之余，在数据运算时模型的检索却存在诸多瓶颈，本文综合八叉树与R树形成O & R树，可实现模型的高性能的检索，并基于序列化的二进制模型的存储，可实现模型的高效索引与快速的模型检索，主要包括：

1) 基于O & R树的索引模式，可以避免八叉树的末端冗余数据，也可以避免R树的索引结果过于庞大，从而实现三角形数据的快速检索；

2) 基于序列化的二进制模型存储方式，可避免在获取定向三角形数据的时候，需要读取所有的三角形数据，可大大提高数据的精确检索效率；

3) 此两个方法的使用可以使目标区域三角形数据的检索变得高效，从而使得运算瓶颈不再存在于模型的查找中，使得计算资源可以更多分配于需要进行运算的地方。

虽然本文实现模型的快速检索与高效动态检索，但是本文提出的格式并不能完美兼容现行的主流的模型格式，后续拟在现有的模型格式的基础上，做更深入的融合，从而使得本文的方法具有更高的适用性与推广性。

致谢

感谢望城经开区投资建设集团有限公司的张三秀女士在本文图表绘制、文章用词修改，以及相关英文翻译中提供的建议与帮助。