×

Tetrahedral meshing via maximal Poisson-disk sampling. (English) Zbl 1418.65189

Summary: In this paper, we propose a simple yet effective method to generate 3D-conforming tetrahedral meshes from closed 2-manifold surfaces. Our approach is inspired by recent work on maximal Poisson-disk sampling (MPS), which can generate well-distributed point sets in arbitrary domains. We first perform MPS on the boundary of the input domain, we then sample the interior of the domain, and we finally extract the tetrahedral mesh from the samples by using 3D Delaunay or regular triangulation for uniform or adaptive sampling, respectively. We also propose an efficient optimization strategy to protect the domain boundaries and to remove slivers to improve the meshing quality. We present various experimental results to illustrate the efficiency and the robustness of our proposed approach. We demonstrate that the performance and quality (e.g., minimal dihedral angle) of our approach are superior to current state-of-the-art optimization-based approaches.

MSC:

65N50 Mesh generation, refinement, and adaptive methods for boundary value problems involving PDEs
65D17 Computer-aided design (modeling of curves and surfaces)
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Alliez, P.; Cohen-Steiner, D.; Yvinec, M.; Desbrun, M., Variational tetrahedral meshing, Proceedings of ACM SIGGRAPH 2005, ACM Trans. Graph., 24, 3, 617-625, (2005)
[2] Ando, R.; Thürey, N.; Wojtan, C., Highly adaptive liquid simulations on tetrahedral meshes, ACM Trans. Graph., 32, 4, (2013)
[3] Barber, C. B.; Dobkin, D.; Huhdanpaa, H., The quickhull algorithm for convex hulls, ACM Trans. Math. Softw., 22, 4, 469-483, (1996)
[4] Bern, M.; Plassmann, P., Mesh generation, (2000), Elsevier Science
[5] Bolander, J.; Saito, S., Fracture analyses using spring networks with random geometry, Eng. Fract. Mech., 61, 5, 569-591, (1998)
[6] Bronson, J.; Levine, J. A.; Whitaker, R., Lattice cleaving: a multimaterial tetrahedral meshing algorithm with guarantees, IEEE Trans. Vis. Comput. Graph., 20, 2, 223-237, (2014)
[7] CGAL, CGAL, computational geometry algorithms library, (2015)
[8] Chen, L., Mesh smoothing schemes based on optimal Delaunay triangulations, (IMR, (2004)), 109-120
[9] 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)
[10] Cheng, S.-W.; Dey, T. K.; Edelsbrunner, H.; Facello, M. A.; Teng, S.-H., Sliver exudation, J. ACM, 47, 5, 883-904, (2000)
[11] Cheng, S.-W.; Dey, T. K.; Levine, J. A., A practical Delaunay meshing algorithm for a large class of domains, (16th Intl. Meshing Roundtable, (2007)), 477-494
[12] Cheng, S.-W.; Dey, T. K.; Shewchuk, J. R., Delaunay mesh generation, (2012), CRC Press
[13] Chew, L. P., Guaranteed-quality Delaunay meshing in 3D, (Proceedings of the Thirteenth Annual Symposium on Computational Geometry, (1997)), 391-393
[14] Choi, W.-Y.; Kwak, D.-Y.; Son, I.-H.; Im, Y.-T., Tetrahedral mesh generation based on advancing front technique and optimization scheme, Int. J. Numer. Methods Eng., 58, 12, 1857-1872, (2003)
[15] Dardenne, J.; Valette, S.; Siauve, N.; Burais, N.; Prost, R., Variational tetrahedral mesh generation from discrete volume data, Proc. CGI 2009, Vis. Comput., 25, 5, 401-410, (2009)
[16] de Goes, F.; Wallez, C.; Huang, J.; Pavlov, D.; Desbrun, M., Power particles: an incompressible fluid solver based on power diagrams, Proc. SIGGRAPH, ACM Trans. Graph., 34, (2015)
[17] Du, Q.; Wang, D., Tetrahedral mesh generation and optimization based on centroidal Voronoi tessellations, Int. J. Numer. Methods Eng., 56, 9, 1355-1373, (2003)
[18] Du, Q.; Faber, V.; Gunzburger, M., Centroidal Voronoi tessellations: applications and algorithms, SIAM Rev., 41, 637-676, (1999)
[19] Ebeida, M.; Mitchell, S., Uniform random Voronoi meshes, (Quadros, W., Proceedings of the 20th International Meshing Roundtable, (2012), Springer Berlin, Heidelberg), 273-290
[20] Ebeida, M. S.; Davidson, A. A.; Patney, A.; Knupp, P. M.; Mitchell, S. A.; Owens, J. D., Efficient maximal Poisson-disk sampling, Proc. SIGGRAPH, ACM Trans. Graph., 30, 4, (2011)
[21] Ebeida, M. S.; Mitchell, S. A.; Davidson, A. A.; Patney, A.; Knupp, P. M.; Owens, J. D., Efficient and good Delaunay meshes from random points, Comput. Aided Des., 43, 11, 1506-1515, (2011)
[22] Ebeida, M. S.; Mitchell, S. A.; Patney, A.; Davidson, A. A.; Owens, J. D., A simple algorithm for maximal Poisson-disk sampling in high dimensions, Proc. EUROGRAPHICS, Comput. Graph. Forum, 31, 2, 785-794, (2012)
[23] Edelsbrunner, H., Geometry and topology for mesh generation, (2001), Cambridge University Press
[24] Frey, P. J.; George, P.-L., Mesh generation: application to finite elements, (2001), Hermes Science
[25] Geuzaine, C.; Remacle, J.-F., Gmsh: a three-dimensional finite element mesh generator with built-in pre- and post-processing facilities, 79, 11, 1309-1331, (2009)
[26] Guo, J.; Yan, D.-M.; Jia, X.; Zhang, X., Efficient maximal Poisson-disk sampling and remeshing on surfaces, Comput. Graph., 46, 6-8, 72-79, (2015)
[27] Ito, Y.; Shih, A. M.; Soni, B. K., Reliable isotropic tetrahedral mesh generation based on an advancing front method, (IMR, (2004)), 95-106
[28] Jamin, C.; Alliez, P.; Yvinec, M.; Boissonnat, J.-D., Cgalmesh: a generic framework for Delaunay mesh generation, ACM Trans. Math. Softw, (2014)
[29] Jiao, X.; Wang, D.; Zha, H., Simple and effective variational optimization of surface and volume triangulations, Eng. Comput., 27, 1, 81-94, (2011)
[30] Jones, T. R., Efficient generation of Poisson-disk sampling patterns, J. Graph. Tools, 11, 2, 27-36, (2006)
[31] Klingner, B. M.; Shewchuk, J. R., Aggressive tetrahedral mesh improvement, (16th Intl. Meshing Roundtable, (2007)), 3-23
[32] Klingner, B. M.; Feldman, B. E.; Chentanez, N.; O’Brien, J. F., Fluid animation with dynamic meshes, Proc. SIGGRAPH, ACM Trans. Graph., 25, 3, 820-825, (2006)
[33] Labelle, F.; Shewchuk, J. R., Isosurface stuffing: fast tetrahedral meshes with good dihedral angles, Proc. SIGGRAPH, ACM Trans. Graph., 26, 3, (2007)
[34] Lagae, A.; Dutré, P., A comparison of methods for generating Poisson disk distributions, Comput. Graph. Forum, 27, 1, 114-129, (2008)
[35] Owen, S. J., A survey of unstructured mesh generation technology, (International Meshing Roundtable, (1998)), 239-267
[36] Patzák, B.; Rypl, D., Object-oriented, parallel finite element framework with dynamic load balancing, Adv. Eng. Softw., 47, 1, 35-50, (2012)
[37] Schöberl, J., NETGEN an advancing front 2D/3D-mesh generator based on abstract rules, Comput. Vis. Sci., 1, 41-52, (1997)
[38] Shewchuk, J. R., What is a good linear element? interpolation, conditioning, and quality measures, (11th Intl. Meshing Roundtable, (2002)), 115-126
[39] Si, H., Tetgen, a Delaunay-based quality tetrahedral mesh generator, ACM Trans. Math. Softw., 41, 2, (2015)
[40] Tournois, J.; Wormser, C.; Alliez, P.; Desbrun, M., Interleaving Delaunay refinement and optimization for practical isotropic tetrahedron mesh generation, Proc. SIGGRAPH, ACM Trans. Graph., 28, 3, (2009)
[41] Vanderzee, E.; Hirani, A. N.; Guoy, D.; Ramos, E., Well-centered triangulation, SIAM J. Sci. Comput., 31, 6, 4497-4523, (2010)
[42] Yan, D.-M.; Wonka, P., Gap processing for adaptive maximal Poisson-disk sampling, ACM Trans. Graph., 32, 5, (2013)
[43] Yan, D.-M.; Lévy, B.; Liu, Y.; Sun, F.; Wang, W., Isotropic remeshing with fast and exact computation of restricted Voronoi diagram, Comput. Graph. Forum, 28, 5, 1445-1454, (2009)
[44] Yan, D.; Wang, W.; Lévy, B.; Liu, Y., Efficient computation of 3D clipped Voronoi diagram, (Advances in Geometric Modeling and Processing - GMP, (2010)), 269-282
[45] Yan, D.-M.; Wang, W.; Lévy, B.; Liu, Y., Efficient computation of clipped Voronoi diagram for mesh generation, Comput. Aided Des., 45, 4, 843-852, (2013)
[46] Yu, Z.; Wang, J.; Gao, Z.; Xu, M.; Hoshijima, M., New software developments for quality mesh generation and optimization from biomedical imaging data, Comput. Methods Programs Biomed., 113, 1, (2014)
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.