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

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.