一种八叉树和三维R树集成的激光点云数据管理方法

龚 俊，柯胜男，朱 庆，钟若飞

1.江西师范大学软件学院，江西南昌330022；2.武汉大学测绘遥感信息工程国家重点实验室，湖北武汉430079；3.首都师范大学资源环境与旅游学院，北京100048

一种八叉树和三维R树集成的激光点云数据管理方法

龚 俊1，柯胜男1，朱 庆2，钟若飞3

1.江西师范大学软件学院，江西南昌330022；2.武汉大学测绘遥感信息工程国家重点实验室，湖北武汉430079；3.首都师范大学资源环境与旅游学院，北京100048

车载激光扫描点云数据已经成为数字城市和危机管理等领域越来越重要的三维空间信息源，针对大规模点云数据高效管理的技术瓶颈，提出一种八叉树和三维R树集成的空间索引方法——3DOR树，充分利用八叉树的良好收敛性创建R树叶节点，避免逐点插入费时过程，同时R树平衡结构保证良好的数据检索效率。并还扩展R树结构生成多细节层次（LOD）点云模型，提出一种支持缓存的多细节层次点云数据组织方法。试验证明，该方法具有良好的空间利用率和空间查询效率，支持多细节层次描述能力和数据缓存机制，可应用于大规模点云数据的后处理与综合应用。

八叉树；三维R树；激光扫描；点云；数据管理

1 引 言

欧洲空间数据研究组织EuroSDR指出三维城市建模能力需要具备高覆盖度、高逼真度和高更新率，意味着对三维城市建模技术提出更好、更快、更廉价和更智能的要求，而这恰恰是传统三维建模手段的弱项［1］。三维激光扫描技术和多角度摄影测量密集匹配技术为三维建模旺盛需求和有限人力物力资源间的冲突提供解决方案。RIEGL的VMX－250、TopCon的IP－S2和Optech的Lynx已是实际运行的移动测图系统［2］。最新的移动测图系统装备多个激光扫描仪，动态获取厘米级密度的海量三维激光点云，精度可达5cm［3］。移动测图系统的原始数据采集率为360GB／h，假设以30～40km／h行驶，每千米道路数据采集量为10GB，一个小城区的数据采集量可能高达若干TB，前所未有的数据采集速度和高分辨率要求对三维激光点云数据高效管理面临更为严峻的挑战［4］。

随着高分辨率车载激光扫描系统的普及应用，大量散乱点云数据的快速处理成为国际研究的焦点。点云数据后处理如简化滤波、语义分割和特征提取等交互操作受限于数据管理和可视化的性能，极大地制约了快速获取点云数据的综合应用能力［5－6］。在计算机图形学领域，发展了多种专门的数据组织方法加速绘制效率和质量，但多关注单个目标的点云数据，难以有效处理复杂场景的地物目标数据。由于点云数据量大且分辨率高，一种有效的处理策略是顾及细节层次的自适应可视化。Surfels［7］和Qsplat［8］是多细节层次点表达模型的两个最具代表性的实现方法，它们的预处理过程均很费时，不平衡的树状结构容易导致树深过高进而致使查询效率恶化。之后，计算机图形领域的绝大多数方法基本是上述两种方法的改进，如采用并行处理方法和图形处理器提高绘制效率，或者实现外存缓存机制等［9］。

在空间信息科学领域，文献［10］提出基于顺序四叉树的数据组织方法管理机载激光点云，采用分段文件映射技术随机抽取不同细节的点云，并关联到相应层的节点中，很好地实现了自适应点云绘制，然而随机抽取方式不能保证对车载激光点云也具有良好简化结果，过深树高引发频繁迭代计算也是影响管理效率的隐患。文献［11］的方法与之类似，它们仍然是一种二维数据管理方法，难以最好地支持视锥体裁剪等可视化算子。文献［12］采用八叉树和平衡二叉树的嵌套结构管理海量点云，顾及了树状结构的平衡性问题，但是采用单一维度作为二叉树剖分依据没有顾及三维空间特性。文献［13］采用空间数据分布方法将海量点云分配至多个服务器，采用并行访问技术提高数据管理效率，是利用计算机集群管理点云的有益尝试。

