A level-of-detail hierarchy for the rotor from a brake assembly. The original model was provided by the Alpha_1 group at the University of Utah.

Simplification Envelopes

Automatic simplification of polygonal models is currently an important problem for interactive, 3D graphics applications. By generating several levels of detail of a model, each containing fewer polygons than the previous one, we can trade off high quality images vs. interactive frame rates.

Simplification envelopes is a method for automatically generating such level-of-detail hierarchies. The user specifies a single error tolerance, the maximum surface deviation of the simplified model from the original model, and a new, simplified model is generated. The method hinges on the generation of two envelope surfaces which surround the original surface. The distance between the envelope surfaces and the original surface is always less than the user-specified tolerance. The output model is generated by making successive modifications to the original model, always making sure that the resulting surface lies between the two envelope surfaces.

Source Code

Version 1.2 of the simplification envelopes source code, written by is now available in compressed tar (4.3 Megs) and zip (3.7 Megs) formats. It is free for non-commercial use. If you compile and use this software, please let us know how it goes.

Paper

For more details, check out our SIGGRAPH 96 paper (also included with the source code):

Cohen, Jonathan, Amitabh Varshney, Dinesh Manocha, Greg Turk, Hans Weber, Pankaj Agarwal, Frederick Brooks, and William Wright. Simplification Envelopes. Proceedings of SIGGRAPH 96 (New Orleans, LA, August 4-9, 1996). In Computer Graphics Proceedings, Annual Conference Series, 1996, ACM SIGGRAPH, pp. 119-128.

Abstract

We propose the idea of simplification envelopes for generating a hierarchy of level-of-detail approximations for a given polygonal model. Our approach guarantees that all points of an approximation are within a user-specifiable distance epsilon from the original model and that all points of the original model are within a distance epsilon from the approximation. Simplification envelopes provide a general framework within which a large collection of existing simplification algorithms can run. We demonstrate this technique in conjunction with two algorithms, one local, the other global. The local algorithm provides a fast method for generating approximations to large input meshes (at least hundreds of thousands of triangles). The global algorithm provides the opportunity to avoid local "minima" and possibly achieve better simplifications as a result.

Each approximation attempts to minimize the total number of polygons required to satisfy the above epsilon constraint. The key advantages of our approach are:

• General technique providing guaranteed error bounds for genus-preserving simplification
• Automation of both the simplification process and the selection of appropriate viewing distances
• Prevention of self-intersection
• Preservation of sharp features
• Allows variation of approximation distance across different portions of a model

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