This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Topology, Accuracy, and Quality of Isosurface Meshes Using Dynamic Particles
November/December 2007 (vol. 13 no. 6)
pp. 1704-1711
This paper describes a method for constructing isosurface triangulations of sampled, volumetric, three-dimensional scalar fields. The resulting meshes consist of triangles that are of consistently high quality, making them well suited for accurate interpolation of scalar and vector-valued quantities, as required for numerous applications in visualization and numerical simulation. The proposed method does not rely on a local construction or adjustment of triangles as is done, for instance, in advancing wavefront or adaptive refinement methods. Instead, a system of dynamic particles optimally samples an implicit function such that the particles' relative positions can produce a topologically correct Delaunay triangulation. Thus, the proposed method relies on a global placement of triangle vertices. The main contributions of the paper are the integration of dynamic particles systems with surface sampling theory and PDE-based methods for controlling the local variability of particle densities, as well as detailing a practical method that accommodates Delaunay sampling requirements to generate sparse sets of points for the production of high-quality tessellations.

[1] P. Alliez, D. Cohen-Steiner, M. Yvinec, and M. Desbrun, Variational tetrahedral meshing. ACM Trans. Graph., 24 (3): 617–625, 2005.
[2] N. Amenta and M. Bern, Surface reconstruction by voronoi filtering. Discrete and Computational Geometry, 22: 481–504, 1999.
[3] N. Amenta, M. Bern, and D. Eppstein, The crust and the beta-skeleton: Combinatorial curve reconstruction. Graphic Models and Image Processing, 60 (2 of 2): 125–135, 1998.
[4] N. Amenta, M. Bern, and M. Kamvysselis, A new voronoi-based surface reconstruction algorithm. Siggraph, pages 415–421, 1998.
[5] N. Amenta, S. Choi, T. Dey, and N. Leekha, A simple algorithm for homeomorphic surface reconstruction. In ACM Symposium on Computational Geometry, pages 213–222, 2000.
[6] N. Amenta, S. Choi, and R. K. Kolluri, The power crust. In SMA '01: Proceedings of the sixth ACM symposium on Solid modeling and applications, pages 249–266, New York, NY, USA, 2001. ACM Press.
[7] I. Babuska and A. K. Aziz, On the angle condition in the finite element method. SIAM Journal on Numerical Analysis, 13 (2): 214–226, 1976.
[8] J.-D. Boissonnat and S. Oudot, Provably good sampling and meshing of surfaces. Graph. Models, 67 (5): 405–451, 2005.
[9] S.-W. Cheng, T. K. Dey, E. A. Ramos, and T. Ray, Sampling and meshing a surface with guaranteed topology and geometry. In SCG '04: Proceedings of the twentieth annual symposium on Computational geometry, pages 280–289, New York, NY, USA, 2004. ACM Press.
[10] L. P. Chew, Guaranteed-quality delaunay meshing in 3d (short version). In SCG '97: Proceedings of the thirteenth annual symposium on Computational geometry, pages 391–393, New York, NY, USA, 1997. ACM Press.
[11] S. Cotin, C. Duriez, J. Lenoir, P. Neumann, and S. Dawson, New approaches to catheter navigation for interventional radiology simulation. pages 534–542, Palm Springs, California, USA, 26–30 october 2005.
[12] T. K. Dey and J. Giesen, Detecting undersampling in surface reconstruction. In SCG '01: Proceedings of the seventeenth annual symposium on Computational geometry, pages 257–263, New York, NY, USA, 2001. ACM Press.
[13] T. K. Dey and S. Goswami, Tight cocone: a water-tight surface reconstructor. In SM '03: Proceedings of the eighth ACM symposium on Solid modeling and applications, pages 127–134, New York, NY, USA, 2003. ACM Press.
[14] T. K. Dey and J. A. Levine, Delaunay meshing of isosurfaces. In SMI '07: Proceedings of the IEEE International Conference on Shape Modeling and Applications 2007, pages 241–250, Washington, DC, USA, 2007. IEEE Computer Society.
[15] H. Edelsbrunner and E. P. Mücke, Three-dimensional alpha shapes. ACM Transactions on Graphics, 13 (1): 43–72, 1994.
[16] E. Hartmann, A marching method for the triangulation of surfaces. The Visual Computer, 14 (3): 95–108, 1998.
[17] E. Hartmann, On the curvature of curves and surfaces defined by normal-forms. Comput. Aided Geom. Des., 16 (5): 355–376, 1999.
[18] T. J. R. Hughes, The Finite Element Method. Prentice-Hall, Inc., Englewood Cliffs, New Jersey, 1987.
[19] M. W. Jones, J. A. Baerentzen, and M. Sramek, 3d distance fields: A survey of techniques and applications. IEEE Transactions on Visualization and Computer Graphics, 12 (4): 581–599, 2006.
[20] T. Karkanis and A. J. Stewart, Curvature-dependent triangulation of implicit surfaces. IEEE Computer Graphics and Applications, 22 (2): 60–69, March 2001.
[21] G. Kindlmann, R. Whitaker, T. Tasdizen, and T. Möller, Curvature-based transfer functions for direct volume rendering: Methods and applications. In Proceedings of IEEE Visualization 2003, pages 513–520, October 2003.
[22] H. Krim and A. Yezzi editors. , Statistics and Analysis of Shapes. Birkhauser Boston, 2006.
[23] T. S. Lau and S. H. Lo, Finite element mesh generation over analytic curved surfaces. Computers and Structures, 59 (2): 301–310, 1996.
[24] A. Lee, H. Moreton, and H. Hoppe, Displaced subdivision surfaces. In SIGGRAPH '00: Proceedings of the 27th annual conference on Computer graphics and interactive techniques, pages 85–94, New York, NY, USA, 2000. ACM Press/Addison-Wesley Publishing Co.
[25] W. E. Lorensen and H. E. Cline, Marching cubes: A high resolution 3d surface construction algorithm. In SIGGRAPH '87: Proceedings of the 14th annual conference on Computer graphics and interactive techniques, pages 163–169, New York, NY, USA, 1987. ACM Press.
[26] M. Meyer, P. Georgel, and R. Whitaker, Robust particle systems for curvature dependent sampling of implicit surfaces. In Proceedings of the International Conference on Shape Modeling and Applications (SMI), pages 124–133, June 2005.
[27] M. Meyer, B. Nelson, R. M. Kirby, and R. Whitaker, Particle systems for efficient and accurate high-order finite element visualization. IEEE Transactions on Visualization and Computer Graphics, In Press, 2007.
[28] T. Möller, K. Mueller, Y. Kurzion, R. Machiraju, and R. Yagel, Design of accurate and smooth filters for function and derivative reconstruction. In VVS '98: Proceedings of the 1998 IEEE symposium on Volume visualization, pages 143–151, New York, NY, USA, 1998. ACM Press.
[29] O. Nemitz, M. Rumpf, T. Tasdizen, and R. Whitaker, Anisotropic curvature motion for structure enhancing smoothing of 3D MR angiography data. Journal of Mathematical Imaging and Vision, December 2006. published online.
[30] G. M. Nielson, A. Huang, and S. Sylvester, Approximating normals for marching cubes applied to locally supported isosurfaces. In VIS '02: Proceedings of the conference on Visualization '02, pages 459–466, Washington, DC, USA, 2002. IEEE Computer Society.
[31] P.-O. Persson, Mesh size functions for implicit geometries and pde-based gradient limiting. Eng. with Comput., 22 (2): 95–109, 2006.
[32] J. Ruppert, A new and simple algorithm for quality 2-dimensional mesh generation. In SODA '93: Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, pages 83–92, Philadelphia, PA, USA, 1993. Society for Industrial and Applied Mathematics.
[33] J. Schreiner, C. Scheidegger, and C. Silva, High-quality extraction of isosurfaces from regular and irregular grids. IEEE Transactions on Visualization and Computer Graphics, 12 (5): 1205–1212, 2006.
[34] J. A. Sethian, Curvature flow and entropy conditions applied to grid generation. J. Comput. Phys., 115 (2): 440–454, 1994.
[35] J. A. Sethian, Level Set Methods and Fast Marching Methods. Cambridge Monograph on Applied and Computational Mathematics. Cambridge University Press, 1999.
[36] J. R. Shewchuk, What is a good linear finite element? interpolation, conditioning, anisotropy, and quality measures. Technical Report Manuscript, 2002.
[37] K. Siddiqi, S. Bouix, A. Tannenbaum, and S. W. Zucker, The hamilton-jacobi skeleton. In ICCV '99: Proceedings of the International Conference on Computer Vision-Volume 2, page 828, Washington, DC, USA, 1999. IEEE Computer Society.
[38] T. Tasdizen, R. Whitaker, P. Burchard, and S. Osher, Geometric surface smoothing via anisotropic diffusion of normals. In VIS '02: Proceedings of the conference on Visualization '02, Washington, DC, USA, 2002. IEEE Computer Society.
[39] C. A. Taylor and M. T. Draney, Experimental and computational methods in cardiovascular fluid mechanics. Annual Review of Fluid Mechanics, 36: 197–231, 2004.
[40] C. Touma and C. Gotsman, Triangle mesh compression. In Graphics Interface, pages 26–34, 1998.
[41] R. V. Uitert, C. Johnson, and L. Zhukov, Influence of head tissue conductivity in forward and inverse magnetoencephalographic simulations using realistic head models. IEEE Transactions on Biomedical Engineering, 51 (12): 2129–2137, 2004.
[42] J. J. van Wijk, Image based flow visualization for curved surfaces. In VIS '03: Proceedings of the 14th IEEE Visualization 2003 (VIS'03), page 17, Washington, DC, USA, 2003. IEEE Computer Society.
[43] L. Velho, Simple and efficient polygonization of implicit surfaces. J. Graph. Tools, 1 (2): 5–24, 1996.
[44] A. P. Witkin and P. S. Heckbert, Using particles to sample and control implicit surfaces. In Proceedings of the 21st annual conference on Computer graphics and interactive techniques, pages 269–277. ACM Press, 1994.
[45] Z. J. Wood, P. Schroder, D. Breen, and M. Desbrun, Semi-regular mesh extraction from volumes. In VIS '00: Proceedings of the conference on Visualization '00, pages 275–282, Los Alamitos, CA, USA, 2000. IEEE Computer Society Press.
[46] G. Wyvill, C. McPheeters, and B. Wyvill, Data structure for soft objects. The Visual Computer, (2): 227–234, 1986.
[47] Y. Zhang, G. Xu, and C. Bajaj, Quality meshing of implicit solvation models of biomolecular structures. Comput. Aided Geom. Des., 23 (6): 510–530, 2006.

Index Terms:
Isosurface extraction, particle systems, Delaunay triangulation.
Citation:
Miriah Meyer, Robert M. Kirby, Ross Whitaker, "Topology, Accuracy, and Quality of Isosurface Meshes Using Dynamic Particles," IEEE Transactions on Visualization and Computer Graphics, vol. 13, no. 6, pp. 1704-1711, Nov.-Dec. 2007, doi:10.1109/TVCG.2007.70604
Usage of this product signifies your acceptance of the Terms of Use.