Generating well-shaped Delaunay meshed in 3D

Xiang-Yang Li, Shang-Hua Teng

Abstract

A triangular mesh in 3D is a decomposition of a given geometric domain into tetrahedra. The mesh is well-shaped if the aspect ratio of every of its tetrahedra is bounded from above by a constant. It is Delaunay if the interior of the circum-sphere of each of its tetrahedra does not contain any other mesh vertices. Generating a well-shaped Delaunay mesh for any 3D domain has been a long term outstanding problem. In this paper, we present an efficient 3D Delaunay meshing algorithm that mathematically guarantees the well-shape quality of the mesh, if the domain does not have acute angles. The main ingredient of our algorithm is a novel refinement technique which systematically forbids the formation of shivers, a family of bad elements that none of the previous known algorithms can cleanly remove, especially near the domain boundary — needless to say, that our algorithm ensure that there is no sliver near the boundary of the domain.
BibTeX
@inproceedings{li2001generating,
  author = {Xiang-Yang Li and Shang-Hua Teng},
  title = {{Generating well-shaped Delaunay meshed in 3D}},
  booktitle = {SODA},
  year = {2001},
}

Loading related content...

Figure