“Appearance-preserving simplification” by Cohen, Olano and Manocha

We present a new algorithm for appearance-preserving simplification. Not only does it generate a low-polygon-count approximation of a model, but it also preserves the appearance. This is accomplished for a particular display resolution in the sense that we properly sample the surface position, curvature, and color attributes of the input surface. We convert the input surface to a representation that decouples the sampling of these three attributes, storing the colors and normals in texture and normal maps, respectively. Our simplification algorithm employs a new texture deviation metric, which guarantees that these maps shift by no more than a user-specified number of pixels on the screen. The simplification process filters the surface position, while the runtime system filters the colors and normals on a per-pixel basis. We have applied our simplification technique to several large models achieving significant amounts of simplification with little or no loss in rendering quality.

1. L. Williams, “Pyramidal Parametrics,” SIGGRAPH 83 Conference Proceedings, pp. 1–11, 1983.
2. J. Rossignac and P. Borrel, “Multi-Resolution 3D Approximations for Rendering,” in Modeling in Computer Graphics: Springer-Verlag, 1993, pp. 455–465.
3. G. Schaufler and W. Sturzlinger, “Generating Multiple Levels of Detail from Polygonal Geometry Models,” Virtual Environments’95 (Eurographics Workshop), pp. 33-41, 1995.
4. W.J. Schroeder, J. A. Zarge, and W. E. Lorensen, “Decimation of Triangle Meshes,” in Proc. ofACMSiggraph, 1992, pp. 65–70.
5. G. Turk, “Re-tiling polygonal surfaces,” Comput. Graphics, vol. 26, pp. 55–64, 1992.
6. M. Garland and P. Heckbert, “Surface Simplification using Quadric Error Bounds,” SIGGRAPH’97 Conference Proceedings, pp. 209-216, 1997.
7. A. Gueziec, “Surface Simplification with Variable Tolerance,” in Second Annual IntL Symp. on Medical Robotics and Computer Assisted Surgery (MRCAS ’95), November 1995, pp. 132–139.
8. J. Cohen, D. Manocha, and M. Olano, “Simplifying Polygonal Models Using Successive Mappings,” Proc. oflEEE Visualization’97, pp. 395-402, 1997.
9. R. Ronfard and J. Rossignac, “Full-range approximation of triangulated polyhedra,” Computer Graphics Forum, vol. 15, pp. 67–76 and 462, August 1996.
10. R. Klein, G. Liebich, and W. Strager, “Mesh Reduction with Error Control,” in IEEE Visualization ’96: IEEE, October 1996.
11. J. Cohen, A. Varshney, D. Manocha, G. Turk, H. Weber, P. Agarwal, F. Brooks, and W. Wright, “Simplification Envelopes,” in SIGGRAPH’96 Conference Proceedings, 1996, pp. 119–128.
12. M. Eck, T. DeRose, T. Duchamp, H. Hoppe, M. Lounsbery, and W. Stuetzle, “Multiresolution Analysis of Arbitrary Meshes,” in SIGGRAPH’95 Conference Proceedings, 1995, pp. 173–182.
13. W. Schroeder, “A Topology Modifying Progressive Decimation Algorithm,” Proc. of lEEE Visualization’97, pp. 205-212, 1997.
14. J. E1-Sana and A. Varshney, “Controlled Simplification of Genus for Polygonal Models,” Proc. oflEEE Visualization’97, pp. 403-410, 1997.
15. H. Hoppe, “Progressive Meshes,” in SIGGRAPH 96 Conference Proceedings: ACM SIGGRAPH, 1996, pp. 99–108.
16. H. Hoppe, “View-Dependent Refinement of Progressive Meshes,” SIG- GRAPH’97 Conference Proceedings, pp. 189-198, 1997.
17. J. Xia, J. E1-Sana, and A. Varshney, “Adaptive Real-Time Level-of-detailbased Rendering for Polygonal Models,” IEEE Transactions on Visualization and Computer Graphics, vol. 3, pp. 171–183, 1997.
18. C. Bajaj and D. Schikore, “Error-bounded reduction of triangle meshes with multivariate data,” SPIE, vol. 2656, pp. 34–45, 1996.
19. M. Hughes, A. Lastra, and E. Saxe, “Simplification of Global-Illumination Meshes,” Proceedings of Eurographics ’96, Computer Graphics Forum, vol. 15, pp. 339-345, 1996.
20. C. Erikson and D. Manocha, “Simplification Culling of Static and Dynamic Scene Graphs,” UNC-Chapel Hill Computer Science TR98-009, 1998.
21. P. Schroder and W. Sweldens, “Spherical Wavelets: Efficiently Representing Functions on the Sphere,” SIGGRAPH 95 Conference Proceedings, pp. 161– 172, August 1995.
22. A. Certain, J. Popovic, T. Derose, T. Duchamp, D. Salesin, and W. Stuetzle, “Interactive Multiresolution Surface Viewing,” in Proc. ofACMSiggraph, 1996, pp. 91–98.
23. R.L. Cook, “Shade trees,” in Computer Graphics (SIGGRAPH ’84 Proceedings), vol. 18, H. Christiansen, Ed., July 1984, pp. 223–231.
24. J. Blinn, “Simulation of Wrinkled Surfaces,” SIGGRAPH ’78 Conference Proceedings, vol. 12, pp. 286–292, 1978.
25. A. Fournier, “Normal distribution functions and multiple surfaces,” Graphics Interface ’92 Workshop on Local Illumination, pp. 45–52, 1992.
26. M. Peercy, J. Airey, and B. Cabral, “Efficient Bump Mapping Hardware,” SIGGRAPH’97 Conference Proceedings, pp. 303-306, 1997.
27. M. Olano and A. Lastra, “A Shading Language on Graphics Hardware: The PixelFlow Shading System,” SIGGRAPH 98 Conference Proceedings, 1998.
28. J. Kajiya, “Anisotropic Reflection Models,” SIGGRAPH ’85 Conference Proceedings, pp. 15–21, 1985.
29. B. Cabral, N. Max, and R. Springmeyer, “Bidirectional Reflection Functions From Surface Bump Maps,” SIGGRAPH ’87 Conference Proceedings, pp. 273- -281, 1987.
30. S. Westin, J. Arvo, and K. Torrance, “Predicting Reflectance Functions From Complex Surfaces,” SIGGRAPH ’92 Conference Proceedings, pp. 255–264, 1992.
31. B.G. Becker and N. L. Max, “Smooth Transitions between Bump Rendering Algorithms,” in Computer Graphics (SIGGRAPH ’93 Proceedings), vol. 27, J. T. Kajiya, Ed., August 1993, pp. 183–190.
32. V. Krishnamurthy and M. Levoy, “Fitting Smooth Surfaces to Dense Polygon Meshes,” SIGGRAPH 96 Conference Proceedings, pp. 313–324, 1996.
33. D.G. Aliaga, “Visualization of Complex Models using Dynamic Texture-based Simplification,” Proc. of IEEE Visualization’96, pp. 101–106, 1996.
34. L. Darsa, B. Costa, and A. Varshney, “Navigating Static Environments using Image-space simplification and morphing,” Proc. of 1997 Symposium on Interactive 3D Graphics, pp. 25-34, 1997.
35. P.W.C. Maciel and P. Shirley, “Visual Navigation of Large Environments Using Textured Clusters,” Proc. of 1995 Symposium on Interactive 3D Graphics, pp. 95–102, 1995.
36. J. Shade, D. Lischinski, D. Salesin, T. DeRose, and J. Snyder, “Hierarchical Image Caching for Accelerated Walkthroughs of Complex Environments,” SIGGRAPH 96 Conference Proceedings, pp. 75–82, August 1996.
37. J. Kent, W. Carlson, and R. Parent, “Shape transformation for polyhedral objects,” SIGGRAPH ’92 Conference Proceedings, pp. 47–54, 1992.
38. J. Maillot, H. Yahia, and A. Veroust, “Interactive Texture Mapping,” SIGGRAPH’93 Conference Proceedings, pp. 27–34, 1993.
39. H. Pedersen, “A Framework for Interactive Texturing Operations on Curved Surfaces,” in SIGGRAPH 96 Conference Proceedings, Annual Conference Series, H. Rushmeier, Ed., August 1996, pp. 295–302.
40. H.d. Fraysseix, J. Pach, and R. Pollack, “How to Draw a Planar Graph on a Grid,” Combinatorica, vol. 10, pp. 41–51, 1990.
41. N. Chiba, T. Nishizeki, S. Abe, and T. Ozawa, “A Linear Algorithm for Embedding Planar Graphs Using PQ-Trees,” J. Comput. Syst. Sci., vol. 30, pp. 54–76, 1985.
42. G.D. Battista, P. Eades, R. Tamassia, and I. G. Tollis, “Algorithms for drawing graphs: an annotated bibliography,” Comput. Geom. Theory Appl., vol. 4, pp. 235–282, 1994.
43. M.d. Berg, M. v. Kreveld, M. Overmars, and O. Schwarzkopf, Computational Geometry: Algorithms and Applications: Springer-Verlag, 1997.
44. R.F. Lyon, “Phong Shading Reformulation for Hardware Renderer Simplification,” Apple Computer #43, 1993.