| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
Streaming Simplification of Tetrahedral Meshes
January/February 2007 (vol. 13 no. 1)
pp. 145-155
Abstract—Unstructured tetrahedral meshes are commonly used in scientific computing to represent scalar, vector, and tensor fields in three dimensions. Visualization of these meshes can be difficult to perform interactively due to their size and complexity. By reducing the size of the data, we can accomplish real-time visualization necessary for scientific analysis. We propose a two-step approach for streaming simplification of large tetrahedral meshes. Our algorithm arranges the data on disk in a streaming, I/O-efficient format that allows coherent access to the tetrahedral cells. A quadric-based simplification is sequentially performed on small portions of the mesh in-core. Our output is a coherent streaming mesh which facilitates future processing. Our technique is fast, produces high quality approximations, and operates out-of-core to process meshes too large for main memory.
[1] 145 A. Mascarenhas, M. Isenburg, V. Pascucci, and J. Snoeyink, “Encoding Volumetric Grids for Streaming Isosurface Extraction,” Proc. Int'l Symp. 3D Data Processing, Visualization, and Transmission, 2004.[2] M. Isenburg, P. Lindstrom, and J. Snoeyink, “Streaming Compression of Triangle Meshes,” Proc. 2005 Eurographics/ACM SIGGRAPH Symp. Geometry Processing, pp. 111-118, 2005.[3] I.J. Trotts, B. Hamann, K.I. Joy, and D.F. Wiley, “Simplification of Tetrahedral Meshes,” Proc. IEEE Visualization Conf. '98, pp. 287-295, 1998.[4] I.J. Trotts, B. Hamann, and K.I. Joy, “Simplification of Tetrahedral Meshes with Error Bounds,” IEEE Trans. Visualization and Computer Graphics, vol. 5, no. 3, pp. 224-237, July-Sept. 1999.[5] A. Van Gelder, V. Verna, and J. Wilhelms, “Volume Decimation of Irregular Tetrahedral Grids,” Computer Graphics Int'l, pp. 222-230, 1999.[6] D. Uesu, L. Bavoil, S. Fleishman, J. Shepherd, and C.T. Silva, “Simplification of Unstructured Tetrahedral Meshes by Point-Sampling,” Volume Graphics, pp. 157-238, 2005.[7] H. Hoppe, “Progressive Meshes,” Proc. ACM SIGGRAPH '96, pp.99-108, 1996.[8] J. Popović and H. Hoppe, “Progressive Simplicial Complexes,” Proc. 24th Ann. Conf. Computer Graphics and Interactive Techniques, pp. 217-224, 1997.[9] O.G. Staadt and M.H. Gross, “Progressive Tetrahedralizations,” Proc. IEEE Visualization Conf. '98, pp. 397-402, 1998.[10] P. Chopra and J. Meyer, “TetFusion: An Algorithm for Rapid Tetrahedral Mesh Simplification,” Proc. IEEE Visualization Conf. '02, pp. 133-140, 2002.[11] P. Cignoni, D. Constanza, C. Montani, C. Rocchini, and R. Scopigno, “Simplification of Tetrahedral Meshes with Accurate Error Evaluation,” Proc. IEEE Visualization Conf. '00, pp. 85-92, 2000.[12] M. Garland and P.S. Heckbert, “Surface Simplification Using Quadric Error Metrics,” Proc. ACM SIGGRAPH '97, pp. 209-216, 1997.[13] V. Natarajan and H. Edelsbrunner, “Simplification of Three-Dimensional Density Maps,” IEEE Trans. Visualization and Computer Graphics, vol. 10, no. 5, pp. 587-597, Sept./Oct. 2004.[14] M. Garland and Y. Zhou, “Quadric-Based Simplification in Any Dimension,” ACM Trans. Graphics, vol. 24, no. 2, Apr. 2005.[15] P. Lindstrom, “Out-Of-Core Simplification of Large Polygonal Models,” Proc. 27th Ann. Conf. Computer Graphics and Interactive Techniques, pp. 259-262, 2000.[16] J. Rossignac and P. Borrel, Geometric Modeling in Computer Graphics, chapter on multiresolution 3D approximations for rendering complex scenes, pp. 455-465. Springer-Verlag, 1993.[17] P. Lindstrom and C.T. Silva, “A Memory Insensitive Technique for Large Model Simplification,” Proc. IEEE Visualization Conf. '01, pp. 121-126, 2001.[18] J. Wu and L. Kobbelt, “A Stream Algorithm for the Decimation of Massive Meshes,” Proc. Graphics Interface Conf. '03, pp. 185-192, 2003.[19] M. Isenburg, P. Lindstrom, S. Gumhold, and J. Snoeyink, “Large Mesh Simplification Using Processing Sequences,” Proc. IEEE Visualization Conf. '03, pp. 465-472, 2003.[20] M. Isenburg and P. Lindstrom, “Streaming Meshes,” Proc. IEEE Visualization Conf. '05, pp. 231-238, Oct. 2005.[21] M. Cox and D. Ellsworth, “Application-Controlled Demand Paging for Out-of-Core Visualization,” Proc. IEEE Visualization Conf. '97, pp. 235-244, 1997.[22] P. Cignoni, C. Montani, C. Rocchini, and R. Scopigno, “External Memory Management and Simplification of Huge Meshes,” IEEE Trans. Visualization and Computer Graphics, vol. 9, no. 4, pp. 525-537, Oct.-Dec. 2003.[23] S.-E. Yoon, P. Lindstrom, V. Pascucci, and D. Manocha, “Cache-Oblivious Mesh Layouts,” ACM Trans. Graphics, vol. 24, no. 3, pp.886-893, 2005.[24] J. Rossignac, “3D Compression Made Simple: Edgebreaker with Zip&Wrap on a Corner-Table,” Proc. Int'l Conf. Shape Modeling & Applications, p. 278, 2001.[25] B. Cutler, J. Dorsey, and L. McMillan, “Simplification and Improvement of Tetrahedral Models for Simulation,” Proc. Eurographics/ACM SIGGRAPH Symp. Geometry Processing, pp. 93-102, 2004.[26] L.P. Kobbelt, M. Botsch, U. Schwanecke, and H.-P. Seidel, “Feature-Sensitive Surface Extraction from Volume Data,” Proc. ACM SIGGRAPH '01, pp. 57-66, 2001.[27] T. Ju, F. Losasso, S. Schaefer, and J. Warren, “Dual Contouring of Hermite Data,” ACM Trans. Graphics, vol. 21, no. 3, pp. 339-346, July 2002.[28] P. Lindstrom, “Out-of-Core Construction and Visualization of Multiresolution Surfaces,” Proc. ACM Symp. Interactive 3DGraphics, pp. 93-102, 2003.[29] G.H. Golub and C.F. Van Loan, Matrix Computations, third ed. Johns Hopkins Univ. Press, 1996.[30] P. Cignoni, C. Rocchini, and R. Scopigno, “Metro: Measuring Error on Simplified Surfaces,” Computer Graphics Forum, vol. 17, no. 2, pp. 167-174, 1998.
Index Terms:
Computational geometry and object modeling, out-of-core algorithms, streaming algorithms, mesh simplification, large meshes, tetrahedral meshes.
Citation:
Huy T. Vo, Steven P. Callahan, Peter Lindstrom, Valerio Pascucci, Cl?udio T. Silva, "Streaming Simplification of Tetrahedral Meshes," IEEE Transactions on Visualization and Computer Graphics, vol. 13, no. 1, pp. 145-155, Jan./Feb. 2007, doi:10.1109/TVCG.2007.21
