VoroCrust: Simultaneous Surface reconstruction and Volume Meshing

  • 2016-07-01
  • Research

The first algorithm for simultaneous surface reconstruction and volumetric Voronoi meshing


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-starshaped 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.


I received a B.S in Applied Math, Engineering & Physics from the University of Wisconsin-Madison in 1988. I received an M.S. (1991) and Ph.D. (1993) in Applied Math from Cornell University. I worked the summer of 1991 at Xerox PARC with Marshall Bern and John Gilbert. Since Oct 1992 I’ve been at Sandia National Laboratories. I researched triangular and tetrahedral meshing algorithms via a computational geometry approach from 1992-1993. I was part of the Cubit project, doing mesh generation R&D from 1993-2000, and project leadership from 2000-2002. I did things like researching algorithms and existence proofs for hexahedral meshes and optimization for assigning the right number of edges locally so the model can be meshed globally. I managed the Optimization and Uncertainty Estimation department from 2002-2007. I served in various capacities on various programs, including LDRD (internal research program) and NNSA’s ASC program. I decided I missed building things and figuring things out for myself and moved on to technical work in 2007. After some informatics projects, I gravitated back to geometry and mesh generation. It’s been very fun and productive working with Mohamed S. Ebeida on disk-packing meshes and geometric approaches to optimization and uncertainty quantification since 2011.


This talk is organized by the Computer Graphics Group at the Institute of Computer Graphics and Algorithms. Supported by VRVis and the Austrian Computer Society (OCG).


Note: This is one of the thousands of items we imported from the old website. We’re in the process of reviewing each and every one, but if you notice something strange about this particular one, please let us know. — Thanks!