Ruppert's algorithm: Difference between revisions

Revision as of 20:10, 10 September 2010

Revision as of 18:04, 30 September 2010

Line 11:

}}

In [[mesh generation]], '''Ruppert's algorithm''', also known as '''Delaunay refinement''', is an [[algorithm]] for creating quality [[Delaunay triangulation]]s. 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.

Discovered by Jim Ruppert discovered this algorithm in the early 1990s.,<ref>{{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}}</ref>

"Ruppert's algorithm for two-dimensional quality mesh generation is perhaps the first theoretically guaranteed meshing algorithm to be truly satisfactory in practice."<ref>{{cite web | last = Shewchuk | first = Jonathan | title = Ruppert's Delaunay Refinement Algorithm | url = http://www.cs.cmu.edu/~quake/tripaper/triangle3.html | accessdate = April 2010}}</ref>

== Motivation ==

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

Line 17 ⟶ 21:

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|thumb|350px|Intermediate triangulations of Ruppert's algorithm]]

== Algorithm Description ==

The algorithm consists of two main operations.

Line 27 ⟶ 34:

These operations are repeated until no poor-quality triangles exist and all segments are not encroached.

[[Image:RuppertsAlgorithm.ogv|thumb|350px|Intermediate triangulations of Ruppert's algorithm]]

According to Shewchuk,

"Ruppert's algorithm for two-dimensional quality mesh generation is perhaps the first theoretically guaranteed meshing algorithm to be truly satisfactory in practice."<ref>{{cite web | last = Shewchuk | first = Jonathan | title = Ruppert's Delaunay Refinement Algorithm | url = http://www.cs.cmu.edu/~quake/tripaper/triangle3.html | accessdate = April 2010}}</ref>

Jim Ruppert discovered this algorithm in the early 1990s.<ref>{{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}}</ref>

Since then, various small improvements have been made.<ref>{{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}}</ref>

== Practical Usage ==

An extension of Ruppert's algorithm in two dimensions is implemented in the freely available [http://www.cs.cmu.edu/~quake/triangle.html Triangle] package.

SinceWithout then,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.<ref>{{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}}</ref> Curved input can also be meshed using similar techniques. <ref>{{cite conference

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., 2005).

| last1 = Pav | first1 = Steven

| last2 = Walkington | first2 = Noel

| title= Delaunay Refinement by Corner Lopping

| booktitle= Proceedings of the 14th International Meshing Roundtable

| pages = 165-181

| year = 2005 }}</ref>

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 [http://www.cs.cmu.edu/~quake/triangle.html 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. <ref>{{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}}</ref> In practice these algorithms are successful for poor-quality thresholds over 30 degrees.

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 √<span style = "text-decoration:overline">''2''</span>. This means that any triangle which contains some angle less than about 20.7 degrees is poor-quality.

== See also ==