Quadric Error Metrics

Numerous applications in computer graphics and related fields rely on polygonal surface models for both simulation and display. Traditionally, such models have been fixed sets of polygons, providing a single level of detail. However, this single level of detail may often be ill-suited for the diverse contexts in which a model of this type will be used. The central focus of this work is the automatic simplification of highly detailed polygonal surface models into faithful approximations containing fewer polygons.

Quadric error metrics provide a useful characterization of local surface shape, and they have modest computational and storage requirements. Combining quadric error metrics with iterative vertex pair contraction results in a fast algorithm for producing high-quality approximations of polygonal surfaces. This algorithm can simplify both manifold and non-manifold models. It is also capable of joining unconnected regions of the model together, thus ultimately simplifying the surface topology by aggregating separate components. In addition to producing single approximations, the algorithm can also be used to generate multiresolution representations such as progressive meshes and vertex hierarchies for view-dependent refinement.

Papers

The basic details of the quadric-based simplification algorithm were first published in the paper:

Surface Simplification Using Quadric Error Metrics,
by Michael Garland and Paul Heckbert, SIGGRAPH 97. [PDF] [PS] [slides]

This basic algorithm was later generalized to handle surfaces with material properties (e.g., color and texture). This later paper also contains an improved discussion of the original algorithm.

Simplifying Surfaces with Color and Texture using Quadric Error Metrics,
by Michael Garland and Paul Heckbert, IEEE Visualization 98. [PDF] [PS] [slides]

My Ph.D. thesis contains the most authoritative description of the simplification algorithm. It also contains the most extensive analysis of the algorithm’s behavior.

Quadric-Based Polygonal Surface Simplification, by Michael Garland, Ph.D. thesis, Tech. Rept. CMU-CS-99-105. [details]

While analyzing the properties of the quadric error metric, we discovered that (under suitable assumptions) minimizing the quadric error will (in the limit) produce triangles of optimal aspect ratio. The details can be found in our paper:

Optimal Triangulation and Quadric-Based Surface Simplification, by Paul Heckbert and Michael Garland, Journal of Computational Geometry: Theory and Applications, vol. 14 no. 1-3, pages 49-65, November 1999. [PDF]

Software

I have released my experimental implementation of this algorithm. It is distributed as free software without support. Naturally, it is not industrial-strength code. However, it does provide useful information about the implementation and performance of our algorithm..

The basic software is written in C++ and will compile on most Unix platforms as well as Windows 95/NT. This provides a command-line interface for simplifying a given input model. In addition, a visual program that allows the user to interact with the model as it is being simplified is available.

Sample Data

For those interested in exploring our results further, I’ve collected together the sample models used in our papers. The results from the SIGGRAPH 97 paper are based on my QSlim 1.0 software. The results reported in the Visualization 98 paper and my dissertation are based on the newer QSlim 2.0 package.

SIGGRAPH 97   You can download the full model collection in both [tar.gz] and [zip] formats. The contents of these archives, also available separately, are:

• Cow model. This model is based on data distributed with SGI’s Powerflip demo, but a nearly identical dataset is available from the Avalon archive.
• Skeletal foot model. This model also comes from the Avalon archive.
• Bunny model. The original dataset which this model was created from is distributed by the Stanford Computer Graphics Laboratory.
• Crater Lake model. I created this model with my Terra terrain approximation software.

Visualization 98   You can download the full model collection in both [tar.gz] and [zip] formats. Primarily because of the Buddha statue, these archives are about 10 MB compressed and 45 MB uncompressed. The contents of these archives, also available separately, are:

Buddha statue, originally from the Stanford Computer Graphics Laboratory.
• Swirl. This is a piece of a sphere with a black and white swirl pattern on it.
• Colored globe dataset. A simple sphere with pseudocolored elevation data mapped onto it.
• Dragon with radiosity solution. This model appears in my slides, but not in the paper. The radiosity solution is courtesy of Andrew Willmott.
• North America model. You’ll also need the acompanying texture file.