 |
Center for Nonlinear Studies |
We introduce VoroCrust for creating polyhedral meshes of 3D solids enclosed by 2D surfaces. VoroCrust is the first algorithm for 3D Voronoi meshes that naturally *conform* to sampled surface points. Conformality is distinguished from the usual *clipping* of Voronoi cells by the surface, which always results in extra surface vertices beyond the original samples, and may result in non-planar, non-convex, or even non-star-shaped cells. VoroCrust creates cell seeds such that points previously generated on the manifold are vertices of the 3D cells, and the only surface vertices. This avoids shrinkage and other changes. All cells are true Voronoi cells; the surface does not restrict or constrain the Voronoi cells, rather the cells are geometrically placed to reconstruct the surface, by the cell facets separating inside and outside seeds. These facets are well-shaped and usually triangles. Mesh polyhedra enjoy all the nice properties of Voronoi cells, such as being convex with planar facets. Cell aspect ratios and dihedral angles are bounded. We have not yet addressed the issues of small edges, sharp edge angles, and small area faces, which may be important for some types of simulations. In contrast to the well-known 'power crust' surface reconstruction algorithm, VoroCrust fills the volume with tunable 3D cells with good shape, that is, VoroCrust output is usable as a finite volume mesh. Also, VoroCrust's 2D manifold reconstruction is from an *unweighted* Voronoi diagram, which supports fast inside/outside queries. The VoroCrust algorithm starts by creating surface sample points. We use Poisson-disk Sampling (MPS), placing points densely compared to the local thinness and curvature, with additional algorithms for sharp and thin features. (Or the points may be generated by some other surface other triangulation mesher and given as input.) In either case we create spheres around samples. We define triple-intersection points as Voronoi seeds near the surface. We create additional seeds interior to the volume; we have algorithms to place these randomly, or in a structured way to create a hex-dominant mesh. We generate the 3D Voronoi tessellation of all these seeds. The manifold is reconstructed by the Voronoi facets separating the inside and outside cells. This talk describes the algorithmic and engineering aspects of VoroCrust, especially the surface sampling (meshing) and mesh grading.
Host: Mikhail Shashkov