则将数组中所有点打包为叶节点插入Ｒ树中；如果ｉＰｔＮｕｍ大于ｉｍａｘ且小
于等于２ｉｍａｘ，将点均分为两个叶节点，插入Ｒ树中；如果ｉＰｔＮｕｍ大于２ｉｍａｘ，ｋ为ｉＰｔＮｕｍ／ｉｍａｘ取整，将数组前（ｋ－１）ｉｍａｘ个点，均分（ｋ－１）个叶节点插入Ｒ树，剩余点数ｉＲｅｓｔＮｕｍ为ｉＰｔＮｕｍ－
（ｋ－１）ｉｍａｘ，如果ｉＲｅｓｔＮｕｍ等于ｉｍａｘ，则将其作为一个叶节点插入到Ｒ树，如果大于ｉｍａｘ（必然小于２ｉｍａｘ）
，则将其均分为两个叶节点，插入Ｒ树中。步骤５：逐一遍历子节点Ｃｈｉｌｄｉ，如果Ｃｈｉｌｄｉ中的点数目大于ｉｍａｘ，则令ｎｏｄｅ为Ｃｈｉｌｄｉ，进入步骤２。
步骤６：逐一遍历子节点Ｃｈｉｌｄｉ，如果Ｃｈｉｌｄｉ
中的点数目大于等于ｉｍｉｎ且小于等于ｉｍａｘ，则将节点中的点组成叶节点插入Ｒ树。
步骤７：所有八叉树分支分裂结束后，将
Ａｒｒａｙ
２中的点以元组身份逐一插入Ｒ树。步骤８：退出。
本方法利用八叉树分配邻近点至相同或相邻节点中，通过以节点为插入单元的策略批量插入点，避免了逐点插入的费时操作，显著地提高索引
生成效率，同时仍然采用动态生成方法构建Ｒ
树，使得树形结构具有很好的空间适应性，保证平衡树状结构和良好空间利用率。图３是某点云数据的八叉树叶节点层（分裂参数为１００，即大于１００个点要分裂节点）和３ＤＯＲ树结构叶节点层（扇出参数为４０和１００
）
。图３ 八叉树和３ＤＯＲ树的叶节点层Ｆｉｇ
．３ Ｌｅａｆ ｎｏｄｅｓ ｉｎ Ｏｃｔｒｅｅ ａｎｄ ３ＤＯＲ－ｔｒｅｅ３ 顾及多细节层次的３ＤＯＲ树扩展结构
对于车载激光点云测图应用需要高效交互性能来说，启用多细节层次策略成为合理甚至必须的选择，即根据视距和软硬件性能实时选择合适细节层次表示点云场景。关于Ｒ树和多细节层次场景结合的已有研究均试图采用Ｒ树的天然层次结构实现目标查询和细节层次查询的双重功
能［
１７－
１９］。然而，应用Ｒ树节点包围盒作为低细节层次描述，忽略单个目标的ＬＯＤ（ｌｅｖｅｌ ｏｆ ｄｅｔａｉｌｓ）描述需求，也不能满足可视化精度要求。
传统Ｒ树索引方法仅在叶节点中管理目标模型，本文扩展结构使得中间节点也能管理目标模型。叶节点层管理全部和最精细的目标，从每个子节点按照某种规则挑选一个最有代表性的目标作为较粗层次目标模型集合存于父节点中，因此上层节点中的目标数目和子节点数目相等。举例说明，
从每个子节点中选择一个距离目标集合重心最近的目标作为上层节点的目标。
本文方法借助Ｒ树的层次结构，叶节点代表最高的细节层次，中间节点代表中等的细节层次，根节点代表最低的细节层次。每层被设置一个适用范围，包括最近距离和最远距离，相邻层的适用范围无缝拼接。同层中所有节点的适用范围相同，当视点和节点的距离落于该范围内，即访问节点中的点模型。在全景描绘时，只需访问根节点中的点模型，随着视点接近，视域逐渐减小，关注
９
９５
Ａｕｇ
ｕｓｔ ２０１２ Ｖｏｌ．４１ Ｎｏ．４ ＡＧＣＳ ｈｔｔｐ：∥ｘｂ．ｓｉｎｏｍａｐ
ｓ．ｃｏｍ细节逐渐提高，从根节点访问其子节点，根节点中的点仅是其子节点中的重要目标，因此关注的目标集合有所增加，细节层次增强。ＬＯＤ选取距离原则的详细解释可以参考文献［２０］。图４是点云的多细节层次描述效果
。
图４ 点云的多细节层次描述
Ｆｉｇ．４ ＬＯＤ ｒｅｐ
ｒｅｓｅｎｔａｔｉｏｎ ｏｆ ｐｏｉｎｔ ｃｌｏｕｄｓ４ 基于３ＤＯＲ树的点云数据高效组织方法
由于文件大小的限制，
大规模点云工程采用工程－点云－点层次模式组织点云数据。车载激光点云采集过程中，每隔几百万个点分段为单个点
云，单个点云的原始文本文件数据量为数百兆字节，某个应用中的点云集合即为点云工程，一个小型城镇的点云工程可能高达数十ＧＢ。本文采用自定义的文件结构组织大规模车载激光点云，目的是为了提高数据管理效率，其方法也可实现于商业数据库管理系统。
以自定义文件系统方式为例，点云工程是包含众多点云的目录，点云是单个二进制数据文件，图５是本文数据组织方法描述。每个点云包括头部分和实体部分，头部分包括点云的整体信息，如版本号、总数据量、Ｒ树扇出参数（子节点数目的最大最小值）、总点数、Ｒ树总层数、
空间范围、中心点坐标、压缩标志以及根节点地址等。点坐标是实际点坐标减去中心点坐标的差值，这样坐标可以采用较少有效位数表示，
有利于采用４字节单精度浮点类型表示点坐标，另外，如果空间范围在各坐标轴上的长度小于６５５．３５ｍ且精度要求在厘米级（车载激光扫描数据精度可达到厘米级），将坐标值乘以１００然后用２字节短整数类型表示点坐标，数据量减少７５％
。
图５ 点云工程数据组织方法
Ｆｉｇ．５ Ｄａｔａ ｏｒｇａｎｉｚａｔｉｏｎ ｍｅｔｈｏｄ ｏｆ ｐｏｉｎｔ ｃｌｏｕｄ ｐｒｏｊ
ｅｃｔ 点云的实体部分采用三维Ｒ树索引结构管
理点数据，Ｒ树索引结构包括根节点、中间节点和叶节点。本文的多细节层次生成方法中，上层节点从每个子节点中选取一个点作为低细节层次描
述，为避免重复存储和处理，选取点将从子节点移出至上层节点，这样中间节点和叶节点中的点数目要减１。为了实现缓存机制，即根据视域条件动态调度数据，父节点记录子节点的首地址，即子
００６
第４期龚 俊，等：一种八叉树和三维Ｒ树集成的激光点云数据管理方法节点相对文件起始位置的偏移量。Ｒ树存储结构可以分为按广度遍历存储顺序和按深度遍历存储顺序组织。广度遍历存储顺序指按节点层的次序存储节点数据，从根节点开始，将节点按层顺序依次记录到文件中，
负面影响是父节点和子节点无法集中存储；深度遍历存储顺序指从根节点开始，然后记录其各个子树，负面影响是中间层的兄弟节点无法集中存储。图６（ａ）和（ｂ）分别是广度遍历存储和深度遍历存储的原理
。
图６ 广度和深度遍历存储原理描述
Ｆｉｇ．６ Ｐｒｉｎｃｉｐａｌ ｄｅｓｃｒｉｐｔｉｏｎ ｏｆ ｂｒｅａｄｔｈ ａｎｄ ｄｅｐ