We study the problem of decomposing a volume bounded by a smooth surface into a collection of Voronoi cells. Unlike the dual problem of conforming Delaunay meshing, a principled solution to this problem for generic smooth surfaces remained elusive. VoroCrust leverages ideas from αshapes and the power crust algorithm to produce unweighted Voronoi cells conforming to the surface, yielding the first provably-correct algorithm for this problem. Given an ϵ-sample on the bounding surface, with a weak σ-sparsity condition, we work with the balls of radius δ times the local feature size centered at each sample. The corners of this union of balls are the Voronoi sites, on both sides of the surface. The facets common to cells on opposite sides reconstruct the surface. For appropriate values of ϵ, σ and δ, we prove that the surface reconstruction is isotopic to the bounding surface. With the surface protected, the enclosed volume can be further decomposed into an isotopic volume mesh of fat Voronoi cells by generating a bounded number of sites in its interior. Compared to state-of-the-art methods based on clipping, VoroCrust cells are full Voronoi cells, with convexity and fatness guarantees. Compared to the power crust algorithm, VoroCrust cells are not filtered, are unweighted, and offer greater flexibility in meshing the enclosed volume by either structured grids or random samples. licensed under Creative Commons License CC-BY Mesh generation is a fundamental problem in computational geometry, geometric modeling, computer graphics, scientific computing and engineering simulations. There has been a growing interest in polyhedral meshes as an alternative to tetrahedral or hex-dominant meshes [48] . Polyhedra are less sensitive to stretching, which enables the representation of complex geometries without excessive refinement. In addition, polyhedral cells have more neighbors even at corners and boundaries, which offers better approximations of gradients and local flow distributions. Even compared to hexahedra, fewer polyhedral cells are needed to achieve a desired accuracy in certain applications. This can be very useful in several numerical methods [18], e.g., finite element [42], finite volume [39], virtual element [17] and Petrov-Galerkin [41] . In particular, the accuracy of a number of important solvers, e.g., the two-point flux approximation for conservation laws [39], greatly benefits from a conforming mesh which is orthogonal to its dual as naturally satisfied by Voronoi meshes. Such solvers play a crucial role in hydrology [51], computational fluid dynamics [22] and fracture modeling [20]. VoroCrust is the first provably-correct algorithm for generating a volumetric Voronoi mesh whose boundary conforms to a smooth bounding surface, and with quality guarantees. A conforming volume mesh exhibits two desirable properties simultaneously: (1) a decomposition of the enclosed volume, and (2) a reconstruction of the bounding surface. Conforming Delaunay meshing is well-studied [28], but Voronoi meshing is less mature. A common practical approach to polyhedral meshing is to dualize a tetrahedral mesh and clip, i.e., intersect and truncate, each cell by the bounding surface [35, 43, 47, 52, 55] . Unfortunately, clipping sacrifices the important properties of convexity and connectedness of cells [35] , and may require costly constructive solid geometry operations. Restricting a Voronoi mesh to the surface before filtering its dual Delaunay facets is another approach [7, 33, 56] , but filtering requires extra checks complicating its implementation and analysis; see also Figure 4 . An intuitive approach is to locally mirror the Voronoi sites on either side of the surface [34, 57] , but we are not aware of any robust algorithms with approximation guarantees in this category. In contrast to these approaches, VoroCrust is distinguished by its simplicity and robustness at producing true unweighted Voronoi cells, leveraging established libraries, e.g., Voro++ [50], without modification or special cases. VoroCrust can be viewed as a principled mirroring technique, which shares a number of key features with the power crust algorithm [13] . The power crust literature [7, 8, 10, 12, 13] developed a rich theory for surface approximation, namely the ϵ-sampling paradigm. Recall that the power crust algorithm uses an ϵ-sample of unweighted points to place weighted sites, so-called poles, near the medial axis of the underlying surface. The surface reconstruction is the collection of facets separating power cells of poles on the inside and outside of the enclosed volume. Abdelkader et al.
In contrast, VoroCrust is able to capture the surface using pairs of unweighted seeds placed close to the surface, enabling further decomposition of the interior using additional seeds; see Figure 3 An abstract version of the VoroCrust algorithm for smooth manifold surfaces was recently analyzed by REF .
Sampling Conditions for Conforming Voronoi Meshing by the VoroCrust Algorithm
LIPIcs : Leibniz international proceedings in informatics
LIPIcs : Leibniz international proceedings in informatics
Computer Science Medicine Mathematics