Premium
Variational Delaunay approach to the generation of tetrahedral finite element meshes
Author(s) -
Krysl Petr,
Ortiz Michael
Publication year - 2001
Publication title -
international journal for numerical methods in engineering
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.421
H-Index - 168
eISSN - 1097-0207
pISSN - 0029-5981
DOI - 10.1002/nme.91
Subject(s) - delaunay triangulation , constrained delaunay triangulation , pitteway triangulation , bowyer–watson algorithm , vertex (graph theory) , tetrahedron , mathematics , surface triangulation , minimum weight triangulation , chew's second algorithm , polygon mesh , triangulation , combinatorics , boundary (topology) , algorithm , geometry , graph , mathematical analysis
We describe an algorithm which generates tetrahedral decomposition of a general solid body, whose surface is given as a collection of triangular facets. The principal idea is to modify the constraints in such a way as to make them appear in an unconstrained triangulation of the vertex set à priori . The vertex set positions are randomized to guarantee existence of a unique triangulation which satisfies the Delaunay empty‐sphere property. (Algorithms for robust, parallelized construction of such triangulations are available.) In order to make the boundary of the solid appear as a collection of tetrahedral faces, we iterate two operations, edge flip and edge split with the insertion of additional vertex, until all of the boundary facets are present in the tetrahedral mesh. The outcome of the vertex insertion is another triangulation of the input surfaces, but one which is represented as a subset of the tetrahedral faces. To determine if a constraining facet is present in the unconstrained Delaunay triangulation of the current vertex set, we use the results of Rajan which re‐formulate Delaunay triangulation as a linear programming problem. Copyright © 2001 John Wiley & Sons, Ltd.