Out-of-core simplification of large polygonal models

ABSTRACT

We present an algorithm for out-of-core simplification of large polygonal datasets that are too complex to fit in main memory. The algorithm extends the vertex clustering scheme of Rossignac and Borrel [13] by using error quadric information for the placement of each cluster's representative vertex, which better preserves fine details and results in a low mean geometric error. The use of quadrics instead of the vertex grading approach in [13] has the additional benefits of requiring less disk space and only a single pass over the model rather than two. The resulting linear time algorithm allows simplification of datasets of arbitrary complexity. In order to handle degenerate quadrics associated with (near) flat regions and regions with zero Gaussian curvature, we present a robust method for solving the corresponding underconstrained least-squares problem. The algorithm is able to detect these degeneracies and handle them gracefully. Key features of the simplification method include a bounded Hausdorff error, low mean geometric error, high simplification speed (up to 100,000 triangles/second reduction), output (but not input) sensitive memory requirements, no disk space overhead, and a running time that is independent of the order in which vertices and triangles occur in the mesh.

REFERENCES

• 1: ACKERMAN, M. J. The Visible Human Project. In Proceedings of the IEEE, 86(3), March 1998, pp. 504-511. Project URL: http://ww~nlm.nih.gov/ research/visible.
• 2: BERNARDINI, F., MITTLEMAN, J., and RUSHMEIER, H. Case Study: Scanning Michelangelo's Florentine Pieth. In ACM SIGGRAPH 99 Course Notes, Course 8, August 1999. Project URL: http://www.research.ibm, com/pieta.
• 3: Fausto Bernardini , Joshua Mittleman , Holly Rushmeier , Cláudio Silva , Gabriel Taubin, The Ball-Pivoting Algorithm for Surface Reconstruction, IEEE Transactions on Visualization and Computer Graphics, v.5 n.4, p.349-359, October 1999 [doi>10.1109/2945.817351]
• 4: Yi-Jen Chiang , Cláudio T. Silva , William J. Schroeder, Interactive out-of-core isosurface extraction, Proceedings of the conference on Visualization '98, p.167-174, October 18-23, 1998, Research Triangle Park, North Carolina, United States
• 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, 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
• 7: LEVOY, M. The Digital Michelangelo Project. In proceedings of the Second international Conference on 3D Digital imaging and Modeling, October 1999, pp. 2-11. Project URL: http://graphics.stanford, edu/ projects~ mich.
• 8: 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
• 9: 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]
• 10: Matt Pharr , Craig Kolb , Reid Gershbein , Pat Hanrahan, Rendering complex scenes with memory-coherent ray tracing, Proceedings of the 24th annual conference on Computer graphics and interactive techniques, p.101-108, August 1997 [doi>10.1145/258734.258791]
• 11: 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
• 12: RONFARD, R. and ROSSIGNAC, J. Full-Range Approximation of Triangulated Polyhedra. Proceedings of Eurographics 96. In Computer Graphics Forum, 15(3), August 1996, pp. 67-76.
• 13: ROSSIGNAC, J. and BORREL, P. Multi-Resolution 3D Approximations for Rendering Complex Scenes. In Modeling in Computer Graphics, edited by B. Falcidieno and T. L. Kunii, Springer-Verlag, 1993, pp. 455-465.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Matrix inversion

General Terms:
Algorithms, Design, Measurement, Performance, Theory