Xiang-Yang Li
Department of Computer Science, IIT
Generating Well-Shaped Delaunay Meshes
Abstract
A mesh is cell-complex that decomposes a spatial domain for numerical simulation.
Delaunay triangulations have many desirable properties for mesh generation.
While there are several efficient methods for well-shaped 2D mesh generation,
the generation of Delaunay meshes of well-shaped tetrahedra in 3D is considerably
more difficult and has been an outstanding open problem for many years. Most
notably, slivers are notoriously common in three dimensional Delaunay meshes,
where a sliver is a tetrahedron that has no short edge and whose four vertices
lie closely to a great circle of its circum-sphere.
In this talk, I will survey the algorithmic and geometric techniques using
weighted Delaunay triangulations and perturbations, that are recently developed
for sliver removal. In particular, I will present the first Delaunay refinement
algorithm, developed by Li and Teng, that always generates sliver free well-shaped
unstructured meshes in three dimensions. The main ingredient of this algorithm
is a novel refinement technique which systematically forbids the formation
of slivers.
This talk contains collaborative works with Shang-Hua Teng, Siu-Wing Cheng,
Tamal Dey, Herbert Edelsbrunner, Micheal Facello, Alper Ungor, Gary Miller,
Dafna Talmor, and Noel Walkington.
|