VoroCrust: Voronoi Meshing Without Clipping

Autor: Ahmad A. Rushdi, Ahmed H. Mahmoud, Chandrajit L. Bajaj, Ahmed Abdelkader, Mohamed S. Ebeida, John D. Owens, Scott A. Mitchell
Rok vydání: 2020
Předmět:
Surface (mathematics)
Computational Geometry (cs.CG)
FOS: Computer and information sciences
Artificial Intelligence and Image Processing
Computer science
Voronoi
02 engineering and technology
Computer Science::Computational Geometry
01 natural sciences
sharp features
Field (computer science)
Article
Computer Science - Graphics
meshing
Slivers
cs.GR
0202 electrical engineering
electronic engineering
information engineering
Mathematics::Metric Geometry
Polygon mesh
0101 mathematics
ComputingMethodologies_COMPUTERGRAPHICS
Flexibility (engineering)
Poisson-disk Sampling
I.3.5
Process (computing)
Software Engineering
020207 software engineering
Refinement
Union of Balls
Computer Graphics and Computer-Aided Design
Graphics (cs.GR)
cs.CG
010101 applied mathematics
Computer Science::Graphics
Computer Science - Computational Geometry
Clipping (computer graphics)
Voronoi diagram
Algorithm
Information Systems
Zdroj: ACM transactions on graphics, vol 39, iss 3
ACM Trans Graph
Popis: 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.
18 pages (including appendix), 18 figures. Version without compressed images available on https://www.dropbox.com/s/qc6sot1gaujundy/VoroCrust.pdf. Supplemental materials available on https://www.dropbox.com/s/6p72h1e2ivw6kj3/VoroCrust_supplemental_materials.pdf
Databáze: OpenAIRE
Externí odkaz: