Empty regions of the space are represented by the voxel type "void." Aswith a quadtree representation, a heterogeneous octant in the region is subdivideduntil the subdivisions are homogeneous. For an octree, each node can have fromzero to eight immediate descendants.
Algorithms for generating octrees can be structured to accept definitions ofobjects in any form, such as a polygon mesh, curved surface patches, or solid-geometry constructions. For a single object, the octree can be constructed fromthe enclosing box (parallelepiped) determined by the coordinate extents of theobject.
Once an octree representation has been established for a solid object, variousmanipulation routines can be applied to the object. An algorithm for performingset operations can be applied to two octree representations for the same region ofspace. For a union operation, a new octree is constructed using the octree nodesfrom each of the input trees. To set up an intersection representation for two inputoctrees, we construct the new tree using the octants where the two objects overlap.Similarly, for a difference operation, we look for regions occupied by one objectand not the other.
A number of other octree-processing algorithms have been developed. Three-dimensional rotations, for instance, are accomplished by applying the transforma-tions to spatial regions represented by the occupied octants. To locate the visibleobjects in a scene, we can first determine whether any front octants are occupied.If not, we proceed to the octants behind the front octants. This process contin-ues until the occupied octants are located along the viewing direction. The firstobject detected along any viewing path through the spatial octants, front to back,is visible, and the information for that object can be transferred to a quadtreerepresentation for display.