三维R树可以根据目标数据自适应地调整索引结构，目标分布状态对其影响较小，是一种有前途的三维空间索引方法［14－15］。理论上，三维R树的动态更新和自适应调整能力非常适合分布散乱、密度不均的三维点云应用。然而，由于算法复杂、点云数量庞大等诸多原因，至今未见R树成功管理点云的文献发表。

本文利用八叉树的快速收敛能力，提出一种八叉树和R树集成的新三维索引方法—3DOR树，显著提升大规模点云的R树索引创建效率，并采用一种顾及多细节层次的三维R树索引扩展结构高效生成多细节层次点云模型，支持大规模车载激光点云的高效管理和自适应可视化。本文研究内容可以描述如图1。

图1 本文研究框架Fig.1 The framework of this study

2 集成八叉树和R树的三维空间索引模型3DOR树

R树索引能够很好地适应空间数据分布特点，且能提供稳健高效的空间查询能力［16］。R树索引生成方法分为动态方法和静态方法，动态生成方法更符合空间数据管理要求，但是每个点均要经过节点选择和节点分裂等复杂操作才能插入到索引结构中，对于数以亿计的点云数据来说并不现实，需要寻求一种更高效的索引创建方法，本文采用一种动静结合的方式构建三维R树索引结构，兼具静态方法的高效率和动态方法的自适应性。

下面是结合三维R树和八叉树（octree）的索引创建算法（3DOct－Rtree，简称3DOR树）描述，图2是3DOR树创建流程图。给三维R树设定扇出（fanout）参数，即每个节点允许包含最大元组数目和最小元组数目，采用八叉树剖分三维空间，节点收敛条件是每个叶节点中的点数目小于等于最大元组数目。八叉树分裂过程中，满足扇出参数条件的子节点将重新计算范围，以叶节点身份插入到三维R树中。点数小于扇出参数最小值的子节点中的点输出至数组，按顺序重组为满足扇出参数的叶节点逐一插入到R树，过程中不对数组中的点重新空间排序，原因是这些点相对邻近，重新排序代价高且意义不大。对于无法保证满足扇出参数的情况，添加其中的点到全局点数组中，待八叉树剖分结束后，以单点身份逐一插入R树。

算法描述：点云的空间索引创建算法。

算法输入：点元组集合，R树扇出参数为［imin，imax］。

算法输出：三维R树索引结构。

步骤1：计算包含所有点集的最小包围盒（minX，minY，minZ，maxX，maxY，maxZ），并以（minX，minY，minZ）为起算点，计算包含所有点集的最小立方体范围，作为八叉树根节点范围，全部点均是节点node中的元组，并创建两个点数组Array1和Array2。

步骤2：如果元组数目大于imax，则将空间均匀分为8个子节点Childi（i＝0，1，…，7），并将点分配至对应的子节点，进入步骤3；如果node中元组数目小于等于imax，则停止分裂。

步骤3：清空Array1，逐一遍历子节点Childi，如果Childi中的点数目小于imin，将其中的点加入Array1中，令Array1中的点数目为iPt－ Num，进入步骤4。

图2 3DOR树创建流程图Fig.2 Flow chart of the 3DOR－Tree construction procedure

步骤4：如果iPtNum小于imin，将数组中所有点逐一插入Array2中；如果iPtNum大于等于imin且小于等于imax，则将数组中所有点打包为叶节点插入R树中；如果iPtNum大于imax且小于等于2imax，将点均分为两个叶节点，插入R树中；如果iPtNum大于2imax，k为iPtNum／imax取整，将数组前（k－1）imax个点，均分（k－1）个叶节点插入R树，剩余点数iRestNum为iPtNum－（k－1）imax，如果iRestNum等于imax，则将其作为一个叶节点插入到R树，如果大于imax（必然小于2imax），则将其均分为两个叶节点，插入R树中。

