Generating a mixed mesh of hexahedra, pentahedra and tetrahedra from an underlying tetrahedral mesh

International Journal for Numerical Methods in Engineering, John Wiley, Vol 49, Num 1, pp.17-30, 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

Sia Meshkatt and Dafna Talmor
LMS CADSI, 3150 Almaden Expressway, San Jose, CA 95118, US.A.

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 subgraphs of hexahedra and pentahedra in a tetrahedral mesh. The problem of finding an optimal solution is NP-complete. We present heuristics to increase the number of hexahedra and pentahedra, within a reasonable amount of computation time. The algorithm has been implemented in the PolyFEM mesher, and examples showing the typical merge success of the algorithm are included.