Indirect unstructured hex-dominant mesh generation using tetrahedra recombination

Corner-point gridding is widely used in reservoir and basin modeling but generally yields approximations in the representation of geological interfaces. This paper introduces an indirect method to generate a hex-dominant mesh conformal to 3D geological surfaces and well paths suitable for finite-element and control-volume finite-element simulations. By indirect, we mean that the method first generates an unstructured tetrahedral mesh whose tetrahedra are then merged into primitives (hexahedra, prisms, and pyramids). More specifically, we focus on determining the optimal set of primitives that can be recombined from a given tetrahedral mesh. First, we detect in the tetrahedral mesh all the feasible volumetric primitives using a pattern-matching algorithm (Meshkat and Talmor Int. J. Numer. Meth. Eng. 49(1-2), 17–30 2000) that we re-visit and extend with configurations that account for degenerated tetrahedra (slivers). Then, we observe that selecting the optimal set of primitives among the feasible ones can be formalized as a maximum weighted independent set problem (Bomze et al. 1999), known to be (mathcal {N}mathcal {P})-Complete. We propose several heuristic optimizations to find a reasonable set of primitives in a practical time. All the tetrahedra of each selected primitive are then merged to build the final unstructured hex-dominant mesh. This method is demonstrated on 3D geological models including a faulted and folded model and a discrete fracture network.