Footnote:
Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
Description:
Most algorithms for guaranteed-quality tetrahedral mesh generation create Delaunay meshes. Delaunay triangulations have many good properties, but the requirement that all tetrahedra be Delaunay often forces mesh generators to overrefine where boundary polygons meet at small angles---that is, they produce too many tetrahedra, making them too small. Relaxing the Delaunay property makes it possible both to reduce overrefinement and to obtain higher-quality tetrahedra. We describe a provably good algorithm that generates high-quality meshes that are constrained Delaunay triangulations, rather than purely Delaunay. Given a piecewise linear domain free of small angles, our algorithm is guaranteed to construct a mesh in which every tetrahedron has a radius-edge ratio of 2 √2/3 = 1.63 or less. This is a substantial improvement over the usual bound of 2; it is obtained by relaxing the conditions in which the algorithm subdivides boundary triangles. Given a domain with small angles, our algorithm produces a mesh in which the quality guarantee is compromised only in specific places near small domain angles. We prove that most mesh edges have lengths proportional to the domain's minimum local feature size; the exceptions span small domain angles or lie on domain edges that participate in small angles. Our algorithm tends to generate meshes with fewer tetrahedra than purely Delaunay methods because it uses the constrained Delaunay property, not just vertex insertions, to enforce the conformity of the mesh to the domain boundaries. An implementation demonstrates that our algorithm does not overrefine near small domain angles.