No Access

SUCCESSIVE MAPPINGS: AN APPROACH TO POLYGONAL MESH SIMPLIFICATION WITH GUARANTEED ERROR BOUNDS

Department of Computer Science, Sitterson Hall, CB 3175, University of North Carolina at Chapel Hill, Chapel Hill, NC 27599-3175, USA

Department of Computer Science, The Johns Hopkins University, Baltimore, Maryland 21218-2694, USA

Search for more papers by this author

DINESH MANOCHA

Department of Computer Science, Sitterson Hall, CB 3175, University of North Carolina at Chapel Hill, Chapel Hill, NC 27599-3175, USA

Search for more papers by this author

, and

MARC OLANO

Department of Computer Science, Sitterson Hall, CB 3175, University of North Carolina at Chapel Hill, Chapel Hill, NC 27599-3175, USA

M/S 590, Silicon Graphics Incorporated, 2011 North Shoreline Boulevard, Mountain View, California, 94043, USA

Search for more papers by this author

https://doi.org/10.1142/S0218195903001074Cited by:9 (Source: Crossref)

Abstract

We present the use of mapping functions to automatically generate levels of detail with known error bounds for polygonal models. We develop a piece-wise linear mapping function for each simplification operation and use this function to measure deviation of the new surface from both the previous level of detail and from the original surface. In addition, we use the mapping function to compute appropriate texture coordinates if the original model has texture coordinates at its vertices. Our overall algorithm uses edge collapse operations. We present rigorous procedures for the generation of local orthogonal projections to the plane as well as for the selection of a new vertex position resulting from the edge collapse operation. The algorithm computes guaranteed error bounds on surface deviation and produces an entire continuum of levels of detail with mappings between them. We demonstrate the effectiveness of our algorithm on several models: a Ford Bronco consisting of over 300 parts and 70, 000 triangles, a textured lion model consisting of 49 parts and 86, 000 triangles, a textured, wrinkled torus consisting of 79, 000 triangles, a dragon model consisting of 871, 000 triangles, a Buddha model consisting of 1,000,000 triangles, and an armadillo model consisting of 2, 000, 000 triangles.

Keywords:

Remember to check out the Most Cited Articles!
Check out these titles in image analysis!

References

