Quadric-Based Polygonal Surface Simplification

Abstract

Many applications in computer graphics and related fields can benefit from<br>automatic simplification of complex polygonal surface models. Applications are<br>often confronted with either very densely over-sampled surfaces or models too<br>complex for the limited available hardware capacity. An effective algorithm<br>for rapidly producing high-quality approximations of the original model is a<br>valuable tool for managing data complexity. <br>In this dissertation, I present my simplification algorithm, based on iterative<br>vertex pair contraction. This technique provides an effective compromise<br>between the fastest algorithms, which often produce poor quality results, and<br>the highest-quality algorithms, which are generally very slow. For example, a<br>1000 face approximation of a 100,000 face model can be produced in about 10<br>seconds on a PentiumPro 200. The algorithm can simplify both the geometry<br>and topology of manifold as well as non-manifold surfaces. In addition to<br>producing single approximations, my algorithm can also be used to generate<br>multiresolution representations such as progressive meshes and vertex hierarchies<br>for view-dependent refinement. <br>The foundation of my simplification algorithm, is the quadric error metric<br>which I have developed. It provides a useful and economical characterization of<br>local surface shape, and I have proven a direct mathematical connection between<br>the quadric metric and surface curvature. A generalized form of this metric can<br>accommodate surfaces with material properties, such as RGB color or texture<br>coordinates. <br>I have also developed a closely related technique for constructing a hierarchy<br>of well-defined surface regions composed of disjoint sets of faces. This algorithm<br>involves applying a dual form of my simplification algorithm to the dual graph<br>of the input surface. The resulting structure is a hierarchy of face clusters which<br>is an effective multiresolution representation for applications such as radiosity.