VoroCrust: Simultaneous Surface Reconstruction and Volume Meshing with Voronoi cells (Guest Talk)

I'll describe VoroCrust, the first algorithm for simultaneous surface reconstruction and volumetric Voronoi meshing. By surface reconstruction, I mean that weighted sample points are created on a smooth manifold, and we are tasked with building a mesh (triangulation) containing those points that approximates the surface. By Voronoi meshing, I mean that we create Voronoi cells that are well-shaped polytopal decompositions of the spaces inside and outside the manifold. By "simultaneous", I mean that the surface mesh is the interface of the two volume meshes.

VoroCrust meshes are distinguished from the usual approach of clipping Voronoi cells by the manifold, which results in many extra surface vertices beyond the original samples, and may result in non-planar, non-convex, or even non-star-shaped cells.

The VoroCrust algorithm is similar to the famous "power crust." Unlike the power crust, our output Voronoi cells are unweighted and have good aspect ratio. Moreover, there is complete freedom of how to mesh the volume far from the surface. Most of the reconstructed surface is composed of Delaunay triangles with small circumcircle radius, and all samples are vertices. In the presence of slivers, the reconstruction lies inside the sliver, interpolating between its upper and lower pair of bounding triangles, and introducing Steiner vertices.