Pankaj K. Agarwal and Subhash Suri, Surface approximation and geometric partitions, Proc. 5th ACM-SIAM Sympos. Discrete Algorithms (1994) pp. 24–33. Google Scholar
C. Bajaj and D. Schikore, SPIE 2656, 34 (1996). Google Scholar
H. Brönnimann and M. T. Goodrich, Almost optimal set covers in finite VC-dimension, Proc. 10th Annu. ACM Sympos. Comput. Geom. (1994) pp. 293–302. Google Scholar
M. P. Do Carmo , Differential Geometry of Curves and Surfaces ( Prentice Hall , 1976 ) . Google Scholar
A. Certainet al., Interactive multiresolution surface viewing, Proc. of ACM Siggraph (1996) pp. 91–98. Google Scholar
Paolo Cignoni, C. Rocchini and Roberto Scopigno, Computer Graphics Forum 17(2), 167 (1998). Web of Science, Google Scholar
Kenneth L. Clarkson. Algorithms for polytope covering and approximation. In Proc. 3rd Workshop Algorithms Data Struct., volume 709 of Lecture Notes Comput. Sci., pages 246–252. Springer-Verlag, 1993 . Google Scholar
J. Cohen, M. Olano and D. Manocha, Appearance preserving simplification, Proc. of ACM SIGGRAPH (1998) pp. 115–122. Google Scholar
J. Cohenet al., Simplification envelopes, Proc. of ACM Siggraph'96 (1996) pp. 119–128. Google Scholar
Jonathan Cohen, Dinesh Manocha and Marc Olano, Simplifying polygonal models using successive mappings, IEEE Visualization '97 (1997) pp. 395–402. Google Scholar
Jonathan Cohen , Dinesh Manocha and Marc Olano , Simplifying polygonal models using successive mappings , Video Proceedings of IEEE Visualization '97 . Google Scholar
G. Das and D. Joseph, The complexity of minimum convex nested polyhedra, Proc. 2nd Canad. Conf. Comput. Geom. (1990) pp. 296–301. Google Scholar
M. J. DeHaemer Jr. and M. J. Zyda, Computers & Graphics 15(2), 175 (1991). Web of Science, Google Scholar
T. Derose, M. Lounsbery, and J. Warren. Multiresolution analysis for surfaces of arbitrary topology type. Technical Report TR 93-10-05, Department of Computer Science, University of Washington, 1993 . Google Scholar
T. K. Dey, H. Edelsbrunner, S. Guha, and D. Nekhayev. Topology preserving edge contraction. Technical Report RGI-Tech-98-018, Raindrop Geomagic, 1999 , http://www.cis.ohiostate.edu/~tamaldey/paper/simplify/paper.ps.gz . Google Scholar
M. Ecket al., Multiresolution analysis of arbitrary meshes, Proc. of ACM Siggraph (1995) pp. 173–182. Google Scholar
Carl Erikson. Polygonal simplification: An overview. Technical Report TR96-016, Department of Computer Science, University of North Carolina at Chapel Hill, 1996 . Google Scholar
Leila De Floriani, Paola Magillo and Enrico Puppo, Building and traversing a surface at variable resolution, IEEE Visualization '97, eds. Roni Yagel and Hans Hagen (IEEE, 1997) pp. 103–110. Google Scholar
Michael Garland and Paul S. Heckbert, Surface simplification using quadric error metrics, Proceedings of SIGGRAPH 97 (Los Angeles, California, 1997) pp. 209–216. Google Scholar
Michael Garland and Paul S. Heckbert, Simplifying surfaces with color and texture using quadric error metrics, IEEE Visualization '98 (1998) pp. 263–270. Google Scholar
A. Gueziec, Surface simplification with variable tolerance, Second Annual Intl. Symp. on Medical Robotics and Computer Assisted Surgery (MRCAS '95) (1995) pp. 132–139. Google Scholar
André Guéziec, IEEE Transactions on Visualization and Computer Graphics 5(2), 168 (1999). Web of Science, Google Scholar
Igor Guskov, Wim Sweldens and Peter Schröder, Multiresolution signal processing for meshes, Proceedings of SIGGRAPH 99 (Los Angeles, California, 1999) pp. 325–334. Google Scholar
P. Heckbert and M. Garland, Multiresolution modeling for fast rendering, Proceedings of Graphics Interface '94 (1994) pp. 43–50. Google Scholar
Paul S. Heckbert and Michael Garland , Survey of polygonal surface simplification algorithms , SIGGRAPH 97 Course Notes . Google Scholar
H. Hoppe, View dependent refinement of progressive meshes, SIGGRAPH 97 Conference Proceedings (ACM SIGGRAPH, 1997) pp. 189–198. Google Scholar
H. Hoppeet al., Mesh optimization, Proc. of ACM Siggraph (1993) pp. 19–26. Google Scholar
Hugues Hoppe, Progressive meshes, SIGGRAPH 96 Conference Proceedings (ACM SIGGRAPH, Addison Wesley, 1996) pp. 99–108. Google Scholar
Hugues H. Hoppe, New quadric metric for simplifying meshes with appearance attributes, IEEE Visualization '99 (San Francisco, California, 1999) pp. 59–66. Google Scholar
Reinhard Klein. Multiresolution representations for surface meshes. Technical report, Wilhelm Schickard Institut für Informatik, Universität Tübingen, 1997 . Google Scholar
Reinhard Klein and Jörg Krämer , Building multiresolution models for fast interactive visualization , SCCG . Google Scholar
Reinhard Klein , Gunther Liebich and Wolfgang Straßer , Mesh reduction with error control , IEEE Visualization '96 ( IEEE , 1996 ) . Google Scholar
Leif Kobbelt, Swen Campagna and Hans-Peter Seidel, A general framework for mesh decimation, Graphics Interface '98 (1998) pp. 43–50. Google Scholar
B. Kolman and R. Beck , Elementary Linear Programming with Applications ( Academic Press , New York , 1980 ) . Google Scholar
Aaron W. F. Leeet al., MAPS: Multiresolution adaptive parameterization of surfaces, SIGGRAPH 98 Conference Proceedings, ed. Michael Cohen (ACM SIGGRAPH, Addison Wesley, 1998) pp. 95–104. Google Scholar
D. T. Lee and F. P. Preparata, J. ACM 26(3), 415 (1979). Web of Science, Google Scholar
Peter Lindstrom and Greg Turk, IEEE Transactions on Visualization and Computer Graphics 5(2), 98 (1999). Web of Science, Google Scholar
Peter Lindstrom and Greg Turk, Fast and memory efficient polygonal simplification, IEEE Visualization '98 (1998) pp. 279–286. Google Scholar
David Luebke and Carl Erikson, View-dependent simplification of arbitrary polygonal environments, SIGGRAPH 97 Conference Proceedings, ed. Turner Whitted (ACM SIGGRAPH, Addison Wesley, 1997) pp. 199–208. Google Scholar
N. Megiddo, SIAM J. Comput. 12, 759 (1983). Web of Science, Google Scholar
Joseph S. B. Mitchell and Subhash Suri, Separation and approximation of polyhedral surfaces, Proc. 3rd ACM-SIAM Sympos. Discrete Algorithms (1992) pp. 296–306. Google Scholar
J. O'Rourke , Computational Geometry in C ( Cambridge University Press , 1994 ) . Google Scholar
John Rohlf and James Helman, IRIS performer: A high performance multiprocessing toolkit for real-time 3D graphics, Proceedings of SIGGRAPH '94, Computer Graphics Proceedings, ed. Andrew Glassner (ACM SIGGRAPH, ACM Press, 1994) pp. 381–395. Google Scholar
R. Ronfard and J. Rossignac, Computer Graphics Forum 15(3), 67 (1996). Google Scholar
J. Rossignac and P. Borrel, Modeling in Computer Graphics, Multi-resolution 3D approximations for rendering (Springer-Verlag, 1993) pp. 455–465. Google Scholar
D. Schikore and C. Bajaj. Decimation of 2d scalar data with error control. Technical report, Computer Science Report CSD-TR-95-004, Purdue University, 1995 . Google Scholar
B. Schneideret al., Brush as a walkthrough system for architectural models, Fifth Eurographics Workshop on Rendering (1994) pp. 389–399. Google Scholar
W. J. Schroeder, J. A. Zarge and W. E. Lorensen, Decimation of triangle meshes, Proc. of ACM Siggraph (1992) pp. 65–70. Google Scholar
R. Seidel, Linear programming and convex hulls made easy, Proc. 6th Ann. ACM Conf. on Computational Geometry (Berkeley, California, 1990) pp. 211–215. Google Scholar
D. C. Taylor and W. A. Barrett, An algorithm for continuous resolution polygonalizations of a discrete surface, Proc. Graphics Interface '94 (Banff, Canada, 1994) pp. 33–42. Google Scholar
G. Turk, Re-tiling polygonal surfaces, Proc. of ACM Siggraph (1992) pp. 55–64. Google Scholar
A. Varshney. Hierarchical Geometric Approximations. PhD thesis, University of N. Carolina, 1994 . Google Scholar
J. Xia, J. El-Sana and A. Varshney, IEEE Transactions on Visualization and Computer Graphics 3(2), 171 (1997). Web of Science, Google Scholar
Julie C. Xia and Amitabh Varshney , Dynamic view-dependent simplification for polygonal models , IEEE Visualization '96 ( IEEE , 1996 ) . Google Scholar