Delaunay refinement

Last updated

In mesh generation, Delaunay refinements are algorithms for mesh generation based on the principle of adding Steiner points to the geometry of an input to be meshed, in a way that causes the Delaunay triangulation or constrained Delaunay triangulation of the augmented input to meet the quality requirements of the meshing application. Delaunay refinement methods include methods by Chew and by Ruppert.

Contents

Chew's second algorithm

Mesh of Lake Michigan using Chew's second algorithm implemented in the Triangle package. LakeMichiganMesh.png
Mesh of Lake Michigan using Chew's second algorithm implemented in the Triangle package.

Chew's second 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, [1] 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. [2] 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. [3]

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.

Ruppert's algorithm

RuppertsAlgorithm-input.png
Input planar straight-line graph
RuppertsAlgorithm-output.png
Output conforming Delaunay triangulation
Example of Ruppert's algorithm

Ruppert's 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, [4] "Ruppert's algorithm for two-dimensional quality mesh generation is perhaps the first theoretically guaranteed meshing algorithm to be truly satisfactory in practice." [5]

Motivation

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.

Intermediate triangulations of Ruppert's algorithm

Algorithm

The algorithm begins with a Delaunay triangulation of the input vertices and then consists of two main operations.

These operations are repeated until no poor-quality triangles exist and all segments are not encroached.

Pseudocode
function Ruppert(points, segments, threshold) isT := DelaunayTriangulation(points)     Q := the set of encroached segments and poor quality triangles      whileQis not empty:                 // The main loopifQ contains a segment s:             insert the midpoint of s into TelseQ contains poor quality triangle t:             if the circumcenter of t encroaches a segment s:                 add s to Q;             else:                 insert the circumcenter of t into Tend ifend if         update Qend whilereturnTend 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. [6] Curved input can also be meshed using similar techniques. [7] 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. [8] 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. [9]

See also

Related Research Articles

<span class="mw-page-title-main">Delaunay triangulation</span> Triangulation method

In computational geometry, a Delaunay triangulation or Delone triangulation of a set of points in the plane subdivides their convex hull into triangles whose circumcircles do not contain any of the points. This maximizes the size of the smallest angle in any of the triangles, and tends to avoid sliver triangles.

Computational geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry. Some purely geometrical problems arise out of the study of computational geometric algorithms, and such problems are also considered to be part of computational geometry. While modern computational geometry is a recent development, it is one of the oldest fields of computing with a history stretching back to antiquity.

<span class="mw-page-title-main">Quadtree</span> Tree data structure in which each internal node has exactly four children, to partition a 2D area

A quadtree is a tree data structure in which each internal node has exactly four children. Quadtrees are the two-dimensional analog of octrees and are most often used to partition a two-dimensional space by recursively subdividing it into four quadrants or regions. The data associated with a leaf cell varies by application, but the leaf cell represents a "unit of interesting spatial information".

<span class="mw-page-title-main">Euclidean minimum spanning tree</span> Shortest network connecting points

A Euclidean minimum spanning tree of a finite set of points in the Euclidean plane or higher-dimensional Euclidean space connects the points by a system of line segments with the points as endpoints, minimizing the total length of the segments. In it, any two points can reach each other along a path through the line segments. It can be found as the minimum spanning tree of a complete graph with the points as vertices and the Euclidean distances between points as edge weights.

<span class="mw-page-title-main">Point-set triangulation</span> Simplicial complex in Euclidean geometry

A triangulation of a set of points in the Euclidean space is a simplicial complex that covers the convex hull of , and whose vertices belong to . In the plane, triangulations are made up of triangles, together with their edges and vertices. Some authors require that all the points of are vertices of its triangulations. In this case, a triangulation of a set of points in the plane can alternatively be defined as a maximal set of non-crossing edges between points of . In the plane, triangulations are special cases of planar straight-line graphs.

In geometry, a triangulation is a subdivision of a planar object into triangles, and by extension the subdivision of a higher-dimension geometric object into simplices. Triangulations of a three-dimensional volume would involve subdividing it into tetrahedra packed together.

<span class="mw-page-title-main">Triangulated irregular network</span> Representation of a surface as a triangle mesh with elevated vertices

In computer graphics, a triangulated irregular network (TIN) is a representation of a continuous surface consisting entirely of triangular facets, used mainly as Discrete Global Grid in primary elevation modeling.

<span class="mw-page-title-main">Mesh generation</span> Subdivision of space into cells

Mesh generation is the practice of creating a mesh, a subdivision of a continuous geometric space into discrete geometric and topological cells. Often these cells form a simplicial complex. Usually the cells partition the geometric input domain. Mesh cells are used as discrete local approximations of the larger domain. Meshes are created by computer algorithms, often with human guidance through a GUI, depending on the complexity of the domain and the type of mesh desired. A typical goal is to create a mesh that accurately captures the input domain geometry, with high-quality (well-shaped) cells, and without so many cells as to make subsequent calculations intractable. The mesh should also be fine in areas that are important for the subsequent calculations.

In computer graphics, marching squares is an algorithm that generates contours for a two-dimensional scalar field. A similar method can be used to contour 2D triangle meshes.

<span class="mw-page-title-main">Pitteway triangulation</span>

