Clipped Voronoi Diagrams on GPU

Voronoi diagrams are one of the most fundamental constructs in computational geometry. Given an arbitrary point cloud (generators), its Voronoi diagram partitions space into convex cells around these generators. These cells are (a) uniquely defined and (b) each cell can be computed independently. Both these properties can be exploited in parallel construction algorithms.

Conceptually, Voronoi diagrams extend to infinity, so to make them useful for numerical simulation they must be restricted to the computational domain, e.g., by clipping them by the domain’s boundary. By moving generators onto the boundary, sliver cells can be avoided (in contrast to Cartesian cut-cells) and faces between two boundary generators tend to be normal to the boundary, both helping accuracy of numerical simulations. Moving generators, adding them for refinement or removing them is possible due to the topological flexibility of Voronoi diagrams.

We present a mesh generator based on clipped Voronoi diagrams on GPU. It is fully automated and designed to be robust against dirty geometry such as gaps and overlaps by utilizing the healing property of winding numbers.

The backbone of this mesh generator is a GPU toolbox of geometric algorithms: Octree creation from a faceted boundary geometry with adaptive size controls, Voronoi diagram construction, robust geometric predicates with systematic handling of degeneracies based on virtual perturbations (Simulation of Simplicity), efficient winding number calculation, ray-surface intersection, clipping of a volume mesh by a faceted boundary geometry, etc.

The mesh generator and the GPU toolbox are being developed in a cross-BU collaboration between DBU, MDU, and FBU. Its first release target is to provide meshes for the CFD solver in Discovery Explore, and it is planned that other products will be targeted soon.

Test cases demonstrating the automation potential of the clipped Voronoi approach and its performance on GPU will be presented at the conference.