×

zbMATH — the first resource for mathematics

Tetrahedral mesh generation based on node insertion in crystal lattice arrangements and advancing-front-Delaunay triangulation. (English) Zbl 0980.74080
Summary: A method of unstructured tetrahedral mesh generation for general three-dimensional domains is presented. A conventional boundary representation is adopted as the basis for the description of solids with evolving geometry and topology. The geometry of the surfaces is represented either analytically or by piecewise polynomial interpolation. A preliminary surface mesh is generated by an advancing-front method, with the nodes inserted by hard-sphere packing in physical space in accordance with a prescribed mesh density. Interior nodes are inserted in a face-centered-cubic crystal lattice arrangement coupled to octree spatial subdivision, with the local lattice parameter determined by a prespecified nodal density function. Prior to triangulation of the volume, the preliminary surface mesh is preprocessed by a combination of local transformations and subdivision in order to guarantee that the surface triangulation be a subcomplex of the volume Delaunay triangulation. A joint Delaunay triangulation of the interior and boundary nodes which preserves the modified surface mesh is then constructed via an advancing-front approach. The resulting mesh is finally improved upon by the application of local transformations. The overall time complexity of the mesher is \(O(N\log N)\). The robustness and versatility of the approach, as well as the good quality of the resulting meshes, are demonstrated with the aid of selected examples.

