Skip to main content

Implementing 2D Delauney Triangulation

Key Takeaways

  • Many mesh generation algorithms are based on the Delauney criterion, which is used to form a structure called a Delauney triangulation.

  • A Delauney triangulation is a certain type of mesh constructed from triangles or tetrahedra where the circumference of the shape forms a boundary for other meshing points.

  • A 2D Delauney triangulation can be used to examine flows along arbitrary surfaces with the goal of minimizing computation time.

2D Delauney triangulation

Many areas of computational geometry and mathematics find practical uses in fluid dynamics, particularly in one area: mesh generation. Before a CFD problem can be solved, a mesh needs to be built to represent the system geometry, within which the main CFD equations will be converted to a numerical problem. The set of discrete points that represent a real system must be chosen such that accuracy and computation time are brought into balance, and so meshing algorithms are constructed to provide a discrete numerical representation of a real system.

A common technique used to build 2D and 3D meshes is to build a Delauney triangulation. For surfaces that must terminate along a set of static mesh points, we use a constrained Delauney triangulation. In this article, we’ll examine the structure of these triangulations and a few of their mathematical properties as well as how to use a 2D Delauney triangulation in a CFD simulation.

Delauney Triangulation Defined

Delauney triangulations are defined as a set of points in a 2D or 3D space, where triangles drawn between groups of points will obey specific geometric properties. In particular, these points must be arranged according to a maximization condition, which produces certain benefits for CFD simulations that require unstructured meshes.

The points in a Delauney triangulation must be arranged such that they satisfy specific mathematical properties. For CFD simulations and unstructured mesh generation, there are two properties that are important:

  1. The circumference about any triangle in the triangulation only contains those points in the triangle; it does not contain any other points. This is one condition that effectively limits mesh density for a given length scale used to build the mesh.
  2. The triangles/tetrahedra in a Delauney triangulation attempt to maximize the minimum angle of all the angles in the triangulation, even if the drawn triangles are not equilateral. This tends to eliminate sliver triangles that might occur at the edges of a surface or structure.

The 1st condition is implemented by enforcing the 2nd condition. The 1st condition is really the fundamental property of a Delauney triangulation, known as the Delauney criterion. In a 2D Delauney triangulation, this is sometimes called the empty circumcircle criterion. Visually, these properties can be verified by circumscribing groups of points in the generated mesh (see below for an example).

2D and 3D Delauney triangulation examples

2D and 3D Delauney triangulations

Another consequence of the fundamental properties of Delauney triangulations is that the resulting triangulation is independent of the order in which points are located in the mesh. This makes it relatively easy to implement in a meshing algorithm in 2D or 3D, including in iterative techniques. 

2D Delauney Triangulation vs. Other Methods

The mesh resulting from a Delauney triangulation calculation will be unstructured when applied to arbitrary surfaces, so the technique should be compared with other triangulation methods for unstructured mesh generation. 

Advancing Front Methods

An advancing front refers to the generation of new unstructured mesh elements by adding them to the edges of an existing array of mesh elements. A 2D mesh is initially generated by discretizing the boundary geometry, and these edge points form the initial front where new mesh elements will be added to the system. A new element is formed along this edge by joining a new grid point to an existing edge, and this is iterated until the constructed mesh spans the entire surface.

Quad/Octree-Based Methods

Mesh generation is performed through recursive subdivision of elements down to a required resolution in 2D or 3D. The vertices of the resulting structure are used as mesh points. At the boundaries, elements are intended to intersect boundary surfaces, so the vertices are normally displaced within some error such that they coincide with the boundary.

Stretched Mesh Generation

These methods are aimed at solving the full Navier-Stokes equations by resolving wakes, boundary layers, and other viscous regions in high-Reynolds number flows. Fine resolution is applied in normal to streamwise flows in order to capture vortical motion with high accuracy. Therefore, it can be used to accurately model turbulent boundary layers in the transition regime.

Non-Simplicial Meshing

Delauney triangulation is sometimes called a simplicial meshing method, meaning the mesh elements are all the same type of shape but they do not have the same dimensions. Non-simplicial meshes are truly unstructured and may contain many possible mesh element shapes and sizes. This can be used to reduce the connectivity of the mesh by enforcing mesh elements with more edges, such as hexahedral meshing.

Adaptive Meshing

Adaptive meshing is naturally useful in unstructured meshing because there is no inherent structure enforced in the mesh. All mesh points can be reconfigured in regions as needed to accommodate high flow gradients where higher accuracy is required. The goal in adaptive meshing is to determine the optimum distribution of mesh points to provide highly accurate interpolation that results in error equipartition in the simulation.

CFD simulation adaptive meshing

Example of adaptive meshing performed for mixing with turbulent flow. [Source]

Aside from non-simplicial meshing and adaptive meshing, a Delauney triangulation gives the designer flexibility in building a mesh for solving CFD problems, regardless of the problem to which it is applied. While we have discussed the above points in terms of 2D Delauney triangulation, the same ideas apply to 3D systems where flow in the bulk needs to be simulated. Finally, meshes generated with the above methods can be transformed into Delauney triangulations using edge and face-swapping methods, which may be advantageous for balancing accuracy and computational time.

No matter the complexity of the system you need to simulate, you can generate meshes based on 2D Delaunay triangulation using the meshing features in Pointwise from Cadence. When you’re ready to run CFD simulations for your system, use the simulation tools in Omnis. Modern numerical approaches used in aerodynamics simulations, turbulent and laminar flow simulations, reduced fluid flow models, and much more can be implemented with Cadence’s simulation tools.

Subscribe to our newsletter for the latest CFD updates or browse Cadence’s suite of CFD software, including Omnis and Pointwise, to learn more about how Cadence has the solution for you.

CFD Software Subscribe to Our Newsletter

About the Author

With an industry-leading meshing approach and a robust host of solver and post-processing capabilities, Cadence Fidelity provides a comprehensive Computational Fluid Dynamics (CFD) workflow for applications including propulsion, aerodynamics, hydrodynamics, and combustion.