Lab Home | Phone | Search
Center for Nonlinear Studies  Center for Nonlinear Studies
 Home 
 People 
 Current 
 Affiliates 
 Visitors 
 Students 
 Research 
 ICAM-LANL 
 Publications 
 Conferences 
 Workshops 
 Sponsorship 
 Talks 
 Colloquia 
 Colloquia Archive 
 Seminars 
 Postdoc Seminars Archive 
 Quantum Lunch 
 Quantum Lunch Archive 
 CMS Colloquia 
 Q-Mat Seminars 
 Q-Mat Seminars Archive 
 P/T Colloquia 
 Archive 
 Kac Lectures 
 Kac Fellows 
 Dist. Quant. Lecture 
 Ulam Scholar 
 Colloquia 
 
 Jobs 
 Postdocs 
 CNLS Fellowship Application 
 Students 
 Student Program 
 Visitors 
 Description 
 Past Visitors 
 Services 
 General 
 
 History of CNLS 
 
 Maps, Directions 
 CNLS Office 
 T-Division 
 LANL 
 
Monday, June 13, 2016
10:00 AM - 11:00 AM
CNLS Conference Room (TA-3, Bldg 1690)

Seminar

VoroCrust Algorithm: 3D Polyhedral Meshing with True Voronoi Cells Conforming to Surface Samples

Mohamed S. Ebeida
SNL

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