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.


For more details, check out our SIGGRAPH 96 paper:

Jonathan Cohen, 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.


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:

Jonathan D. Cohen. Last revised: January 27, 1997.

Geometric Algorithms for Modeling, Motion, and Animation