A level-of-detail hierarchy for the Ford Bronco model. The original model was provided by the Division and Viewpoint.

Simplification Using Successive Mappings

Though the hardware for interactive display of 3D graphics gets faster and faster each year, the models we would like to render grow at an even faster rate. For this reason, it is necessary to automatically simplify our polygonal models, allowing us to trade quality for interactivity.

The successive mapping technique uses edge collapses in conjunction with guaranteed error bounds to generate high-quality levels of detail for polygonal models. The input to the algorithm is a single polygonal model. The output is a progressive mesh -- a sequence of simplification operations, each with associated error bounds. Using this representation, the rendering software may choose to create any number of levels of detail for the model of different compleixties (and qualities).

For each simplification operation, the algorithm computes a local mapping between the current mesh and the mesh resulting from the operation. It measures the maximum geometric deviation between the original mesh and the new mesh. For texture-mapped surfaces, the algorithm also measures the maximum deviation of points with corresponding texture coordinates, thus bounding the distortion of the texture map as the object is simplified.

We have an mpeg animation (1.9 MB) of a wrinkled torus model switching levels of detail. The higher level of detail (shown in yellow) contains 19,800 triangles. The lower level of detail (shown in green) contains 9,900 triangles. The levels of detail are guaranteed to have no more than two pixels of screen-space deviation from the original model (79,200 triangles). This includes not only the deviation of the geometry, but the deviation of a texture map as well.

Paper

For more details, check out our paper (2.5 MB):

Cohen, Jonathan, Dinesh Manocha, and Marc Olano. Simplifying Polygonal Models Using Successive Mappings. Proceedings of IEEE Visualization '97. pp. 395-402, and 564.

The color images in this pdf file have been reduced in size and color depth to make the file easier to print. You may also wish to download the color plate (6.2 MB tiff) at original resolution. These images are at actual rendering resolution. No pixels have been injured by postprocessing. You must gamma correct these images to make them appropriately bright.

Or, if you don't mind a bit of pixel corruption, you may download the considerably smaller jpeg-compressed color plate (1.1 MB) These images have already had some gamma correction applied as well.

Abstract

We present the use of mapping functions to automatically generate levels of detail with known error bounds for polygonal models. We develop a piece-wise linear mapping function for each simplification operation and use this function to measure deviation of the new surface from both the previous level of detail and from the original surface. In addition, we use the mapping function to compute appropriate texture coordinates if the original map has texture coordinates at its vertices. Our overall algorithm uses edge collapse operations. We present rigorous procedures for the generation of local planar projections as well as for the selection of a new vertex position for the edge collapse operation. As compared to earlier methods, our algorithm is able to compute tight error bounds on surface deviation and produce an entire continuum of levels of detail with mappings between them. We demonstrate the effectiveness of our algorithm on several models: a Ford Bronco consisting of over 300 parts and 70,000 triangles, a textured lion model consisting of 49 parts and 86,000 triangles, and a textured, wrinkled torus consisting of 79,000 triangles.

Jonathan D. Cohen

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

Last revised: August 13, 1997