Delaunay Refinement Mesh Generation 

                         Jonathan Richard Shewchuk
                         School of Computer Science
                         Carnegie Mellon University
                       Pittsburgh, Pennsylvania 15213

Delaunay refinement is a technique for generating unstructured meshes of
triangles or tetrahedra suitable for use in the finite element method or other
numerical methods for solving partial differential equations.  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 enforce boundary conformity and to improve the quality of
the mesh.  Pioneering papers by L. Paul Chew and Jim Ruppert have placed
Delaunay refinement on firm theoretical ground.  The purpose of this thesis is
to further this progress by cementing the foundations of two-dimensional
Delaunay refinement, and by extending the technique and its analysis to three
dimensions.

In two dimensions, I unify the algorithms of Chew and Ruppert in a common
theoretical framework.  Using Ruppert's analysis technique, I prove that one of
Chew's algorithms can produce triangular meshes that are nicely graded, are
size-optimal, and have no angle smaller than 26.5 degrees.  (Chew proved a 30
degree bound without guarantees on grading or size.)  I show that there are
inputs with small angles that cannot be meshed by any algorithm without
introducing new small angles; hence, all provably good mesh generation
algorithms, including those not yet discovered, suffer from a fundamental
limitation.  I introduce techniques for handling small input angles that
minimize the impact of this limitation on two-dimensional Delaunay refinement
algorithms.

In three dimensions, I introduce a Delaunay refinement algorithm that can
produce tetrahedral meshes that are nicely graded and whose tetrahedra have
circumradius-to-shortest edge ratios bounded below 1.63.  By sacrificing good
grading in theory (but not in practice), the bound can be improved to 1.15.
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.  These results assume that all input angles are large; the removal
of this restriction remains the most important open problem in
three-dimensional Delaunay refinement.  Nevertheless, Delaunay refinement
methods for tetrahedral mesh generation have the rare distinction that they
offer strong theoretical bounds and frequently perform well in practice.

I describe my implementations of the triangular and tetrahedral Delaunay
refinement algorithms.  The robustness of these mesh generators against
floating-point roundoff error is strengthened by fast correct floating-point
implementations of four geometric predicates: the two-dimensional and
three-dimensional orientation and incircle tests.  These predicates owe their
speed to two features.  First, they employ new fast algorithms for arbitrary
precision arithmetic on standard floating-point units.  Second, they are
adaptive; their running time depends on the degree of uncertainty of the
result, and is usually small.  Hence, these predicates cost little more than
ordinary nonrobust predicates, but never sacrifice correctness for speed.


Ph.D. thesis.  Technical Report CMU-CS-97-137, School of Computer Science,
Carnegie Mellon University, Pittsburgh, Pennsylvania, May 1997.


Compressed PostScript (1,768k) available through the URL
http://www.cs.cmu.edu/~quake-papers/delaunay-refinement.ps.gz


BibTeX entry:

@phdthesis{shewchuk97b,
author = {Jonathan Richard Shewchuk},
title = {Delaunay {R}efinement {M}esh {G}eneration},
school = {School of Computer Science, Carnegie Mellon University},
address = {Pittsburgh, Pennsylvania},
month = may,
year = 1997,
note = {Available as Technical Report CMU-CS-97-137}
}