Skip to main content
SpringerLink
Log in

Indirect unstructured hex-dominant mesh generation using tetrahedra recombination

  • ORIGINAL PAPER
  • Published:
Computational Geosciences Aims and scope Submit manuscript

Abstract

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Aavatsmark, I., Barkve, T., Bøe, O., Mannseth, T.: Discretization on unstructured grids for inhomogeneous, anisotropic media. Part I Derivation of the methods. SIAM J. Sci. Comput. (1998)

  2. Avenali, A.: Resolution branch and bound and an application: the maximum weighted stable set problem. Oper. Res. 55(5), 932–948 (2007)

    Article  Google Scholar 

  3. Baudouin, T.C., Remacle, J.F., Marchandise, E., Henrotte, F., Geuzaine, C.: A frontal approach to hex-dominant mesh generation. Adv. Model. Simul. Eng. Sci. 1(1), 1–30 (2014)

    Article  Google Scholar 

  4. Bernard, P.E., Remacle, J.F., Kowalski, N., Geuzaine, C.: Hex-dominant meshing approach based on frame field smoothness. In: 23rd IMR, pp 175–186 (2014)

  5. Bomze, I., Budinich, M., Pardalos, P.M., Pelillo, M.: The Maximum Clique Problem. Springer (1999)

  6. Bonneau, F., Henrion, V., Caumon, G., Renard, P., Sausse, J.: A methodology for pseudo-genetic stochastic modeling of discrete fracture networks. Comput. Geosci. 56, 12–22 (2013)

    Article  Google Scholar 

  7. Burer, S., Monteiro, R., Zhang, Y.: Maximum stable set formulations and heuristics based on continuous optimization. Math. Program. 94(1), 137–166 (2002)

    Article  Google Scholar 

  8. Busygin, S., Butenko, S., Pardalos, P.M.: A heuristic for the maximum independent set problem based on optimization of a quadratic over a sphere. J. Comb. Optim. 6(3), 287–297 (2002). doi:10.1023/A:1014899909753

    Article  Google Scholar 

  9. Campelo, M., Correa, R.: A Lagrangian relaxation for the maximum stable set problem (2009). arXiv:09031407

  10. Caumon, G., Collon-Drouaillet, P., Le Carlier de Veslud, C., Viseur, S., Sausse, J: Surface-based 3D modeling of geological structures. Math. Geosci. 41(8), 927–945 (2009)

    Article  Google Scholar 

  11. Chen, Y., Mallison, B.T., Durlofsky, L.J.: Nonlinear two-point flux approximation for modeling full-tensor effects in subsurface flow simulations. Comptat. Geosci. 12(3), 317–335 (2008)

    Article  Google Scholar 

  12. Cherpeau, N., Caumon, G., Caers, J., Lévy, B.: Method for stochastic inverse modeling of fault geometry and connectivity using flow data. Math. Geosci. 44(2), 147–168 (2012)

    Article  Google Scholar 

  13. Dean, B., Goemans, M., Vondrák, J.: Adaptivity and approximation for stochastic packing problems. In: Proceedings of the 16th annual ACM-SIAM symposium on Discrete algorithms (2005)

  14. Eymard, R., Guichard, C., Herbin, R., Masson, R.: Vertex-centred discretization of multiphase compositional Darcy flows on general meshes. Comput. Geosci. 16(4), 987–1005 (2012)

    Article  Google Scholar 

  15. Flandrin, N., Borouchaki, H, Bennis, C.: 3D hybrid mesh generation for reservoir simulation. Int. J. Numer Meth. Eng (2006)

  16. Garey, M., Johnson, D.: Computers and intractability: a guide to the theory of NP-completeness. WH Freeman and Company, New York (1979)

    Google Scholar 

  17. Gibbons, L.E., Hearn, D.W., Pardalos, P.M., Ramana, M.V.: Continuous characterizations of the maximum clique problem. Math. Oper. Res. 22(3), 754–768 (1997). doi:10.1287/moor.22.3.754

    Article  Google Scholar 

  18. Gruber, G., Rendl, F.: Computational experience with stable set relaxations. SIAM J. Optimiz. 13(4), 1014–1028 (2003)

    Article  Google Scholar 

  19. Homer, S., Peinado, M.: On the performance of polynomial-time clique approximation algorithms on very large graphs. DIMACS Ser. Discret. M. 26, 147–168 (1996)

    Google Scholar 

  20. Huang, J., Tong, Y., Wei, H., Bao, H.: Boundary aligned smooth 3D cross-frame field. In: ACM T. Graphic. (TOG), ACM, vol. 30, p 143 (2011)

  21. Johnson, D.: Approximation algorithms for combinatorial problems. J. Comput. Syst. Sci. 9(3), 256–278 (1974)

    Article  Google Scholar 

  22. Lévy, B., Liu, Y.: Lp Centroidal Voronoi Tesselation and its Applications. ACM T. Graphic 29(4) (2010)

  23. Mallison, B., Sword, C., Viard, T., Milliken, W., Cheng, A., et al.: Unstructured cut-cell grids for modeling complex reservoirs. SPE J. 19(02), 340–352 (2014)

    Article  Google Scholar 

  24. Manzocchi, T., Heath, A.E., Palananthakumar, B., Childs, C., Walsh, J.J.: Faults in conventional flow simulation models: a consideration of representational assumptions and geological uncertainties. Petrol. Geosci. 14(1), 91–110 (2008)

    Article  Google Scholar 

  25. Merland, R., Caumon, G., Lévy, B., Collon-Drouaillet, P.: Voronoi grids conforming to 3D structural features. Comput. Geosci., 1–11 (2014)

  26. Meshkat, S., Talmor, D.: Generating a mixed mesh of hexahedra, pentahedra and tetrahedra from an underlying tetrahedral mesh. Int. J. Numer. Meth. Eng. 49(1-2), 17–30 (2000)

    Article  Google Scholar 

  27. Meyers, R., Tautges, T., Tuchinsky, P.: The “Hex-Tet” hex-dominant meshing algorithm as implemented in CUBIT. In: 7th IMR, pp 151–158 (1998)

  28. Mustapha, H.: G23FM: a tool for meshing complex geological media. Comptat. Geosci. 15(3), 385–397 (2011)

    Article  Google Scholar 

  29. Mustapha, H., Dimitrakopoulos, R., Graf, T., Firoozabadi, A.: An efficient method for discretizing 3D fractured media for subsurface flow and transport simulations. Int. J. Numer. Meth. Fl. 67(5), 651–670 (2011)

    Article  Google Scholar 

  30. Owen, S., Canann, J., Scott, A., Saigal, S.: Pyramid elements for maintaining tetrahedra to hexahedra conformability. Appl. Mech. Div. ASME 220, 123–130 (1997)

    Google Scholar 

  31. Owen, S.: A survey of unstructured mesh generation technology. In: 7th IMR, pp 239–267 (1998)

  32. Owen, S., Saigal, S.: H-Morph: an indirect approach to advancing front hex meshing. Int. J. Numer. Meth. Eng. 49(1-2), 189–312 (2000)

    Article  Google Scholar 

  33. Paluszny, A., Matthai, S.K., Hohmeyer, M.: Hybrid finite element finite volume discretization of complex geologic structures and a new simulation workflow demonstrated on fractured rocks. Geofluids 7(2), 186–208 (2007)

    Article  Google Scholar 

  34. Pardalos, P.M., Rodgers, G.: A branch and bound algorithm for the maximum clique problem. Comput. Oper. Res. 19(5), 363–375 (1992)

    Article  Google Scholar 

  35. Pellerin, J., Lévy, B., Caumon, G., Botella, A.: Automatic surface remeshing of 3D structural models at specified resolution: a method based on Voronoi diagrams. Comput. Geol. 62, 103–116 (2014)

    Article  Google Scholar 

  36. Pellerin, J., Caumon, G., Julio, C., Mejia-Herrera, P., Botella, A: Elements for measuring the complexity of 3D structural models: connectivity and geometry. Comp. Geosci. 76, 130–140 (2015)

    Article  Google Scholar 

  37. Östergård, P.: A fast algorithm for the maximum clique problem. Discrete Appl. Math. 120(1), 197–207 (2002)

    Article  Google Scholar 

  38. Rebennack, S., Oswald, M., Theis, D.O., Seitz, H., Reinelt, G., Pardalos, P.M.: A Branch and Cut solver for the maximum stable set problem. J. Comb. Optim. 21(4), 434–457 (2009). doi:10.1007/s10878-009-9264-3

    Article  Google Scholar 

  39. Rebennack, S., Reinelt, G., Pardalos, P.M.: A tutorial on branch and cut algorithms for the maximum stable set problem. Int. T. Oper. Res. 19(1-2), 161–199 (2012). doi:10.1111/j.1475-3995.2011.00805.x

    Article  Google Scholar 

  40. Sakai, S., Togasaki, M., Yamazaki, K.: A note on greedy algorithms for the maximum weighted independent set problem. Discrete Appl. Math. 126(2), 313–322 (2003)

    Article  Google Scholar 

  41. Shepherd, J., Johnson, C.: Hexahedral mesh generation constraints. Eng. Comput. 24(3), 195–213 (2008)

    Article  Google Scholar 

  42. Si, H.: A quality tetrahedral mesh generator and a 3d delaunay triangulator (2010) http://tetgenberliosde

  43. Suzuki, S., Caumon, G., Caers, J.: Dynamic data integration for structural modeling: model screening approach using a distance-based model parameterization. Comput. Geosci. 12(1), 105–119 (2008)

    Article  Google Scholar 

  44. Wang, Y., Zhang, C., Liu, Z.: A matrix approach to graph maximum stable set and coloring problems with application to multi-agent systems. Automatica 48(7), 1227–1236 (2012)

    Article  Google Scholar 

  45. Warren, J., Hicks, I.: Combinatorial branch-and-bound for the maximum weight independent set problem. Tech. rep. (2006)

  46. Warrier, D., Wilhelm, W., Warren, J., Hicks, I.: A branch-and-price approach for the maximum weight independent set problem. Networks 46(4), 198–209 (2005)

    Article  Google Scholar 

  47. Yamakawa, S., Shimada, K.: Fully-automated hex-dominant mesh generation with directionality control via packing rectangular solid cells. Int. J. Numer. Meth. Eng. 57(15), 2099–2129 (2003)

    Article  Google Scholar 

  48. Zafiris, V.: Quality metrics for geologic grid structures. In: Proceedings of the 2007 ACM SPM, pp 361–366. ACM (2007)

Download references

Author information

Authors and Affiliations

  1. GeoRessources (UMR 7359, Gocad Research Group - ASGA / Universitè de Lorraine-ENSG / CNRS / CREGU), 54518, Vandoeuvre-lès-Nancy, France

    Arnaud Botella

  2. INRIA Lorraine - LORIA, Project ALICE, 615 rue du Jardin Botanique, 54600, Villers-lès-Nancy, France

    Bruno Lévy

  3. GeoRessources (UMR 7359, Universitè de Lorraine-ENSG / CNRS / CREGU), 54518, Vandoeuvre-lès-Nancy, France

    Guillaume Caumon

Authors
  1. Arnaud Botella
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Bruno Lévy
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Guillaume Caumon
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Arnaud Botella.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Botella, A., Lévy, B. & Caumon, G. Indirect unstructured hex-dominant mesh generation using tetrahedra recombination. Comput Geosci 20, 437–451 (2016). https://doi.org/10.1007/s10596-015-9484-9

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10596-015-9484-9

Keywords

Search

Navigation