原理

简单示例：

假设我们有以下一组三维点云数据：

points = [
    [0.1, 0.1, 0.1],
    [0.4, 0.1, 0.1],
    [0.1, 0.4, 0.1],
    [0.4, 0.4, 0.1],
    [0.1, 0.1, 0.4],
    [0.4, 0.1, 0.4],
    [0.1, 0.4, 0.4],
    [0.4, 0.4, 0.4],
]

我们可以使用八叉树将这些点云数据存储在三维空间中。首先，我们创建一个八叉树根节点，它表示一个立方体区域，例如中心在原点 (0, 0, 0)，尺寸为 1 的立方体。然后，我们将点云数据逐个插入到八叉树中。

在插入过程中，根据每个点的位置，我们可以判断它属于哪个子空间。例如，在这个示例中，点 (0.1, 0.1, 0.1) 属于 x 轴正方向的子空间，而点 (0.4 0.1, 0.1) 也属于 x 轴正方向的子空间。我们将每个点插入到相应的子空间，并在需要时将子空间继续细分。当所有点都插入到八叉树中时，我们就完成了点云数据的空间划分。

通过这个简单的示例，我们可以看到八叉树如何将三维空间分层划分，并将点云数据存储在相应的子空间中。这种数据结构在计算机图形学、地理信息系统、机器人导航等领域有广泛应用，因为它可以将复杂的三维数据划分为较小的区域，从而降低搜索和处理的计算量。

intro

八叉树（Octree）是一种用于描述三维空间的树状数据结构。八叉树的每个节点表示一个正方体的体积元素，每个节点有八个子节点，这八个子节点所表示的体积元素加在一起就等于父节点的体积。一般中心点作为节点的分叉中心。八叉树若不为空树的话，树中任一节点的子节点恰好只会有八个，或零个，也就是子节点不会有0与8以外的数目。

　　八叉树叶子节点代表了分辨率最高的情况。例如分辨率设成0.01m，那么每个叶子就是一个1cm见方的小方块。

那么，这要用来做什么？想象一个立方体，我们最少可以切成多少个相同等分的小立方体？答案就是8个。再想象我们有一个房间，房间里某个角落藏着一枚金币，我们想很快的把金币找出来，聪明的你会怎么做？我们可以把房间当成一个立方体，先切成八个小立方体，然后排除掉没有放任何东西的小立方体，再把有可能藏金币的小立方体继续切八等份….如此下去，平均在Log8(房间内的所有物品数)的时间内就可找到金币。因此，Octree就是用在3D空间中的场景管理，可以很快地知道物体在3D场景中的位置，或侦测与其它物体是否有碰撞以及是否在可视范围内。

2、实现Octree的原理

(1). 设定最大递归深度

(2). 找出场景的最大尺寸，并以此尺寸建立第一个立方体

(3). 依序将单位元元素丢入能被包含且没有子节点的立方体

(4). 若没有达到最大递归深度，就进行细分八等份，再将该立方体所装的单位元元素全部分担给八个子立方体

(5). 若发现子立方体所分配到的单位元元素数量不为零且跟父立方体是一样的，则该子立方体停止细分，因为跟据空间分割理论，细分的空间所得到的分配必定较少，若是一样数目，则再怎么切数目还是一样，会造成无穷切割的情形。

(6). 重复3，直到达到最大递归深度。