Voronoi Dual Meshing and Simulation

Scott Mitchell, Sandia National Laboratories
Mohamed Ebeida, Sandia National Laboratories
Unstructured meshing traditionally focuses on the quality of the primal triangulation, often with no consideration of the dual mesh. However, there is growing recognition of the desirability of well-shaped primal/dual pairs for enabling fast and accurate numerical computations. The primal/dual formulation is appealing for compatible discretizations of second-order elliptic PDEs, and stability and accuracy on general unstructured finite element grids.

For primal/dual mesh pairs, the two most important properties are “orthogonality,” dual facets being orthogonal to their primal edges for accurate computation of divergence, flux, velocity, circulation, etc.; and “interpolation,” dual vertices lying  inside their primal simplex for fast and accurate interpolation, discrete differential operators, control volumes, etc. Divergence and curl have natural expressions on, and can be related by, a mesh and its dual. Simulation accuracy often degrades when a dual vertex falls outside the corresponding primal element, as the simulation value assigned to a dual node arises from, or represents, integration over the primal element. Achieving both properties simultaneously is a mesh optimization problem, or can be finessed by changing the finite element formulation.

In some simulations, the primal mesh is unimportant and only the dual mesh is used. Dual Voronoi cells are polygons in 2d, and polyhedral in 3d. Hence generating these dual meshes is known as “Polyhedral Meshing.” Polyhedral meshes have advantages over other types (e.g. tetrahedral) in terms of filling space with fewer elements, computing numerical gradients and flux, tolerating stretched elements, axis-insensitivity, etc. Polyhedral meshes can be easily obtained by the Voronoi diagram of a point set, the dual of its Delaunay triangulation. As with traditional meshes, complicated, convoluted, concave, or even just curved boundaries present some challenges and require smaller elements, etc. Small edges can be time-step limiting, and collapsing short edges leads to non-planar facets and other numerical issues. Polyhedral meshing is an increasingly important area, both in research and commercial contexts.

This minisymposium aims to present the current state of the art in Voronoi meshing and its connection to simulation quality and stability, including simultaneous primal-dual meshes, and polyhedral-only meshes. There are a variety of researchers within computational science studying different simulation approaches and different criteria for dual meshes. In addition, dual meshes are also being studied in the context of computer graphics. This minisymposium aims to bring together researchers from these diverse fields and approaches, for a cross cultural exchange, and to engage those new to the field.