步骤5：逐一遍历子节点Childi，如果Childi中的点数目大于imax，则令node为Childi，进入步骤2。

步骤6：逐一遍历子节点Childi，如果Childi中的点数目大于等于imin且小于等于imax，则将节点中的点组成叶节点插入R树。

步骤7：所有八叉树分支分裂结束后，将Array2中的点以元组身份逐一插入R树。

步骤8：退出。

本方法利用八叉树分配邻近点至相同或相邻节点中，通过以节点为插入单元的策略批量插入点，避免了逐点插入的费时操作，显著地提高索引生成效率，同时仍然采用动态生成方法构建R树，使得树形结构具有很好的空间适应性，保证平衡树状结构和良好空间利用率。图3是某点云数据的八叉树叶节点层（分裂参数为100，即大于100个点要分裂节点）和3DOR树结构叶节点层（扇出参数为40和100）。

图3 八叉树和3DOR树的叶节点层Fig.3 Leaf nodes in Octree and 3DOR－tree

3 顾及多细节层次的3DOR树扩展结构

对于车载激光点云测图应用需要高效交互性能来说，启用多细节层次策略成为合理甚至必须的选择，即根据视距和软硬件性能实时选择合适细节层次表示点云场景。关于R树和多细节层次场景结合的已有研究均试图采用R树的天然层次结构实现目标查询和细节层次查询的双重功能［17－19］。然而，应用R树节点包围盒作为低细节层次描述，忽略单个目标的LOD（level of details）描述需求，也不能满足可视化精度要求。

传统R树索引方法仅在叶节点中管理目标模型，本文扩展结构使得中间节点也能管理目标模型。叶节点层管理全部和最精细的目标，从每个子节点按照某种规则挑选一个最有代表性的目标作为较粗层次目标模型集合存于父节点中，因此上层节点中的目标数目和子节点数目相等。举例说明，从每个子节点中选择一个距离目标集合重心最近的目标作为上层节点的目标。

本文方法借助R树的层次结构，叶节点代表最高的细节层次，中间节点代表中等的细节层次，根节点代表最低的细节层次。每层被设置一个适用范围，包括最近距离和最远距离，相邻层的适用范围无缝拼接。同层中所有节点的适用范围相同，当视点和节点的距离落于该范围内，即访问节点中的点模型。在全景描绘时，只需访问根节点中的点模型，随着视点接近，视域逐渐减小，关注细节逐渐提高，从根节点访问其子节点，根节点中的点仅是其子节点中的重要目标，因此关注的目标集合有所增加，细节层次增强。LOD选取距离原则的详细解释可以参考文献［20］。图4是点云的多细节层次描述效果。

图4 点云的多细节层次描述Fig.4 LOD representation of point clouds

4 基于3DOR树的点云数据高效组织方法

由于文件大小的限制，大规模点云工程采用工程－点云－点层次模式组织点云数据。车载激光点云采集过程中，每隔几百万个点分段为单个点云，单个点云的原始文本文件数据量为数百兆字节，某个应用中的点云集合即为点云工程，一个小型城镇的点云工程可能高达数十GB。本文采用自定义的文件结构组织大规模车载激光点云，目的是为了提高数据管理效率，其方法也可实现于商业数据库管理系统。

以自定义文件系统方式为例，点云工程是包含众多点云的目录，点云是单个二进制数据文件，图5是本文数据组织方法描述。每个点云包括头部分和实体部分，头部分包括点云的整体信息，如版本号、总数据量、R树扇出参数（子节点数目的最大最小值）、总点数、R树总层数、空间范围、中心点坐标、压缩标志以及根节点地址等。点坐标是实际点坐标减去中心点坐标的差值，这样坐标可以采用较少有效位数表示，有利于采用4字节单精度浮点类型表示点坐标，另外，如果空间范围在各坐标轴上的长度小于655.35m且精度要求在厘米级（车载激光扫描数据精度可达到厘米级），将坐标值乘以100然后用2字节短整数类型表示点坐标，数据量减少75%。

图5 点云工程数据组织方法Fig.5 Data organization method of point cloud project

