views updated

octree A representation of space and solid objects used in computer graphics and spatial reasoning; it is a tree structure. The space around the origin point is divided up into eight octants. Each octant is marked occupied or free according to whether there is any object occupying that location in the environment to be represented. Each occupied octant is then divided again into eight subspaces and the process continues recursively until sufficient resolution has been achieved. The representation is efficient where large volumes of space are unoccupied, and the level of detail required is in proportion to the spatial complexity of the object structure. The two-dimensional version is called a quadtree.