Sampling Conditions for Conforming Voronoi Meshing
- Thursday, February 15, 2018 from 3:10pm to 4:00pm
- Wilson Hall, 1-144 - view map
Applied Mathematics Seminar:
Ahmed Abdelkader (University of Maryland at College Park)
We study the problem of decomposing a volume with a smooth boundary 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 weighted $\alpha$-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 a $\sigma$-sparse $\epsilon$-sample, we work with the balls of radius $\delta$ times the local feature size centered at each sample. The corners of the union of these balls on both sides of the surface are the Voronoi sites and the interface of their cells is the medial axis of the union of balls yielding a watertight surface reconstruction. With the surface protected, the enclosed volume can be further decomposed by generating more sites inside it. Compared to clipping-based algorithms, 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 or randomly generated samples.
Joint work with Chandrajit L. Bajaj, Mohamed S. Ebeida, Ahmed H. Mahmoud, Scott A. Mitchell, John D. Owens, Ahmad A. Rushdi