Ruppert's algorithm
Encyclopedia
In mesh generation
, Ruppert's algorithm, also known as Delaunay refinement, is an algorithm
for creating quality Delaunay triangulation
s. The 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,
"Ruppert's algorithm for two-dimensional quality mesh generation is perhaps the first theoretically guaranteed meshing algorithm to be truly satisfactory in practice."
, 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.
These operations are repeated until no poor-quality triangles exist and all segments are not encroached.
2 T := DelaunayTriangulation(points);
3 Q := the set of encroached segments and poor quality triangles;
4 while Q is not empty: // The main loop
5 if Q contains a segment s:
6 insert the midpoint of s into T;
7 else Q contains poor quality triangle t:
8 if the circumcenter of t encroaches a segments s:
9 add s to Q;
10 else:
11 insert the circumcenter of t into T;
12 end if;
13 end if;
14 update Q;
15 end while;
16 return T;
17 end Ruppert.
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. 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.
Mesh generation
Mesh generation is the practice of generating a polygonal or polyhedral mesh that approximates a geometric domain. The term "grid generation" is often used interchangeably. Typical uses are for rendering to a computer screen or for physical simulation such as finite element analysis or...
, Ruppert's algorithm, also known as Delaunay refinement, is an algorithm
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
for creating quality Delaunay triangulation
Delaunay triangulation
In mathematics and computational geometry, a Delaunay triangulation for a set P of points in a plane is a triangulation DT such that no point in P is inside the circumcircle of any triangle in DT. Delaunay triangulations maximize the minimum angle of all the angles of the triangles in the...
s. The algorithm takes a planar straight-line graph
Planar straight-line graph
Planar straight-line graph is a term used in computational geometry for an embedding of a planar graph in the plane such that its edges are mapped into straight line segments...
(or in dimension higher than two a piecewise linear
Piecewise linear manifold
In mathematics, a piecewise linear manifold is a topological manifold together with a piecewise linear structure on it. Such a structure can be defined by means of an atlas, such that one can pass from chart to chart in it by piecewise linear functions.An isomorphism of PL manifolds is called a PL...
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,
"Ruppert's algorithm for two-dimensional quality mesh generation is perhaps the first theoretically guaranteed meshing algorithm to be truly satisfactory in practice."
Motivation
When doing computer simulations such as computational fluid dynamicsComputational fluid dynamics
Computational fluid dynamics, usually abbreviated as CFD, is a branch of fluid mechanics that uses numerical methods and algorithms to solve and analyze problems that involve fluid flows. Computers are used to perform the calculations required to simulate the interaction of liquids and gases with...
, one starts with a model such as a 2D outline of a wing section.
The input to a 2D finite element method
Finite element method
The finite element method is a numerical technique for finding approximate solutions of partial differential equations as well as integral equations...
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
Unstructured grid
An unstructured grid is a tessellation of a part of the Euclidean plane or Euclidean space by simple shapes, such as triangles or tetrahedra, in an irregular pattern...
.
The computer uses Ruppert's algorithm (or some similar meshing algorithm) to convert the polygonal model into triangles suitable for the finite element method.
Algorithm Description
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
1 function Ruppert(points,segments,threshold):2 T := DelaunayTriangulation(points);
3 Q := the set of encroached segments and poor quality triangles;
4 while Q is not empty: // The main loop
5 if Q contains a segment s:
6 insert the midpoint of s into T;
7 else Q contains poor quality triangle t:
8 if the circumcenter of t encroaches a segments s:
9 add s to Q;
10 else:
11 insert the circumcenter of t into T;
12 end if;
13 end if;
14 update Q;
15 end while;
16 return T;
17 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. Curved input can also be meshed using similar techniques.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. 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.
See also
- Chew's second algorithmChew's second algorithmIn mesh generation, Chew's second algorithm is a Delaunay refinement algorithm for creating quality constrained Delaunay triangulations. The algorithm takes a piecewise linear system and returns a constrained Delaunay triangulation of only quality triangles where quality is defined by the minimum...
- Delaunay triangulationDelaunay triangulationIn mathematics and computational geometry, a Delaunay triangulation for a set P of points in a plane is a triangulation DT such that no point in P is inside the circumcircle of any triangle in DT. Delaunay triangulations maximize the minimum angle of all the angles of the triangles in the...
- Local feature sizeLocal feature sizeLocal feature size refers to several related concepts in computer graphics and computational geometry for measuring the size of a geometric object near a particular point....
- Polygon meshPolygon meshA polygon mesh or unstructured grid is a collection of vertices, edges and faces that defines the shape of a polyhedral object in 3D computer graphics and solid modeling...
- TetGenTetGenTetGen is a mesh generator developed by Hang Si which is designed to partition any 3D geometry into tetrahedrons by employing a form of Delaunay triangulation whose algorithm was developed by the author....
- Voronoi diagramVoronoi diagramIn mathematics, a Voronoi diagram is a special kind of decomposition of a given space, e.g., a metric space, determined by distances to a specified family of objects in the space...