## 8.7. Octrees

An octree is the natural progression from a quadtree for the
representation of 3-D space. Rather than an area being divided
into four, octrees divide a 3-D object space into eight smaller
cubes known as cells. If any one of the resulting cells is
homogeneous, that is the cell lies entirely inside or outside the
object, the sub-division stops. If, on the other hand, the cell
is heterogeneous, that is intersected by one or more of the
object's bounding surfaces, the cell is sub-divided further into
eight sub-cells. The sub-division process halts when all the leaf
cells are homogeneous to some degree of accuracy (Carlbom and others 1985).

According to Samet (1990) the region octree is the simplest variant of
the octree data structure. It also has the same drawbacks as the
region quadtree inthe sense it is only an approximation of an
image. The octree is also costly to compute because of the
amount of data that must be examined.

Octrees have the same structure as a quadtree except that
every parent node has eight children instead of the four used
with octrees. Because of the eight children octrees are very
useful in storing information about three-dimensional space. As
you can see in the example the octree has exactly the same
structure as a quadtree.

Fig. 8.7 : 3-D image, its octree block composition and tree representation(Samet 1990)