VoroCrust: Voronoi Meshing Without Clipping.

Area of Science:

• Computational Geometry
• Mesh Generation
• Computer-Aided Design

Background:

• Polyhedral meshes offer advantages over traditional meshes for specific applications.
• Existing polyhedral meshing algorithms struggle with complex domains, arbitrary curved boundaries, and sharp features.
• Primal-dual mesh pairs, like Voronoi-Delaunay meshes, are valuable in various formulations.

Purpose of the Study:

• To introduce VoroCrust, the first provably correct algorithm for conforming Voronoi meshing.
• To address limitations of existing methods in handling non-convex, non-manifold domains with curved boundaries and sharp features.
• To guarantee the quality of both surface and volume elements in the generated mesh.

Main Methods:

• VoroCrust employs a robust refinement process to estimate a suitable sizing field.
• Voronoi seeds are carefully placed on the surface, avoiding the need for clipping.
• The algorithm supports both structured and random sampling for filling the mesh interior.
• Sharp features are preserved throughout the meshing process.

Main Results:

• VoroCrust provides guaranteed quality for surface and volume elements in complex domains.
• The algorithm successfully handles non-convex and non-manifold domains with arbitrary curved boundaries and sharp features.
• It circumvents the drawbacks associated with clipping methods used in other Voronoi meshing techniques.
• Demonstrated superior performance compared to state-of-the-art clipped Voronoi cell methods.

Conclusions:

• VoroCrust is a significant advancement in polyhedral mesh generation, offering robustness and quality.
• The algorithm provides a provably correct and flexible solution for complex geometric domains.
• VoroCrust establishes a new standard for polyhedral meshing, particularly for applications requiring high-quality elements and feature preservation.