Quadric-based simplification in any dimension

ABSTRACT

We present a novel generalization of the quadric error metric used in surface simplification that can be used for simplifying simplicial complexes of any type embedded in Euclidean spaces of any dimension. We demonstrate that our generalized simplification system can produce high quality approximations of plane and space curves, triangulated surfaces, tetrahedralized volume data, and simplicial complexes of mixed type. Our method is both efficient and easy to implement. It is capable of processing complexes of arbitrary topology, including nonmanifolds, and can preserve intricate boundaries.

REFERENCES

• 1: Pankaj K. Agarwal , Subhash Suri, Surface approximation and geometric partitions, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.24-33, January 23-25, 1994, Arlington, Virginia, United States
• 2: Dana H. Ballard, Strip trees: a hierarchical representation for curves, Communications of the ACM, v.24 n.5, p.310-321, May 1981 [doi>10.1145/358645.358661]
• 3: Bruce Guenther Baumgart, Geometric modeling for computer vision., 1974
• 4: Laurence Boxer , Chun-Shi Chang , Russ Miller , Andrew Rau-Chaplin, Polygonal approximation by boundary reduction, Pattern Recognition Letters, v.14 n.2, p.111-119, Feb. 1993 [doi>10.1016/0167-8655(93)90084-Q]
• 5: Prashant Chopra , Joerg Meyer, TetFusion: an algorithm for rapid tetrahedral mesh simplification, Proceedings of the conference on Visualization '02, October 27-November 01, 2002, Boston, Massachusetts
• 6: Ciampalini, A., Cignoni, P., Montani, C., and Scopigno, R. 1997. Multiresolution decimation based on global error. Visual Comput. 13, 5, 228--246.
• 7: Ciarlet, P. and Lamour, F. 1996. Does contraction preserve triangular meshes? Numer. Algor. 13, 201--223.
• 8: P. Cignoni , D. Constanza , C. Montani , C. Rocchini , R. Scopigno, Simplification of Tetrahedral meshes with accurate error evaluation, Proceedings of the conference on Visualization '00, p.85-92, October 2000, Salt Lake City, Utah, United States
• 9: Paolo Cignoni , Leila De Floriani , Paola Magillo , Enrico Puppo , Roberto Scopigno, Selective Refinement Queries for Volume Visualization of Unstructured Tetrahedral Meshes, IEEE Transactions on Visualization and Computer Graphics, v.10 n.1, p.29-45, January 2004 [doi>10.1109/TVCG.2004.1260756]
• 10: P. Cignoni , C. Montani , R. Scopigno , C. Rocchini, A general method for preserving attribute values on simplified meshes, Proceedings of the conference on Visualization '98, p.59-66, October 18-23, 1998, Research Triangle Park, North Carolina, United States
• 11: Cignoni, P., Montani, C., and Scopigno, R. 1998b. A comparison of mesh simplification algorithms. Comput. Graph. 22, 1, 37--54.
• 12: Cignoni, P., Rocchini, C., and Scopigno, R. 1998c. Metro: Measuring error on simplified surfaces. Comput. Graph. Forum 17, 2 (June), 167--174.
• 13: 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]
• 14: 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]
• 15: E. F. D'Azevedo, Optimal triangular mesh generation by coordinate transformation, SIAM Journal on Scientific and Statistical Computing, v.12 n.4, p.755-786, July 1991 [doi>10.1137/0912040]
• 16: Dey, T. K., Edelsbrunner, H., Guha, S., and Nekhayev, D. V. 1999. Topology preserving edge contraction. Publ. Inst. Math. (Beograd) (N.S.) 66, 23--45.
• 17: Douglas, D. H. and Peucker, T. K. 1973. Algorithms for the reduction of the number of points required to represent a digitized line or its caricature. The Canadian Cartographer 10, 2 (Dec.), 112--122.
• 18: Duda, R. O. and Hart, P. E. 1973. Pattern Classification and Scene Analysis. Wiley, New York.
• 19: 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]
• 20: Garland, M. 1999a. Multiresolution modeling: Survey & future opportunities. In State of the Art Report. Eurographics, 111--131.
• 21: Michael Garland , Paul Heckbert, Quadric-based polygonal surface simplification, 1999
• 22: 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]
• 23: 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
• 24: Michael Garland , Eric Shaffer, A multiphase approach to efficient surface simplification, Proceedings of the conference on Visualization '02, October 27-November 01, 2002, Boston, Massachusetts
• 25: Guéziec, A. 1995. Surface simplification with variable tolerance. In Second Annual International Symposium on Medical Robotics and Computer Assisted Surgery (MRCAS '95). 132--139.
• 26: Guéziec, A. 1996. Surface simplification inside a tolerance volume. Tech. Rep., Yorktown Heights, NY 10598. Mar. IBM Research Report RC 20440, http://www.watson.ibm.com:8080/search_paper.shtml.
• 27: Heckbert, P. S. and Garland, M. 1997. Survey of polygonal surface simplification algorithms. In Multiresolution Surface Modeling Course Notes. ACM SIGGRAPH.
• 28: Paul S. Heckbert , Michael Garland, Optimal triangulation and quadric-based surface simplification, Computational Geometry: Theory and Applications, v.14 n.1-3, p.49-65, Nov. 1999 [doi>10.1016/S0925-7721(99)00030-9 ]
• 29: John Hershberger , Jack Snoeyink, An O(nlogn) implementation of the Douglas-Peucker algorithm for line simplification, Proceedings of the tenth annual symposium on Computational geometry, p.383-384, June 06-08, 1994, Stony Brook, New York, United States [doi>10.1145/177424.178097]
• 30: 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]
• 31: 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]
• 32: 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
• 33: Insung Ihm , Bruce Naylor, Piecewise linear approximations of digitized space curves with applications, Scientific visualization of physical phenomena, Springer-Verlag New York, Inc., New York, NY, 1991
• 34: Imai, H. and Iri, M. 1988. Polygonal approximations of a curve---formulations and algorithms. In Computational Morphology, G. T. Toussaint, Ed. Elsevier Science, 71--86.
• 35: Tao Ju , Frank Losasso , Scott Schaefer , Joe Warren, Dual contouring of hermite data, ACM Transactions on Graphics (TOG), v.21 n.3, July 2002
• 36: Youngihn Kho , Michael Garland, User-guided simplification, Proceedings of the 2003 symposium on Interactive 3D graphics, April 27-30, 2003, Monterey, California [doi>10.1145/641480.641504]
• 37: Jia-Guu Leu , Limin Chen, Polygonal approximation of 2-D shape through boundary merging, Pattern Recognition, v.7 n.4, p.231-238, April 1988
• 38: Peter Lindstrom , Greg Turk, Model simplification using image and geometry-based metrics, 2000
• 39: Peter Lindstrom, Out-of-core simplification of large polygonal models, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.259-262, July 2000 [doi>10.1145/344779.344912]
• 40: 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
• 41: David Luebke , Benjamin Watson , Jonathan D. Cohen , Martin Reddy , Amitabh Varshney, Level of Detail for 3D Graphics, Elsevier Science Inc., New York, NY, 2002
• 42: Maruya, M. 1995. Generating a texture map from object-surface texture data. Comput. Graph. Forum 14, 3, 397--405, 506--507. Proceedings Eurographics '95.
• 43: Meyer, M., Desbrun, M., Schröder, P., and Barr, A. H. 2003. Discrete differential-geometry operators for triangulated 2-manifolds. In Visualization and Mathematics III, H.-C. Hege and K. Polthier, Eds. Springer-Verlag, Heidelberg, 35--57.
• 44: Nadler, E. 1986. Piecewise linear best L2 approximation on triangulations. In Approximation Theory V, C. K. Chui et al., Eds. Academic Press, Boston, 499--502.
• 45: Vijay Natarajan , Herbert Edelsbrunner, Simplification of Three-Dimensional Density Maps, IEEE Transactions on Visualization and Computer Graphics, v.10 n.5, p.587-597, September 2004 [doi>10.1109/TVCG.2004.32]
• 46: Pavlidis, T. 1977. Structural Pattern Recognition. Springer-Verlag, Berlin.
• 47: Jovan Popović , Hugues Hoppe, Progressive simplicial complexes, Proceedings of the 24th annual conference on Computer graphics and interactive techniques, p.217-224, August 1997 [doi>10.1145/258734.258852]
• 48: William H. Press , Saul A. Teukolsky , William T. Vetterling , Brian P. Flannery, Numerical recipes in C (2nd ed.): the art of scientific computing, Cambridge University Press, New York, NY, 1992
• 49: Ramer, U. 1972. An iterative procedure for the polygonal approximation of plane curves. Computer Graphics and Image Processing 1, 244--256.
• 50: Kevin J. Renze , James H. Oliver, Generalized Unstructured Decimation, IEEE Computer Graphics and Applications, v.16 n.6, p.24-32, November 1996 [doi>10.1109/38.544069 ]
• 51: Ronfard, R. and Rossignac, J. 1996. Full-range approximation of triangulated polyhedra. Comput. Graph. Forum 15, 3 (Aug.). Proceedings Eurographics '96.
• 52: Rossignac, J. and Borrel, P. 1993. Multi-resolution 3D approximations for rendering complex scenes. In Modeling in Computer Graphics: Methods and Applications, B. Falcidieno and T. Kunii, Eds. Springer-Verlag, Berlin, 455--465. Proceedings of Conference, Genoa, Italy, June 1993. (Also available as IBM Research Report RC 17697, Feb. 1992, Yorktown Heights, NY 10598).
• 53: Jim Ruppert , Raimund Seidel, On the difficulty of triangulating three-dimensional nonconvex polyhedra., Discrete & Computational Geometry, v.7 n.3, p.227-253, 1992
• 54: Will Schroeder , Kenneth M. Martin , William E. Lorensen, The visualization toolkit (2nd ed.): an object-oriented approach to 3D graphics, Prentice-Hall, Inc., Upper Saddle River, NJ, 1998
• 55: 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
• 56: Eric Shaffer , Michael Garland, Efficient adaptive simplification of massive meshes, Proceedings of the conference on Visualization '01, October 21-26, 2001, San Diego, California
• 57: Jonathan Richard Shewchuk, Triangle: Engineering a 2D Quality Mesh Generator and Delaunay Triangulator, Selected papers from the Workshop on Applied Computational Geormetry, Towards Geometric Engineering, p.203-222, May 27-28, 1996
• 58: Soucy, M., Godin, G., and Rioux, M. 1996. A texture-mapping approach for the compression of colored 3D triangulations. The Visual Computer 12, 10, 503--514.
• 59: Oliver G. Staadt , Markus H. Gross, Progressive tetrahedralizations, Proceedings of the conference on Visualization '98, p.397-402, October 18-23, 1998, Research Triangle Park, North Carolina, United States
• 60: Strang, G. 1988. Linear Algebra and its Applications, Third Ed. Harcourt Brace Jovanovich, San Diego.
• 61: Issac J. Trotts , Bernd Hamann , Kenneth I. Joy, Simplification of Tetrahedral Meshes with Error Bounds, IEEE Transactions on Visualization and Computer Graphics, v.5 n.3, p.224-237, July 1999 [doi>10.1109/2945.795214 ]
• 62: Issac J. Trotts , Bernd Hamann , Kenneth I. Joy , David F. Wiley, Simplification of tetrahedral meshes, Proceedings of the conference on Visualization '98, p.287-295, October 18-23, 1998, Research Triangle Park, North Carolina, United States
• 63: Greg Turk, Re-tiling polygonal surfaces, ACM SIGGRAPH Computer Graphics, v.26 n.2, p.55-64, July 1992
• 64: Turner, K. J. 1974. Computer perception of curved objects using a television camera. Ph.D. thesis, U. of Edinburgh, Scotland.
• 65: Allen Van Gelder , Vivek Verma , Jane Wilhelms, Volume Decimation of Irregular Tetrahedral Grids, Proceedings of the International Conference on Computer Graphics, p.222, June 07-11, 1999
• 66: Robert Weibel, Generalization of Spatial Data: Principles and Selected Algorithms, Algorithmic Foundations of Geographic Information Systems, this book originated from the CISM Advanced School on the Algorithmic Foundations of Geographic Information Systems, p.99-152, September 16-20, 1996
• 67: Yizhou Yu, Modeling Realistic Virtual Hairstyles, Proceedings of the 9th Pacific Conference on Computer Graphics and Applications, p.295, October 16-18, 2001
• 68: Steve Zelinka , Michael Garland, Permission grids: practical, error-bounded simplification, ACM Transactions on Graphics (TOG), v.21 n.2, p.207-229, April 2002 [doi>10.1145/508357.508363]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Curve, surface, solid, and object representations

Keywords:
Quadric error metric, curve simplification, edge contraction, surface simplification, volume simplification