ｎｘ已是实际运行的移动测图系统［
２
］。最新的移动测图系统装备多个激光扫描仪，
动态获取厘米级密度的海量三维激光点云，精度可达５ｃｍ［３］
。移动测图
系统的原始数据采集率为３６０ＧＢ／ｈ，假设以３０～
４０ｋｍ／ｈ行驶，每千米道路数据采集量为１０ＧＢ，一个小城区的数据采集量可能高达若干ＴＢ，前所未有的数据采集速度和高分辨率要求对三维激光点
云数据高效管理面临更为严峻的挑战［
４
］。随着高分辨率车载激光扫描系统的普及应用，大量散乱点云数据的快速处理成为国际研究的焦点。点云数据后处理如简化滤波、语义分割和特征提取等交互操作受限于数据管理和可视化的性能，极大地制约了快速获取点云数据的综合
应用能力［５－
６］。在计算机图形学领域，发展了多种
专门的数据组织方法加速绘制效率和质量，但多关注单个目标的点云数据，难以有效处理复杂场
Ａｕｇ
ｕｓｔ ２０１２ Ｖｏｌ．４１ Ｎｏ．４ ＡＧＣＳ ｈｔｔｐ：∥ｘｂ．ｓｉｎｏｍａｐ
ｓ．ｃｏｍ景的地物目标数据。由于点云数据量大且分辨率高，一种有效的处理策略是顾及细节层次的自适
应可视化。Ｓｕｒｆｅｌｓ［７］和Ｑｓｐ
ｌａｔ［８］是多细节层次点表达模型的两个最具代表性的实现方法，它们的预处理过程均很费时，
不平衡的树状结构容易导致树深过高进而致使查询效率恶化。之后，计算机图形领域的绝大多数方法基本是上述两种方法的改进，
如采用并行处理方法和图形处理器提高绘制效率，
或者实现外存缓存机制等［９］
。在空间信息科学领域，文献［１０］提出基于顺序四叉树的数据组织方法管理机载激光点云，采用分段文件映射技术随机抽取不同细节的点云，并关联到相应层的节点中，很好地实现了自适应点云绘制，然而随机抽取方式不能保证对车载激光点云也具有良好简化结果，
过深树高引发频繁迭代计算也是影响管理效率的隐患。文献［１１］的方法与之类似，
它们仍然是一种二维数据管理方法，难以最好地支持视锥体裁剪等可视化算子。文献［１２］采用八叉树和平衡二叉树的嵌套结构管理海量点云，顾及了树状结构的平衡性问题，但是采用单一维度作为二叉树剖分依据没有顾及三维空间特性。文献［１３］采用空间数据分布方法将海量点云分配至多个服务器，
采用并行访问技术提高数据管理效率，是利用计算机集群管理点云的有益尝试。
三维Ｒ树可以根据目标数据自适应地调整索引结构，目标分布状态对其影响较小，是一种有
前途的三维空间索引方法［１４－
１５］。理论上，三维Ｒ
树的动态更新和自适应调整能力非常适合分布散乱、
密度不均的三维点云应用。然而，由于算法复杂、点云数量庞大等诸多原因，至今未见Ｒ树成功管理点云的文献发表。
本文利用八叉树的快速收敛能力，提出一种八叉树和Ｒ树集成的新三维索引方法—３ＤＯＲ
树，显著提升大规模点云的Ｒ树索引创建效率，并采用一种顾及多细节层次的三维Ｒ树索引扩展结构高效生成多细节层次点云模型，支持大规模车载激光点云的高效管理和自适应可视化。本文研究内容可以描述如图１
。
图１ 本文研究框架
Ｆｉｇ．１ Ｔｈｅ ｆｒａｍｅｗｏｒｋ ｏｆ ｔｈｉｓ ｓｔｕｄｙ
２ 集成八叉树和Ｒ树的三维空间索引
模型３ＤＯＲ树
Ｒ树索引能够很好地适应空间数据分布特点，
且能提供稳健高效的空间查询能力［
１６
］。Ｒ树索引生成方法分为动态方法和静态方法，动态生成方法更符合空间数据管理要求，
但是每个点均要经过节点选择和节点分裂等复杂操作才能插入到索引结构中，对于数以亿计的点云数据来说并不现实，需要寻求一种更高效的索引创建方法，本文采用一种动静结合的方式构建三维Ｒ树索引结构，兼具静态方法的高效率和动态方法的自适应性。
下面是结合三维Ｒ树和八叉树（ｏｃｔｒｅｅ）的索引创建算法（３ＤＯｃｔ－Ｒｔｒｅｅ，简称３ＤＯＲ树）描述，图２是３ＤＯＲ树创建流程图。给三维Ｒ树设定扇出
（ｆａｎｏｕｔ）参数，即每个节点允许包含最大元组数目和最小元组数目，
采用八叉树剖分三维空间，节点收敛条件是每个叶节点中的点数目小于等于最大元组数目。八叉树分裂过程中，满足扇出参数条件的子节点将重新计算范围，
以叶节点身份插入到三维Ｒ树中。点数小于扇出参数最小值的子节点中的点输出至数组，
按顺序重组为满足扇出参数的叶节点逐一插入到Ｒ树，
过程中不对数组中的点重新空间排序，原因是这些点相对邻近，重新排序代价高且意义不大。对于无法保证满足扇出参数的情况，添加其中的点到全局点数组中，待八叉树剖分结束后，以单点身份逐一插入Ｒ树。
算法描述：点云的空间索引创建算法。算法输入：点元组集合，Ｒ树扇出参数为［ｉｍｉｎ，ｉｍａｘ］
。算法输出：三维Ｒ树索引结构。
步骤１：计算包含所有点集的最小包围盒（ｍｉｎＸ，ｍｉｎＹ，ｍｉｎＺ，ｍａｘＸ，ｍａｘＹ，ｍａｘＺ），并以（ｍｉｎＸ，ｍｉｎＹ，ｍｉｎＺ）为起算点，计算包含所有点集的最小立方体范围，作为八叉树根节点范围，全部点均是节点ｎｏｄｅ中的元组，并创建两个点数组Ａｒｒａｙ１和Ａｒｒａｙ
２。步骤２：如果元组数目大于ｉｍａｘ，则将空间均匀分为８个子节点Ｃｈｉｌｄｉ（
ｉ＝０，１，…，７），并将点分配至对应的子节点，进入步骤３；如果ｎｏｄｅ中
元组数目小于等于ｉｍａｘ，
则停止分裂。步骤３：清空Ａｒｒａｙ１，逐一遍历子节点Ｃｈｉｌｄｉ，如果Ｃｈｉｌｄｉ中的点数目小于ｉｍｉｎ，将其中的点加入Ａｒｒａｙ１中，令Ａｒｒａｙ
１中的点数目为ｉＰｔ－８９５
第４期龚 俊，等：一种八叉树和三维Ｒ树集成的激光点云数据管理方法Ｎｕｍ，
进入步骤４
。图２ ３ＤＯＲ树创建流程图
Ｆｉｇ
．２ Ｆｌｏｗ ｃｈａｒｔ ｏｆ ｔｈｅ ３ＤＯＲ－Ｔｒｅｅ ｃｏｎｓｔｒｕｃｔｉｏｎｐ
ｒｏｃｅｄｕｒｅ步骤４：如果ｉＰｔＮｕｍ小于ｉｍｉｎ，将数组中所有点逐一插入Ａｒｒａｙ２中；如果ｉＰｔＮｕｍ大于等于ｉｍｉｎ且小于等于ｉｍａｘ，