# High-Fidelity CFD Mesh Generation With Voronoi Diagram

A geometric concept that helps shorten the time to create an accurate mesh.

We are attuned to the fact that the law of nature, or nature’s rule, drives various scientific phenomena. Humans often replicate naturally occurring phenomena to achieve a desirable outcome, similar to how scientists mimic photosynthesis to generate energy. Comparable is the case with Voronoi geometries. These geometries are widely seen in beehives, the structure of sponges, rock fragmentation, and even in human epidermal cells and bones. What if these geometries can be applied to Computational Fluid Dynamics (CFD) for high-fidelity meshes?

## About Voronoi diagrams

The Voronoi diagram, or Thiessen Polygon maps, or Dirichlet tessellation, is formed when a plane is partitioned into polygons, and each polygon encompasses one generating point. In other words, in a Voronoi diagram, each point “owns” the region of space closer to itself than any other points [1]. The cells or polygons formed by this partition are called Voronoi polygons or Dirichlet regions.

The use of Voronoi diagrams dates to the 1600s when Rene Descartes, a philosopher, used a similar concept as the Voronoi diagram to partition the universe into vortices for his research. The actual work and definition of Voronoi diagrams were coined by two German mathematicians, Lejeune Dirichlet in 1850 and Georgy Voronoy in 1908; hence the name Dirichlet tessellation or Voronoi diagram.

## Predicting the cholera outbreak with the Voronoi diagram

A famous use of the Voronoi diagram was during the cholera outbreak in 1854 in Soho, London. Health authorities asserted that the spread was due to the “bad air” from the open sewers, but John Snow, a physician, was confident that the epidemic was due to contaminated water, and he used Voronoi diagrams to prove it.

At first, Snow created a map that depicted the geographic distribution of deaths due to the outbreak. The bars on the map represented death and illustrated how the deaths were clustered in a specific zone around a particular water pump (Broad Street pump). However, there were also other pumps nearby, so it was difficult to confirm the source of water contamination from the Broad Street pump.

As the second step in his investigation, he drew a curve that covered an equal distance between the Broad Street pump and the other pumps, and this curve defined the Broad Street pump’s Voronoi cell. Almost all the points on the map were within the curve, and he used this evidence to convince the health authorities that the outbreak was due to water contamination and that the source was the Broad Street pump.

## Delaunay triangulation: Geometric dual of Voronoi diagrams

Delaunay triangulation.

Delaunay triangulation (DT) dates back to 1934, put forth by mathematician Boris Delaunay. 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.

Examples of Delaunay triangulation.

A Delaunay triangulation is a point-wise structure consisting of non-overlapping triangles, as shown above. When extended to a plane or surface, the triangles are not restricted to uniformity. We now know that a Voronoi diagram splits the space into polygons enclosing a generating point. DT is the nerve of the cells in the Voronoi diagram and is referred to as the geometric dual of the latter. DT is largely used for creating meshes that can be used for finite element analysis and finite volume method solvers because of its angle guarantee and as speedy triangulation algorithms are available.

## High-fidelity meshing using Voronoi diagram

Solving complex flow equations requires highly accurate meshing, and the Cadence CFD portfolio provides meshing, solving, and post-processing solutions and is compatible with external CFD workflows. Mesh generation is one of the most impactful steps in a CFD workflow. It impacts the solution accuracy, convergence, and simulation efficiency. Our robust geometry preparation capabilities shorten the time needed to create a high-quality mesh.

There are many avenues for meshing available. Our rapid generation of hybrid meshes uses an advancing layer technique to generate near-wall, boundary layer-resolving prisms and hexahedra. To refine and adapt a mesh, clustering sources provide control of mesh resolution away from walls, near wakes, vortices, and other flow features.

CFD workflow with Fidelity Cascade Technologies.

Our recent investment in Cascade Technologies has expanded our portfolio of high-fidelity CFD solutions. We now have solutions for advanced simulations that can be accelerated on CPU and GPUs to reduce turnaround time, allowing system companies to improve the durability and performance of the systems they design and manufacture.

Cadence Cascade technologies offer a robust, rapid, and massively parallel generation of 3D meshes based on clipped Voronoi diagrams. This meshing tool allows fast point-seeding routines for various packings, window-based refinement zones, and near-wall strand seedings. It also supports integration with other mesh point sources for partial or full volume.

Reference

1. Ambo, K., Nagaoka, H., Philips, D.A., Ivey, C., Bres, G.A., and Bose, S.T., Aerodynamic force prediction of the laminar to turbulent flow transition around the front bumper of the vehicle using Dynamic-slip wall model LES. AIAA 2020-0036. Retrieved from: https://arc.aiaa.org/doi/10.2514/6.2020-0036