定义
八叉树（octree）是一种树形数据结构，每个内部节点都正好有八个子节点。八叉树常用于分割三维空间，将其递归细分为八个卦限。八叉树是四叉树在三维空间中的对应，在三维图形、三维游戏引擎等领域有很多应用。
图1 左：递归地将原始的空间切割成子空间；右：对应的八叉树
八叉树结构是由 Hunter 博士于1978年首次提出的一种数据模型。八叉树结构通过对三维空间的几何实体进行体元剖分，每个体元具有相同的时间和空间复杂度，通过循环递归的划分方法对大小为( 2 n × 2 n × 2 n ) 的三维空间的几何对象进行剖分，从而构成一个具有根节点的方向图。在八叉树结构中如果被划分的体元具有相同的属性，则该体元构成一个叶节点；否则继续对该体元剖分成8个子立方体，依次递剖分，对于( 2 n × 2 n × 2 n ) 大小的空间对象，最多剖分n次，如图1所示[1] 。
参考文献
[1] http://zengzeyu.com/2018/03/30/18_3_30/pcl_kdtree_and_octree/
