Using a Delaunay Triangulation Algorithm for Mesh Generation
Key Takeaways
-
What is Delaunay triangulation?
-
Delaunay triangulation algorithm properties.
-
Using Delaunay triangulation algorithms for mesh generation.
Delaunay triangulation
Without a doubt, analytical geometry is one of the most useful tools engineers have for evaluating the properties of areas and surfaces. However, determining the best technique or method of analysis can be a challenge, as there are several algorithms from which to choose. Ultimately, the best choice depends on arriving at the optimum grouping of points to represent the shape, which is not an easy task. Too few can mean missing important data, such as local extrema, while too many may strain computing resources without any real analytical benefit.
Successfully addressing this issue can be critical when performing boundary layer analysis to avoid problems such as vortex shedding, which can greatly affect system operation. Therefore, your design process should include an effective CFD analysis tool, which requires the generation of an accurate surface mesh. One of the most commonly implemented methods for creating this essential surface model is to utilize a Delaunay triangulation algorithm.
What Is Delaunay Triangulation?
Examples of Delaunay triangulation. Image from Mathworks.
Delaunay triangulation dates back to 1934, when it was put forth by its namesake—mathematician Boris Delaunay (pronounced Delone). Since then, it has gained widespread usage in analytical geometry and is primarily used to generate a mesh model of a surface or enclosed space to enable boundary condition analysis.
A Delaunay triangulation is a point-wise structure consisting of non-overlapping triangles, as shown by the examples above. When extended to a plane or surface, the triangles are not restricted to uniformity. In fact, atypical Delaunay triangulations will include triangles of various sizes and angles. However, these comprehensive coverage triangulations possess specific properties to which development algorithms must adhere.
Properties of Delaunay Triangulation Algorithms
There are several techniques that can be used to create triangulations. However, to qualify as a Delaunay triangulation algorithm, certain properties must be satisfied (as listed below).
Delaunay Triangulation Algorithm Attributes
▲ All points of a Delaunay triangulation are vertices of a triangle within the point space.
▶ A circle circumscribed within the triangulation contains no interior points.
▼ Within the triangulation, minimum coplanar angles of each Delaunay triangle are
maximized.
◀ The projection of an n-dimensional Delaunay triangle is a convex facet of the points,
projected within an (n+1)-dimensional paraboloid.
◣ The convex hull of the Delaunay triangulation is the union of all simplices.
◤ The triangulation is the dual of the corresponding Voronoi diagram for the set of points.
Valid Delaunay triangulation algorithms must produce point structures that satisfy the listings above. Notable techniques used to achieve the triangulation are:
- Divide and Conquer
Done properly, the divide and conquer may be the fastest Delaunay triangulation algorithm. The process is to split the vertices into two sets, recursively, then compute the triangulation for each set. The sets are merged along the split line. - Flipping
Flipping is a direct approach. Start by creating any triangulation, and as non-Delaunay triangles are found, simply flip one of the edges until none remain. - Sweep Hull
Sweep hull is a hybrid technique that combines radial propagation from inside the point space to its extent and flipping to achieve triangulation. - Incrementalization
This is a basic technique of adding vertices sequentially and correcting the triangulation as necessary at each step. - Bowyer-Watson
Bowyer-Watson utilizes incrementalization, where points are continually added and where created triangles that contain points within their circumscribed circle are deleted. For n points, this process can require from n2 to nlog(n) operations to complete the triangulation.
A successful Delaunay triangulation algorithm provides the mesh foundation that enables CFD analysis for your system.
Mesh Generation and Analysis With Delaunay Triangulation
In the figure below, a mesh created for aerodynamics analysis using Delaunay triangulation is shown.
CFD analysis with Pointwise 3D Delaunay triangulation
This implementation demonstrates the high dimensional order for which Delaunay triangulation can be used. For these and complex structures, however, advanced mathematical methods and tools are necessary for efficient mesh analysis. Standalone packages such as Matlab, Mathematica, and MathCAD provide functions that minimize or eliminate any script writing. However, these do not provide solutions that can be directly applied to system design. A more efficient alternative is to utilize Cadence’s Pointwise—used to generate the mesh above—which integrates smoothly with the other system design capabilities required for your design.
For designs where Delaunay triangulation algorithm-created mesh analysis is required, such as aerodynamics and other CFD applications, Pointwise is a powerful and easy-to-use program that is a part of Cadence’s advanced systems analysis toolbox.
Subscribe to our newsletter for the latest CFD updates or browse Cadence’s suite of CFD software to learn more about how Cadence has the solution for you.