八叉树
外观
![本页使用了标题或全文手工转换](http://upload.wikimedia.org/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
八叉树 | |||||
---|---|---|---|---|---|
类型 | 树 | ||||
发明时间 | 1980年 | ||||
发明者 | 唐纳德·米格尔 | ||||
用大O符号表示的时间复杂度 | |||||
|
![](http://upload.wikimedia.org/wikipedia/commons/thumb/3/35/Octree2.png/400px-Octree2.png)
八叉树(英语: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]。
主要用途
[编辑]另见
[编辑]- 线性八叉树
- 体素
- 四叉树
- OGRE,有基于八叉树的场景管理器
- Irrlicht引擎,支持八叉树场景节点
参考资料
[编辑]- ^ 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).
外部链接
[编辑]- 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(页面存档备份,存于互联网档案馆)
|