八叉树
八叉树（英語：）是一种树形数据结构，每个内部节点都正好有八个子节点。八叉树常用于分割三维空间，将其递归细分为八个卦限。八叉树是四叉树在三维空间中的对应，在三维图形、三维游戏引擎等领域有很多应用。
| 八叉树 | |||||
|---|---|---|---|---|---|
| 类型 | 樹 | ||||
| 发明时间 | 1980年 | ||||
| 发明者 | 唐納德·米格爾 | ||||
| 用大O符号表示的时间复杂度 | |||||
| |||||
左：遞迴子切分一個立方體為多個卦限。右：對應的八叉樹
表示空间
八叉树的每个节点都可以代表一个空间，对应的八个子节点则将这个空间细分为八个卦限。点域（，简称PR）八叉树的节点中都存储着一个三维点，即该节点对应区域的「中心」，也是八个子节点对应区域中的一个角落。矩阵（，简称MX）八叉树中，节点只记录区域范围，对应的中心点坐标需要从区域范围推算。因此，PR八叉树的根节点可以表示无限大的空间；而MX八叉树的根节点只能表示有限空间，这样才可以得到隐含的中心点。
参考资料
- Meagher, Donald. . Rensselaer Polytechnic Institute. October 1980, (Technical Report IPL-TR-80-111).
- David P. Luebke. . Morgan Kaufmann. 2003. ISBN 978-1-55860-838-2.
- (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（页面存档备份，存于）
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.