01
基本逻辑
用八叉树来表示三维形体，并研究这种表示下的各种操作以及应用，是进入80年代后开展起来的一种方法。这种方法，既可以看成是四叉树方法在三维空间的推广，也可以认为是三维体素阵列表示形体方法的一种改进。假设要表示的形体V可以放在一个充分大的正方体C中，C的边长为2n。
??八叉树的每一个节点与C的一个子立方体对应，树根与C本身相对应。如果V=C，那么V的八叉树只有树根。如果V不等于C，则将C等分为8个子立方体，每个子立方体与树根的一个子节点相对应。只要某个子立方体不是完全空白，或者完全为V所占据，就要被八等分，从而对应的节点也就有了八个子节点。这样的递归判断，分割一直要进行到节点所对应的立方体完全为空，或是完全为V所占据，或是其大小已经是预先定义的体素大小，并且对他与V之交作一定的“舍入”，使体素或认为是空白的，或认为是V占据的。
八叉树空间结构
02
CloudCompare中的八叉树
CloudCompare中使用的DgmOctree作为八叉树数据结构，具体实现过程如下：
八叉树将空间分割成八块，根据2进制，3位2进制即可表示8个数字，3位中的顺序:zyx顺序区分，从小递增到大，如：，即z为0，x为1，y为1的块位置。所以64位操作系统最多可分割为64/3=21级，32位操作系统最多可分割为32/3=10级。1、建立单维索引（CellCode）
将原有的1位2进制转为3位，如：(1)转为000000，(2)转为000000，以此类推。另外两个维度的code分别左移1位和2位即可。软件初始化时就计算完了所有CellCode。
//we
