| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
High-Quality Extraction of Isosurfaces from Regular and Irregular Grids
September-October 2006 (vol. 12 no. 5)
pp. 1205-1212
Isosurfaces are ubiquitous in many fields, including visualization, graphics, and vision. They are often the main computational component of important processing pipelines (e.g. , surface reconstruction), and are heavily used in practice. The classical approach to compute isosurfaces is to apply the Marching Cubes algorithm, which although robust and simple to implement, generates surfaces that require additional processing steps to improve triangle quality and mesh size. An important issue is that in some cases, the surfaces generated by Marching Cubes are irreparably damaged, and important details are lost which can not be recovered by subsequent processing. The main motivation of this work is to develop a technique capable of constructing high-quality and high-fidelity isosurfaces. We propose a new advancing front technique that is capable of creating high-quality isosurfaces from regular and irregular volumetric datasets. Our work extends the guidance field framework of Schreiner et al. to implicit surfaces, and improves it in significant ways. In particular, we describe a set of sampling conditions that guarantee that surface features will be captured by the algorithm. We also describe an efficient technique to compute a minimal guidance field, which greatly improves performance. Our experimental results show that our technique can generate high-quality meshes from complex datasets.
[1] 1205 S. Akkouche and E. Galin, Adaptive implicit surface polygonization using marching triangles. Comput. Graph. Forum, 20 (2): 67–80, 2001.[2] P. Alliez, D. Cohen-Steiner, M. Yvinec, and M. Desbrun, Variational tetrahedral meshing. ACM Trans. Graph., 24 (3): 617–625, 2005.[3] P. Alliez, G. Ucelli, C. Gotsman, and M. Attene, Recent advances in remeshing of surfaces. In State-of-the-art report of the AIM@SHAPE EU network. Springer, 2005.[4] N. Amenta and M. W. Bern, Surface reconstruction by voronoi filtering. In Symposium on Computational Geometry, pages 39–48, 1998.[5] C. L. Bajaj, J. Chen, and G. Xu, Modeling with cubic a-patches. ACM Trans. Graph., 14 (2): 103–133, 1995.[6] C. L. Bajaj, V. Pascucci, and D. R. Schikore, Fast isocontouring for improved interactivity. In 1996 Volume Visualization Symposium, pages 39–46, 1996.[7] F. Bernardini, J. Mittleman, H. Rushmeier, C. Silva, and G. Taubin, The ball-pivoting algorithm for surface reconstruction. IEEE Transactions on Visualization and Computer Graphics, 5 (4): 349–359, 1999.[8] J. Bloomenthal, An implicit surface polygonizer. In P. Heckbert, editor, Graphics Gems IV, pages 324–349. Academic Press, Boston, 1994.[9] J. Bloomenthal, editor. Introduction to Implicit Surfaces. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1997.[10] H. Borouchaki, F. Hecht, and P. J. Frey, Mesh gradation control. In 6th International Meshing Roundtable, pages 131–141, 1997.[11] E. Catmull and R. Rom, Computer Aided Geometric Design, chapter A Class of Local Interpolating Splines. Academic Press, 1974.[12] J. R. Cebral and R. Löhner, From medical images to CFD meshes. In 8th International Meshing Roundtable, pages 321–331, 1999.[13] M. Cermák and V. Skala, Adaptive edge spinning algorithm for poligonization of implicit surfaces. In Computer Graphics International, pages 36–43, 2004.[14] P. Cignoni, F. Ganoveii, C. Montani, and R. Scopigno, Reconstruction of topologically correct and adaptive trilinear isosurfaces. Computers & Graphics, 24 (3): 399–418, 2000.[15] P. Cignoni, P. Marino, C. Montani, E. Puppo, and R. Scopigno, Speeding up isosurface extraction using interval trees. IEEE Transactions on Visualization and Computer Graphics, 3 (2): 158–170, 1997.[16] P. Cignoni, C. Montani, E. Puppo, and R. Scopigno, Optimal isosurface extraction from irregular volume data. 1996 Volume Visualization Symposium, pages 31–38, 1996. ISBN 0-89791-741-3.[17] R. Courant and F. John, Introduction to Calculus and Analysis, volume 2. John Wiley and sons, 1974.[18] P. Crossno and E. Angel, Isosurface extraction using particle systems. In R. Yagel and H. Hagen, editors, IEEE Visualization 1997, pages 495–498, 1997.[19] W. Dahmen, C. A. Micchelli, and H.-P. Seidel, Blossoming begets bsplines built better by b-patches. Math. Comp., 59 (199): 97–115, 1992.[20] L. H. de Figueiredo, J. Gomes, D. Terzopolous, and L. Velho, Physically-based methods for polygonization of implicit surfaces. In Graphics Interface, 1992.[21] M. Garland and P. S. Heckbert, Surface simplification using quadric error metrics. In SIGGRAPH 1997, pages 209–216, 1997.[22] I. Guskov and Z. Wood, Topological noise removal. In Graphics Interface, 2001.[23] E. Hartmann, A marching method for the triangulation of surfaces. The Visual Computer, 14 (3): 95–108, 1998.[24] A. Hilton, A. Stoddart, J. Illingworth, and T. Windeatt, Marching triangles: Range image fusion for complex object modelling. International Conference on Image Processing, B: 381–384, 1996.[25] T. Ju, F. Losasso, S. Schaefer, and J. Warren, Dual contouring of hermite data. ACM Transactions on Graphics, 21 (3): 339–346, 2002.[26] T. Karkanis and A. J. Stewart, Curvature-dependent triangulation of implicit surfaces. IEEE Computer Graphics and Applications, 21 (2): 60–69, 2001.[27] G. Kindlmann, R. Whitaker, T. Tasdizen, and T. Möller, Curvature-based transfer functions for direct volume rendering: Methods and applications. In IEEE Visualization, 2003.[28] P. Lancaster and K. Salkauskas, Surfaces generated by moving least squares methods. Mathematics of Computation, 87: 141–158, 1981.[29] M. Levoy, K. Pulli, B. Curless, S. Rusinkiewicz, D. Koller, L. Pereira, M. Ginzton, S. Anderson, J. Davis, J. Ginsberg, J. Shade, and D. Fulk, The digital michelangelo project: 3D scanning of large statues. In SIGGRAPH 2000, pages 131–144, 2000.[30] P. Lindstrom, Out-of-core simplification of large polygonal models. In SIGGRAPH 2000, pages 259–262. ACM Press/Addison-Wesley Publishing Co., 2000.[31] Y. Livnat, H. Shen, and C. Johnson, A near optimal isosurface extraction algorithm using the span space. IEEE Transactions on Visualization and Computer Graphics, 2 (1): 73–84, 1996.[32] Y. Livnat and X. Tricoche, Interactive point-based isosurface extraction. In IEEE Visualization, pages 457–464, 2004.[33] W. Lorensen and H. Cline, Marching Cubes: A high-resolution 3D surface construction algorithm. In SIGGRAPH 1987, pages 163–169, 1987.[34] M. Meyer, P. Georgel, and R. Whitaker, Robust particle systems for curvature dependent sampling of implicit surfaces. In International Conference on Shape Modeling and Applications, pages 123–133, 2005.[35] B. K. Natarajan, On generating topologically consistent isosurfaces from uniform samples. The Visual Computer, 11 (1): 52–62, 1994.[36] B. Nelson and R. M. Kirby, Ray-tracing polymorphic multi-domain spectral/hp elements for isosurface rendering. IEEE Transactions in Visualization and Computer Graphics, 12 (1): 114–125, 2006.[37] G. Nielson, On marching cubes. IEEE Transactions on Visualization and Computer Graphics, 9 (3): 283–297, 2003.[38] G. Nielson, H. Hagen, and H. Müller, Scientific Visualization, chapter 20. IEEE Computer Society, 1997.[39] G. M. Nielson and B. Hamann, The asymptotic decider: Removing the ambiguity in marching cubes. In IEEE Visualization, pages 83–91, 1991.[40] P. Ning and J. Bloomenthal, An evaluation of implicit surface tilers. IEEE Computer Graphics and Applications, 13 (6): 33–41, 1993.[41] S. Owen, A survey of unstructured mesh generation technology. http://www.andrew.cmu.edu/user/sowen/survey index.html.[42] L. Piegl and W. Tiller, The NURBS book. Springer, 1997.[43] J. Ruppert, A new and simple algorithm for quality 2-dimensional mesh generation. In Symposium on Discrete Algorithms, 1993.[44] C. E. Scheidegger, S. Fleishman, and C. T. Silva, Triangulating point set surfaces with bounded error. In Symposium on Geometry Processing, pages 63–72, 2005.[45] J. Schreiner, C. Scheidegger, S. Fleishman, and C. Silva, Direct (re)meshing for efficient surface processing. Comput. Graph. Forum (Proceedings of Eurographics 2006), 2006. to appear.[46] C. T. Silva and J. S. B. Mitchell, Greedy cuts: An advancing front terrain triangulation algorithm. In ACM-GIS, pages 137–144, 1998.[47] G. Treece, R. Prager, and A. Gee, Regularised marching tetrahedra: Improved iso-surface extraction. Computers & Graphics, 23 (4): 583–598, 1999.[48] G. Turk, Re-tiling polygonal surfaces. In SIGGRAPH 1992, pages 55–64, 1992.[49] J. Wilhelms and A. V. Gelder, Octrees for faster isosurface generation. ACM Transactions on Graphics, 11 (3): 201–227, 1992.[50] A. P. Witkin and P. S. Heckbert, Using particles to sample and control implicit surfaces. In SIGGRAPH 1994, pages 269–277, 1994.[51] Z. J. Wood, P. Schröder, D. Breen, and M. Desbrun, Semi-regular mesh extraction from volumes. In IEEE Visualization, pages 275–282, 2000.
Index Terms:
Isosurface Extraction, Curvature, Advancing Front
Citation:
John Schreiner, Carlos Scheidegger, Claudio Silva, "High-Quality Extraction of Isosurfaces from Regular and Irregular Grids," IEEE Transactions on Visualization and Computer Graphics, vol. 12, no. 5, pp. 1205-1212, Sept. 2006, doi:10.1109/TVCG.2006.149