点云的实体部分采用三维R树索引结构管理点数据，R树索引结构包括根节点、中间节点和叶节点。本文的多细节层次生成方法中，上层节点从每个子节点中选取一个点作为低细节层次描述，为避免重复存储和处理，选取点将从子节点移出至上层节点，这样中间节点和叶节点中的点数目要减1。为了实现缓存机制，即根据视域条件动态调度数据，父节点记录子节点的首地址，即子节点相对文件起始位置的偏移量。R树存储结构可以分为按广度遍历存储顺序和按深度遍历存储顺序组织。广度遍历存储顺序指按节点层的次序存储节点数据，从根节点开始，将节点按层顺序依次记录到文件中，负面影响是父节点和子节点无法集中存储；深度遍历存储顺序指从根节点开始，然后记录其各个子树，负面影响是中间层的兄弟节点无法集中存储。图6（a）和（b）分别是广度遍历存储和深度遍历存储的原理。

图6 广度和深度遍历存储原理描述Fig.6 Principal description of breadth and depth traversal storage

点云工程数据规模通常很大，超出主存容量和图形绘制硬件处理能力，一般打开工程时仅调度上面数层节点中的点数据以描述全景，当视点逼近局部场景时，将通过父节点依次访问子节点直至叶节点，因此广度优先存储和深度优先存储方式均不能完全满足高效调度的要求。本文采用二者混合方案来最大限度提升数据调度效率。以叶节点层为第0层，例如全景显示第2层及以上节点中的点数据时，将第2层及以上层采用广度优先存储，最下两层按照深度优先存储，至于具体以第几层为分界线，将根据总数据量决定，如果数据量小可以下调，如果数据量大可以上调。图7是本文方法的原理描述，其中第2层是分界线。本文方法采用文件映射技术访问点云文件，每个父节点记录所有子节点地址，采用类似于访问内存方法根据节点地址访问节点外存数据。本文方法将极有可能连续访问的节点数据集中存储，有利于提高外存访问效率。

图7 混合存储方式原理描述Fig.7 Principal description of mixed storage

单点数据内容包括三维坐标、颜色以及强度等信息，可以根据应用需要扩展单点结构。如果采取压缩方式存储，三维坐标值采用2字节短整型表示，相对于双精度浮点型表示，数据量减少75%，可以显著减少数据调度量，提升外存访问效率。另外，为最大限度提升三维可视化效率，点数据应当按照图形绘制硬件特点进行组织，例如，采用OpenGL绘制引擎时，可以将节点中的点数据组织成VBO顶点缓冲形式，直接送入绘制管线处理。

5 试验结果与分析

本试验采用测试数据是车载激光扫描移动测图系统采集的真实数据，是中国某小型城镇的真彩色三维点云数据。车辆行驶耗费20min扫描该镇全部道路，获取详细的街道、房屋立面、树木以及电线等点模型。原始数据包含92个点云文件，每个点云文件包含200多万个点，总数据量约为14.6GB（包含坐标、颜色、时间等数据），总点数为2.2亿。测试环境配置如下：笔记本电脑，CPU Intel Duo T7500，内存1GB。

5.1 索引创建效率测试

索引创建效率关系到应用成败，如果索引创建需要十几个小时甚至更长，即使查询效率满足交互要求，也不能适应实际应用需要。由于格网索引的格网尺寸难以确定，且大量空格网容易导致空间利用率极低，本文不予比较测试。本文分别对八叉树、三维动态R树和3DOR树生成算法进行效率测试。其中，八叉树参数为100，即节点中点数目小于等于100时停止分裂，三维R树的扇出参数为40和100，而3DOR树中，八叉树分裂参数为100，R树扇出参数为40和100。

采用一份包含2 426 454个点的点云数据测试索引创建效率，表1中有八叉树、3DOR树以及三维动态R树的创建效率对比。八叉树深度不平衡，叶节点树深从1到17不等。3DOR树深度平衡，树深为4。三维动态R树深度平衡，树深为5。从测试数据可知，本文的3DOR索引方法创建效率满足准实时要求，树深平衡，并且树深比另两种方法小。原因是，3DOR树本质上仍是R树索引结构，且叶节点基本是满负荷，从而节点数目减少和深度减小。较小的树深直接减少迭代运算层数，有利于显著改善算法效率。本文对总数据量14.6GB的点云工程创建索引，总耗费时间约为40min。

