Jonathan Richard Shewchuk

Delaunay Refinement Mesh Generation Degree Type: Ph.D. in Computer Science
Advisor(s): Gary Miller, David O'Hallaron
Graduated: May 1997

Abstract:

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 Delauany 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.

Thesis Committee:
Gary L. Miller (Co-chair)
David R. O’Hallaron (Co-chair)
Thomas R. Gross
Omar Ghattas (Department of Civil and Environmental Engineering)
Jim Ruppert (Arris Pharmaceutical)

James Morris, Head, Computer Science Department
Raj Reddy Dean, School of Computer Science

Keywords:
Tetrahedral mesh generation, Delaunay triangulation, arbitrary precision floating-point arithmetic, computational geometry, geometric robustness