结构

八叉树是对三维空间立方体体积进行递归分割的结构。从初始立方体出发，通过将立方体分割为8个等效子立方体形成八叉树单元 。默认情况下，八叉树细分会从云数据集的方形边界框开始构建，但也可基于任意空间立方体进行计算（例如优化距离计算等比较算法时）。

CloudCompare采用的八叉树结构（DgmOctree）严格来说并不能算作真正的“树”结构。其数据形式表现为数值列表（每个点对应一个数值），这些数值编码了该点在所有细分层级中的绝对位置，特别适合空间索引应用。当两个点位于同一细分层级的同一单元格内时，它们会关联相同的（部分）编码。此外，八叉树在内存中的占用空间始终保持恒定。该编码体系通过将3位二进制组合（0-7）进行串联来实现，每个子层级的单元相对位置都由这些组合编码。其中最高有效位对应第一级细分单元，最低有效位则对应最深层单元。经过排序处理的编码既能支持快速二分查找，又便于对云图进行空间扫描 （排序后的列表中相邻单元保持相邻）。

标准版CloudCompare的最大八叉树深度为10级。当前版本采用32位编码方式，每个点对应32位索引值（即八叉树权重每点128位=8字节→每百万点占用8 Mb内存）。用户可编译64位编码版本，支持最高21级细分（但内存消耗会增加50%）。