A multiphase approach to efficient surface simplification

ABSTRACT

We present a new multiphase method for efficiently simplifying polygonal surface models of arbitrary size. It operates by combining an initial out-of-core uniform clustering phase with a subsequent in-core iterative edge contraction phase. These two phases are both driven by quadric error metrics, and quadrics are used to pass information about the original surface between phases. The result is a method that produces approximations of a quality comparable to quadric-based iterative edge contraction, but at a fraction of the cost in terms of running time and memory consumption.

REFERENCES

• 1: P. Cignoni, C. Montani, and R. Scopigno. A comparison of mesh simplification algorithms. Computers & Graphics, 22(1):37-54, 1998.
• 2: Jihad El-Sana and Yi-Jen Chiang. External memory view-dependent simplification. Computer Graphics Forum, 19(3):139-150, August 2000.
• 3: Michael Garland. Multiresolution modeling: Survey & future opportunities. In State of the Art Report, pages 111-131. Eurographics, September 1999.
• 4: Michael Garland , Paul Heckbert, Quadric-based polygonal surface simplification, 1999
• 5: 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]
• 6: 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]
• 7: Hugues Hoppe, Smooth view-dependent level-of-detail control and its application to terrain rendering, Proceedings of the conference on Visualization '98, p.35-42, October 18-23, 1998, Research Triangle Park, North Carolina, United States
• 8: 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]
• 9: Peter Lindstrom , Cláudio T. Silva, A memory insensitive technique for large model simplification, Proceedings of the conference on Visualization '01, October 21-26, 2001, San Diego, California
• 10: 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
• 11: Kok-Lim Low , Tiow-Seng Tan, Model simplification using vertex-clustering, Proceedings of the 1997 symposium on Interactive 3D graphics, p.75-ff., April 27-30, 1997, Providence, Rhode Island, United States [doi>10.1145/253284.253310]
• 12: David Luebke, Jonathan Cohen, Martin Reddy, Amitabh Varshney, and Benjamin Watson. Advanced Issues in Level of Detail. Number 45 in SIGGRAPH 2001 Course Notes. ACM SIGGRAPH, August 2001.
• 13: 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]
• 14: 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]
• 15: 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
• 16: Chris Prince. Progressive meshes for large models of arbitrary topology. Master's thesis, University of Washington, 2000.
• 17: Jarek Rossignac and Paul Borrel. Multi-resolution 3D approximations for rendering complex scenes. In B. Falcidieno and T. Kunii, editors, Modeling in Computer Graphics: Methods and Applications, pages 455-465, 1993.
• 18: Eric Shaffer , Michael Garland, Efficient adaptive simplification of massive meshes, Proceedings of the conference on Visualization '01, October 21-26, 2001, San Diego, California

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:
massive meshes, multiphase simplification, out-of-core simplification, quadric error metrics