八叉树

八叉树（Octree）是一种用于描述三维空间的树状数据结构。八叉树的每个节点表示一个正方体的体积元素，每个节点有八个子节点，这八个子节点所表示的体积元素加在一起就等于父节点的体积。一般中心点作为节点的分叉中心。八叉树是四叉树在三维空间上的扩展，二维上我们有四个象限，而三维上，我们有 8 个卦限。八叉树主要用于空间划分和最近邻搜索。

八叉树的构建过程如下：

① 设定最大递归深度； ② 找出场景的最大尺寸，并以此尺寸建立第一个立方体； ③ 依序将单位元元素丢入能被包含且没有子节点的立方体； ④ 若未达到最大递归深度，就进行细分八等份，再将该立方体所装的单位元元素全部分担给八个子立方体； ⑤ 若发现子立方体所分配到的单位元元素数量不为零且跟父立方体是一样的，则该子立方体停止细分，因为跟据空间分割理论，细分的空间所得到的分配必定较少，若是一样数目，则再怎么切数目还是一样，会造成无穷切割的情形； ⑥ 重复 ③，直到达到最大递归深度；

八叉树算法的算法实现简单，但大数据量点云数据下，其使用比较困难的是最小粒度（叶节点）的确定，粒度较大时，有的节点数据量可能仍比较大，后续查询效率仍比较低，反之，粒度较小，八叉树的深度增加，需要的内存空间也比较大（每个非叶子节点需要八个指针），效率也降低。而等分的划分依据，使得在数据重心有偏斜的情况下，受划分深度限制，其效率不是太高。k-d 在邻域查找上比较有优势，但在大数据量的情况下，若划分粒度较小时，建树的开销也较大，但比八叉树灵活些。在小数据量的情况下，其搜索效率比较高，但在数据量增大的情况下，其效率会有一定的下降，一般是线性上升的规律。

也有将八叉树和 k-d 树结合起来的应用，应用八叉树进行大粒度的划分和查找，而后使用 k-d 树进行细分，效率会有一定的提升，但其搜索效率变化也与数据量的变化有一个线性关系。

八叉树三维数据结构

用八叉树来表示三维形体，既可以看成是四叉树方法在三维空间的推广，也可以认为是用三维体素阵列表示形体方法的一种改进。八叉树的逻辑结构如下：假设要表示的形体 V 可以放在一个充分大的正方体 C 内，C 的边长为 2n(偶数)，形体 V=C，它的八叉树可以用以下的递归方法来定义：

八叉树的每个节点与 C 的一个子立方体对应，树根与 C 本身相对应，如果 V ＝ C，那么 V 的八叉树仅有树根，如果 V≠C，则将 C 等分为八个子立方体，每个子立方体与树根的一个子节点相对应。只要某个子立方体不是完全空白或完全为 V 所占据，就要被八等分（图 2-5-1），从而对应的节点也就有了八个子节点。这样的递归判断、分割一直要进行到节点所对应的立方体或是完全空白，或是完全为 V 占据，或是其大小已是预先定义的体素大小，并且对它与 V 之交作一定的“舍入”，使体素或认为是空白的，或认为是 V 占据的。

如此所生成的八叉树上的节点可分为三类：

• 灰节点，它对应的立方体部分地为 V 所占据；
• 白节点，它所对应的立方体中无 V 的内容；
• 黑节点，它所对应的立方体全为 V 所占据。

后两类又称为叶结点。形体 V 关于 C 的八叉树的逻辑结构是这样的：它是一颗树，其上的节点要么是叶节点，要么就是有八个子节点的灰节点。根节点与 C 相对应，其它节点与 C 的某个子立方体相对应。因为八叉树的结构与四叉树的结构是如此的相似，所以八叉树的存贮结构方式可以完全沿用四叉树的有关方法。因而，根据不同的存贮方式，八叉树也可以分别称为常规的、线性的、一对八的八叉树等等。

另外，由于这种方法充分利用了形体在空上的相关性，因此，一般来说，它所占用的存贮空间要比三维体素阵列的少。但是实际上它还是使用了相当多的存贮，这并不是八叉树的主要优点。这一方法的主要优点在于可以非常方便地实现有广泛用途的集合运算(例如可以求两个物体的并、交、差等运算)，而这些恰是其它表示方法比较难以处理或者需要耗费许多计算资源的地方。不仅如此，由于这种方法的有序性及分层性，因而对显示精度和速度的平衡、隐线和隐面的消除等，带来了很大的方便，特别有用。

八叉树的存贮结构

八叉树有三种不同的存贮结构，分别是规则方式、线性方式以及一对八方式。相应的八叉树也分别称为规则八叉树、线性八叉树以及一对八式八叉树。不同的存贮结构的空间利用率及运算操作的方便性是不同的。分析表明，一对八式八叉树优点更多一些。

规则八叉树

规则八叉树的存贮结构用一个有九个字段的记录来表示树中的每个结点。其中一个字段用来描述该结点的特性(在目前假定下，只要描述它是灰、白、黑三类结点中哪一类即可)，其余的八个字段用来作为存放指向其八个子结点的指针。这是最普遍使用的表示树形数据的存贮结构方式。

规则八叉树缺陷较多，最大的问题是指针占用了大量的空间。假定每个指针要用两个字节表示，而结点的描述用一个字节，那么存放指针要占总的存贮量的 94％。因此，这种方法虽然十分自然，容易掌握，但在存贮空间的使用率方面不很理想。

线性八叉树

线性八叉树注重考虑如何提高空间利用率。用某一预先确定的次序遍历八叉树(例如以深度优先的方式)，将八叉树转换成一个线性表（图 2-5-2），表的每个元素与一个结点相对应。对于结点的描述可以丰富一点，例如用适当的方式来说明它是否为叶结点，如果不是叶结点时还可用其八个子结点值的平均值作为非叶结点的值等等。这样，可以在内存中以紧凑的方式来表示线性表，可以不用指针或者仅用一个指针表示即可。

一对八式的八叉树

一个非叶结点有八个子结点，为了确定起见，将它们分别标记为 0，1，2，3，4，5，6，7。从上面的介绍可以看到，如果一个记录与一个结点相对应，那么在这个记录中描述的是这个结点的八个子结点的特性值。而指针给出的则是该八个子结点所对应记录的存放处，而且还隐含地假定了这些子结点记录存放的次序。也就是说，即使某个记录是不必要的(例如，该结点已是叶结点)，那么相应的存贮位置也必须空闲在那里（图 2-5-3），以保证不会错误地存取到其它同辈结点的记录。这样当然会有一定的浪费，除非它是完全的八叉树，即所有的叶结点均在同一层次出现，而在该层次之上的所有层中的结点均为非叶结点。

为了克服这种缺陷，有两条途径可以采纳。一是增加计算量，在记录中增加一定的信息，使计算工作适当减少或者更方便。