Ruppert's algorithm: Difference between revisions

Revision as of 18:07, 30 September 2010

Revision as of 18:10, 30 September 2010

Line 38:

== 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.<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

| last1 = Pav | first1 = Steven

| last2 = Walkington | first2 = Noel

Line 47:

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.