An enhanced octree structure for representing the spatial/boundary decomposition of 3-D objects

The paper describes an enhanced octree in which both the volume and the surface boundary of a 3D object are represented in the same data structure. An enhanced octree includes those octants right beneath the boundary surface of an object. The fully exposed faces of an octant will be associated with the boundary surface patches nearest to the them. For those exposed faces partially covered by smaller octants, quadtree decomposition will be performed and the exposed quadrants will be associated with the surface patches in the same way as the fully exposed faces. In this manner, an enhanced octree facilitates the modelling of a 3D object by providing both the volumetric and the surface properties in a single hierarchical structure.