Conquering 3D Delaunay Triangulation
Key Takeaways
-
The Delaunay criterion can be used for unstructured grid generation, forming a structure called a Delaunay triangulation.
-
A 3D Delaunay triangulation uses tetrahedra to discretize the volume through which a flow will occur.
-
This meshing method can be used to examine flows along arbitrary surfaces and complex volumes, including in hybrid meshes that require various levels of resolution.
Fluid dynamics, structural mechanics, thermodynamics, and even electromagnetics share a common geometric tool that is used in various simulations. Structural meshes and discretized numerical models are used in systems requiring 3D simulations of complex phenomena in space and time. Computational tools are used to generate these simulation models by implementing various algorithms, all of which are designed to balance the need for high accuracy with low computational complexity.
One powerful meshing method is Delaunay triangulation, which can be efficiently generated through several methods based on some simple geometric constraints. 3D Delaunay triangulation builds a set of discrete points that represent a real system, and these points must be chosen such that the system can be simulated with the desired accuracy. In this article, we’ll explore the important properties of 3D Delaunay triangulation as well as some methods to compute these standard algorithms.
Defining 3D Delaunay Triangulations
Delaunay triangulation can be used to generate unstructured meshes in 2D or 3D spaces. In the case of 3D triangulations, tetrahedral regions are drawn out subject to a geometric constraint that sets the shape and distance between nodes that make up mesh elements. The resulting tetrahedron gives a set of 3D regions where the main fluid dynamics equations can be discretized and solved. Points in the mesh are selected such that the following properties are enforced:
- Circumference condition: If a sphere is circumscribed about any tetrahedron in the triangulation, that sphere must only contain the points that make up the sphere. All other grid points that make up the mesh must lie outside this 3D volume. This condition is equivalent to limiting the mesh density for a given length scale.
- Angle maximization condition: The smallest internal solid angles in the tetrahedra in the resulting Delaunay triangulation attempt to maximize the minimum solid angle for all angles in the triangulation. As a result, the tetrahedra in the mesh may not be equilateral. However, this helps eliminate sliver elements that might result along boundaries in a simulation system.
- Order-independent and unique: A uniqueness property of Delaunay triangulation states the calculated triangulation will be independent of the order in which new points are added to the mesh. Some meshing algorithms are iterative and will add new points as the algorithm proceeds; the above two properties of Delaunay triangulation will ensure the same mesh is generated regardless of the order of point addition.
A major advantage of Delaunay triangulation is its flexibility in adapting to complex surfaces and volumes. A Delaunay triangulation is a good option to start building a CFD model that does not require adaptive meshing throughout the system, yet it can still be implemented as the basis for a hybrid mesh in a 3D system.
Example triangles used to construct 3D Delaunay triangulations
Methods for Calculating Delaunay Triangulation
There are many methods for calculating a Delaunay triangulation for a given system in Euclidean space. These include:
Bowyer-Watson Algorithm: This algorithm is probably the most popular algorithm implemented in meshing software. Given an initial tetrahedra and boundaries, this iterative procedure adds points outside the circumscription to create new tetrahedra. Generated points that happen to lie inside any circumscribed tetrahedra are removed from the generated grid.
Divide and Conquer: The divide and conquer method uses a recursive algorithm to split vertices of existing tetrahedra into two sets, then the triangulation is calculated for each set of vertices. The sets are then merged along their intersecting boundaries to give a combined triangulation. This method can be faster than other methods, as it effectively splits regions into simpler blocks that require lower computation time than the entire system.
Incremental Algorithms: This method involves sequentially adding new vertices and checking that the generated vertices satisfy the Delaunay triangulation properties. When the generated vertices do not create a grid that satisfies the main properties of Delaunay triangulations, a vertex can be adjusted or deleted. This is akin to a random search procedure that is used in other types of optimization problems.
Flipping: This is similar to the previous iterative technique, but it involves swapping an edge between two vertices in a tetrahedron that does not satisfy the main conditions listed above. The selected edge swap will be adjacent to the minimum solid angle in the tetrahedron. This will take a non-Delaunay triangulation and transform it into a Delaunay triangulation by enforcing the Delaunay geometric conditions.
Sweep Hull: The sweep hull algorithm is a hybrid incrementalization and flipping algorithm. Tetrahedra in the triangulation are constructed by sequentially adding new points to the triangulation in the 2D face on each tetrahedron, followed by flipping within the constructed tetrahedron to achieve the triangulation. New points are added until the resulting triangulation spans the entire solution space.
When you need to calculate a 3D Delaunay triangulation to simulate flows in complex systems, use the meshing features in Pointwise from Cadence. When you’re ready to run a CFD simulation for your system, you can use the simulation tools in Omnis to implement modern numerical approaches for complex flows. Cadence’s complete set of CFD simulation features can be used to implement aerodynamics simulations, turbulent and laminar flow simulations, reduced fluid flow models, and much more.
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.