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

The decomposition of an arbitrary polyhedral domain into tetrahedra is curr ently more tractable than its decomposition into hexahedra. However, for so me engineering applications, a mesh composed of hexahedra, or even a mixtur e of hexahedra, pentahedra and tetrahedra, is preferable. One such applicat ion 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 tetrah edral decomposition, some of the tetrahedra can be efficiently combined int o hexahedra and pentahedra. The basis of the method is a classification, us ing a generalized graph representation, of all possible tetrahedral decompo sitions of pentahedra and hexahedra. We then present a tetrahedral merge al gorithm that utilizes this result to search for the subgraphs of hexahedra and pentahedra in a tetrahedral mesh. The problem of finding an optimal sol ution is NP-complete. We present heuristics to increase the number of hexah edra and pentahedra, within a reasonable amount of computation time. The al gorithm has been implemented in the PolyFEM mesher, and examples showing th e typical merge success of the algorithm are included. Copyright (C) 2000 J ohn Wiley & Sons, Ltd.