Octree

From Free net encyclopedia

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

Octrees are the three-dimensional analog of quadtrees. The name is formed from oct + tree, and normally written octree not octtree.

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.

Template:Compu-sci-stubde:Octree nl:Octree pl:Drzewo ósemkowe zh:八叉树