Computer Science Department
School of Computer Science, Carnegie Mellon University
Delaunay Refinement Mesh Generation
Jonathan Richard Shewchuk
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.