Face Clustering

Main Pages


Michael Garland

Many graphics applications, and interactive systems in particular, rely on hierarchical surface representations to efficiently process very complex models. Considerable attention has been focused on hierarchies of surface approximations and their construction via automatic surface simplification. Such representations have proven effective for adapting the level of detail used in real time 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.

The method described here is a new technique 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 approximations of varying complexity. This research is focused on the representation of these hierarchies, effective algorithms for their construction, and their use in creating efficient applications in areas such as radiosity and collision detection.

Our current clustering algorithm is in many ways the dual form of the QSlim quadrics simplification algorithm. It uses a dual form of the quadric error metric to guide a process of iterative contraction on the dual graph of the original mesh. Just as normal edge contraction induces a binary tree of vertex neighborhoods on the surface, dual edge contraction induces a binary tree of face clusters on the surface.


The details of our clustering algorithm are described in:

Hierarchical Face Clustering on Polygonal Surfaces,
by Michael Garland, Andrew Willmott, and Paul S. Heckbert, ACM Symposium on Interactive 3D Graphics, March 2001. [PDF]

This I3D paper summarizes the results of using face clustering in building a multiresolution radiosity system. Full details about the radiosity algorithm and its performance can be found in:

Face Cluster Radiosity,
by Andrew Willmott, Paul Heckbert, and Michael Garland, Eurographics Workshop on Rendering, June 1999. [details]

Much of the same information, along with the authoritative description of the related quadric simplification algorithm can be found in:

Quadric-Based Polygonal Surface Simplification, by Michael Garland, Ph.D. thesis, Tech. Rept. CMU-CS-99-105. [details]


We will be making our experimental implementation publicly available in the near future. This is the system whose performance is described in the I3D paper and which was used to generate the radiosity results in the Eurographics paper.

Currently, we plan to release the software in early 2001 as part of a new release of the QSlim simplification package.