Delaunay refinement

In mesh generation, Delaunay refinements are algorithms for mesh generation based on the principle of adding Steiner points to the geometry of an input to be meshed, in a way that causes the Delaunay triangulation or constrained Delaunay triangulation of the augmented input to meet the quality requirements of the meshing application. Delaunay refinement methods include methods by Chew and by Ruppert.

Chew's second algorithm

File:LakeMichiganMesh.png using Chew's second algorithm implemented in the Triangle package.]]

Chew's second algorithm takes a piecewise linear system (PLS) and returns a constrained Delaunay triangulation of only quality triangles where quality is defined by the minimum angle in a triangle. Developed by L. Paul Chew for meshing surfaces embedded in three-dimensional space,{{cite conference | first1=L. Paul| last1=Chew| title=Guaranteed-quality mesh generation for curved surfaces | book-title=Proceedings of the Ninth Annual Symposium on Computational Geometry | year=1993 | pages=274–280}} Chew's second algorithm has been adopted as a two-dimensional mesh generator due to practical advantages over Ruppert's algorithm in certain cases and is the default quality mesh generator implemented in the freely available Triangle package.{{cite journal | first1=Jonathan | last1=Shewchuk | title=Delaunay refinement algorithms for triangular mesh generation | journal=Computational Geometry: Theory and Applications | year=2002 | volume=22 | issue=1–3 | pages=21–74 | doi=10.1016/s0925-7721(01)00047-5| doi-access=free }} Chew's second algorithm is guaranteed to terminate and produce a local feature size-graded meshes with minimum angle up to about 28.6 degrees.{{cite conference | first1=Alexander | last1=Rand | title=Where and How Chew's Second Delaunay Refinement Algorithm Works | book-title=Proceedings of the 23rd Canadian Conference on Computational Geometry | year=2011 | pages=157–162 | url=http://2011.cccg.ca/PDFschedule/papers/paper91.pdf}}

The algorithm begins with a constrained Delaunay triangulation of the input vertices. At each step, the circumcenter of a poor-quality triangle is inserted into the triangulation with one exception: If the circumcenter lies on the opposite side of an input segment as the poor quality triangle, the midpoint of the segment is inserted. Moreover, any previously inserted circumcenters inside the diametral ball of the original segment (before it is split) are removed from the triangulation.

Circumcenter insertion is repeated until no poor-quality triangles exist.

Ruppert's algorithm

{{multiple image

| direction = vertical

| width = 350

| footer = Example of Ruppert's algorithm

| image1 = RuppertsAlgorithm-input.png

| alt1 = Ruppert's Algorithm input

| caption1 = Input planar straight-line graph

| image2 = RuppertsAlgorithm-output.png

| alt2 = Output conforming Delaunay triangulation

| caption2 = Output conforming Delaunay triangulation

}}

Ruppert's algorithm takes a planar straight-line graph (or in dimension higher than two a piecewise linear system) 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.

Discovered by Jim Ruppert in the early 1990s,{{cite journal | doi=10.1006/jagm.1995.1021 | first=Jim | last=Ruppert | title=A Delaunay refinement algorithm for quality 2-dimensional mesh generation | journal=Journal of Algorithms | year=1995 | issue=3 | pages= 548–585 | volume=18}}

"Ruppert's algorithm for two-dimensional quality mesh generation is perhaps the first theoretically guaranteed meshing algorithm to be truly satisfactory in practice."{{cite web| last=Shewchuk| first=Jonathan| title=Ruppert's Delaunay Refinement Algorithm| url=https://www.cs.cmu.edu/~quake/tripaper/triangle3.html| date=12 August 1996| access-date=28 December 2018}}

= Motivation =

When doing computer simulations such as computational fluid dynamics, one starts with a model such as a 2D outline of a wing section.

The input to a 2D finite element method needs to be in the form of triangles that fill all space, and each triangle to be filled with one kind of material – in this example, either "air" or "wing".

Long, skinny triangles cannot be simulated accurately.

The simulation time is generally proportional to the number of triangles, and so one wants to minimize the number of triangles, while still using enough triangles to give reasonably accurate results – typically by using an unstructured grid.

The computer uses Ruppert's algorithm (or some similar meshing algorithm) to convert the polygonal model into triangles suitable for the finite element method.

Image:RuppertsAlgorithm.ogv

= Algorithm =

The algorithm begins with a Delaunay triangulation of the input vertices and then 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.

;Pseudocode

function Ruppert(points, segments, threshold) is

T := DelaunayTriangulation(points)

Q := the set of encroached segments and poor quality triangles

while Q is not empty: // The main loop

if Q contains a segment s:

insert the midpoint of s into T

else Q contains poor quality triangle t:

if the circumcenter of t encroaches a segment s:

add s to Q;

else:

insert the circumcenter of t into T

end if

update Q

end while

return T

end Ruppert.

= Practical usage =

Without modification Ruppert's algorithm is guaranteed to terminate and generate a quality mesh for non-acute input and any poor-quality threshold less than about 20.7 degrees. To relax these restrictions various small improvements have been made. By relaxing the quality requirement near small input angles, the algorithm can be extended to handle any straight-line input.{{cite journal| doi=10.1142/S0218195905001592| first1=Gary | last1=Miller | first2=Steven | last2=Pav | first3=Noel | last3=Walkington | title=When and why Delaunay refinement algorithms work | journal=International Journal of Computational Geometry and Applications | year=2005 | volume=15 | issue=1 | pages=25–54}} Curved input can also be meshed using similar techniques.{{cite conference

| last1 = Pav | first1 = Steven

| last2 = Walkington | first2 = Noel

| title = Delaunay refinement by corner lopping

| conference = Proceedings of the 14th International Meshing Roundtable

| pages = 165–181

| year = 2005 }}

Ruppert's algorithm can be naturally extended to three dimensions, however its output guarantees are somewhat weaker due to the sliver type tetrahedron.

An extension of Ruppert's algorithm in two dimensions is implemented in the freely available Triangle package. Two variants of Ruppert's algorithm in this package are guaranteed to terminate for a poor-quality threshold of about 26.5 degrees.{{cite journal | first1=Jonathan | last1=Shewchuk | title=Delaunay refinement algorithms for triangular mesh generation | journal=Computational Geometry: Theory and Applications | year=2002 | volume=22 | issue=1–3 | pages=21–74 | doi=10.1016/s0925-7721(01)00047-5| doi-access=free }} In practice these algorithms are successful for poor-quality thresholds over 30 degrees. However, examples are known which cause the algorithm to fail with a threshold greater than 29.06 degrees.{{cite arXiv|last=Rand|first=Alexander|title=Improved Examples of Non-Termination for Ruppert's Algorithm|year=2011|eprint=1103.3903|class=cs.CG }}.

Delaunay refinement

Chew's second algorithm

Ruppert's algorithm

= Motivation =

= Algorithm =

= Practical usage =

See also

References

Further reading