Image-driven simplification

ABSTRACT

We introduce the notion of image-driven simplification, a framework that uses images to decide which portions of a model to simplify. This is a departure from approaches that make polygonal simplification decisions based on geometry. As with many methods, we use the edge collapse operator to make incremental changes to a model. Unique to our approach, however, is the use at comparisons between images of the original model against those of a simplified model to determine the cost of an ease collapse. We use common graphics rendering hardware to accelerate the creation of the required images. As expected, this method produces models that are close to the original model according to image differences. Perhaps more surprising, however, is that the method yields models that have high geometric fidelity as well. Our approach also solves the quandary of how to weight the geometric distance versus appearance properties such as normals, color, and texture. All of these trade-offs are balanced by the image metric. Benefits of this approach include high fidelity silhouettes, extreme simplification of hidden portions of a model, attention to shading interpolation effects, and simplification that is sensitive to the content of a texture. In order to better preserve the appearance of textured models, we introduce a novel technique for assigning texture coordinates to the new vertices of the mesh. This method is based on a geometric heuristic that can be integrated with any edge collapse algorithm to produce high quality textured surfaces.

REFERENCES

• 1: Peter R. Atherton, A method of interactive visualization of CAD surface models on a color video display, Proceedings of the 8th annual conference on Computer graphics and interactive techniques, p.279-287, August 03-07, 1981, Dallas, Texas, United States
• 2: Mark R. Bolin , Gary W. Meyer, A perceptually based adaptive sampling algorithm, Proceedings of the 25th annual conference on Computer graphics and interactive techniques, p.299-309, July 1998 [doi>10.1145/280814.280924]
• 3: CIAMPALINI, A., CIGNONI, P., MONTANI, C., AND SCOPIGNO, R. 1997. Multiresolution decimation based on global error. Visual Comput. 13, 5, 228-246.
• 4: CIGNONI, P., ROCCHINI, C., AND SCOPIGNO, R. 1998. Metro: Measuring error on simplified surfaces. Comput. Graph. Forum 17, 2, 167-174.
• 5: Jonathan Cohen , Dinesh Manocha , Marc Olano, Simplifying polygonal models using successive mappings, Proceedings of the 8th conference on Visualization '97, p.395-ff., October 18-24, 1997, Phoenix, Arizona, United States
• 6: Jonathan Cohen , Marc Olano , Dinesh Manocha, Appearance-preserving simplification, Proceedings of the 25th annual conference on Computer graphics and interactive techniques, p.115-122, July 1998 [doi>10.1145/280814.280832]
• 7: Jonathan Cohen , Amitabh Varshney , Dinesh Manocha , Greg Turk , Hans Weber , Pankaj Agarwal , Frederick Brooks , William Wright, Simplification envelopes, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.119-128, August 1996 [doi>10.1145/237170.237220]
• 8: Scott Daly, The visible differences predictor: an algorithm for the assessment of image fidelity, Digital images and human vision, MIT Press, Cambridge, MA, 1993
• 9: EL-SANA, J. 1999. Generalized view-dependent simplification. Comput. Graph. Forum 18,3 (Sept.), 83-94.
• 10: Jihad El-Sana , Elvir Azanli , Amitabh Varshney, Skip strips: maintaining triangle strips for view-dependent rendering, Proceedings of the conference on Visualization '99: celebrating ten years, p.131-138, October 1999, San Francisco, California, United States
• 11: Carl Erikson , Dinesh Manocha, GAPS: general and automatic polygonal simplification, Proceedings of the 1999 symposium on Interactive 3D graphics, p.79-88, April 26-29, 1999, Atlanta, Georgia, United States [doi>10.1145/300523.300532]
• 12: James A. Ferwerda , Peter Shirley , Sumanta N. Pattanaik , Donald P. Greenberg, A model of visual masking for computer graphics, Proceedings of the 24th annual conference on Computer graphics and interactive techniques, p.143-152, August 1997 [doi>10.1145/258734.258818]
• 13: Michael Garland , Paul S. Heckbert, Surface simplification using quadric error metrics, Proceedings of the 24th annual conference on Computer graphics and interactive techniques, p.209-216, August 1997 [doi>10.1145/258734.258849]
• 14: Michael Garland , Paul S. Heckbert, Simplifying surfaces with color and texture using quadric error metrics, Proceedings of the conference on Visualization '98, p.263-269, October 18-23, 1998, Research Triangle Park, North Carolina, United States
• 15: Steven J. Gortler , Radek Grzeszczuk , Richard Szeliski , Michael F. Cohen, The lumigraph, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.43-54, August 1996 [doi>10.1145/237170.237200]
• 16: GU, X., GORTLER,S.J.,HOPPE, H., MCMILLAN, L., BROWN,B.J.,AND STONE, A. D. 1999. Silhouette mapping. Tech. Rep. TR-1-99. Harvard Univ., Cambridge, MA.
• 17: Hugues Hoppe, Progressive meshes, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.99-108, August 1996 [doi>10.1145/237170.237216]
• 18: Hugues Hoppe, View-dependent refinement of progressive meshes, Proceedings of the 24th annual conference on Computer graphics and interactive techniques, p.189-198, August 1997 [doi>10.1145/258734.258843]
• 19: Hugues Hoppe , Tony DeRose , Tom Duchamp , John McDonald , Werner Stuetzle, Mesh optimization, Proceedings of the 20th annual conference on Computer graphics and interactive techniques, p.19-26, September 1993 [doi>10.1145/166117.166119]
• 20: Hugues Hoppe, New quadric metric for simplifiying meshes with appearance attributes, Proceedings of the conference on Visualization '99: celebrating ten years, p.59-66, October 1999, San Francisco, California, United States
• 21: KOBBELT, L., CAMPAGNA, S., AND SEIDEL, H.-P. 1998. A general framework for mesh decimation. In Graphics Interface '98, K. Booth and A. Fournier, Eds. 43-50.
• 22: Marc Levoy , Pat Hanrahan, Light field rendering, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.31-42, August 1996 [doi>10.1145/237170.237199]
• 23: Bruno Lévy , Jean-Laurent Mallet, Non-distorted texture mapping for sheared triangulated meshes, Proceedings of the 25th annual conference on Computer graphics and interactive techniques, p.343-352, July 1998 [doi>10.1145/280814.280930]
• 24: Peter Lindstrom , Greg Turk, Fast and memory efficient polygonal simplification, Proceedings of the conference on Visualization '98, p.279-286, October 18-23, 1998, Research Triangle Park, North Carolina, United States
• 25: Peter Lindstrom , Greg Turk, Evaluation of Memoryless Simplification, IEEE Transactions on Visualization and Computer Graphics, v.5 n.2, p.98-115, April 1999 [doi>10.1109/2945.773803]
• 26: LUBIN, J. 1995. A visual discrimination model for imaging system design and development. In Vision Models for Target Detection and Recognition. World Scientific Publishing Co., Inc., River Edge, NJ, 245-283.
• 27: David Luebke , Carl Erikson, View-dependent simplification of arbitrary polygonal environments, Proceedings of the 24th annual conference on Computer graphics and interactive techniques, p.199-208, August 1997 [doi>10.1145/258734.258847]
• 28: Paulo W. C. Maciel , Peter Shirley, Visual navigation of large environments using textured clusters, Proceedings of the 1995 symposium on Interactive 3D graphics, p.95-ff., April 09-12, 1995, Monterey, California, United States [doi>10.1145/199404.199420]
• 29: Leonard McMillan , Gary Bishop, Plenoptic modeling: an image-based rendering system, Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, p.39-46, September 1995 [doi>10.1145/218380.218398]
• 30: Mahesh Ramasubramanian , Sumanta N. Pattanaik , Donald P. Greenberg, A perceptually based physical error metric for realistic image synthesis, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.73-82, July 1999 [doi>10.1145/311535.311543]
• 31: RONFARD,R.AND ROSSIGNAC, J. 1996. Full-range approximation of triangulated polyhedra. Comput. Graph. Forum 15, 3, 67-76.
• 32: ROSSIGNAC,J.AND BORREL, P. 1993. Multi-resolution 3d approximations for rendering complex scenes. In Modeling in Computer Graphics, B. Falciendo and T. L. Kunii, Eds. Springer-Verlag, New York, NY, 455-465.
• 33: RUSHMEIER, H., LARSON,G.W.,PIATKO, C., SANDERS, P., AND RUST, B. 1995. Comparing real and synthetic images: Some ideas about metrics. In Proceedings of the Eurographics Workshop on Rendering (Dublin, Ireland, June), P. Hanrahan and W. Purgathofer, Eds. 82-91.
• 34: William J. Schroeder, A topology modifying progressive decimation algorithm, Proceedings of the 8th conference on Visualization '97, p.205-ff., October 18-24, 1997, Phoenix, Arizona, United States
• 35: William J. Schroeder , Jonathan A. Zarge , William E. Lorensen, Decimation of triangle meshes, ACM SIGGRAPH Computer Graphics, v.26 n.2, p.65-70, July 1992
• 36: Julie C. Xia , Jihad El-Sana , Amitabh Varshney, Adaptive Real-Time Level-of-Detail-Based Rendering for Polygonal Models, IEEE Transactions on Visualization and Computer Graphics, v.3 n.2, p.171-183, April 1997 [doi>10.1109/2945.597799]
• 37: Julie C. Xia , Amitabh Varshney, Dynamic view-dependent simplification for polygonal models, Proceedings of the 7th conference on Visualization '96, p.327-ff., October 28-29, 1996, San Francisco, California, United States

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.3 Picture/Image Generation
          Subjects: Display algorithms

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Object hierarchies

General Terms:
Algorithms, Performance

Keywords:
image metrics, level-of-detail, polygonal simplification, visual perception