Mesh Generation by Delaunay Refinement

triangles or tetrahedra suitable for use in such applications as
o graphics (especially radiosity),
o terrain databases and Geographical Information Systems,
o function interpolation, and most importantly,
o numerical methods such as the finite element method.
In response to the needs of Carnegie Mellon's Quake project, an
interdisciplinary Grand Challenge project whose goal is to simulate
earthquake-induced ground motion in the Los Angeles basin, I have
produced two general-purpose mesh generators. Triangle and Pyramid
are implementations of two- and three-dimensional Delaunay refinement,
respectively. Triangle has been released to the public, and has hundreds or
thousands of users in both research and industrial settings, who use Triangle
for all the applications listed above and more.

In this talk, I discuss the algorithmic underpinnings and current state of
the art of Delaunay refinement methods. Popularized by the engineering
community in the mid-1980s, Delaunay refinement operates by maintaining a
Delaunay triangulation or Delaunay tetrahedralization, which is refined by
the insertion of additional vertices. The placement of these vertices is
chosen to force the mesh to conform to an object's boundaries, and to improve
its quality as a grid for interpolation.

I present a new three-dimensional Delaunay refinement algorithm, which builds
on the pioneering two-dimensional work by L. Paul Chew and Jim Ruppert. My
algorithm produces tetrahedral meshes that are nicely graded (in a provable
sense) and whose tetrahedra have circumradius-to-shortest edge ratios bounded
below 1.63. This theoretical guarantee ensures that all poor quality
tetrahedra except slivers (a particular type of poor tetrahedron) are
removed. The slivers that remain are easily removed in practice, although
there is no theoretical guarantee.