In mesh generation, Ruppert's algorithm, also known as Delaunay refinement, is an algorithm for creating quality Delaunay triangulations. The algorithm takes a piecewise linear system (PLS) and returns a conforming Delaunay triangulation of only quality triangles. A triangle is considered poor-quality if it has a circumradius to shortest edge ratio larger than some prescribed threshold.
The algorithm consists of two main operations.
- The midpoint of a segment with non-empty diametral circles is inserted into the triangulation.
- The circumcenter of a poor-quality triangle is inserted into the triangulation, unless this circumcenter lies in the diametral circle of some segment. In this case, the encroached segment is split instead.
These operations are repeated until no poor-quality triangles exist and all segments are not encroached.
An extension of Ruppert's algorithm in two dimensions is implemented in the freely available (yet non-free) Triangle package.
Ruppert's algorithm has been shown to terminate for any input PLS with no small angles. The algorithm can be extended to handle any input by slightly relaxing the quality requirement on the output (Miller et al., 2003).
Ruppert's algorithm can be naturally extended to three dimensions, however its output guarantees are somewhat weaker due to the sliver type tetrahedron.
In two dimensions, the poor-quality threshold must be at least √2. This means that any triangle which contains some angle less than about 20.7 degrees is poor-quality.
See also
References
- G. L. Miller, S. E. Pav, and N. J. Walkington. When and why Ruppert's algorithm works. In Proceedings of the 12th International Meshing Roundtable, pages 91-102. Sandia National Laboratory, September 2003.
- J. Ruppert. A Delaunay refinement algorithm for quality 2-dimensional mesh generation, 1995.