八叉树

八叉树（）是一种树形数据结构，每个内部节点都正好有八个子节点。八叉树常用于分割三维空间，将其递归细分为八个卦限。八叉树是四叉树在三维空间中的对应，在三维图形、三维游戏引擎等领域有很多应用。

 表示空间 

八叉树的每个节点都可以代表一个空间，对应的八个子节点则将这个空间细分为八个卦限。点域（，简称PR）八叉树的节点中都存储着一个三维点，即该节点对应区域的「中心」，也是八个子节点对应区域中的一个角落。矩阵（，简称MX）八叉树中，节点只记录区域范围，对应的中心点坐标需要从区域范围推算。因此，PR八叉树的根节点可以表示无限大的空间；而MX八叉树的根节点只能表示有限空间，这样才可以得到隐含的中心点。

 历史 

八叉树在三维计算机图形领域的应用可以追溯到1980年伦斯勒理工学院唐纳德·马尔（）的报告《八叉树编码：使用计算机表示、操作、显示任意三维对象的新技术》（）。

 主要用途 

 三维计算机图形学中的细节层次渲染
 最邻近搜索
 三维空间中的高效碰撞检测

 状态估计

 另见 

 体素
 四叉树
 OGRE，有基于八叉树的场景管理器
 ，支持八叉树场景节点

 参考资料 

外部連結

Octree Quantization in Microsoft Systems Journal
Color Quantization using Octrees in Dr. Dobb's
Octree Color Quantization Overview
Parallel implementation of octtree generation algorithm, P. Sojan Lal, A Unnikrishnan, K Poulose Jacob, ICIP 1997, IEEE Digital Library
C++ implementation (GPL license)
Parallel Octrees for Finite Element Applications
Cube 2: Sauerbraten - a game written in the octree-heavy Cube 2 engine
Ogre - A 3d Object-oriented Graphics Rendering Engine with a Octree Scene Manager Implementation (MIT license)
Dendro: parallel multigrid for octree meshes (MPI/C++ implementation)
Video: Use of an octree in state estimation

B