1887
  1. Home
  2. Conferences
  3. Conference Proceedings
  4. ECMOR XIV - 14th European Conference on the Mathematics of Oil Recovery
  5. Conference paper

Abstract

Summary

Corner-point gridding of reservoir and basin models is widely used but generally yields approximations in the geological interfaces representation in flow simulation. This paper introduces an indirect method to generate a hexdominant mesh conformal to 3D geological surfaces 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 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, known to be N P-Complete. We propose five 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 complex 3D geological models including a discrete fracture network.

© EAGE Publications BV
Loading

Article metrics loading...

/content/papers/10.3997/2214-4609.20141857
2014-09-08
2024-04-25

  • From This Site

    /content/papers/10.3997/2214-4609.20141857
    dcterms_title,dcterms_subject,pub_keyword
    -contentType:Journal -contentType:Contributor -contentType:Concept -contentType:Institution
    10
    5
Loading full text...

Full text loading...

References

  1. Avenali, A.
    [2007] Resolution branch and bound and an application: the maximum weighted stable set problem. Operations research, 55(5), 932–948.
     [Google Scholar]
  2. Bomze, I., Budinich, M., Pardalos, P.M. and Pelillo, M.
    [1999] The maximum clique problem. Springer.
     [Google Scholar]
  3. Bonneau, F., Henrion, V., Caumon, G., Renard, P. and Sausse, J.
    [2013] A methodology for pseudo-genetic stochastic modeling of discrete fracture networks. Computers & Geosciences, 56, 22–.
     [Google Scholar]
  4. Burer, S., Monteiro, R. and Zhang, Y.
    [2002] Maximum stable set formulations and heuristics based on continuous optimization. Mathematical Programming, 94(1), 137–166.
     [Google Scholar]
  5. Busygin, S., Butenko, S. and Pardalos, P.M.
    [2002] A Heuristic for the Maximum Independent Set Problem Based on Optimization of a Quadratic Over a Sphere. Journal of Combinatorial Optimization, 6(3), 287–297, ISSN 1573–2886, doi:10.1023/A:1014899909753.
     https://doi.org/10.1023/A:1014899909753 [Google Scholar]
  6. Campelo, M. and Correa, R.
    [2009] A Lagrangian relaxation for the maximum stable set problem. arXiv preprint arXiv:0903.1407.
     [Google Scholar]
  7. Caumon, G., Collon-Drouaillet, P., De Veslud, C.L.C., Viseur, S. and Sausse, J.
    [2009] Surface-based 3D modeling of geological structures. Mathematical Geosciences, 41(8), 927–945.
     [Google Scholar]
  8. Cherpeau, N., Caumon, G., Caers, J. and Lévy, B.
    [2012] Method for stochastic inverse modeling of fault geometry and connectivity using flow data. Mathematical Geosciences, 44(2), 147–168.
     [Google Scholar]
  9. Dean, B., Goemans, M. and Vondrák, J.
    [2005] Adaptivity and approximation for stochastic packing problems. Proceeding SODA ’05 Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms.
     [Google Scholar]
  10. Garey, M. and Johnson, D.
    [1979] Computers and intractability: A guide to the theory of NP-completeness. WHFreeman and Company, New York.
     [Google Scholar]
  11. Gibbons, L.E., Hearn, D.W., Pardalos, P.M. and Ramana, M.V.
    [1997] Continuous Characterizations of the Maximum Clique Problem. Mathematics of Operations Research, 22(3), 754–768, ISSN 0364-765X, doi: 10.1287/moor.22.3.754.
     https://doi.org/10.1287/moor.22.3.754 [Google Scholar]
  12. Gruber, G. and Rendl, F.
    [2003] Computational experience with stable set relaxations. SIAM Journal on Optimization, 13(4), 1014–1028.
     [Google Scholar]
  13. Homer, S. and Peinado, M.
    [1996] On the performance of polynomial-time clique approximation algorithms on very large graphs. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 26, 168–.
     [Google Scholar]
  14. Huang, J., Tong, Y., Wei, H. and Bao, H.
    [2011] Boundary aligned smooth 3D cross-frame field. ACM Transactions on Graphics (TOG), ACM, vol. 30, 143.
     [Google Scholar]
  15. Johnson, D.
    [1974] Approximation algorithms for combinatorial problems. Journal of computer and system sciences, 9(3), 256–278.
     [Google Scholar]
  16. Lévy, B. and Liu, Y.
    [2010] Lp Centroidal Voronoi Tesselation and its Applications. ACM Transactions on Graphics, 29(4).
     [Google Scholar]
  17. Manzocchi, T., Heath, A.E., Palananthakumar, B., Childs, C. and Walsh, J.J.
    [2008] Faults in conventional flow simulation models: a consideration of representational assumptions and geological uncertainties. Petroleum Geoscience, 14(1), 91–110.
     [Google Scholar]
  18. Merland, R., Caumon, G., Lévy, B. and Collon-Drouaillet, P.
    [2014] Voronoi grids conforming to 3D structural features. Computational Geosciences, 1–11.
     [Google Scholar]
  19. Meshkat, S. and Talmor, D.
    [2000] Generating a mixed mesh of hexahedra, pentahedra and tetrahedra from an underlying tetrahedral mesh. International Journal for Numerical Methods in Engineering, 49(1–2), 17–30, ISSN 0029-5981.
     [Google Scholar]
  20. Östergård, P.
    [2002] A fast algorithm for the maximum clique problem. Discrete Applied Mathematics, 120(1), 197–207.
     [Google Scholar]
  21. Owen, S.
    [1998] A survey of unstructured mesh generation technology. 7th International Meshing Roundtable, 239–267.
     [Google Scholar]
  22. Owen, S. and Saigal, S.
    [2000] H-Morph: an indirect approach to advancing front hex meshing. International Journal for Numerical Methods in Engineering, 49(1–2), 189–312.
     [Google Scholar]
  23. Paluszny, A., Matthai, S.K. and Hohmeyer, M.
    [2007] Hybrid finite element finite volume discretization of complex geologic structures and a new simulation workflow demonstrated on fractured rocks. Geofluids, 7(2), 186–208.
     [Google Scholar]
  24. Pardalos, P.M. and Rodgers, G.
    [1992] A branch and bound algorithm for the maximum clique problem. Computers & operations research, 19(5), 363–375.
     [Google Scholar]
  25. Rebennack, S., Oswald, M., Theis, D.O., Seitz, H., Reinelt, G. and Pardalos, P.M.
    [2009] A Branch and Cut solver for the maximum stable set problem. Journal of Combinatorial Optimization, 21(4), 434–457, ISSN 1382–6905, doi:10.1007/s10878‑009‑9264‑3.
     https://doi.org/10.1007/s10878-009-9264-3 [Google Scholar]
  26. Rebennack, S., Reinelt, G. and Pardalos, P.M.
    [2012] A tutorial on branch and cut algorithms for the maximum stable set problem. International Transactions in Operational Research, 19(1–2), 161–199, ISSN 09696016, doi:10.1111/j.1475‑3995.2011.00805.x.
     https://doi.org/10.1111/j.1475-3995.2011.00805.x [Google Scholar]
  27. Sakai, S., Togasaki, M. and Yamazaki, K.
    [2003] A note on greedy algorithms for the maximum weighted independent set problem. Discrete Applied Mathematics, 126(2), 313–322.
     [Google Scholar]
  28. Suzuki, S., Caumon, G. and Caers, J.
    [2008] Dynamic data integration for structural modeling: model screening approach using a distance-based model parameterization. Computational Geosciences, 12(1), 105–119.
     [Google Scholar]
  29. Thomson, J., Warsi, Z. and Mastin, C.
    [1985] Numerical Grid Generation: Foundations and Applications. Elsevier, Amsterdam.
     [Google Scholar]
  30. Wang, Y., Zhang, C. and Liu, Z.
    [2012] A matrix approach to graph maximum stable set and coloring problems with application to multi-agent systems. Automatica, 48(7), 1227–1236.
     [Google Scholar]
  31. Warren, J. and Hicks, I.
    [2006] Combinatorial branch-and-bound for the maximum weight independent set problem. Tech. rep.
     [Google Scholar]
  32. Warrier, D., Wilhelm, W., Warren, J. and Hicks, I.
    [2005] A branch-and-price approach for the maximum weight independent set problem. Networks, 46(4), 198–209.
     [Google Scholar]
http://instance.metastore.ingenta.com/content/papers/10.3997/2214-4609.20141857
Loading
Indirect Unstructured Hex-dominant Mesh Generation Using Tetrahedra Recombination
Conference Proceedings 2014, 1 (2014); https://doi.org/10.3997/2214-4609.20141857
/content/papers/10.3997/2214-4609.20141857
/content/papers/10.3997/2214-4609.20141857
Loading

Data & Media loading...

Most Cited This Month Most Cited RSS feed

This is a required field
Please enter a valid email address
Approval was a Success
Invalid data
An Error Occurred
Approval was partially successful, following selected items could not be processed due to error