Generating a Mixed Mesh of Hexahedra, Pentahedra and Tetrahedra from an Underlying Tetrahedral Mesh

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

MESHING
RESEARCH
CORNER

LMS CADSI, 3150 Almaden Expressway, Suite 104, San Jose, CA 95118
[sia | dafna]@cadsi.com

Abstract
The decomposition of an arbitrary polyhedral domain into tetrahedra is currently more tractable than its decomposition into hexahedra. However, for some engineering applications, a mesh composed of hexahedra, or even a mixture of hexahedra, pentahedra and tetrahedra, is preferable. One such application is the p-type finite element method, where the total number of elements should be as small as possible.

We show in this paper, that given a tetrahedral decomposition, some of the tetrahedra can be efficiently combined into hexahedra and pentahedra. The basis of the method is a classification, using a generalized graph representation, of all possible tetrahedral decompositions of pentahedra and hexahedra.

We then present a tetrahedral merge algorithm that utilizes this result to search for the sub-graphs of hexahedra and pentahedra in a tetrahedral mesh. The problem of finding an optimal solution is NP-complete. We present heuristics to maximize the number of hexahedra and pentahedra, given a reasonable amount of computation time.

The algorithm has been implemented in the PolyFEM mesher. We'll presents examples showing the typical merge success of the algorithm.