Philip HubbardCornell University |
Greg TurkUniversity of North Carolina |
The last few years have seen the development of an amazingly diverse array of algorithms for automatic simplification of polygonal models. Automatic simplification is necessary because many of the polygon models that people wish to display are so large that they overwhelm current rendering hardware. Million-plus polygon models are becoming commonplace. These large models come from a wide variety of sources, including computer-aided geometric design, terrain models, global-illumination solutions, meshes from range data and iso-surfaces from volumetric data.
In the fist part of this talk we will survey a number of algorithms that perform automatic simplification of polygon models. The diversity of approaches for performing simplification is reminiscent of the wonderful variety of hidden surface algorithms for polygon rendering that were primarily developed in the late 1960's and early 1970's. Just as with hidden surface algorithms, there are many issues to consider when selecting a simplification algorithm. Some important issues include error measures, topology preservation, man-made versus organically-shaped objects, ease of implementation and speed. We will end this part of the talk by discussing some open areas of research in automatic simplification.
In the second part of this talk we will focus on a particular simplification problem, in which the polygonal models represent view-independent global-illumination solutions. This context introduces additional issues concerning human perception of illumination. We will present our experiences adapting polygonal simplification algorithms to this context, and we will conclude by identifying some challenges for future work.
Paul S. Heckbert and Michael Garland, "Multiresolution Modeling for Fast Rendering," Proceedings of Graphics Interface '94, pp. 43-50. http://www.cs.cmu.edu/afs/cs/user/ph/www/multirend.ps.Z (Survey of many multiresolution techniques for rendering including several polygonal approaches.)
Peter Shirley, Bretton Wade, Philip M. Hubbard, David Zareski, Bruce Walter and Donald P. Greenberg, "Global Illumination via Density Estimation," Proceedings Sixth Eurographics Rendering Workshop, June 1995, pp. 219-230. http://www.graphics.cornell.edu/~bwade/der/ (Section 4.3 discusses a basic approach to simplifying global-illumination solutions.)
Matthias Eck, Tony DeRose, Tom Duchamp, Hugues Hoppe, Michael Lounsbery, and Werner Stuetzle, "Multiresolution Analysis of Arbitrary Meshes," Technical Report 95-01-02, Department of Computer Science and Engineering, University of Washington, January 1995 and SIGGRAPH 95 Conference Proceedings, August 1995. http://www.cs.washington.edu:80/homes/derose/papers.html (A wavelet-based approach to multi-resolution meshes.)
Paul S. Heckbert and Michael Garland, "Fast Polygonal Approximation of Terrains and Height Fields," Technical Report CMU-CS-95-181, School of Computer Science, Carnegie Mellon University, August 1995. http://www.cs.cmu.edu/afs/cs/user/garland/public/scape (Includes a comprehensive discussion of work from many fields related to geometry simplification.)
Hugues Hoppe, Tony DeRose, Tom Duchamp, J. McDonald, and Werner Stuetzle, "Mesh optimization," Computer Graphics (SIGGRAPH '93 Proceedings), 1993 Annual Conference Series, pp. 19-26. http://www.research.microsoft.com/research/graphics/hoppe/siggraph93/main.html (Simplification by energy minimization. Produces very good simplifications.)
Ricardo J. Motta, "Visual Characterization of Color CRTs," Device-Independent Color Imaging and Imaging Systems Integration, Ricardo J. Motta and Hapet A. Berberian, eds., SPIE, 1993, pp. 212--221. (Discusses gamma correction, which affects simplification of global- illumination solutions.)
Jarek Rossignac and Paul Borrel, "Multi-resolution 3D Approximations for Rendering Complex Scenes," IBM Research Report RC 17697, February 1992. (First simplification method that simplifies topology.)
William J. Schroeder, Jonathan A. Zarge and William E. Lorensen, "Decimation of Triangle Meshes," Proceedings of SIGGRAPH '92, July 1992, pp. 64-70. (An early and influential automatic simplification method.)
M. Ibrahim Sezan, Kwok-Leung Yip and Scott J. Daly, "Uniform Perceptual Quantization: Applications to Digital Radiography," IEEE Transactions on Systems, Man and Cybernetics, SMC-17:4, July/August 1987, pp. 622-634. (Discusses how people perceive intensity differences, which affects simplification of global-illumination solutions.)
Taosong He, Lichan Hong, Arie Kaufman, Amitabh Varshney and Sidney Wang, "Voxel Based Object Simplification," Visualization '95 Proceedings, Atlanta, Georgia, October 29 - November 3, 1995, pp. 296-303. http://www.cs.sunysb.edu/~volvis/vislab/papers.html (A method of topology simplification that blurs models in voxel-space.)
Greg Turk, "Re-Tiling Polygonal Surfaces," Proceedings of SIGGRAPH '92, July 1992, pp. 55-64. (Early heuristic simplification paper that includes a method for interpolating between levels-of-detail.)
Amitabh Varshney, "Hierarchical Geometric Approximations,", Doctoral Dissertation. Department of Computer Science, Univerisity of North Carolina at Chapel Hill, 1994. (First topology preserving simplification method that give a guarenteed error bound.)
