Hexahedral Meshing of Non-Linear Volumes using Voronoi Faces and Edges

2nd Symposium on Trends in Unstructured Mesh Generation, University of Colorado, Boulder, August 1999

MESHING
RESEARCH
CORNER

Institute of Computer Science, The Hebrew University, Jerusalem 91904, Israel.
sheffa@cs.huji.ac.il

Abstract
In our recent work a new approach for automatic hexahedral meshing was presented [2]. The presented algorithm decomposes the object into simple parts based on the Embedded Voronoi Graph (EVG) [1]. The EVG contains the complete symbolic information of the Voronoi diagram (or the medial axis) of the object, and a tolerance based geometric approximation to the real geometry. The EVG 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 easily combined and smoothed to yield the final mesh.

This approach possesses several advantages:

1. the algorithm for computing the EVG is provenly correct, stable and easy to implement;
2. the approach is well defined and valid on shapes of any geometry, including shapes whose medial axis is degenerate;
3. the decomposition is order independent and prevents intersections between decomposition surfaces;
4. the number of sub-volumes generated is not large since every sub-volume contains a different Voronoi face;
5. since the directions and entities involved in each decomposition are defined by the medial axis, there are no intersection computations;
6. since a decomposition is used, as opposed to template, there is only a minimal need for medial axis geometry; and
7. 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.

The algorithm as presented in [2] is not complete. First, while it is shown that most of the sub-volumes resulting from the decomposition are sweepable or hexahedral, some sub-volumes that result from decomposing along one or more Voronoi edges might be not meshable by the available basic algorithms. Second, though a general explanation is given on handling non-polyhedral volumes, it was not fully defined or implemented.

In this work the algorithm is developed further, to address the issues unresolved in the previous publication. The decomposition algorithm is expanded to further decompose the problematic sub-volumes mentioned above. The purpose of the decomposition is to create sub-volumes sweepable along previously unaddressed medial edges. The EVG computation and analysis are expanded to non-linear objects, enabling the meshing of non-polyhedral volumes. The algorithm is demonstrated on several real life examples.

References

[1] M. Etzion, A. Rappoport, 'Computing Voronoi Skeletons of a 3-D Polyhedron by Space Subdivision', Technical Report TR-8-97, Institute of Computer Science, The Hebrew University of Jerusalem, 1997.

[2] A. Sheffer, M. Ezion, A. Rappoport, M. Bercovier 'Hexahedral Mesh Generation using the Embedded Voronoi Graph', Proc. 7th International Meshing Roundtable, Dearborn, USA, October 26-28, 1998. Accepted to 'Engineering with Computers'.