Quadric-Based Polygonal Surface Simplification
May 9, 1999
Copyright © 1999 Michael Garland
This page contains a short synopsis of the contents of my Ph.D. thesis.
The complete text is available in the following formats:
PDF (10 MB) for print output
PDF (2.5 MB)
with images downsampled and JPEG-encoded for on-screen viewing
PostScript (110 MB)
I strongly recommend downloading the PDF version of my thesis. The
final image quality should be identical to the PostScript version, at
one tenth the size.
I have made my experimental implementation of the
algorithms described in this dissertation publicly available. I also
have a collection of sample data and related papers
that you might find useful.
Many applications in computer graphics and related fields can benefit
from automatic simplification of complex polygonal surface models.
Applications are often confronted with either very densely
over-sampled surfaces or models too complex for the limited available
hardware capacity. An effective algorithm for rapidly producing
high-quality approximations of the original model is a valuable tool
for managing data complexity.
In this dissertation, I 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 face approximation
of a 100,000 face model can be produced in about 10 seconds on a
PentiumPro 200. The algorithm can simplify both the geometry and
topology of manifold as well as non-manifold surfaces. In addition to
producing single approximations, my algorithm can also be used to
generate multiresolution representations such as progressive meshes
and vertex hierarchies for view-dependent refinement.
The foundation of my simplification algorithm, is the quadric error
metric which I have developed. It provides a useful and economical
characterization of local surface shape, and I have proven a direct
mathematical connection between the quadric metric and surface
curvature. A generalized form of this metric can accommodate surfaces
with material properties, such as RGB color or texture coordinates.
I have also developed a closely related technique for constructing
a hierarchy of well-defined surface regions composed of disjoint sets
of faces. This algorithm involves applying a dual form of my
simplification algorithm to the dual graph of the input surface. The
resulting structure is a hierarchy of face clusters which is an
effective multiresolution representation for applications such as
The following is a high-level overview of the content of my dissertation:
- Chapter 1: Introduction.
- Chapter 2: Background & Related Work. In this
chapter, I provide a detailed discussion of surface
simplification and a review of the prior work in the field.
- Chapter 3: Basic Simplification Algorithm.
This chapter introduces the core material of the dissertation. It
contains a description of the quadric error metric and the
simplification algorithm which I have built around it.
- Chapter 4: Analysis of Quadric Metric.
The quadric error metric is the central component of my
simplification algorithm, and this chapter is devoted to analyzing
its behavior. For example, the quadric metric
has an interesting geometric interpretation; in
particular, the isosurfaces of the error function are (possibly
degenerate) ellipsoids. In this chapter, I discuss this
interpretation and also demonstrate a mathematical relationship
between the eigenvalues of the quadric metric and the principal
curvatures of the surface.
- Chapter 5: Extended Simplification Algorithm.
The algorithm described in Chapter 3 considers surface geometry
exclusively. In this chapter, I discuss the extension of the
quadric error metric to surfaces with material properties (e.g., color
- Chapter 6: Results & Performance Analysis. This
chapter illustrates the results of my algorithm. The emphasis is on
empirical performance, although I also present some theoretical
analysis of the complexity of the algorithm.
- Chapter 7: Applications.
In this chapter, I examine some of the applications of my
simplification algorithm. In particular, I review the progressive
mesh and vertex hierarchy structures developed by others. I also
describe the close connection between simplification and minimum
spanning tree algorithms.
- Chapter 8: Hierarchical Face Clustering. This chapter
outlines my hierarchical face clustering algorithm. I perform
hierarchical clustering by applying what is essentially the dual of
my simplification algorithm to the dual graph of the surface.
The resulting structure can be quite useful in hierarchical
computations for applications such as radiosity and collision
- Chapter 9: Conclusion. This chapter summarizes the
content of all the previous chapters. I also discuss some of the
more interesting directions for future work.
- Appendix A: Implementation Notes. To
highlight certain design choices and techniques, I have included
Appendix A, which contains details on my implementation of the
simplification algorithm described in Chapter 3.