Sliver -Free Three Dimensional Delaunay Mesh Generation

The second algorithm adds points to generate well-shaped meshes. It is based on the following observations. Any tetrahedron will disappear from the Delaunay triangulation if a point is added inside the circumsphere of the tetrahedron. Among the tetrahedra created by inserting this new point there could be tetrahedra with large radius-edge ratios, or slivers, or both. However, the new point is incident to every new tetrahedron. We first eliminate tetrahedra with large radius-edge ratios. We then select the point that avoids creating any small slivers when inserting point inside the circumsphere of slivers. We show that the algorithm will not introduce short edges to the Delaunay triangulation. A simple volume argument implies that the algorithm terminates and generates a well-shaped Delaunay mesh. The generated mesh has a good grading. The number of mesh elements is within a small constant factor of any almost-good mesh for that given domain. We also describe some variations of this refinement-based algorithm. In particular, we show that inserting points near sinks instead of circumcenters of bad tetrahedra also generates sliver-free Delaunay meshes.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2015

Author dc:creator

• Li, Xiangyang

Contributors dc:contributor

• Shang-Hua Teng

• Computer Science

Language dc:language

eng

Identifier

(MiAaPQ)AAI9996652

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/81994