MSC:
74S99 Numerical and other methods in solid mechanics
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] Amenta, N.; Bern, M., Surface reconstruction by Voronoi filtering, Discret. comput. geom., 22, 4, 481-504, (1999) · Zbl 0939.68138
[2] Baker, T.J., Automatic mesh generation for complex three-dimensional regions using a constrained Delaunay triangulation, Engrg. comput., 5, 161-175, (1989)
[3] Beall, M.W.; Shephard, M.S., A general topology-based mesh data structure, Int. J. numer. methods engrg., 40, 1573-1596, (1997)
[4] Borouchaki, H.; Lo, S.H., Fast Delaunay triangulation in three dimensions, Comput. methods appl. mech. engrg., 128, 153-167, (1995) · Zbl 0859.65149
[5] Bowyer, A., Computing Dirichlet tesslations, Comput. J., 24, 2, 162-166, (1981)
[6] Buratynski, E.G., Fully automatic three-dimensional mesh generator for complex geometries, Int. J. numer. methods engrg., 30, 931-952, (1990)
[7] Camacho, G.T.; Ortiz, M., Adaptive Lagrangian modelling of ballistic penetration of metallic targets, Comput. methods appl. mech. engrg., 142, 269-301, (1997) · Zbl 0892.73056
[8] Cavendish, J.C.; Field, D.A.; Frey, W.H., An approach to automatic three-dimensional finite element mesh generation, Int. J. numer. methods engrg., 21, 329-347, (1985) · Zbl 0573.65090
[9] Chan, C.T.; Anastasiou, K., An automatic tetrahedral mesh generation scheme by the advancing-front method, Commun. appl. numer. methods, 13, 33-46, (1997) · Zbl 0873.65103
[10] Chazelle, B., Application challenges to computational geometry: impact task force report, Technical report TR-521-96, (1996), Princeton University
[11] Chew, P., Constrained Delaunay triangulations, (1987), ACM New York
[12] Ciarlet, P.G., Numerical analysis of the finite element method, (1976), Les Presses de L’Universite de Montreal Quebec, Canada · Zbl 0436.73081
[13] Dari, E.A., Contribuciones a la triangulaci’on autom’atica de dominios tridimensionales, Ph.D. thesis, (1994), Instituto Balseiro Bariloche, Argentina
[14] Delaunay, B., Sur la sphere vide, Classe sci. mat. nat. vol.VII bull. acad. sci. USSR, VIII, 793-800, (1934) · JFM 60.0946.06
[15] Dyn, N.; Levin, D., A butterfly subdivision scheme for surface interpolation with tension control, AMC trans. graphics, 9, 160-169, (1990) · Zbl 0726.68076
[16] Farestam, S.; Simpson, R.B., A framework for advancing-front techniques of finite element mesh generation, Bit, 35, 210-232, (1995) · Zbl 0831.65128
[17] Fleischmann, P.; Selberherr, S., Three-dimensional Delaunay mesh generator using a modified advancing-front approach, (), 267-276
[18] Freitag, L.; Ollivier-Gooch, C., A comparison of tetrahedral mesh improvement techniques, (), 87-100
[19] George, P.L.; Hermeline, F., Delaunay’s mesh of a convex polyhedron in dimension d. application to arbitrary polyhedra, Int. J. numer. methods engrg., 33, 975-995, (1992) · Zbl 0762.65111
[20] Guillemin, V.; Pollack, A., Differential topology, (1974), Prentice-Hall Englewood Cliffs, NJ · Zbl 0361.57001
[21] Hammond, C., Introduction to crystallography, (1990), Oxford University Press Oxford
[22] Hazlewood, C., Approximating constrained tetrahedrizations, Comput. aided geometric design, 10, 67-87, (1993) · Zbl 0772.65099
[23] Hoffmann, C.M., Geometric and solid modeling, (1989), Morgan Kaufmann Publishers San Mateo, California
[24] Hull, D.; Bacon, D.J., ()
[25] Jin, H.; Tanner, R.I., Generation of unstructured tetrahedral meshes by advancing-front technique, Int. J. numer. methods engrg., 36, 1805-1823, (1993) · Zbl 0771.76057
[26] Joe, B., Three-dimensional triangulations from local transformations, SIAM J. scientific statist. comput., 10, 718-741, (1989) · Zbl 0681.65087
[27] Joe, B., Construction of three-dimensional improved-quality triangulations using local transformations, SIAM J. scientific comput., 16, 6, 1292-1307, (1995) · Zbl 0851.65081
[28] Lau, T.S.; Lo, S.H., Finite element mesh generation over analytical curved surfaces, Comput. struct., 59, 2, 301-309, (1996) · Zbl 0925.65179
[29] Liu, A.; Joe, B., Relation between tetrahedron shape measures, Bit, 34, 268-287, (1994) · Zbl 0806.65104
[30] Lo, S.H., Finite element mesh generation over curved surfaces, Comput. struct., 29, 5, 731-742, (1988) · Zbl 0666.73052
[31] Lo, S.H., Volume discretization into tetrahedra - II. 3D triangulation by advancing-front approach, Comput. struct., 39, 5, 501-511, (1991) · Zbl 0764.65073
[32] Lo, S.H., Volume discretization into tetrahedra - I. verification and orientation of boundary surfaces, Comput. struct., 39, 5, 493-500, (1991) · Zbl 0764.65072
[33] Lo, S.H., Automatic mesh generation over intersecting surfaces, J. numer. methods engrg., 38, 943-954, (1995) · Zbl 0822.65008
[34] Löhner, R., Some useful data structures for the generation of unstructured grids, Commun. appl. numer. methods, 4, 123-135, (1988) · Zbl 0643.65075
[35] Löhner, R., Finite elements in CFD: grid generation, adaptivity and parallelization, AGARD report, vol. 787, (1992), (Chapter 8)
[36] Löhner, R., Regridding surface triangulations, J. comput. phys., 126, 1-10, (1996) · Zbl 0862.65010
[37] Löhner, R.; Parikh, P., Generation of three-dimensional unstructure grids by the advancing-front method, Int. J. numer. methods fluids, 8, 1135-1149, (1988) · Zbl 0668.76035
[38] Mantyla, M., An introduction to solid modeling, (1988), Computer Science Press Rockville, Maryland
[39] Mavriplis, D.J., An advancing-front Delaunay triangulation algorithm designed for robustness, paper 93-0671, Aiaa, (1993)
[40] Mavriplis, D.J., Unstructured mesh generation and adaptivity, technical report 95-26, Nasa, (1995)
[41] Merriam, M.L., An efficient advancing-front algorithm for Delaunay triangulation, paper 91-0792, Aiaa, (1991)
[42] Möller, P.; Hansbo, P., An advancing-front mesh generation in three dimensions, Int. J. numer. methods engrg., 38, 3551-3569, (1995) · Zbl 0835.73093
[43] Ortiz, M.; Pandolfi, A., Finite-deformation cohesive elements for three-dimensional crack-propagation, Int. J. numer. meth. eng., 44, 9, 1267-1282, (1999) · Zbl 0932.74067
[44] Pandolfi, A.; Ortiz, M., Solid modeling aspects of three-dimensional fragmentation, Eng. comput., 14, 4, 287-308, (1998) · Zbl 0933.68141
[45] Parthasarathy, V.N.; Graichen, C.M.; Hathaway, A.F., A comparison of tetrahedron quality measures, finite elements and design, 15, 225-261, (1993)
[46] Peraire, J.; Peiro, J.; Formaggia, L.; Morgan, K.; Zienkiewicz, O.C., Finite element Euler computations in three dimensions, Int. J. numer. methods engrg., 26, 2135-2159, (1988) · Zbl 0665.76073
[47] Peraire, J.; Vahdati, M.; Morgan, K.; Zienkiewicz, O.C., Adaptive remeshing for compressible flow computations, J. comput. phys., 72, 449-466, (1987) · Zbl 0631.76085
[48] Perucchio, R.; Saxena, M.; Kela, A., Automatic mesh generations from solid models based on recursive spatial decompositions, Int. J. numer. methods engrg., 28, 2469-2501, (1989) · Zbl 0712.68099
[49] Radovitzky, R.; Ortiz, M., Lagrangian finite element analysis of Newtonian fluid flows, Int. J. numer. methods engrg., 43, 607-619, (1998) · Zbl 0945.76047
[50] Radovitzky, R.; Ortiz, M., Error estimation and adaptive meshing in strongly nonlinear dynamic problems, Comput. methods appl. mech. engrg., 172, 203-240, (1999) · Zbl 0957.74058
[51] Rajan, V.T., Optimality of the Delaunay triangulation in R^{d}, discrete & computational geometry, 12, 189-202, (1994) · Zbl 0808.52012
[52] Requicha, A.A.G., Representations for rigid solids: theory methods and systems, Comput. surveys, 12, 437-465, (1980)
[53] Rypl, D.; Krysl, P., Triangulation of 3d surfaces, Engrg. comput., 13, 2, 87-98, (1997)
[54] Samet, H., The design and analysis of spatial data structures, (1990), Addison-Wesley New York
[55] Schroeder, W.J.; Shephard, M.S., Geometry-based fully automatic mesh generation and the Delaunay triangulation, Int. J. numer methods engrg., 26, 2503-2515, (1988) · Zbl 0662.73052
[56] Schroeder, W.J.; Shephard, M.S., A combined octree/Delaunay method for fully automatic 3-d mesh generation, Int. J. numer. methods engrg., 29, 37-55, (1990) · Zbl 0719.68086
[57] Shephard, M.S.; Georges, M.K., Automatic three-dimensional mesh generation by the finite octree technique, Int. J. numer. methods engrg., 32, 4, 709-749, (1991) · Zbl 0755.65116
[58] Standish, T.A., Data structures, algorithms and software principles in C, (1995), Addison-Wesley New York · Zbl 0853.68080
[59] Tanemura, M.; Ogawa, T.; Ogita, N., A new algorithm for three-dimensional Voronoi tesselation, J. comput. phys., 51, 2, 191-207, (1983) · Zbl 0529.05016
[60] Watson, D.F., Computing the n-dimensional Delaunay tesslation with application to Voronoi polytopes, Comput. J., 24, 2, 167-172, (1981)
[61] Weatherill, N.P.; Hassan, O., Efficient three-dimensional Delaunay triangulation with automatic point creation and imposed boundary constraints, Int. J. numer. methods engrg., 37, 2005-2039, (1994) · Zbl 0806.76073
[62] Weatherill, N.P., The reconstruction of boundary contours and surfaces in arbitrary unstructured triangular and tetrahedral grids, Engrg. comput., 13, 8, 66-81, (1996) · Zbl 0983.74540
[63] Wright, J.P.; Jack, A.G., Aspects of three-dimensional constrained Delaunay meshing, Int. J. numer. methods engrg., 37, 1841-1861, (1994) · Zbl 0806.65116
[64] Yerry, M.A.; Shephard, M.S., Automatic mesh generation for three-dimensional solids, Comput. struct., 20, 211-223, (1985)
[65] Zorin, D.; Schroeder, P.; Sweldens, W., Interpolating subdivision for meshes with arbitrary topology, Siggraph ’96, (1996)
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.