Ruppert's algorithm
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.
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.
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.
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."[1]
Jim Ruppert discovered this algorithm in the early 1990s.[2] Since then, various small improvements have been made.[3]
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
- ^ Shewchuk, Jonathan. "Ruppert's Delaunay Refinement Algorithm". Retrieved April 2010.
{{cite web}}: Check date values in:|accessdate=(help) - ^ Ruppert, Jim (1995). "A Delaunay refinement algorithm for quality 2-dimensional mesh generation". Journal of Algorithms. 18 (3): 548–585.
- ^ Miller, Gary (2003). "When and why Ruppert's algorithm works". Proceedings of the 12th International Meshing Roundtable. pp. 91–102.
{{cite conference}}: Unknown parameter|booktitle=ignored (|book-title=suggested) (help); Unknown parameter|coauthors=ignored (|author=suggested) (help)
External links
- Pav, Steven. "Research". Retrieved April 2010.
{{cite web}}: Check date values in:|accessdate=(help)
- Rineau, Laurent. "2D Conforming Triangulations and Meshes". Retrieved April 2010.
{{cite web}}: Check date values in:|accessdate=(help)
- Shewchuk, Jonathan. "Triangle: A Two-Dimensional Quality Mesh Generator and Delaunay Triangulator". Retrieved April 2010.
{{cite web}}: Check date values in:|accessdate=(help)
- Si, Hang. "TetGen: A Quality Tetrahedral Mesh Generator and a 3D Delaunay Triangulator". Retrieved April 2010.
{{cite web}}: Check date values in:|accessdate=(help)