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.
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 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]
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 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.
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.
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]
In mathematics and computational geometry, a Delaunay triangulation for a given set P of discrete points in a general position is a triangulation DT(P) such that no point in P is inside the circumcircle of any triangle in DT(P). Delaunay triangulations maximize the minimum of all the angles of the triangles in the triangulation; they tend to avoid sliver triangles. The triangulation is named after Boris Delaunay for his work on this topic from 1934.
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.
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".
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.
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.
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.
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.
In computer graphics, a nonobtuse triangle mesh is a polygon mesh composed of a set of triangles in which no angle is obtuse, i.e. greater than 90°. If each (triangle) face angle is strictly less than 90°, then the triangle mesh is said to be acute. Every polygon with sides has a nonobtuse triangulation with triangles, allowing some triangle vertices to be added to the sides and interior of the polygon. These nonobtuse triangulations can be further refined to produce acute triangulations with triangles.
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:
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.
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.
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 β.
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.
In computational geometry, a Steiner point is a point that is not part of the input to a geometric optimization problem but is added during the solution of the problem, to create a better solution than would be possible from the original points alone.
Algorithmic Geometry is a textbook on computational geometry. It was originally written in the French language by Jean-Daniel Boissonnat and Mariette Yvinec, and published as Géometrie algorithmique by Edusciences in 1995. It was translated into English by Hervé Brönnimann, with improvements to some proofs and additional exercises, and published by the Cambridge University Press in 1998.
{{cite web}}
: CS1 maint: bot: original URL status unknown (link)