Surface Simplification Using Quadric Error Metrics

Michael Garland and Paul S. Heckbert

This page describes an efficient algorithm for producing good quality approximations of triangulated surfaces. It is part of my work on multiresolution modeling. The basic details of this algorithm were published in:

Surface Simplification Using Quadric Error Metrics
Michael Garland and Paul S. Heckbert, SIGGRAPH 97.

The text of this article is available in both PDF and PostScript formats. The PDF file is recommended. It is much smaller and will reproduce well on printers. The original PostScript is available for those unable to process PDF files. You can also look at the slides I used for my SIGGRAPH talk. These slides were designed for onscreen viewing; they may or may not print well.

I have a new paper that describes the extension of the quadric-based algorithm to handle surfaces with material properties. It also contains an improved discussion of the original algorithm.

Simplifying Surfaces with Color and Texture using Quadric Error Metrics
Michael Garland and Paul S. Heckbert, IEEE Visualization 98.

You can grab the PDF or PostScript versions of this paper now. The slides that I used for my talk at Vis98 contain some additional pictures that don't appear in the paper. The extended algorithm described in this paper is not supported by the QSlim software.

Finally, you can grab a copy of my Ph.D. thesis

Quadric-Based Polygonal Surface Simplification
Michael Garland, Ph.D. Thesis, Tech. Rept. CMU-CS-99-105.

It contains the most authoritative description of the simplification algorithm, as well as the most extensive analysis of its behavior.

Sample Data

For those interested in exploring our results further, I've collected together the sample models used in our papers. The QSlim software which was the basis of the results in our SIGGRAPH 97 paper is available online. My newer software which I used in the Visualization 98 paper, is not yet available, but will be in the near future.

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.

Free Software

I have released my experimental implementation of this algorithm. It is distributed as public domain code 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 will be available. This requires both the XForms library and an OpenGL or Mesa library.

Michael Garland

garland@cs.cmu.edu

Last modified: Thu May 27 18:24:50 EDT 1999