In computational geometry, a Pitteway triangulation is a point set triangulation in which the nearest neighbor of any point p within the triangulation is one of the vertices of the triangle containing p. Alternatively, it is a Delaunay triangulation in which each internal edge crosses its dual Voronoi diagram edge. Pitteway triangulations are named after Michael Pitteway, who studied them in 1973. Not every point set supports a Pitteway triangulation. When such a triangulation exists it is a special case of the Delaunay triangulation, and consists of the union of the Gabriel graph and convex hull.

In computational geometry, the Bowyer–Watson algorithm is a method for computing the Delaunay triangulation of a finite set of points in any number of dimensions. The algorithm can be also used to obtain a Voronoi diagram of the points, which is the dual graph of the Delaunay triangulation.

Parallel mesh generation in numerical analysis is a new research area between the boundaries of two scientific computing disciplines: computational geometry and parallel computing. Parallel mesh generation methods decompose the original mesh generation problem into smaller subproblems which are solved (meshed) in parallel using multiple processors or threads. The existing parallel mesh generation methods can be classified in terms of two basic attributes:

  1. the sequential technique used for meshing the individual subproblems and
  2. the degree of coupling between the subproblems.

Jump-and-Walk is an algorithm for point location in triangulations. Surprisingly, the algorithm does not need any preprocessing or complex data structures except some simple representation of the triangulation itself. The predecessor of Jump-and-Walk was due to Lawson (1977) and Green and Sibson (1978), which picks a random starting point S and then walks from S toward the query point Q one triangle at a time. But no theoretical analysis was known for these predecessors until after mid-1990s.

<span class="mw-page-title-main">Herbert Edelsbrunner</span> American computer scientist

Herbert Edelsbrunner is a computer scientist working in the field of computational geometry, the Arts & Science Professor of Computer Science and Mathematics at Duke University, Professor at the Institute of Science and Technology Austria (ISTA), and the co-founder of Geomagic, Inc. He was the first of only three computer scientists to win the National Science Foundation's Alan T. Waterman Award.

<span class="mw-page-title-main">Beta skeleton</span>

In computational geometry and geometric graph theory, a β-skeleton or beta skeleton is an undirected graph defined from a set of points in the Euclidean plane. Two points p and q are connected by an edge whenever all the angles prq are sharper than a threshold determined from the numerical parameter β.

<span class="mw-page-title-main">Local feature size</span>

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.

In computational geometry, a constrained Delaunay triangulation is a generalization of the Delaunay triangulation that forces certain required segments into the triangulation as edges, unlike the Delaunay triangulation itself which is based purely on the position of a given set of vertices without regard to how they should be connected by edges. It can be computed efficiently and has applications in geographic information systems and in mesh generation.

<span class="mw-page-title-main">FEATool Multiphysics</span>

FEATool Multiphysics is a physics, finite element analysis (FEA), and partial differential equation (PDE) simulation toolbox. FEATool Multiphysics features the ability to model fully coupled heat transfer, fluid dynamics, chemical engineering, structural mechanics, fluid-structure interaction (FSI), electromagnetics, as well as user-defined and custom PDE problems in 1D, 2D (axisymmetry), or 3D, all within a graphical user interface (GUI) or optionally as script files. FEATool has been employed and used in academic research, teaching, and industrial engineering simulation contexts.

Newest Vertex Bisection is an algorithmic method to locally refine triangulations. It is widely used in computational science, numerical simulation, and computer graphics. The advantage of newest vertex bisection is that it allows local refinement of triangulations without degenerating the shape of the triangles after repeated usage.

References

  1. Chew, L. Paul (1993). "Guaranteed-quality mesh generation for curved surfaces". Proceedings of the Ninth Annual Symposium on Computational Geometry . pp. 274–280.
  2. Shewchuk, Jonathan (2002). "Delaunay refinement algorithms for triangular mesh generation". Computational Geometry: Theory and Applications . 22 (1–3): 21–74. doi: 10.1016/s0925-7721(01)00047-5 .
  3. Rand, Alexander (2011). "Where and How Chew's Second Delaunay Refinement Algorithm Works" (PDF). Proceedings of the 23rd Canadian Conference on Computational Geometry. pp. 157–162.
  4. Ruppert, Jim (1995). "A Delaunay refinement algorithm for quality 2-dimensional mesh generation". Journal of Algorithms. 18 (3): 548–585. doi:10.1006/jagm.1995.1021.
  5. Shewchuk, Jonathan (12 August 1996). "Ruppert's Delaunay Refinement Algorithm" . Retrieved 28 December 2018.
  6. Miller, Gary; Pav, Steven; Walkington, Noel (2005). "When and why Delaunay refinement algorithms work". International Journal of Computational Geometry and Applications. 15 (1): 25–54. doi:10.1142/S0218195905001592.
  7. Pav, Steven; Walkington, Noel (2005). Delaunay refinement by corner lopping. Proceedings of the 14th International Meshing Roundtable. pp. 165–181.
  8. Shewchuk, Jonathan (2002). "Delaunay refinement algorithms for triangular mesh generation". Computational Geometry: Theory and Applications . 22 (1–3): 21–74. doi: 10.1016/s0925-7721(01)00047-5 .
  9. Rand, Alexander (2011). "Improved Examples of Non-Termination for Ruppert's Algorithm". arXiv: 1103.3903 [cs.CG]..

Further reading