Octree
Encyclopedia : O : OC : OCT : Octree
An octree is a tree data structure in which each internal node has up to eight children. Octrees are most often used to partition a three dimensional space by recursively subdividing it into eight octants.
Some common uses of octrees are:
- Spatial indexing
- Efficient collision detection in three dimensions
- View frustum culling
Each node in an octree subdivides the space it represents into eight subspaces (octants). In a point region (PR) octree, the node stores an explicit 3-dimensional point, which is the "center" of the subdivision for that node; the point defines one of the corners for each of the eight children. In an MX octree, the subdivision point is implicitly the center of the space the node represents. The root node of a PR quadtree can represent infinite space; the root node of an MX octree must represent a finite bounded space so that the implicit centers are well-defined.
From Wikipedia, the Free Encyclopedia. Original article here. Support Wikipedia by contributing or donating.
All text is available under the terms of the GNU Free Documentation License See Wikipedia Copyrights for details.