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

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