Interleaving Delaunay refinement and optimization for practical isotropic tetrahedron mesh generation

ABSTRACT

We present a practical approach to isotropic tetrahedral meshing of 3D domains bounded by piecewise smooth surfaces. Building upon recent theoretical and practical advances, our algorithm interleaves Delaunay refinement and mesh optimization to generate quality meshes that satisfy a set of user-defined criteria. This interleaving is shown to be more conservative in number of Steiner point insertions than refinement alone, and to produce higher quality meshes than optimization alone. A careful treatment of boundaries and their features is presented, offering a versatile framework for designing smoothly graded tetrahedral meshes.

REFERENCES

• 1: Acar, U., Hudson, B., Miller, G., and Phillips, T. 2007. SVR: Practical Engineering of a Fast 3D Meshing Algorithm. In Proc. of 16th Int. Meshing Roundtable, 45--62.
• 2: Pierre Alliez , David Cohen-Steiner , Mariette Yvinec , Mathieu Desbrun, Variational tetrahedral meshing, ACM SIGGRAPH 2005 Papers, July 31-August 04, 2005, Los Angeles, California
• 3: Nina Amenta , Marshall Bern , David Eppstein, Optimal point placement for mesh smoothing, Journal of Algorithms, v.30 n.2, p.302-322, Feb. 1999 [doi>10.1006/jagm.1998.0984]
• 4: Antani, L., Delage, C., and Alliez, P. 2007. Mesh Sizing with Additively Weighted Voronoi Diagrams. In Proc. of the 16th Int. Meshing Roundtable, 335--346.
• 5: Boissonnat, J.-D., Wormser, C., and Yvinec, M. 2007. Curved Voronoi diagrams. In Effective Comp. Geometry for Curves and Surfaces, Springer, Ed. 67--116.
• 6: Boivin, C., and Ollivier-Gooch, C. 2002. Guaranteed-quality Triangular Mesh Generation for Domains with Curved Boundaries. Int. J. Numer. Methods Eng. 55, 1185--1213.
• 7: Chen, L., and Xu, J. 2004. Optimal Delaunay triangulations. J. of Comp. Mathematics 22, 2, 299--308.
• 8: Chen, L. 2004. Mesh Smoothing Schemes based on Optimal Delaunay Triangulations. In Proc. of the 13th Int. Meshing Roundtable, 109--120.
• 9: Siu-Wing Cheng , Tamal K. Dey , Herbert Edelsbrunner , Michael A. Facello , Shang-Hua Teng, Silver exudation, Journal of the ACM (JACM), v.47 n.5, p.883-904, Sept. 2000 [doi>10.1145/355483.355487]
• 10: Cheng, S., Dey, T., and Levine, J. 2007. A Practical Delaunay Meshing Algorithm for a Large Class of Domains. In Proc. of the 16th Int. Meshing Roundtable, 477--494.
• 11: Siu-Wing Cheng , Tamal K. Dey , Edgar A. Ramos, Delaunay refinement for piecewise smooth complexes, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.1096-1105, January 07-09, 2007, New Orleans, Louisiana
• 12: Chew, L. 1989. Guaranteed-Quality Triangular Meshes. Tech. rep., Dept. of Computer Science, Cornell Univ.
• 13: L. Paul Chew, Guaranteed-quality mesh generation for curved surfaces, Proceedings of the ninth annual symposium on Computational geometry, p.274-280, May 18-21, 1993, San Diego, California, United States [doi>10.1145/160985.161150]
• 14: Qiang Du , Vance Faber , Max Gunzburger, Centroidal Voronoi Tessellations: Applications and Algorithms, SIAM Review, v.41 n.4, p.637-676, Dec. 1999 [doi>10.1137/S0036144599352836]
• 15: Freitag, L., and Ollivier-Gooch, C. 1997. Tetrahedral Mesh Improvement using Swapping and Smoothing. Int. J. for Num. Methods in Eng. 40, 21, 3979--4002.
• 16: George, P.-L. 2004. Tetmesh-GHS3D, Tetrahedral Mesh Generator. INRIA User's Manual, INRIA (Institut National de Recherche en Informatique et Automatique), France.
• 17: Klingner, B., and Shewchuk, J. 2007. Aggressive Tetrahedral Mesh Improvement. In Proc. of the 16th Int. Meshing Roundtable, 3--23.
• 18: François Labelle , Jonathan Richard Shewchuk, Isosurface stuffing: fast tetrahedral meshes with good dihedral angles, ACM Transactions on Graphics (TOG), v.26 n.3, July 2007
• 19: Xiangyang Li , Shang-Hua Teng, Sliver-free three dimensional delaunay mesh generation, University of Illinois at Urbana-Champaign, Champaign, IL, 2001
• 20: Démian Nave , Nikos Chrisochoides , L. Paul Chew, Guaranteed: quality parallel delaunay refinement for restricted polyhedral domains, Proceedings of the eighteenth annual symposium on Computational geometry, p.135-144, June 05-07, 2002, Barcelona, Spain [doi>10.1145/513400.513418]
• 21: Oudot, S., Rineau, L., and Yvinec, M. 2005. Meshing Volumes Bounded by Smooth Surfaces. In Proc. of the 14th Int. Meshing Roundtable, 203--219.
• 22: Persson, P., and Strang, G. 2004. A Simple Mesh Generator in MATLAB. SIAM Review, 329--346.
• 23: Rineau, L., and Yvinec, M. 2007. Meshing 3D Domains Bounded by Piecewise Smooth Surfaces. In Proc. of the 16th Int. Meshing Roundtable, 443--460.
• 24: Shewchuk, J. 2002. Delaunay Refinement Algorithms for Triangular Mesh Generation. Comp. Geometry: Theory and Applications 22, 1--3, 21--74.
• 25: Shewchuk, J. 2002. What is a Good Linear Element? Interpolation, Conditioning, and Quality Measures. In Proc. of the 11th Int. Meshing Roundtable, 115--126.
• 26: Si, H., 2007. TetGen, A Quality Tetrahedral Mesh Generator and 3-Dimensional Delaunay Triangulator. http://tetgen.berlios.de/.
• 27: Terdiman, P., 2005. OPCODE 3D Collision Detection library. http://www.codercorner.com/Opcode.htm.
• 28: Tournois, J., Alliez, P., and Devillers, O. 2007. Interleaving Delaunay Refinement and Optimization for 2D Triangle Mesh Generation. In Proc. of the 16th Int. Meshing Roundtable.
• 29: Tournois, J. 2009. Mesh Optimization. PhD thesis, INRIA, Univ. de Nice Sophia Antipolis, France.
• 30: Jeremy D. Wendt , William Baxter , Ipek Oguz , Ming C. Lin, Finite volume flow simulations on arbitrary domains, Graphical Models, v.69 n.1, p.19-32, January, 2007 [doi>10.1016/j.gmod.2006.05.004]
• 31: Wu, J., and Kobbelt, L. 2002. Fast Mesh Decimation by Multiple-Choice Techniques. Vision, Modeling, and Visualization 2002, 241--249.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.4 IMAGE PROCESSING AND COMPUTER VISION
      I.4.1 Digitization and Image Capture

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.1 Interpolation

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.3 Picture/Image Generation
      I.3.5 Computational Geometry and Object Modeling

General Terms:
Algorithms, Design, Theory

Keywords:
Delaunay refinement, graded meshing, isotropic meshing, mesh generation, mesh optimization