Sliver-suppressing tetrahedral mesh optimization with gradient-based shape matching energy. (English) Zbl 1366.65043

Summary: In this paper, a novel shape matching energy is proposed to suppress slivers for tetrahedral mesh generation. Given a volumetric domain with a user-specified template (regular) simplex, the tetrahedral meshing problem is transformed into a shape matching formulation with a gradient-based energy, i.e., the gradient of linear shape function. It effectively inhibits small heights and suppresses all the badly-shaped tetrahedrons in tetrahedral meshes. The proposed approach iteratively optimizes vertex positions and mesh connectivity, and makes the simplices in the computed mesh as close as possible to the template simplex. We compare our results qualitatively and quantitatively with the state-of-the-art algorithm in tetrahedral meshing on extensive models using the standard measurement criteria.


65D18 Numerical aspects of computer graphics, image analysis, and computational geometry
65N50 Mesh generation, refinement, and adaptive methods for boundary value problems involving PDEs


Netgen; CGALmesh
Full Text: DOI


[1] Alliez, P.; Cohen-Steiner, D.; Yvinec, M.; Desbrun, M., Variational tetrahedral meshing, ACM Trans. Graph., 24, 3, 617-625, (2005)
[2] Chen, L.; Xu, J.-C., Optimal Delaunay triangulations, J. Comput. Math., 299-308, (2004) · Zbl 1048.65020
[3] Chen, Z.; Wang, W.; Lévy, B.; Liu, L.; Sun, F., Revisiting optimal Delaunay triangulation for 3D graded mesh generation, SIAM J. Sci. Comput., 36, 3, A930-A954, (2014) · Zbl 1298.49049
[4] Cheng, S.-W.; Dey, T.; Edelsbrunner, H.; Facello, M.; Teng, S.-H., Sliver exudation, J. ACM, 47, 5, 883-904, (2000) · Zbl 1320.68210
[5] Cheng, S.-W.; Dey, T.; Shewchuk, J., Delaunay mesh generation, (2012), Chapman and Hall/CRC
[6] Chew, L. P., Guaranteed-quality Delaunay meshing in 3D, (Proceedings of the 13th Annual Symposium on Computational Geometry, (1997)), 391-393
[7] Du, Q.; Wang, D., Tetrahedral mesh generation and optimization based on centroidal Voronoi tessellations, Int. J. Numer. Methods Biomed. Eng., 56, 9, 1355-1373, (2003) · Zbl 1106.74431
[8] Du, Q.; Wang, D., Anisotropic centroidal Voronoi tessellations and their applications, SIAM J. Sci. Comput., 26, 3, 737-761, (2005) · Zbl 1121.65306
[9] Du, Q.; Faber, V.; Gunzburger, M., Centroidal Voronoi tessellations: applications and algorithms, SIAM Rev., 41, 4, 637-676, (1999) · Zbl 0983.65021
[10] Freitag, L.; Knupp, P., Tetrahedral mesh improvement via optimization of the element condition number, Int. J. Numer. Methods Biomed. Eng., 53, 6, 1377-1391, (2002) · Zbl 1112.74512
[11] Guo, J.; Yan, D.-M.; Chen, L.; Zhang, X.; Deussen, O.; Wonka, P., Tetrahedral meshing via maximal Poisson-disk sampling, Comput. Aided Geom. Des., 43, 186-199, (2016) · Zbl 1418.65189
[12] Ito, Y.; Shih, A.; Soni, B., Reliable isotropic tetrahedral mesh generation based on an advancing front method, (Proceedings of 13th International Meshing Roundtable, (2004)), 95-106
[13] Jamin, C.; Alliez, P.; Yvinec, M.; Boissonnat, J.-D., Cgalmesh: a generic framework for Delaunay mesh generation, ACM Trans. Math. Softw., 41, 4, 23:1-23:24, (2015) · Zbl 1347.65047
[14] Klingner, B. M.; Shewchuk, J. R., Aggressive tetrahedral mesh improvement, (Proceedings of 16th International Meshing Roundtable, (2007)), 3-23 · Zbl 1238.65011
[15] Knupp, P., Algebraic mesh quality metrics, SIAM J. Sci. Comput., 23, 1, 193-218, (2001) · Zbl 0996.65101
[16] Labelle, F.; Shewchuk, J. R., Isosurface stuffing: fast tetrahedral meshes with good dihedral angles, ACM Trans. Graph., 26, 3, 57.1-57.10, (2007)
[17] Li, X.-Y.; Teng, S.-H.; Üngör, A., Biting: advancing front meets sphere packing, Int. J. Numer. Methods Biomed. Eng., 49, 1-2, 61-81, (2000) · Zbl 0966.65096
[18] Neil Molino, J. T.; Bridson, Robert; Fedkiw, R., A crystalline, red Green strategy for meshing highly deformable objects with tetrahedra, (Proceedings of 12th International Meshing Roundtable, (2003)), 103-114
[19] Owen, S. J., A survey of unstructured mesh generation technology, (Proceedings of 7th International Meshing Roundtable, (1998)), 239-267
[20] Schöberl, J., NETGEN an advancing front 2D/3D-mesh generator based on abstract rules, Comput. Vis. Sci., 1, 1, 41-52, (1997) · Zbl 0883.68130
[21] Shewchuk, J. R., What is a good linear element? interpolation, conditioning, and quality measures, (11th International Meshing Roundtable, (2002)), 115-126
[22] Shewchuk, J.R., 2002b. Two discrete optimization algorithms for the topological improvement of tetrahedral meshes. Unpublished Manuscript 65.
[23] Si, H., Tetgen, a Delaunay-based quality tetrahedral mesh generator, ACM Trans. Math. Softw., 41, 2, 11:1-11:36, (2015) · Zbl 1369.65157
[24] Tournois, J.; Srinivasan, R.; Alliez, P., Perturbing slivers in 3D Delaunay meshes, (Proceedings of 18th International Meshing Roundtable, (2009)), 157-173
[25] Yan, D.-M.; Lévy, B.; Liu, Y.; Sun, F.; Wang, W., Isotropic remeshing with fast and exact computation of restricted Voronoi diagram, (Proceedings of the Symposium on Geometry Processing, (2009)), 1445-1454
[26] Yan, D.-M.; Wang, W.; Lévy, B.; Liu, Y., Efficient computation of 3D clipped Voronoi diagram, (Proceedings of the 6th International Conference on Advances in Geometric Modeling and Processing, (2010)), 269-282
[27] Zhong, Z.; Guo, X.; Wang, W.; Lévy, B.; Sun, F.; Liu, Y.; Mao, W., Particle-based anisotropic surface meshing, ACM Trans. Graph., 32, 4, 1-14, (2013) · Zbl 1305.68294
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.