| | This Article | | | |
| | | | Share | | | |
| | | | Bibliographic References | | | |
| | | | Add to: | | | |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| | | | Search | | | |
| | | | |
Edge Transformations for Improving Mesh Quality of Marching Cubes
January/February 2009 (vol. 15 no. 1) pp. 150-159
Marching Cubes is a popular choice for isosurface extraction from regular grids due to its simplicity, robustness, and efficiency. One of the key shortcomings of this approach is the quality of the resulting meshes, which tend to have many poorly shaped and degenerate triangles. This issue is often addressed through post processing operations such as smoothing. As we demonstrate in experiments with several datasets, while these improve the mesh, they do not remove all degeneracies, and incur an increased and unbounded error between the resulting mesh and the original isosurface. Rather than modifying the resulting mesh, we propose a method to modify the grid on which Marching Cubes operates. This modification greatly increases the quality of the extracted mesh. In our experiments, our method did not create a single degenerate triangle, unlike any other method we experimented with. Our method incurs minimal computational overhead, requiring at most twice the execution time of the original Marching Cubes algorithm in our experiments. Most importantly, it can be readily integrated in existing Marching Cubes implementations, and is orthogonal to many Marching Cubes enhancements (particularly, performance enhancements such as out-of-core and acceleration structures). [1] E. Artzy, G. Frieder, and G.T. Herman, “The Theory, Design, Implementation and Evaluation of a Three-Dimensional Surface Detection Algorithm,” Proc. ACM SIGGRAPH '80, pp. 2-9, 1980.
[2] C.L. Bajaj, V. Pascucci, and D.R. Schikore, “Fast Isocontouring for Improved Interactivity,” Proc. Symp. Volume Visualization (VolVis '96), pp. 39-46, 1996.
[3] L. Balmelli, C.J. Morris, G. Taubin, and F. Bernardini, “Volume Warping for Adaptive Isosurface Extraction,” Proc. IEEE Visualization (VIS '02), pp. 467-474, 2002.
[4] H. Carr, T. Möller, and J. Snoeyink, “Artifacts Caused by Simplicial Subdivision,” IEEE Trans. Visualization and Computer Graphics, vol. 12, no. 2, pp. 231-242, Mar./Apr. 2006.
[5] H. Carr, T. Theussl, and T. Möller, “Isosurfaces on Optimal Regular Samples,” Proc. Symp. Data Visualisation (VISSYM '03), pp. 39-48, 2003.
[6] L.-S. Chen, G.T. Herman, R.A. Reynolds, and J.K. Udupa, “Surface Shading in the Cuberille Environment,” IEEE Computer Graphics and Applications, vol. 5, no. 12, pp. 33-43, 1985.
[7] P. Cignoni, C. Montani, E. Puppo, and R. Scopigno, “Optimal Isosurface Extraction from Irregular Volume Data,” Proc. Symp. Volume Visualization (VolVis '96), pp. 31-38, 1996.
[8] P. Cignoni, C. Rocchini, and R. Scopigno, “Metro: Measuring Error on Simplified Surfaces,” Computer Graphics Forum, vol. 17, no. 2, pp. 167-174, 1998.
[9] P. Crossno and E. Angel, “Isosurface Extraction Using Particle Systems,” Proc. IEEE Visualization (VIS '97), pp. 495-498, 1997.
[10] L.H. de Figueiredo, J. de Miranda Gomes, D. Terzopoulos, and L. Velho, “Physically-Based Methods for Polygonization of Implicit Surfaces,” Proc. Graphics Interface (GI '92), pp. 250-257, 1992.
[11] A. Doi and A. Koide, “An Efficient Method of Triangulating Equivalued Surfaces by Using Tetrahedral Cells,” IEICE Trans. Comm. and Electronics Information Systems, vol. E74, no. 1, pp. 214-224, Jan. 1991.
[12] M. Garland and P.S. Heckbert, “Surface Simplification Using Quadric Error Metrics,” Proc. ACM SIGGRAPH '97, pp. 209-216, 1997.
[13] M. Gavriliu, J. Carranza, D. Breen, and A. Barr, “Fast Extraction of Adaptive Multiresolution Meshes with Guaranteed Properties from Volumetric Data,” Proc. IEEE Visualization (VIS '01), pp. 295-302, 2001.
[14] The Visualization Handbook, C.D. Hansen and C.R. Johnson, eds., Academic Press, 2004.
[15] G.T. Herman and J.K. Udupa, “Display of 3D Digital Images: Computational Foundations and Medical Applications,” IEEE Computer Graphics and Applications, vol. 3, pp. 39-46, 1983.
[16] T. Ju, F. Losasso, S. Schaefer, and J. Warren, “Dual Contouring of Hermite Data,” Proc. ACM SIGGRAPH '02, pp. 339-346, 2002.
[17] 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.
[18] F. Labelle and J. Shewchuk, “Isosurface Stuffing: Fast Tetrahedral Meshes with Good Dihedral Angles,” ACM Trans. Graphics, vol. 26, 2007.
[19] T. Lewiner, H. Lopes, A.W. Vieira, and G. Tavares, “Efficient Implementation of Marching Cubes' Cases with Topological Guarantees,” J. Graphics Tools, vol. 8, no. 2, pp. 1-15, 2003.
[20] Y. Livnat and X. Tricoche, “Interactive Point-Based Isosurface Extraction,” Proc. IEEE Visualization (VIS '04), pp. 457-464, 2004.
[21] A. Lopes and K. Brodlie, “Improving the Robustness and Accuracy of the Marching Cubes Algorithm for Isosurfacing,” IEEE Trans. Visualization and Computer Graphics, vol. 9, no. 1, pp.16-29, Jan.-Mar. 2003.
[22] W. Lorensen and H. Cline, “Marching Cubes: A High-Resolution 3D Surface Construction Algorithm,” Proc. ACM SIGGRAPH '87, pp. 163-169, 1987.
[23] S.V. Matveyev, “Approximation of Isosurface in the Marching Cube: Ambiguity Problem,” Proc. IEEE Visualization (VIS '94), pp.288-292, 1994.
[24] G.M. Nielson, “Dual Marching Cubes,” Proc. IEEE Visualization (VIS '04), pp. 489-496, 2004.
[25] G.M. Nielson and B. Hamann, “The Asymptotic Decider: Resolving the Ambiguity in Marching Cubes,” Proc. IEEE Visualization (VIS '91), pp. 83-91, 1991.
[26] P.P. Pebay and T.J. Baker, “A Comparison of Triangle Quality Measures,” Proc. 10th Int'l Meshing Roundtable (IMR '01), pp. 327-340, 2001.
[27] S. Schaefer, T. Ju, and J. Warren, “Manifold Dual Contouring,” IEEE Trans. Visualization and Computer Graphics, vol. 13, no. 3, pp.610-619, May/June 2007.
[28] J. Schreiner, C. Scheidegger, and C.T. Silva, “High-Quality Extraction of Isosurfaces from Regular and Irregular Grids,” IEEE Trans. Visualization and Computer Graphics, vol. 12, no. 5, pp. 1205-1212, Sept./Oct. 2006.
[29] H.-W. Shen, C.D. Hansen, Y. Livnat, and C.R. Johnson, “Isosurfacing in Span Space with Utmost Efficiency (ISSUE),” Proc. IEEE Visualization (VIS '96), pp. 287-294, 1996.
[30] J.R. Shewchuk, “What is a Good Linear Element? Interpolation, Conditioning, and Quality Measures,” Proc. 11th Int'l Meshing Roundtable (IMR '02), pp. 115-126, 2002.
[31] H. Si, “On Refinement of Constrained Delaunay Tetrahedralizations,” Proc. 15th Int'l Meshing Roundtable (IMR '06), pp. 509-528, 2006.
[32] H. Si and K. Gaertner, “Meshing Piecewise Linear Complexes by Constrained Delaunay Tetrahedralizations,” Proc. 14th Int'l Meshing Roundtable (IMR '05), pp. 147-163, 2005.
[33] G.M. Treece, R.W. Prager, and A.H. Gee, “Regularised Marching Tetrahedra: Improved Iso-Surface Extraction,” Computers and Graphics, vol. 23, pp. 583-598, 1999.
[34] L. Tzeng, “Warping Cubes: Better Triangles from Marching Cubes,” Proc. 20th European Workshop Computational Geometry (EWCG '04), 2004.
[35] A. van Gelder and J. Wilhelms, “Topological Considerations in Isosurface Generation,” ACM Trans. Graphics, vol. 13, no. 4, pp.337-375, 1994.
[36] J. Wilhelms and A.V. Gelder, “Octrees for Faster Isosurface Generation,” ACM Trans. Graphics, vol. 11, no. 3, pp. 201-227, 1992.
[37] A.P. Witkin and P.S. Heckbert, “Using Particles to Sample and Control Implicit Surfaces,” Proc. ACM SIGGRAPH '94, pp. 269-277, 1994.
Index Terms:
Curve, surface, solid, and object representations, Applications, Visual
Citation:
Carlos A. Dietrich, Carlos E. Scheidegger, John Schreiner, João L.D. Comba, Luciana P. Nedel, Cláudio T. Silva, "Edge Transformations for Improving Mesh Quality of Marching Cubes," IEEE Transactions on Visualization and Computer Graphics, vol. 15, no. 1, pp. 150-159, Jan./Feb. 2009, doi:10.1109/TVCG.2008.60 Usage of this product signifies your acceptance of the Terms of Use.
|
