The Voronoi Diagram and Delaunay Triangulation
Key Takeaways
The Voronoi diagram and Delaunay triangulation are the ideal approaches to generating an unstructured mesh complex geometry simulation.
The Voronoi diagram is a dual of Delaunay triangulation. Both use the same set of points and the properties that are true for one hold true for another.
Through capture of the flow domain with high-order meshing, the Voronoi diagram and Delaunay triangulation facilitate an in-depth understanding of flow behavior.
Unstructured grid creation using Delaunay triangulation
In the computational analysis of a fluid system, mesh generation for simulation is a commonly implemented method. This generated mesh can be used to simulate flow behavior or heat transfer behavior in a wide range of applications, including in the aerospace and automotive industry.
For complex geometries, mesh generation can be accomplished using the Voronoi diagram and Delaunay triangulation approach. In computational fluid dynamics (CFD), these methods generate accuracy and stability in the meshing process. Let us take a detailed look at the concept of the Voronoi diagram and Delaunay triangulation and analyze their implications in generating high-quality meshes.
The Voronoi Diagram and Delaunay Triangulation for Mesh Generation
In CFD analysis, system designers seek to represent the real flow problems in a geometric domain. Mesh generation divides this domain into a finite number of smaller cells where the governing equation is discretized using different techniques and solved for numerical analysis of complex engineering problems. These meshes can be structured or unstructured, depending on the complexity of the geometry; however, their quality is an extremely important determinant of the accuracy of the simulation.
Unstructured meshes are more flexible for representing complex geometries and generally use the triangulation method to represent such complicated domains with accuracy. The Voronoi diagram and Delaunay triangulation are commonly used to generate unstructured mesh.
Delaunay Triangulation
Delaunay triangulation
Delaunay triangulation is the algorithm that facilitates the dividing of discrete sets of points in a plane to form a set of triangles. While there are many methods to achieve triangulation, what differentiates Delaunay triangulation is that:
- The circumcircle of each triangle contains only the three vertices of the given triangle.
- No vertices exist inside the circumcircle of this triangle.
- The triangles are equiangular or have very slight variations.
If the mesh generated is not fine enough, it can be refined by inserting additional points for improved resolution. The advantages of such an approach are improved accuracy and complete reflection of the natural boundary of the geometry.
Another benefit of Delaunay triangulation includes the construction of the Voronoi diagram.
Voronoi Diagram
Delaunay triangulation (in black) and Voronoi diagram (in red).
The Voronoi diagram is the process of mesh generation where the plane is divided into smaller regions based on the proximity of the points called ‘sites’ or ‘seeds’. For instance, imagine there are multiple points scattered on a plane. For each of these points, draw a line that is closer in proximity and equidistant from the two adjacent points. The Voronoi diagram is formed through the connection of these lines, which divides the domain into a set of polygons.
The Voronoi diagram is also considered to be the dual of Delaunay triangulation. Given both approaches use the same set of points, the property for Delaunay triangulation holds true for the Voronoi diagram and vice versa.
Implications of Voronoi Diagram - Delaunay Triangulation in CFD Meshing
The algorithm for Delaunay triangulation and the Voronoi diagram present many benefits in the CFD mesh generation process, including:
- Efficient computation of a large set of points
- Flexibility to adapt to complex geometries
- High-quality meshing with well-defined cells
- Adaptive mesh generation for addressing complexity near boundaries
These benefits can be leveraged using the following steps for CFD meshing:
- Define the flow geometry and identify the shape of the domain.
- Generate a finite set of points to sufficiently capture the geometrical complexity within the domain. These points will be referenced in the Voronoi diagram and Delaunay triangulation.
- Compute the Voronoi diagram and Delaunay triangulation using the points generated to create a set of polygons and triangles. This can be done using techniques such as the Bowyer-Watson algorithm.
- Define the boundary conditions to ideally represent the effects of flow parameters such as velocity and temperature at the boundary.
- Refine the mesh if required to improve the resolution and accuracy of the mesh.
- Use a CFD solver to run the simulation and analyze the fluid flow behavior by solving the governing equation.
High-Quality Mesh Generation for Simulation Accuracy
The higher the quality of the mesh, the more precise and accurate the analysis of fluid system behavior. Tools such as the Voronoi diagram and Delaunay triangulation facilitate the generation of unstructured mesh to define the complex geometrical flow domain. In this domain, the governing partial differential equation can be discretized and solved to understand the flow behavior and its effect on the structure.
You can make use of CFD tools such as Fidelity Pointwise to support the mesh generation process for a wide range of flow analysis and simulation applications for accuracy and efficiency.
Subscribe to our newsletter for the latest CFD updates or browse Cadence’s suite of CFD software, including Fidelity and Fidelity Pointwise, to learn more about how Cadence has the solution for you.