“Variational tetrahedral meshing” by Alliez, Cohen-Steiner, Yvinec and Desbrun

In this paper, a novel Delaunay-based variational approach to isotropic tetrahedral meshing is presented. To achieve both robustness and efficiency, we minimize a simple mesh-dependent energy through global updates of both vertex positions and connectivity. As this energy is known to be the ∠1 distance between an isotropic quadratic function and its linear interpolation on the mesh, our minimization procedure generates well-shaped tetrahedra. Mesh design is controlled through a gradation smoothness parameter and selection of the desired number of vertices. We provide the foundations of our approach by explaining both the underlying variational principle and its geometric interpretation. We demonstrate the quality of the resulting meshes through a series of examples.

1. Amenta, N., and Bern, M. 1998. Surface Reconstruction by Voronoi Filtering. In Proc. of 14th Symp. on Computational Geometry (SCG’98), 39–48. Google ScholarDigital Library
2. Amenta, N., Choi, S., Dey.-T., and Leekhau, N. 200. A Simple Algorithm for Homomorphic Surface Reconstruction. In Proceedings of the Symposium on Computational geometry, 213–222. Google ScholarDigital Library
3. Boissonnat, J.-D., and Oudot, S. 2005. Provably Good Sampling and Meshing of Surfaces. Graphical Models (special issue on Solid Modeling). To appear. Google ScholarDigital Library
4. Borouchaki, H., George, P., Hecht, F., Laug, P., and Saltel, E. 1997. Delaunay mesh generation governed by metric specifications. Part 1: Algorithms, Finite Elements in Analysis and Design 25, 61–83. Google ScholarDigital Library
5. Borouchaki, H., George, P., and Mohammadi, B. 1997. Delaunay mesh generation governed by metric specifications. Part 2: Application examples. Finite Elements in Analysis and Design 25, 85–109. Google ScholarDigital Library
6. Carey, G. F. 1997. Computational Grids: Generation, Adaptation, and Solution Strategies. Taylor & Francis eds.Google Scholar
7. Chen, L., and Xu, J. 2004. “Optimal Delaunay triangulations”. Journal of Computational Mathematics 22, 2, 299–308.Google Scholar
8. Chen, L. 2004. Mesh smoothing schemes based on optimal Delaunay triangulations. In Proceedings of 13th International Meshing Roundtable, 109–120.Google Scholar
9. Cheng, S. W., and Dey, T. K. 2002. Quality meshing with weighted Delaunay refinement. In Proc. 13th ACM-SIAM Sympos. Discrete Algorithms, 137–146. Google ScholarDigital Library
10. Cheng, S.-W., and Poon, S.-H. 2003. Graded conforming Delaunay tetrahedralization with bounded radius-edge ratio. In Proc. of the 14th ACM-SIAM Symposium on Discrete algorithms (SODA). 295–304. Google ScholarDigital Library
11. Cheng, S.-W., Dey, T. K., Edelsbrunner, H., Facello, M. A., and Teng, S.-H. 1999. Sliver Exudation. In Proc. 15th ACM Symp. Comput. Geom., 1–13. Google ScholarDigital Library
12. Cheng, S.-W., Dey, T. K., Ramos, E., and Ray, T. 2004. Quality Meshing for Polyhedra with Small Angles. In Proc. of ACM Symp. on Comp. Geom., 290–299. Google ScholarDigital Library
13. Cohen-Steiner, D., De Verdiere, E. C., and Yvinec, M. 2002. Conforming Delaunay triangulations in 3D. In Proc. of Symp. on Comp. Geom., 237–246. Google ScholarDigital Library
14. Cohen-Steiner, D., Alliez, P., and Desbrun, M. 2004. Variational Shape Approximation. ACM Trans. on Graphics (SIGGRAPH), 905–914. Google ScholarDigital Library
15. Cutler, B., Dorsey, J., and McMillan, L. 2004. Simplification and Improvement of Tetrahedral Models for Simulation. In Proceedings of the 2004 Eurographics/ACM SIGGRAPH Symposium on Geometry Processing, 95–104. Google ScholarDigital Library
16. Du, Q., and Wang, D. 2003. Tetrahedral mesh generation and optimization based on centroidal Voronoi tessellations. International Journal on Numerical Methods in Engineering 56(9), 1355–1373.Google ScholarCross Ref
17. Du, Q., Gunzburger, M., and Ju, L. 2003. Constrained Centroidal Voronoi Tessellations for Surfaces. SIAM J. Sci. Comput. 24, 5, 1488–1506. Google ScholarDigital Library
18. Eppstein, D., 2001. Global optimization of mesh quality. Tutorial at the 10th Int. Meshing Roundtable, Newport Beach.Google Scholar
19. Fabri, A., Giezeman, G.-J., Kettner, L., Schirra, S., and Schönherr, S. 2000. On the Design of CGAL, a Computational Geometry Algorithms Library, Softw.–Pract. Exp. 30, 11, 1167–1202. www.cgal.org. Google ScholarDigital Library
20. Freitag, L., and Ollivier-Gooch, C. 1996. A comparison of Tetrahedral Mesh Improvement Techniques. In Proc. of 6th Int. Meshing Roundtable, 87–1000.Google Scholar
21. Frey, J. L., and George, P. L. 2000. Mesh Generation: Applications to Finite Elements. Hermès, Paris. Google ScholarDigital Library
22. Hardin, D. P., and Saff, E. B. 2004. Discretizing Manifolds via Minimum Energy Points. Notices of the AMS 51(10), 1186–1194.Google Scholar
23. Hoppe, H., DeRose, T., Duchamp, T., McDonald, J., and Stuetzle, W. 1993. “Mesh Optimization”. ACM Trans. on Graphics (SIGGRAPH), 19–26. Google ScholarDigital Library
24. Krysl, P., and Ortiz, M. 2001. Variational Delaunay Approach to the Generation of Finite Element Meshes. Int. J. for Num. Meth. in Eng. 50(7), 1681–1700.Google ScholarCross Ref
25. Li, X.-Y., and Teng, S.-H. 2001. Generate Sliver Free Three Dimensional Mesh. In Proc. 12th ACM-SIAM Sympos. Discrete Algorithms.Google Scholar
26. Li, X.-Y., Teng, S.-H., and Ungor, A. 2000. “Biting: Advancing Front Meets Sphere Packing”. Int. J. on Num. Methods in Eng. 49, 1, 61–81.Google ScholarCross Ref
27. Lloyd, S. P. 1957. Least Squares Quantization in PCM’s. Tech. rep., Bell Telephone Laboratories, Murray Hill, NJ.Google Scholar
28. Mitchell, S., and Vavasis, S. 2000. Quality Mesh Generation in Higher Dimensions. SIAM J. Sci. Comput. 29, 1334–1370. Google ScholarDigital Library
29. Molino, N., Bridson, R., Teran, J., and Fedkiw, R. 2003. A Crystalline. Red Green Strategy for Meshing Highly Deformable Objects with Tetrahedra. In Proceedings of the 12th International Meshing Roundtable, 103–114.Google Scholar
30. Ostromoukhov, V. 2001. A simple and efficient error-diffusion algorithm. In Proceedings of ACM SIGGRAPH, 567–572. Google ScholarDigital Library
31. Owen, S. J. 1998. A Survey of Unstructured Mesh Generation Technology. In Proceedings of the 7th International Meshing Roundtable. 239–267.Google Scholar
32. Quadros, W. R., Shimada, K., and Owen, S. J., 2004. 3D Discrete Skeleton Generation by Wave Propagation on PR-Octree for Finite Element Mesh Sizing. Poster, Solid Modeling Conference. Google ScholarDigital Library
33. Ruppert, J. 1993. A New and Simple Algorithm for Quality 2-Dimensional Mesh Generation. In Proc. of the 4th ACM/SIAM Symp. on Disc. Algo. (SODA), 83–92. Google ScholarDigital Library
34. Shewchuk, J. R. 1998. A Condition Guaranteeing the Existence of Higher-Dimensional Constrained Delaunay Triangulations. In Proc. 14th Annu. ACM Sympos, Comput. Geom., 76–85. Google ScholarDigital Library
35. Shewchuk, J. R. 1998. Tetrahedral mesh generation by Delaunay refinement. In Proc. 14th Annu. ACM Sympos. Comput. Geom., 115–126. Google ScholarDigital Library
36. Shewchuk, J. 2002. What Is a Good Linear Element? Interpolation, Conditioning, and Quality Measure, In Proc. of 11th Int. Meshing Roundtable, 115–126.Google Scholar
37. Shewchuk, J. R. 2002. Delaunay Refinement Algorithms for Triangular Mesh Generation, Computational Geometry: Theory and Applications 22, 21–74. Google ScholarDigital Library
38. Surazhsky, V., Alliez, R. and Gotsman, C. 2003. Isotropic Remeshing of Surfaces: a Local Parameterization Approach. In Proc. of 12th Int. Meshing Roundtable.Google Scholar
39. Teng, S.-H., Wong, C. W., and Lee, D. T. 2000. Unstructured Mesh Generation: Theory, Practice, and Perspectives, International Journal Computational Geometry and Applications 10, 3 (June), 227–266.Google ScholarCross Ref
40. Warren, J., Schaefer, S., Hirani, A., and Desbrun, M., 2004. Barycentric Coordinates for Convex Sets. Preprint.Google Scholar