Appearance-Preserving Simplification

A level-of-detail hierarchy for the "Armadillo" model. The original model was provided by Venkat Krishnamurthy and Marc Levoy of the Stanford Computer Graphics Laboratory and Peter Schröder of the California Institue of Technology. The levels of detail contain 7809, 3905, 1951, 975, and 488 triangles, respectively (from nearest to farthest).

This image is available at full resolution as Figure 11.

More and more polygonal simplification algorithms are providing error bounds on how close the position of the simplified surface comes to the position of the input surface. This sort of error bound is useful for determining that a rendering of the simplified surface will cover the correct pixels on the screen to within some user-specified tolerance. However, such a bound says nothing about what color these rendered pixels will be, and how close those of a rendering of the input surface.

The surface position alone is not enough to determine the output color of the pixels it covers. Surfaces typically have some base color and curvature information which have a large impact on the output color. These attributes are often stored at the vertices of a polygonal surface, so we lose information about them as we simplify the surface.

Instead, we choose to store information about color and curvature (surface normals) in texture and normal maps, respectively. Texture coordinates are stored at the triangle vertices to map between the surface and texture domains. We can now safely simplify the surface geometry without losing information about these other appearance attributes.

As the surface is simplified, only the surface position and texture coordinates are affected. We measure the effects of the simplification on these two attributes as a maximum 3D deviation between corresponding points from the input surface and the simplified surface. When projected into 2D, this 3D deviation provides a simple and intuitive metric for the effect of the simplification process: correctly colored pixels may now deviate from their correct positions on the screen by no more than a user-specified number of pixels.

Paper

For more details, check out our SIGGRAPH 98 paper:

Cohen, Jonathan, Marc Olano, and Dinesh Manocha. Appearance-Preserving Simplfication. Proceedings of SIGGRAPH 98 (Orlando, Florida, July 19-24, 1998). In Computer Graphics, Annual Conference Series, ACM SIGGRAPH, 1998.

3.5 MB .pdf file (300 dpi images)
or
0.7 MB .pdf file (reduced resolution images)

The color images are also available in pristine form as TIFFs or gamma-corrected, slightly lossy JPEGs.

Figure 1: ( 290K tiff) ( 51K jpeg)
Figure 4: ( 530K tiff) ( 41K jpeg)
Figure 5: ( 552K tiff) ( 79K jpeg)
Figure 6: ( 160K tiff) ( 154K jpeg)
Figure 11: ( 185K tiff) ( 70K jpeg)
Figure 12: ( 1.5MB tiff) ( 409K jpeg)

Abstract

We present a new algorithm for appearance-preserving simplification. Not only does it generate a low-polygon-count approximation of a model, but it also preserves the appearance. This is accomplished for a particular display resolution in the sense that we properly sample the surface position, curvature and color attributes of the input surface. We convert the input surface to a represetnation that decouples the sampling of these three attributes, storing the colors and normals in texture and normal maps, respectively. Our simplification algorithm employs a new texture deviation metric, which guarantees that these maps shift by no more than a user-specified number of pixels on the screen. The simplification process filters the surface position, while the run-time system filters the colors and normals on a per-pixel basis. We have applied our simplification technique to several large models, achieving significant amounts of simplification with little or no loss in rendering quality.

UNC Research Group on Modeling, Physically-Based Simulation and Applications