5.2 空间利用率测试

相对于CPU计算和主存访问效率，外存访问效率低两个数量级以上且改善空间有限，数据量大小直接关系到后续外存数据调度效率，进而影响用户体验。点云工程数据量往往大于主存容量，动态调度和数据缓存机制成为必须采用的策略。本文通过中心点平移方法将双精度浮点型数据转化为单精度浮点型，进一步将单精度浮点型转化为短整型，并清除冗余点（距离小于1cm视为冗余点），数据量压缩显著，表1中有文本格式、Pointools商业格式和本文结构的数据量对比。不难看出，原始文本数据转化为本文数据格式，压缩率超过全球业界领先者Pointools。

表1 空间索引重要指标对比Tab.1 Comparison of key criteria for spatial index

5.3 数据调度与可视化效率测试

如果用户打开和全景显示工程的等待时间过长，将严重影响用户体验。采用Pointools商业平台将试验数据转化为其特有POD格式并组织成为工程后，试验环境打开工程耗时超过4min。由于是商业平台，无法测算其效率瓶颈。值得指出的是，当工程打开后，该商业平台可以保证后续交互操作的流畅性。

本文方法中，点云工程包含2亿多个点，扇出参数为40和100，第2层及以上点云模型不会超过10万个点（2×108／（40×40）），因此打开工程只需调度第2层及以上的点云模型。第2层以上按照广度优先遍历方法进行存储，后续访问时按照广度优先遍历顺序即可将所需节点外存数据依次读取，不会出现跳跃访问，最大限度地提高数据访问效率，试验结果表明耗时仅需4s，图8是点云工程的全景图。另外，本文设计试验测试深度优先存储方法的访问效率，节点数据重新按照深度优先遍历方式存储，打开整个工程耗时3min，相比于本文方法，效率下降明显。

图8 点云工程全景Fig.8 Full scene of point cloud project

本试验环境允许的数据缓存容量不超过200兆，单帧绘制点数不超过500万个，如果超过容许值将自动清理缓冲区。当视点落于场景中近距离浏览地物目标时，自适应可视化机制下最高细节层次作用范围的最远距离一般保持在15m左右，即使显著改变视点位置，所需调度数据量也不会超过10MB，调度时间不超过2s。试验采用多线程机制调度数据，并不影响主线程绘制任务，实现点云场景多细节层次描述效果。

5.4 空间查询效率测试

车载激光扫描平台的一项重要任务是三维测图，捕捉三维点成为应用成败的关键。如果不借助空间索引功能，从场景中数以亿计的点集中搜索目标点将会效率极低。本文借助三维R树索引能力，捕捉目标点没有明显停顿，符合交互测图要求。试验过程测试多个环节，如捕捉点、场景移动和连线等功能，均能实现流畅交互操作。图9是本试验平台的测图结果，其中包括天线和建筑物墙面等测图成果。

图9 试验平台三维测图效果Fig.9 3Dmapping in experimental platform

6 结 论

大规模点云管理和可视化是阻碍点云应用的难题，本文采用一种集成八叉树和三维R树的新方法，借助八叉树细粒度地划分点云的三维空间，通过将八叉树叶节点组织为R树叶节点的策略，避免了海量点云的逐点插入操作，显著提升索引创建效率，由于依然采用动态插入方法创建三维R树，保证了深度平衡的树状结构，实现良好的空间查询效率。基于R树的天然层次结构，本文还提出了一种点云场景多细节层次模型生成方法和点云数据层次组织结构。本文研究不仅为大规模点云自适应可视化提供管理支持，同时也为激光点云深度利用提供理论和方法支持。

