Quadric-Based Polygonal Surface Simplification
May 9, 1999
Copyright © 1999 Michael Garland
The full text of my thesis is available in the following formats:
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.
You may also be interested in the following items:
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
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
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
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
Overview of Material
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.
Last modified: Thu May 27 18:16:33 EDT 1999