×

zbMATH — the first resource for mathematics

Tetrahedral mesh generation and optimization based on centroidal Voronoi tessellations. (English) Zbl 1106.74431
Summary: The centroidal Voronoi tessellation based Delaunay triangulation (CVDT) provides an optimal distribution of generating points with respect to a given density function and accordingly generates a high-quality mesh. In this paper, we discuss algorithms for the construction of the constrained CVDT from an initial Delaunay tetrahedral mesh of a three-dimensional domain. By establishing an appropriate relationship between the density function and the specified sizing field and applying the Lloyd’s iteration, the constrained CVDT mesh is obtained as a natural global optimization of the initial mesh. Simple local operations such as edges/faces flippings are also used to further improve the CVDT mesh. Several complex meshing examples and their element quality statistics are presented to demonstrate the effectiveness and efficiency of the proposed mesh generation and optimization method.

MSC:
74S99 Numerical and other methods in solid mechanics
74E30 Composite and mixture properties
65N50 Mesh generation, refinement, and adaptive methods for boundary value problems involving PDEs
65M50 Mesh generation, refinement, and adaptive methods for the numerical solution of initial value and initial-boundary value problems involving PDEs
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Lohner, International Journal for Numerical Methods in Fluids 8 pp 1135– (1988) · Zbl 0661.65017
[2] Moller, International Journal for Numerical Methods in Engineering 38 pp 3551– (1995)
[3] Rassineux, International Journal for Numerical Methods in Engineering 41 pp 647– (1998)
[4] Marcum, David, AIAA Journal 33 pp 1619– (1995)
[5] Shephard, International Journal for Numerical Methods in Engineering 32 pp 709– (1991)
[6] Borouchaki, International Journal for Numerical Methods in Engineering 49 pp 233– (2000)
[7] Frey, Computer Methods in Applied Mechanics and Engineering 157 pp 115– (1998)
[8] Borouchaki, International Journal for Numerical Methods in Engineering 39 pp 3407– (1996)
[9] Borouchaki, Computer Methods in Applied Mechanics and Engineering 128 pp 153– (1995)
[10] George, Computer Methods in Applied Mechanics and Engineering 92 pp 268– (1991)
[11] Weatherill, International Journal for Numerical Methods in Engineering 37 pp 2005– (1994)
[12] Delaunay refinement mesh generation. PhD Dissertation, Computer Science Department, Carnegie Mellon University, 1997.
[13] Wright, International Journal for Numerical Methods in Engineering 37 pp 1841– (1994)
[14] Delaunay Triangulation and Meshing: Application to Finite Elements. Editions HERMES: Paris, 1998. · Zbl 0908.65143
[15] Amenta, Journal of Algorithms 30 pp 302– (1999)
[16] Freitag, International Journal for Numerical Methods in Engineering 40 pp 3979– (1997)
[17] Zavattieri, International Journal for Numerical Methods in Engineering 39 pp 2055– (1996)
[18] Dari, Structural Optimization 8 pp 181– (1994)
[19] Cheng, Journal of the ACM 47 pp 883– (2000)
[20] A Delaunay based numerical method for 3 dimensions: generation, formulation, and partition. In Proceedings of the 27th ACM Symposium on Theory and Computing 1995; 683-692. · Zbl 0978.68575
[21] Smoothing and cleaning up slivers, Proceedings of the 32nd ACM Symposium on Theory and Computing 2000; 273-277. · Zbl 1296.68175
[22] Buscaglia, International Journal for Numerical Methods in Engineering 40 pp 4119– (1997)
[23] Du, SIAM Review 41 pp 637– (1999)
[24] Meshfree probabilistic determination of point sets and support regions for meshless computing. Computer Methods in Applied Mechanics and Engineering, 2001, accepted for publication.
[25] Grid generation and optimization based on centroidal Voronoi tessellations. Applied and Computational Mathematics, 2001, accepted for publication.
[26] Lloyd, IEEE Transactions on Information Theory 28 pp 129– (1982)
[27] Lohner, Journal of Computational Physics 126 pp 1– (1996)
[28] Hartmann, The Visual Computer 14 pp 95– (1998)
[29] Sheng, Computer-Aided Design 24 pp 437– (1992)
[30] Anisotropic triangular meshing of parametric surfaces via close packing of ellipsoidal bubbles. Sixth International Meshing Roundtable 97 Proceedings, 1997; 63-74.
[31] Advancing front surface mesh generation in parametric space using a Riemannian surface definition. Seventh International Meshing Roundtable, 98Proceedings, 1998; 429-445.
[32] Mesh generation. Handbook of Computational Geometry. Elsevier: Amsterdam, 2000; 291-332. · doi:10.1016/B978-044482537-7/50007-3
[33] Spatial tessellations: Concept and Application of Voronoi Diagrams. Wiley: Chichester, 1992.
[34] Aurenhammer, ACM Computing Surveys 23 pp 345– (1991)
[35] Constrained centroidal Voronoi tessellations on general surfaces. SIAM Journal on Scientific Computing, 2001, submitted for publication.
[36] Du, Journal of Parallel Computing 28 pp 1477– (2002)
[37] Babuska, SIAM Journal on Numerical Analysis 15 pp 736– (1978)
[38] Gersho, IEEE Transactions on Information Theory 25 pp 373– (1979)
[39] Gray, IEEE Transactions on Information Theory 44 pp 2325– (1998)
[40] Baker, Engineering Computations 5 pp 161– (1989)
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.