WIAS Preprint No. 1976, (2014)

Higher-quality tetrahedral mesh generation for domains with small angles by constrained Delaunay refinement


  • Shewchuk, Jonathan Richard
  • Si, Hang

2010 Mathematics Subject Classification

  • 65M50 65N50 65D18


  • constrained Delaunay triangulation, Delaunay refinement algorithm, tetrahedral mesh generation, computational geometry


Algorithms for generating Delaunay tetrahedral meshes have difficulty with domains whose boundary polygons meet at small angles. The requirement that all tetrahedra be Delaunay often forces mesh generators to overrefine near small domain angles---that is, to produce too many tetrahedra, making them too small. We describe a provably good algorithm that generates 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 sqrt2 / 3 doteq 1.63$ or better. This is a substantial improvement over the usual bound of $2$; it is obtained by relaxing the conditions in which boundary triangles are subdivided. 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. Our algorithm tends to generate meshes with fewer tetrahedra than purely Delaunay methods because it uses the constrained Delaunay property, rather than 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.

Appeared in

  • Proceedings of the Thirtieth Annual Symposium on Computational Geometry, Association for Computing Machinery, New York, NY, USA, 2014, pp. 290--299

Download Documents