“Interleaving Delaunay refinement and optimization for practical isotropic tetrahedron mesh generation” by Tournois, Wormser, Alliez and Desbrun

  • ©Jane Tournois, Camille Wormser, Pierre Alliez, and Mathieu Desbrun




    Interleaving Delaunay refinement and optimization for practical isotropic tetrahedron mesh generation



    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.


    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.Google Scholar
    2. Alliez, P., Cohen-Steiner, D., Yvinec, M., and Desbrun, M. 2005. Variational Tetrahedral Meshing. In Proc. of ACM SIGGRAPH 2005, vol. 24(3), 617–625. Google ScholarDigital Library
    3. Amenta, N., Bern, M., and Eppstein, D. 1999. Optimal Point Placement for Mesh Smoothing. J. of Algorithms 30, 2, 302–322. Google ScholarDigital Library
    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.Google Scholar
    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.Google Scholar
    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.Google ScholarCross Ref
    7. Chen, L., and Xu, J. 2004. Optimal Delaunay triangulations. J. of Comp. Mathematics 22, 2, 299–308.Google Scholar
    8. Chen, L. 2004. Mesh Smoothing Schemes based on Optimal Delaunay Triangulations. In Proc. of the 13th Int. Meshing Roundtable, 109–120.Google Scholar
    9. Cheng, S., Dey, T., Edelsbrunner, H., Facello, M., and Teng, S. 2000. Sliver Exudation. J. of the ACM 47, 5, 883–904. Google ScholarDigital Library
    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.Google Scholar
    11. Cheng, S., Dey, T., and Ramos, E. 2007. Delaunay Refinement for Piecewise Smooth Complexes. In Proc. of the 18th Symp. on Discrete Algorithms, 1096–1105. Google ScholarDigital Library
    12. Chew, L. 1989. Guaranteed-Quality Triangular Meshes. Tech. rep., Dept. of Computer Science, Cornell Univ.Google Scholar
    13. Chew, L. 1993. Guaranteed-quality Mesh Generation for Curved Surfaces. In Proc. of the 9th Symp. on Comp. Geometry, ACM NY, USA, 274–280. Google ScholarDigital Library
    14. Du, Q., Faber, V., and Gunzburger, M. 1999. Centroidal Voronoi tesselations. SIAM Review 41, 4, 637–676. Google ScholarDigital Library
    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.Google ScholarCross Ref
    16. George, P.-L. 2004. Tetmesh-GHS3D, Tetrahedral Mesh Generator. INRIA User’s Manual, INRIA (Institut National de Recherche en Informatique et Automatique), France.Google Scholar
    17. Klingner, B., and Shewchuk, J. 2007. Aggressive Tetrahedral Mesh Improvement. In Proc. of the 16th Int. Meshing Roundtable, 3–23.Google Scholar
    18. Labelle, F., and Shewchuk, J. 2007. Isosurface Stuffing: Fast Tetrahedral Meshes with Good Dihedral Angles. In ACM Transactions on Graphics, vol. 26(3), No. 57. Google ScholarDigital Library
    19. Li, X. 2000. Sliver-free 3-Dimensional Delaunay Mesh Generation. PhD thesis, University of Illinois at Urbana-Champaign. Google ScholarDigital Library
    20. Nave, D., Chrisochoides, N., and Chew, L. 2002. Guaranteed Quality Parallel Delaunay Refinement for Restricted Polyhedral Domains. Proc. of the 18th Symp. on Comp. Geometry, 135–144. Google ScholarDigital Library
    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.Google Scholar
    22. Persson, P., and Strang, G. 2004. A Simple Mesh Generator in MATLAB. SIAM Review, 329–346.Google Scholar
    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.Google Scholar
    24. Shewchuk, J. 2002. Delaunay Refinement Algorithms for Triangular Mesh Generation. Comp. Geometry: Theory and Applications 22, 1–3, 21–74. Google ScholarDigital Library
    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.Google Scholar
    26. Si, H., 2007. TetGen, A Quality Tetrahedral Mesh Generator and 3-Dimensional Delaunay Triangulator. http://tetgen.berlios.de/.Google Scholar
    27. Terdiman, P., 2005. OPCODE 3D Collision Detection library. http://www.codercorner.com/Opcode.htm.Google Scholar
    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.Google Scholar
    29. Tournois, J. 2009. Mesh Optimization. PhD thesis, INRIA, Univ. de Nice Sophia Antipolis, France.Google Scholar
    30. Wendt, J. D., Baxter, W., Oguz, I., and Lin, M. C. 2007. Finite Volume Flow Simulations on Arbitrary Domains. Graphical Models 69, 1, 19–32. Google ScholarDigital Library
    31. Wu, J., and Kobbelt, L. 2002. Fast Mesh Decimation by Multiple-Choice Techniques. Vision, Modeling, and Visualization 2002, 241–249.Google Scholar

ACM Digital Library Publication: