Generating a mixed mesh of hexahedra, pentahedra and tetrahedra from an underlying tetrahedral mesh
Sia Meshkat, Dafna Talmor · International Journal for Numerical Methods in Engineering · 2000
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. Copyright © 2000 John Wiley & Sons, Ltd.