“Simplification envelopes” by Cohen, Varshney, Manocha, Turk, Weber, et al. …

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 from the original model and that all points of the original model are within a distance 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 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

1. E Agarwal and S. Suri. Surface approximation and geometric partitions. In Proceedings Fifth Symposium on Discrete Algorithms, pages 24-33, 1994.
2. H. Br6nnimann and M. Goodrich. Almost optimal set covers in finite VC-dimension. In Proceedings Tenth ACM Symposium on Computational Geometry, pages 293-302,1994.
3. K. L. Clarkson. Algorithms for polytope covering and approximation. In Proc. 3rd Workshop Algorithms Data Struct., Lecture Notes in Computer Science, 1993.
4. M. Cosman and R. Schumacker. System strategies to optimize CIG image content. In Proceedings of the Image II Conference, Scottsdale, Arizona, June 10-12 1981.
5. G. Das and D. Joseph. The complexity of minimum convex nested polyhedra. In Proc. 2nd Canad. Conf. Comput. Geom., pages 296- 301, 1990.
6. M. J. DeHaemer, Jr. and M. J. Zyda. Simplification of objects rendered by polygonal approximations. Computers & Graphics, 15(2):175-184,1991.
7. T.D. DeRose, M. Lounsbery, and J. Warren. Multiresolution analysis for surface of arbitrary topological type. Report 93-10-05, Department of Computer Science, University of Washington, Seattle, WA, 1993.
8. M. Eck, T. DeRose, T. Duchamp, H. Hoppe, M. Lounsbery, and W. Stuetzle. Multiresolution analysis of arbitrary meshes. Computer Graphics: Proceedings of SIGGRAPH’ 95, pages 173-182,1995.
9. T.A. Funkhouser and C. H. S6quin. Adaptive display algorithm for interactive frame rates during visualization of complex virtual environments. In Computer Graphics (SIGGRAPH ’93 Proceedings), volume 27, pages 247-254, August 1993.
10. N. Greene, M. Kass, and G. Miller. Hierarchical z-buffer visibility. In Computer Graphics: Proceedings of SIGGRAPH 1993, pages 231-238. ACM SIGGRAPH, 1993.
11. T. He, L. Hong, A. Kaufman, A. Varshney, and S. Wang. Voxelbased object simplification. In G. M. Nielson and D. Silver, editors, IEEE Visualization ’95 Proceedings, pages 296-303,1995.
12. E Heckbert and M. Garland. Multiresolution modeling for fast rendering. Proceedings of Graphics Interface, 1994.
13. E Hinker and C. Hansen. Geometric optimization. In Gregory M. Nielson and Dan Bergeron, editors, Proceedings Visualization ’93, pages 189-195, October 1993.
14. H. Hoppe, T. DeRose, T. Duchamp, J. McDonald, and W. Stuetzle. Mesh optimization. In James T. Kajiya, editor, Computer Graphics (SIGGRAPH ’93 Proceedings), volume 27, pages 19-26, August 1993.
15. A. D. Kalvin and R. H. Taylor. Superfaces: Polyhedral approximation with bounded error. Technical Report RC 19135 (#82286), IBM Research Division, T. J. Watson Research Center, Yorktown Heights, NY 10958, 1993.
16. J. Mitchell and S. Suri. Separation and approximation of polyhedral surfaces. In Proceedings of 3rd ACM-SIAM Symposium on Discrete Algorithms, pages 296-306,1992.
17. Kevin J. Renze and J. H. Oliver. Generalized surface and volume decimation for unstructured tessellated domains. In Proceedings of SIVE’ 95, 1995.
18. J. Rossignac and E Borrel. Multi-resolution 3D approximations for rendering. In Modeling in Computer Graphics, pages 455-465. Springer-Verlag, June-July 1993.
19. H.E. Rushmeier, C. Patterson, and A. Veerasamy. Geometric simplification for indirect illumination calculations. In Proceedings Graphics Interface ’93, pages 227-236,1993.
20. E J. Schmitt, B. A. Barsky, and W. Du. An adaptive subdivision method for surface-fitting from sampled data. Computer Graphics (SIGGRAPH ’86 Proceedings), 20(4): 179-188,1986.
21. W. J. Schroeder, J. A. Zarge, and W. E. Lorensen. Decimation of triangle meshes. In Edwin E. Catmull, editor, Computer Graphics (SIGGRAPH ’92 Proceedings), volume 26, pages 65-70, July 1992.
22. G. Taubin. A signal processing approach to fair surface design. In Proc. of ACM Siggraph, pages 351-358,1995.
23. G. Turk. Re-filing polygonal surfaces. In Computer Graphics (SIG- GRAPH ’92 Proceedings), volume 26, pages 55-64, July 1992.
24. A. Varshney. Hierarchical geometric approximations. Ph.D. Thesis TR-050-1994, Department of Computer Science, University of North Carolina, Chapel Hill, NC 27599-3175,1994.