八叉树（Octree）是一种树形数据结构，每个内部节点都正好有八个子节点。它用于分割三维空间，将其递归细分为八个卦限，是四叉树在三维空间中的对应。八叉树在3D软件、三维游戏引擎等领域有广泛应用，如场景管理、碰撞检测和可视范围判断等。通过八叉树，可以在Log8(房间内的所有物品数)的时间内快速定位物体位置。

八叉树是一种用于描述三维空间的树状数据结构。八叉树的每个节点表示一个立方体的体积元素，每个节点有八个子节点，将八个子节点所表示的体积元素加在一起就等于父节点的体积。八叉树的节点可以代表一个空间，对应的八个子节点则将这个空间细分为八个卦限。

八叉树的概念最早可以追溯到1980年，由伦斯勒理工学院的唐纳德·马尔（Donald Meagher）在其报告《八叉树编码：使用计算机表示、操作、显示任意三维对象的新技术》（Octree Encoding: A New Technique for the 表征, Manipulation and Display of Arbitrary 3-D Objects by 计算机）中提出。

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

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

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

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

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

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

八叉树的存储结构用一个有（若干+八）个字段的记录来表示树中的每个结点。其中若干字段用来描述该结点的特性(本例中的特性为：节点的值和节点坐标)，其余的八个字段用来作为存放指向其八个子结点的指针。此外，还有线性存储和1托8式存储。

a) BSP树将场景分割为1个面，而八叉树分割为3个面。

b) BSP树每个节点最多有2个子结点，而八叉树最多有8个子结点

因此BSP树可以用在任意维度的场景中，而八叉树则常用于三维空间场。

八叉树的节点可以按照不同的方式来表示空间。点域（小数点 region，简称PR）八叉树的节点中都存储着一个三维点，即该节点对应区域的“中心”，也是八个子节点对应区域中的一个角落。矩阵（matrix based，简称MX）八叉树中，节点只记录区域范围，对应的中心点坐标需要从区域范围推算。PR八叉树的根节点可以表示无限大的空间；而MX八叉树的根节点只能表示有限空间，这样才可以得到隐含的中心点。

八叉树在三维计算机图形学中有多种用途，包括但不限于：

- 细节层次渲染（LOD，Level of Detail）：在三维场景中根据视点和重要性来动态调整对象的细节层次。

- 最邻近搜索：在三维空间中快速找到最接近某个点的其他点。

- 高效碰撞检测：在三维空间中快速判断物体是否发生碰撞。

- 稀疏体素八叉树：用于存储和处理稀疏数据集，如体素化的三维模型。

- 状态估计：在机器人学和自动化领域，用于估计物体的状态或位置。