License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2018.1
URN: urn:nbn:de:0030-drops-87147
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8714/
Abdelkader, Ahmed ;
Bajaj, Chandrajit L. ;
Ebeida, Mohamed S. ;
Mahmoud, Ahmed H. ;
Mitchell, Scott A. ;
Owens, John D. ;
Rushdi, Ahmad A.
Sampling Conditions for Conforming Voronoi Meshing by the VoroCrust Algorithm
Abstract
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 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 an epsilon-sample on the bounding surface, with a weak sigma-sparsity condition, we work with the balls of radius delta 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 epsilon, sigma and delta, 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.
BibTeX - Entry
@InProceedings{abdelkader_et_al:LIPIcs:2018:8714,
author = {Ahmed Abdelkader and Chandrajit L. Bajaj and Mohamed S. Ebeida and Ahmed H. Mahmoud and Scott A. Mitchell and John D. Owens and Ahmad A. Rushdi},
title = {{Sampling Conditions for Conforming Voronoi Meshing by the VoroCrust Algorithm}},
booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)},
pages = {1:1--1:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-066-8},
ISSN = {1868-8969},
year = {2018},
volume = {99},
editor = {Bettina Speckmann and Csaba D. T{\'o}th},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8714},
URN = {urn:nbn:de:0030-drops-87147},
doi = {10.4230/LIPIcs.SoCG.2018.1},
annote = {Keywords: sampling conditions, surface reconstruction, polyhedral meshing, Voronoi}
}
|
Keywords: |
|
sampling conditions, surface reconstruction, polyhedral meshing, Voronoi |
|
Collection: |
|
34th International Symposium on Computational Geometry (SoCG 2018) |
|
Issue Date: |
|
2018 |
|
Date of publication: |
|
08.06.2018 |