当前单点包含4～6个属性值，随着传感器技术的发展，未来极可能翻倍甚至更多，通过自动分类和目标提取还可以产生更加丰富的语义信息，也给点云管理带来新挑战。语义可以视为点云的另一种细节层次，后续研究将面向数据融合和语义管理的点云管理方法，实现同全景影像、矢量图形以及语义信息的集成应用。

［1］ NEBIKER S，BLEISCH S，GÜLCH E.EuroSDR Online Survey on Virtual Globes［R］.The 114th EuroSDR Steering Committee Meeting，Paris：［s.n.］，2009.

［2］ BARBER D，MILLS J，SMITH－VOYSEY S.Geometric Validation of a Ground Based Mobile Laser Scanning System［J］.ISPRS Journal of Photogrammetry and Remote Sensing，2008，63（1）：128－141.

［3］ HAALA N，PETER M，KREMER J，et al.Mobile LiDAR Mapping for 3DPoint Cloud Collection in Urban Areas—A Performance Test［C］∥Proceedings of XXI ISPRS Congress.［S.l.］：ISPRS，2008.

［4］ NEBIKER S，BLEISCH S，CHRISTEN M.Rich Point Clouds in Virtual Globes——A New Paradigm in City Modeling？［J］Computer，Environment ＆Urban System，2010，34（6）：508－517.

［5］ YANG Bisheng，WEI Zheng，LI Qingquan，et al.A Classification－oriented Method of Feature Image Generation for Vehicle－borne Laser Scanning Point Clouds［J］.Acta Geodaetica et Cartographica Sinica，39（5）：540－545.（杨必胜，魏征，李清泉，等.面向车载激光扫描点云快速分类的点云特征图像生成方法［J］.测绘学报，2010，39（5）：540－545.）

［6］ HUANG Xianfeng，LI Hui，WANG Xiao，et al.Filter Algorithms of Airborne LiDAR Data：Review and Prospects［J］.Acta Geodaetica et Cartographica Sinica， 2009，38（5）：466－469.（黄先锋，李卉，王潇，等.机载Li－DAR数据滤波方法评述［J］.测绘学报，2009，38（5）：466－469.）

［7］ PFISTER H，ZWICKER M，VAN BAAR J，et al.Surfels：Surface Elements as Rendering Primitives［C］∥Proceedings of ACM SIGGRAPH 2000.New York：ACM Press，2000：335－342.

［8］ RUSINKIEWICZ S，LEVOY M.QSplat：A Multiresolution Point Rendering System for Large Meshes［C］∥Proceedings of ACM SIGGRAPH 2000.New York：ACM Press，2000：343－352.

［9］ WAND M，BERNER A，BOKELOH M，et al.Processing and Interactive Editing of Huge Point Clouds from 3D Scanners［J］.Computer ＆Graphics，2008，32（2）：204－220.

［10］ HUANG Xiangfeng.Research on 3DBuilding Model Extraction from Airborne LIDAR Data［D］.Wuhan：Wuhan University，2006.（黄先锋.利用机载LiDAR数据重建3D建筑物模型的关键技术研究［D］.武汉：武汉大学，2006.）

［11］ ZHI Xiaodong，LIN Zongjian，SU Guozhong，et al.Research on Organization of Airborne LiDAR Points Cloud Based on Improved Quadtree Algorithm［J］.Computer Engineering and Applications，2010，46（9）：71－74.（支晓栋，林宗坚，苏国中，等.基于改进四叉树的LiDAR点云数据组织研究［J］.计算机工程与应用，2010，46（9）：71－74.）

［12］ LU Mingyue，HE Yongjian.Organization and Indexing Method for 3DPoints Cloud Data［J］.Geo－information Science，2008，10（2）：190－194.（路明月，何永健.三维海量点云数据的组织与索引方法［J］.地球信息科学，2008，10（2）：190－194.）

［13］ MA H，WANG Z.Distributed Data Organization and Parallel Data Retrieval Methods for Huge Scanner Point Clouds［J］.Computer ＆Geoscience，2011，37（1）：193－201.

