Working & Computing Constrained Delaunay Triangulations
Key Takeaways
-
The Delaunay criterion forms the basis of perhaps the most widely used mesh generation algorithm for unstructured meshes.
-
A Delaunay triangulation is said to be constrained when it must conform to a prescribed set of mesh points on its boundaries.
-
A rich set of algorithms can be built around the Delaunay criterion from which a robust mesher can be written.
Constrained Delauney triangulation is used as the basis for algorithms that generate unstructured meshes on complex surfaces
Computer graphics, topography, and, of course, CFD all have something in common: they use a common technique to map surfaces of discrete points that represent real objects. In these fields, a discrete set of points is mapped to a surface so that a visual representation of a real object can be created from a set of discrete points. Discrete points are not useful for visualizing the surfaces of real objects, but these mathematically reconstructed surfaces are needed to represent real objects as well as to perform simulations involving interactions between physical phenomena and those surfaces.
In CFD, arguably the common technique used to build meshes that represent the surfaces of real objects is a mathematical object known as a constrained Delauney triangulation. We call this particular type of Delaunay triangulation “constrained” because we enforce it to conform to a boundary with a static set of mesh points. In this article, we’ll look at the structure and formation of these triangulations as well as why they are so important for building CFD simulations.
Calculating Delaunay Triangulations
When approaching a CFD simulation, the intent is to calculate flow behavior at and between a set of discrete points within the system being designed. Delaunay triangulations are used to visualize the connections between discrete points that represent surfaces in a system. The connections between solution points in the system are then used to build a finite difference scheme to solve the governing fluid dynamics equations.
Construction of a Delaunay triangulation requires establishing a triangulated connection between discrete points in your solution space, such that the smallest angle in the triangulation is maximized. The maximization procedure sets the triangulation to be as close to equilateral as possible. Maximizing the minimal angle in the triangulation is equivalent to finding a triangulation such that a circumscribed circle around each triangulation does not contain any other points except the vertices of the triangulation. This can be visualized in 2D below.
In this example, triangle ABD would be a Delaunay triangulation because its circumscribed circle only contains the vertices A, B, and D. Triangle ABC would not be a Delaunay triangulation because its circumscribed circle contains D, which is not a vertex of the triangle ABC. Therefore, we would prefer to use triangle ABD for mashing instead of ABC.
In 3D, the same central concept is used to define a Delaunay triangulation, but tetrahedra are drawn in 3D with circumscribed spheres. The triangulation procedure used in either case produces a mesh in O(nᐧlog(n)) time with maximum resolution in terms of area or volume elements. The procedure could be performed graphically in 2D, although for highly accurate CFD simulations, an algorithm is used to perform the triangulation.
Characteristics of Delaunay Triangulations
Applying Delaunay triangulation to a set of discrete points in 2D or 3D results in triangular or tetrahedral surface elements called a triangulated irregular network (TIN). This network has some important characteristics:
- Uniqueness: All Delaunay triangulations are unique for any set of points in 2D as long as points are not co-circular.
- Resolution: With fine enough discretization in the point set, the resulting Delaunay triangulation will produce maximum area/volume resolution. This results from repeated subdivisions when performing a triangulation algorithm.
- Computation time: For large datasets, a Delaunay triangulation has the shortest computation time among various point-set triangulation techniques. Two other methods that run with O(nᐧlog(n)) are the closest pair of points problem and the convex hull method.
Next, we need to consider how Delaunay triangulations can be constrained to conform to real surfaces, which may be discontinuous or include gaps. For this, we need to use a constrained Delaunay triangulation.
Constrained Delaunay Triangulations
If we start with a point set that overlaps some surface with prescribed holes or boundaries where the Delaunay triangulation must terminate, we are constructing a constrained Delaunay triangulation. Given a set of discrete points in space, how can triangulations be constructed around these points such that the surface resolution is maximized while accounting for boundaries on the meshed surface?
One technique is to perform the standard Delaunay triangulation across an entire surface while assuming continuity and then removing connecting edges that are bounded by discontinuities. A simple example is shown below. After removing edges that fall outside the prescribed boundaries, the resulting mesh only conforms to the surface that requires meshing. Note that this also eliminates some edges that would lie outside of the surface being meshed, as one would expect.
Constrained Delauney triangulation is used as the basis for algorithms that generate unstructured meshes on complex surfaces.
Why Is Constrained Delaunay Triangulation Used in CFD Meshing?
In addition to the useful properties of unconstrained Delauney triangulation, the constrained method nicely provides unstructured meshes for real systems. A real geometry used in a CFD simulation would involve some fluid flow across multiple surfaces that are discontinuous and oddly shaped. The unstructured meshing approach provided by constrained Delaunay triangulation is simple enough that it can be used as the basis of many unstructured meshing algorithms that are applicable in complex systems.
Real systems involving fluid flow can involve multiple geometric elements that require different levels of resolution and enforce prescribed mesh points on the boundaries. Meshing software that uses constrained Delaunay triangulation as the basis for its meshing procedure can accommodate these systems in a reasonable amount of time.
No matter the complexity of the system you need to simulate, you can generate unstructured meshes based on constrained Delaunay triangulation using the CFD simulation tools from Cadence. 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.