Ruppert's algorithm: Difference between revisions

Revision as of 01:56, 6 January 2011

Revision as of 08:24, 9 March 2011

Line 18:

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.

Line 45:

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.<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-31–3 | pages=21–74}}</ref> 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.51 degrees.<ref>{{citation|last=Rand|first=Alexander|title=On the non-termination of Ruppert's algorithm|year=2011|id={{arxiv|1101.1071}}}}.</ref>

== See also ==