Many applications in computer graphics and related fields can benefit fromautomatic simplification of complex polygonal surface models. Applications areoften confronted with either very densely over-sampled surfaces or models toocomplex for the limited available hardware capacity. An effective algorithmfor rapidly producing high-quality approximations of the original model is avaluable tool for managing data complexity.
In this dissertation, I present my simplification algorithm, based on iterativevertex pair contraction. This technique provides an effective compromisebetween the fastest algorithms, which often produce poor quality results, andthe highest-quality algorithms, which are generally very slow. For example, a1000 face approximation of a 100,000 face model can be produced in about 10seconds on a PentiumPro 200. The algorithm can simplify both the geometryand topology of manifold as well as non-manifold surfaces. In addition toproducing single approximations, my algorithm can also be used to generatemultiresolution representations such as progressive meshes and vertex hierarchiesfor view-dependent refinement.
The foundation of my simplification algorithm, is the quadric error metricwhich I have developed. It provides a useful and economical characterization oflocal surface shape, and I have proven a direct mathematical connection betweenthe quadric metric and surface curvature. A generalized form of this metric canaccommodate surfaces with material properties, such as RGB color or texturecoordinates.
I have also developed a closely related technique for constructing a hierarchyof well-defined surface regions composed of disjoint sets of faces. This algorithminvolves applying a dual form of my simplification algorithm to the dual graphof the input surface. The resulting structure is a hierarchy of face clusters whichis an effective multiresolution representation for applications such as radiosity.
| Identifer | oai:union.ndltd.org:cmu.edu/oai:repository.cmu.edu:dissertations-1282 |
| Date | 09 May 1999 |
| Creators | Garland, Michael |
| Publisher | Research Showcase @ CMU |
| Source Sets | Carnegie Mellon University |
| Detected Language | English |
| Type | text |
| Format | application/pdf |
| Source | Dissertations |
Page generated in 0.0018 seconds