Hexahedral meshing of non-linear volumes using Voronoi faces and edges

International Journal for Numerical Methods in Engineering, John Wiley, Vol 49, Num 1, pp.329-351, September 10-20 2000

MESHING
RESEARCH
CORNER

Special Edition on Unstructured Mesh Generation
International Journal for Numerical Methods in Engineering, Vol 49 Number 1-2, 10-20 September 2000

Correspondence to: Alla Sheffer, 3242 Digital Computer Laboratory (DCL), University of Illinois at Urbana-Champaign, 1304 W. Springfield Avenue, Urbana, IL 61801, U.S.A.
E-mail: sheffa@uiuc.edu
E-mail: berco@cs.huji.ac.il

Abstract
This work extends an algorithm presented in our recent paper (Sheffer et al. Engng. Comput. 1999; 15: 248-262.) for automatic hexahedral meshing, based on the embedded Voronoi graph (EVG). The embedded Voronoi graph contains the full symbolic information of the Voronoi diagram and the medial axis of the object, and a geometric approximation to the real geometry. The EVG is used for decomposing the object, into simple sub-volumes meshable by basic meshing techniques.

The EVG provides complete information regarding proximity and adjacency relationships between the entities of the volume. Hence, decomposition faces are determined unambiguously, without any further geometric computations and the resulting sub-volumes are guaranteed to be well defined and disjoint. The decomposition algorithm is applicable to any volume, including volumes with degenerate medial axis. The previous paper defined the decomposition based on sub-volumes sweepable perpendicular to an EVG face. This work extends the decomposition to handle all types of EVG entities, providing a complete decomposition of the volume. It analyses the types of sub-volumes that are generated and the meshing techniques applicable to them.