八叉树

八叉树
类型	樹
发明时间	1980年
发明者	唐納德·米格爾
用大O符号表示的时间复杂度

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

表示空间

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

历史

八叉树在三维计算机图形领域的应用可以追溯到1980年伦斯勒理工学院唐纳德·马尔（Donald Meagher）的报告《八叉树编码：使用计算机表示、操作、显示任意三维对象的新技术》（Octree Encoding: A New Technique for the Representation, Manipulation and Display of Arbitrary 3-D Objects by Computer）^[1]。

主要用途

另见

线性八叉树（英语：Linear octree）
体素
四叉树
OGRE，有基于八叉树的场景管理器
Irrlicht引擎（英语：Irrlicht Engine），支持八叉树场景节点

参考资料

^ Meagher, Donald. Octree Encoding: A New Technique for the Representation, Manipulation and Display of Arbitrary 3-D Objects by Computer. Rensselaer Polytechnic Institute. October 1980, (Technical Report IPL-TR-80-111).
^ David P. Luebke. Level of Detail for 3D Graphics. Morgan Kaufmann. 2003. ISBN 978-1-55860-838-2.
^ Henning Eberhardt, Vesa Klumpp, Uwe D. Hanebeck, Density Trees for Efficient Nonlinear State Estimation, Proceedings of the 13th International Conference on Information Fusion, Edinburgh, United Kingdom, July, 2010. (PDF). [2018-07-03]. （原始内容存档 (PDF)于2016-03-03）.

外部連結

[1] Meagher, Donald. Octree Encoding: A New Technique for the Representation, Manipulation and Display of Arbitrary 3-D Objects by Computer. Rensselaer Polytechnic Institute. October 1980, (Technical Report IPL-TR-80-111).

[Luebke2003-2] David P. Luebke. Level of Detail for 3D Graphics. Morgan Kaufmann. 2003. ISBN 978-1-55860-838-2.

[3] Henning Eberhardt, Vesa Klumpp, Uwe D. Hanebeck, Density Trees for Efficient Nonlinear State Estimation, Proceedings of the 13th International Conference on Information Fusion, Edinburgh, United Kingdom, July, 2010. (PDF). [2018-07-03]. （原始内容存档 (PDF)于2016-03-03）.

[1]

[2]

[3]