Chew's second algorithm
Encyclopedia
In mesh generation
, Chew's second algorithm is a Delaunay refinement algorithm
for creating quality constrained Delaunay triangulation
s. The algorithm takes a piecewise linear system (PLS) and returns a constrained Delaunay triangulation of only quality triangles where quality is defined by the minimum angle in a triangle. Developed by L. Paul Chew for meshing surfaces embedded in three-dimensional space, Chew's second algorithm has been adopted as a two-dimensional mesh generator due to practical advantages over Ruppert's algorithm
in certain cases and is the default quality mesh generator implemented in the freely available Triangle package. Chew's second algorithm is guaranteed to terminate and produce a local feature size
-graded meshes with minimum angle up to about 28.6 degrees.
Circumcenter insertion is repeated until no poor-quality triangles exist.
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...
, Chew's second algorithm is a Delaunay refinement 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 constrained Delaunay triangulation
Constrained Delaunay triangulation
In computational geometry, a constrained Delaunay triangulation is a generalization of the Delaunay triangulation that forces certain required segments into the triangulation. Because a Delaunay triangulation is almost always unique, often a constrained Delaunay triangulation contains edges that do...
s. The algorithm takes a piecewise linear system (PLS) and returns a constrained Delaunay triangulation of only quality triangles where quality is defined by the minimum angle in a triangle. Developed by L. Paul Chew for meshing surfaces embedded in three-dimensional space, Chew's second algorithm has been adopted as a two-dimensional mesh generator due to practical advantages over Ruppert's algorithm
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 planar straight-line graph and returns a conforming Delaunay triangulation of only quality triangles...
in certain cases and is the default quality mesh generator implemented in the freely available Triangle package. Chew's second algorithm is guaranteed to terminate and produce a local feature size
Local feature size
Local 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....
-graded meshes with minimum angle up to about 28.6 degrees.
Algorithm Description
The algorithm begins with a constrained Delaunay triangulation of the input vertices. At each step, the circumcenter of a poor-quality triangle is inserted into the triangulation with one exception. If the circumcenter lies on the opposite side of an input segment as the poor quality triangle, the midpoint of the segment is inserted. Moreover, any previously inserted circumcenters inside the diametral ball of the original segment (before it is split) are removed from the triangulation.Circumcenter insertion is repeated until no poor-quality triangles exist.