Abstract: Many graphics applications,and interactive systems in particular, rely on hierarchical surface represenations to efficiently process very complex models. Considerable attention has been focused on hierarchies of surface approximations and their construction via automatic surface simplification. Such represenations have proven effective for adapting the level of detail used in real tie display systems. However, other applications such as ray tracing, collision detection,and radiosity benefit from an alternative multiresolution framework: hierarchical partitions of the original surface geometry.

We present a new method for representing a hierarchy of regions on a polygonal surface which partition that surface into a set of face clusters. These clusters, which are connected sets of faces, represent the aggregate properties of the original surface at different scales rather than providing geometric approxmations of varying complexity. We also describe the combination of an effective error metric and a novel algorithm for constructing these hierarchies.