##
Hexahedral Mesh Generation using the Embedded Voronoi Graph

This work presents a new approach for automatic hexahedral meshing,
based on the embedded Voronoi graph. 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
embedded Voronoi graph is used for decomposing the object, with the guiding
principle that resulting sub-volumes are sweepable. Sub-volumes are meshed
independently, and the resulting meshes are combined and smoothed to yield
the final mesh.

The approach presented here is general and automatic.
It handles any volume, even if its medial axis is degenerate.
The embedded Voronoi graph 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.
The sub-volumes computed by the algorithm are guaranteed to be well-defined
and disjoint. The size of the decomposition is
relatively small since every sub-volume contains a different Voronoi face.
Mesh quality seems high since the decomposition avoids generation of sharp
angles, and sweep and other basic methods are used to mesh the sub-volumes.

Proceedings, * Seventh International Meshing Roundtable,* pp. 347-364, 1998.