VoroCrust: Voronoi Meshing Without Clipping
Authors:
- Ahmed AbdelkaderAAAhmed Abdelkader
- Chandrajit L. BajajCBChandrajit L. Bajaj
- Mohamed S. EbeidaMEMohamed S. Ebeida
- Ahmed H. MahmoudAMAhmed H. Mahmoud
- Scott A. MitchellSMScott A. Mitchell
- John D. OwensJOJohn D. Owens
- Ahmad A. RushdiARAhmad A. Rushdi
Preprint
Abstract
Polyhedral meshes are increasingly becoming an attractive option with particular advantages over traditional meshes for certain applications. What has been missing is a robust polyhedral meshing algorithm that can handle broad classes of domains exhibiting arbitrarily curved boundaries and sharp features. In addition, the power of primal-dual mesh pairs, exemplified by Voronoi-Delaunay meshes, has been recognized as an important ingredient in numerous formulations. The VoroCrust algorithm is the first provably-correct algorithm for conforming polyhedral Voronoi meshing for non-convex and non-manifold domains with guarantees on the quality of both surface and volume elements. A robust refinement process estimates a suitable sizing field that enables the careful placement of Voronoi seeds across the surface circumventing the need for clipping and avoiding its many drawbacks. The algorithm has the flexibility of filling the interior by either structured or random samples, while preserving all sharp features in the output mesh. We demonstrate the capabilities of the algorithm on a variety of models and compare against state-of-the-art polyhedral meshing methods based on clipped Voronoi cells establishing the clear advantage of VoroCrust output.Keywords
All Related Versions
This publication has 44 references indexed in Scilit:
- A displacement‐based finite element formulation for general polyhedra using harmonic shape functionsInternational Journal for Numerical Methods in Engineering, 2014
- Solution of the diffusion equation in multi‐material domains by sub‐division of elements along reconstructed interfacesInternational Journal for Numerical Methods in Fluids, 2011
- Meshing volumes with curved boundariesEngineering with Computers, 2010
- Optimizing Voronoi Diagrams for Polygonal Finite Element Computations2010
- Delaunay Refinement for Piecewise Smooth ComplexesDiscrete & Computational Geometry, 2008
- Barycentric coordinates for convex setsAdvances in Computational Mathematics, 2006
- Three-Dimensional Delaunay Mesh GenerationDiscrete & Computational Geometry, 2006
- Discrete Riemann Surfaces and the Ising ModelCommunications in Mathematical Physics, 2001
- Conservation Properties of Unstructured Staggered Mesh SchemesJournal of Computational Physics, 2000
- Surface Reconstruction by Voronoi FilteringDiscrete & Computational Geometry, 1999