Face octrees: involved algorithms and applications

Volume models can be effectively represented by means of octree structures, that recursively subdivide the space into cubic octants. Classical octrees are well suited for objects with very complex surfaces whereas other schemes, such as extended octrees, are well adapted for the representation of polyhedra. The present paper introduces face octrees as an scheme for the representation of solids limited by smooth free form surfaces. The representation is discrete and approximated, through a tolerance specified by the user. Anyway, an exact canonic surface can be derived from the face octree representation. The spatial complexity of the model as a function of the geometric properties of the surface is discussed, together with its ability for the interrogation and realization of boolean operations