。右：對應的八叉樹]]
八叉树（）是一种树形数据结构，每个内部节点都正好有八个子节点。八叉树常用于分割三维空间，将其递归细分为八个卦限。八叉树是四叉树在三维空间中的对应，在三维图形、三维游戏引擎等领域有很多应用。
表示空间
八叉树的每个节点都可以代表一个空间，对应的八个子节点则将这个空间细分为八个卦限。点域（，简称PR）八叉树的节点中都存储着一个三维点，即该节点对应区域的「中心」，也是八个子节点对应区域中的一个角落。矩阵（，简称MX）八叉树中，节点只记录区域范围，对应的中心点坐标需要从区域范围推算。因此，PR八叉树的根节点可以表示无限大的空间；而MX八叉树的根节点只能表示有限空间，这样才可以得到隐含的中心点。
历史
八叉树在三维计算机图形领域的应用可以追溯到1980年伦斯勒理工学院唐纳德·马尔（）的报告《八叉树编码：使用计算机表示、操作、显示任意三维对象的新技术》（）。
主要用途
- 三维计算机图形学中的细节层次渲染
- 最邻近搜索
- 三维空间中的高效碰撞检测
*
- 状态估计
另见
*
- 体素
- 四叉树
- OGRE，有基于八叉树的场景管理器
- ，支持八叉树场景节点
参考资料
外部連結
*[https://web.archive.org/web/20140605161956/http://www.microsoft.com/msj/archive/S3F1.aspx Octree Quantization in Microsoft Systems Journal]
*[http://www.ddj.com/184409805 Color Quantization using Octrees in Dr. Dobb's]
*[https://web.cs.wpi.edu/~matt/courses/cs563/talks/color_quant/CQoctree.html Octree Color Quantization Overview]
*[http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=727419 Parallel implementation of octtree generation algorithm, P. Sojan Lal, A Unnikrishnan, K Poulose Jacob, ICIP 1997, IEEE Digital Library]
*[http://nomis80.org/code/octree.html C++ implementation (GPL license)]
*[http://sc07.supercomputing.org/schedule/pdf/pap117.pdf Parallel Octrees for Finite Element Applications]
*[http://www.sauerbraten.org/ Cube 2: Sauerbraten - a game written in the octree-heavy Cube 2 engine]
*[https://www.ogre3d.org Ogre - A 3d Object-oriented Graphics Rendering Engine with a Octree Scene Manager Implementation (MIT license)]
*[https://web.archive.org/web/20150129021620/http://www.cc.gatech.edu/csela/dendro/ Dendro: parallel multigrid for octree meshes (MPI/C++ implementation)]
*[http://www.youtube.com/watch?v=Jw4VAgcWruY Video: Use of an octree in state estimation]
评论 (0)