［14］ ZHU Q，GONG J，ZHANG Y T.An Efficient 3DR－tree Spatial Index Method for Virtual Geographic Environments［J］.ISPRS Journal of Photogrammetry and Remote Sensing，2007，62（3）：217－224.

［15］ GONG Jun，ZHU Qing，ZHANG Yeting，et al.An Efficient 3DR－tree Extension Method Concerned with Levels of Detail［J］.Acta Geodaetica et Cartographica Sinica，2011，40（2）：249－255.（龚俊，朱庆，张叶廷，等.顾及多细节层次的三维R树索引扩展方法［J］.测绘学报，2011，40（2）：249－255.）

［16］ MANOLOPOULOS Y，NANOPOULOS A，PAPADOPOULOS A N，et al.R－Trees：Theory and Applications［M］.Germany：Springer Press，2005.

［17］ KOFLER M.R－trees for Visualizing and Organizing Large 3DGIS Databases［D］.Graz：Graz University of Technology，1998.

［18］ ZLATANOVA S.3DGIS for Urban Development［D］.Enschede：ITC，2000.

［19］ LI Jun，JING Ning，SUN Maoyin.A Mechanism of Implementing Visualization with Level of Detail at Multi－Scale［J］.Journal of Software，2002，13（10）：2037－2043.（李军，景宁，孙茂印.多比例尺下细节层次可视化的实现机制［J］.软件学报，2002，13（10）：2037－2043.）

［20］ GONG Jun，ZHU Qing，ZHANG Hanwu，et al.An Adaptive Control Method of LoDs for 3DScene Based on R－tree Index［J］.Acta Geodaetica et Cartographica Sinica，2011，40（4）：531－534.（龚俊，朱庆，章汉武，等.基于R树索引的三维场景细节层次自适应控制方法［J］.测绘学报，2011，40（4）：531－534.）

E－mail：gongjunbox＠gmail.com

An Efficient Management Method for Point Cloud Data Based on Octree and3D R－tree

GONG Jun1，KE Shengnan1，ZHU Qing2，ZHONG Ruofei3
1.Department of Software，Jiangxi Normal University，Nanchang330022，China；2.State Key Laboratory of Information Engineering in Surveying，Mapping and Remote Sensing，Wuhan University，Wuhan 430079，China；3.Capital Normal University，College of Resources，Environment and Tourism，Beijing100048，China

Vehicle－borne laser point cloud data has become key 3D spatial information source in fields such as digital city and crisis management.Aiming at technical bottleneck of large－scale point cloud data management，a new spatial index method－3DOR－tree is presented，which integrates octree and3D R－tree.This method utilizes octree to forbid point－by－point insertion and generates leaf nodes of R－tree efficiently.R－tree structure is extended to present levels of detail（LOD）generation algorithm of point cloud models.Finally，a data organization approach is put forward for large－scale point cloud，which easily uses file mapping technique to accelerate data access.Experiments prove that this approach has fine space utilization and spatial query efficience with LOD representation capability and data cache mechanism，which lays a solid foundation for post－processing and comprehensive practices of large－scale point cloud data.

octree；3D R－tree；laser－scanning；point cloud；data management

GONG Jun（1978—），PhD，associate professor，majors in multi－dimension GIS and LiDAR.

GONG Jun，KE Shengnan，ZHU Qing，et al.An Efficient Management Method for Point Cloud Data Based on Octree and 3DR－tree［J］.Acta Geodaetica et Cartographica Sinica，2012，41（4）：597－604.（龚俊，柯胜男，朱庆，等.一种八叉树和三维R树集成的激光点云数据管理方法［J］.测绘学报，2012，41（4）：597－604.）

P208

A

1001－1595（2012）04－0597－08

国家自然科学基金（41001222）；国家973计划（2010CB731801；2011CB302306）；国家863计划（SS2012AA121001）；江西师范大学青年英才培育资助计划；江西省教育厅科技项目（GJJ12188）

雷秀丽）

2011－04－11

2012－02－29

龚俊（1978—），博士，副教授，从事多维地理信息系统和三维激光点云数据处理的理论与应用研究。