Quadric-Based Polygonal Surface Simplification
             ===============================================

                           Michael Garland
                       Carnegie-Mellon University

                       2:00 -- 3:00pm February 22
                           CS Seminar Room


Many applications in computer graphics and related fields can benefit
from automatic simplification of complex polygonal surface models.
For example, surface reconstruction algorithms often produce very
densely over-sampled meshes.  Due to limited hardware capacity,
systems such as flight simulators, computer games, and distributed
virtual environments must often maintain strict control over the level
of detail used in surface models.  In all these applications,
automatic surface simplification is a valuable tool for managing data
complexity.

In this talk, I will present my simplification algorithm, based on
iterative vertex pair contraction.  This technique provides an
effective compromise between the fastest algorithms, which often
produce poor quality results, and the highest-quality algorithms,
which are generally very slow.  For example, a 1000 triangle
approximation of a model containing 100,000 triangles can be produced
in about 10 seconds on a PentiumPro 200.  Both manifold and
non-manifold surfaces are supported, and the topology of the model can
be simplified as well.

The foundation of my simplification algorithm, is a quadric error
metric which provides a useful and economical characterization of
local surface shape.  A generalized form of this metric can
accommodate surfaces with material properties, such as RGB color or
texture coordinates.  I have also proven a direct mathematical
connection between the quadric error metric and surface curvature.

In addition to producing single approximations, my algorithm may be
used to generate multiresolution representations such as progressive
meshes and vertex hierarchies for view-dependent refinement.  I have
also developed a dual version of the algorithm which can produce a
hierarchy of surface regions that is an effective multiresolution
representation for other applications such as radiosity.

More details, the relevant papers, and my experimental software can be
found at <http://www.cs.cmu.edu/~garland/quadrics/>.
accommodate surfaces with material properties, such as RGB color or
texture coordinates.  I have also proven a direct mathematical
connection between the quadric error metric and surface curvature.

In addition to producing single approximations, my algorithm may be
used to generate multiresolution representations such as progressive
meshes and vertex hierarchies for view-dependent refinement.  I have
also developed a dual version of the algorithm which can produce a
hierarchy of surface regions that is an effective multiresolution
representation for other applications such as radiosity.

More details, the relevant papers, and my experimental software can be
found at <http://www.cs.cmu.edu/~garland/quadrics/>.