Abstract
We present a novel mixed-dimensional method for generating unstructured polyhedral grids that conform to prescribed geometric objects in arbitrary dimensions. Two types of conformity are introduced: (i) control-point alignment of cell centroids to accurately represent horizontal and multilateral wells or create volumetric representations of fracture networks, and ii) boundary alignment of cell faces to accurately preserve lower dimensional geological objects such as layers, fractures, faults, and/or pinchouts. The prescribed objects are in this case assumed to be lower dimensional, and we create a grid hierarchy in which each lower dimensional object is associated with a lower dimensional grid. Further, the intersection of two objects is associated with a grid one dimension lower than the objects. Each grid is generated as a clipped Voronoi diagram, also called a perpendicular bisector (PEBI) grid, for a carefully chosen set of generating points. Moreover, each grid is generated in such a way that the cell faces of a higher dimensional grid conform to the cells of all lower dimensional grids. We also introduce a sufficient and necessary condition which makes it easy to check if the sites for a given perpendicular bisector grid will conform to the set of prescribed geometric objects.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Berge, R. L.: Unstructured Pebi grids adapting to geological feautres in subsurface reservoirs. Master’s thesis, Norwegian University of Science and Technology (2016)
Branets, L., Ghai, S.S., Lyons, S.L., Wu, X.-H.: Efficient and accurate reservoir modeling using adaptive gridding with global scale up. In: Proceedings of the SPE Reservoir Simulation Symposium, The Woodlands, Texas (2009a). https://doi.org/10.2118/118946-MS
Branets, L.V., Ghai, S.S., Lyons, S.L., Wu, X.-H.: Challenges and technologies in reservoir modeling. Communications in Computational Physics 6(1), 1–23 (2009b)
Brewer, M., Camilleri, D., Ward, S., Wong, T.: Generation of hybrid grids for simulation of complex, unstructured reservoirs by a simulator with MPFA. SPE Reservoir Simulation Symposium, 23-25 February, Houston, Texas, USA (2015). https://doi.org/10.2118/173191-MS
Courrioux, G., Nullans, S., Guillen, A., Boissonnat, J. D., Repusseau, P., Renaud, X., Thibaut, M.: 3d volumetric modelling of cadomian terranes northern brittany, france): an automatic method using Voronoi diagrams. Tectonophysics 331, 181–196 (2001). https://doi.org/10.1016/S0040-1951(00)00242-0
Ding, X.Y., Fung, L.S.K.: An unstructured gridding method for simulating faulted reservoirs populated with complex wells. In: Proceedings of the SPE Reservoir Simulation Symposium, Houston, Texas, USA (2015). https://doi.org/10.2118/173243-MS
Du, Q., Faber, V., Gunzburger, M.: Centroidal Voronoi tessellations: Applications and algorithms. SIAM Rev. 41(4), 637–676 (1999). https://doi.org/10.1137/S0036144599352836
Filippov, D. D., Kudryashov, I. Y., Maksimov, D. Y., Mitrushkin, D. A., Vasekin, B. V., Roshchektaev, A. P.: Reservoir Modeling of Complex Structure Reservoirs on Dynamic Adaptive 3D Pebi-grid. In: SPE Russian Petroleum Technology Conference, 16-18 October, Moscow, Russia (2017). https://doi.org/10.2118/187799-MS
Fung, L. -K., Hiebert, A., method, L. Nghiem.: Reservoir simulation with a control-volume finite-element. SPE Reservoir Engineering 7(3), 349–356 (1992). https://doi.org/10.2118/21224-PA
Fung, L.S.K., Ding, X.Y., Dogru, A.H.: Unconstrained Voronoi grids for densely spaced complex wells in full-field reservoir simulation. SPE J. 19(5), 803–815 (2014). https://doi.org/10.2118/163648-PA
Geiger-Boschung, S., Matthäi, S.K., Niessner, J., Helmig, R.: Black-oil simulations for three-component, three-phase flow in fractured porous media. SPE J. 14(02), 338–354 (2009). https://doi.org/10.2118/107485-PA
Gringarten, E.J., Arpat, G.B., Haouesse, M.A., Dutranois, A., Deny, L., Jayr, S., Tertois, A.-L., Mallet, J.-L., Bernal, A., Nghiem, L.X.: New grids for robust reservoir modeling. In: In SPE Annual Technical Conference and Exhibition, 21-24 September, Denver, Colorado, USA. Society of Petroleum Engineers. https://doi.org/10.2118/116649-MS (2008)
Gringarten, E.J., Haouesse, M.A., Arpat, G.B., Nghiem, L.X.: Advantages of Using Vertical Stair Step Faults in Reservoir Grids for Flow Simulation. In: SPE Reservoir Simulation Symposium, 2-4 February, The Woodlands, Texas. Society of Petroleum Engineers. https://doi.org/10.2118/119188-MS (2009)
Guerillot, D., Swaby, P.: An interactive 3D mesh builder for fluid flow reservoir simulation. SPE Comput. Appl. 5(6), 5–10 (1993). https://doi.org/10.2118/26227-PA
Heinemann, Z.E., Brand, C.W., Munka, M., Chen, Y.M.: Modeling reservoir geometry with irregular grids. SPE Reserv. Eng. 6(2), 225–232 (1991). https://doi.org/10.2118/18412-PA
Holm, R., Kaufmann, R., Heimsund, B.-O., Øian, E., Espedal, M.S.: Meshing of domains with complex internal geometries. Numer. Linear Algebra Appl. 13(9), 717–731 (2006). ISSN 1099-1506. https://doi.org/10.1002/nla.505
Iri, M., Murota, K., Ohya, T.: System Modelling and Optimization: Proceedings of the 11th IFIP Conference Copenhagen, Denmark, July 25–29, 1983, chapter A fast Voronoi-diagram algorithm with applications to geographical optimization problems, pp. 273–288. Springer Berlin Heidelberg, Berlin, Heidelberg, 1984. ISBN 978-3-540-38828-9. https://doi.org/10.1007/BFb0008901
Karimi-Fard, M., Durlofsky, L.J., Aziz, K.: An efficient discrete-fracture model applicable for general-purpose reservoir simulators. SPE J. 9(2), 227–236 (2004). https://doi.org/10.2118/88812-PA
Keilegavlen, E., Fumagalli, A., Berge, R., Stefansson, I., Berre, I.: PorePy: an open-source simulation tool for flow and transport in deformable fractured rocks. ArXiv e-prints (2017)
Klemetsdal, Ø.S., Berge, R.L., Lie, K.-A., Nilsen, H.M., Møyner, O.: Unstructured gridding and consistent discretizations for reservoirs with faults and complex wells. In: Proceedings of the SPE Reservoir Simulation Symposium (2017). https://doi.org/10.2118/182666-MS
Lie, K.-A.: An introduction to reservoir simulation using MATLAB: User guide for the Matlab Reservoir Simulation Toolbox (MRST). SINTEF ICT (2016)
Liu, Y., Wang, W., Lévy, B., Sun, F., Yan, D.-M., Lu, L., Yang, C.: On centroidal Voronoi tessellation-energy smoothness and fast computation. ACM Trans. Graph. 28(4), 101:1–101:17 (2009). ISSN 0730-0301. https://doi.org/10.1145/1559755.1559758
Mallison, B., Sword, C., Viard, T., Milliken, W., Cheng, A.: Unstructured Cut-Cell grids for modeling complex reservoirs. SPE J. 19(02), 340–352 (2014). https://doi.org/10.2118/163642-PA
Manzoor, S., Edwards, M.G., Dogru, A.H., Al-Shaalan, T.M.: Interior boundary-aligned unstructured grid generation and cell-centered versus vertex-centered CVD-MPFA performance. Computational Geosciences, Oct 2017. ISSN 1573-1499. https://doi.org/10.1007/s10596-017-9686-4
Meng, X., Duan, Z., Yang, Q., Liang, X.: Local PEBI grid generation method for reverse faults. Computers & Geosciences 110, 73–80 (2018). https://doi.org/10.1016/j.cageo.2017.09.012
Merland, R., Lévy, B., Caumon, G.: Building PEBI grids conforming to 3D geological features using centroidal Voronoi tessellation. In: Marschallinger, R., Zolb, R. (eds.) Proceedings of IAMG, pp. 12, Salzburg (2011)
Merland, R., Caumon, G., Lévy, B., Collon-Drouaillet, P.: Voronoi grids conforming to 3D structural features. Computational Geosciences 18(3-4), 373–383 (2014). ISSN 1420-0597. https://doi.org/10.1007/s10596-014-9408-0
Mustapha, H.: G23fm: A tool for meshing complex geological media. Computational Geosciences 15(3), 385–397 (2011). ISSN 1573-1499. https://doi.org/10.1007/s10596-010-9210-6
Nocedal, J., Wright, S.J.: Numerical optimization, 2nd edn. Springer, New York (2006). https://doi.org/10.1007/978-0-387-40065-5
Palagi, C., Aziz, K.: Use of Voronoi grid in reservoir simulation. Soc. Petrol. Eng. 2(2), 69–77 (1994). https://doi.org/10.2118/22889-PA
Peaceman, D.W.: Interpretation of well-block pressures in numerical reservoir simulation. Soc. Petrol. Eng. J. 18(3), 183–194 (1978). https://doi.org/10.2118/6893-PA
Persson, P. -O., Strang, G.: A simple mesh generator in MATLAB. SIAM Rev. 46(2), 329–345 (2004). https://doi.org/10.1137/S0036144503429121
Ponting, D.K.: Corner point geometry in reservoir simulation. In: King, P. (ed.) Proceedings of the 1st European Conference on Mathematics of Oil Recovery, Cambridge, 1989, pp 45–65. Clarendon Press, Oxford (1989). https://doi.org/10.3997/2214-4609.201411305
Shah, S., Møyner, O., Tene, M., Lie, K.-A., Hajibeygi, H.: The multiscale restriction smoothed basis method for fractured porous media (F-MsRSB). J. Comput. Phys. 318, 36–57 (2016)
Shewchuk, J.R., Cheng, S.-W., Dey, T.K.: Delaunay mesh generation. Computer and information science. Chapman and hall/CRC (2012). https://doi.org/10.1201/b12987-3
Sun, J., Schechter, D.: Optimization-Based Unstructured meshing algorithms for simulation of hydraulically and naturally fractured reservoirs with variable distribution of fracture aperture, spacing, length, and strike. SPE Reservoir Evaluation & Engineering 18(04), 463–480 (2015). https://doi.org/10.2118/170703-PA
Sun, J., Schechter, D., Huang, C.-K.: Grid-sensitivity analysis and comparison between unstructured perpendicular bisector and structured tartan/local-grid-refinement grids for hydraulically fractured horizontal wells in eagle ford formation with complicated natural fractures. SPE J. 21(06), 2–260 (2016). https://doi.org/10.2118/177480-PA
Toor, S.M., Edwards, M.G., Dogru, A.H., Shaalan, T.M.: Boundary aligned grid generation in three dimensions and CVD-MPFA discretization. In: Proceedings of the SPE Reservoir Simulation Symposium, Houston, Texas, USA. https://doi.org/10.2118/173313-MS (2015)
Verma, S., Aziz, K.: A control volume scheme for flexible grids in reservoir simulation. In: SPE Reservoir Simulation Symposium, 8-11 June, Dallas, Texas. Society of Petroleum Engineers (1997). https://doi.org/10.2118/37999-MS
Wu, X.-H., Parashkevov, R.: Effect of grid deviation on flow solutions. SPE J. 14(01), 67–77 (2009). https://doi.org/10.2118/92868-PA
Yan, D.-M., Wang, W., Lévy, B., Liu, Y.: Advances in Geometric Modeling and Processing: 6th International Conference, GMP 2010, Castro Urdiales, Spain, June 16-18, 2010. Proceedings, chapter Efficient Computation of 3D Clipped Voronoi Diagram, pp. 269–282. Springer Berlin Heidelberg, 2010. ISBN 978-3-642-13411-1. https://doi.org/10.1007/978-3-642-13411-1_18
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher’s Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Appendices
Appendix A: Optimal Delaunay triangulation
To create a fully unstructured grid, we can place the reservoir sites using the force-based method proposed by [32]. For completeness, we will briefly review this method. The key idea is to associate edges in the Delaunay triangulation with springs, whereas vertices are associated with joints connecting the springs. The forces on each joint will depend on the difference between the actual length of the springs and their uncompressed length.
The uncompressed length l0 of a spring is based on an element size function h. We evaluate the spring at its midpoint. For the domain [0, 1] × [0, 1] and element size function h(x,y) = 1 + x, the uncompressed length of the springs will be about twice as big in the right side of the domain as the left side.
We let the forces from the springs follow Hooke’s law; that is, the force is proportional to the difference of its actual length l and its uncompressed length l0. However, we assume that the springs only have repulsive forces, and no attractive forces. The force f from a spring is:
Here, k is a constant of value one that is needed to obtain the correct units.
Let P be the coordinates of all joints. To find the force on a joint pi, we find the force from all springs connected to pi. The total force F(pi) is the sum of these forces. Figure 25a shows seven springs connected to one joint. The repulsive force from a spring acts in the longitudinal direction of the spring. We do not want the joints to move outside the domain we wish to triangulate. Figure 25b shows how an external force is added to the boundary joints. The external force is perpendicular to the boundary and balances the repulsive forces of the springs. Boundary joints can therefore only move along the boundary. We also allow for fixed joints that can be thought of as glued to their initial position and are not allowed to move, no matter how large the forces acting on them are.
The optimization loop of the force-based algorithm is very simple. We calculate the Delaunay triangulation of the joints Pk. For each edge in the triangulation, we calculate the repulsive force f(l,l0). For joints on the boundary we also add an external force to prevent it from passing over the boundary. The total force on a joint is found by summing all repulsive forces and external forces. The total force on a fixed joint is set to zero. All joints are moved a step length ξ along the direction of the total force acting on them:
An example of an optimum triangulation and its dual PEBI-grid is shown in Fig. 26 for a case where initial reservoir sites were placed semi-randomly in the domain.
To achieve refinement towards wells, we create an element size function that decreases towards wells. We let the element size function decrease exponentially:
The desired grid size of the background grid far from and close to the wells is hmax and hmin respectively. The distance d(p,W) is the closest distance from the point p to the set of well sites W. The constant ε controls the transition region. If ε is small, the refinement happens quickly around the wells. If ε is large, the transition region is large. When we run the force algorithm, all well and fracture sites are set as fixed points.
Appendix B: Duality of Delaunay triangulation and PEBI-grids
There is a close relationship between the Delaunay triangulation and PEBI-grids. They are often called dual of each other in the sense that the topology of one is defined by the topology of the other. The duality is defined by a bijection between the faces of the Delaunay triangulation and the faces of the PEBI-grid. Following the presentation in [1], we first define the k-face of a tessellation as a face of dimension k. In 2D a 2-face is a cell, a 1-face the edge between two cells and a 0-face a vertex. We then state the Voronoi-Delaunay duality precisely in the following theorem [35].
Theorem 1
(Duality of Delaunay triangulation and PEBIgrids) Let P be a generic point set in \(\mathbb R^{d}\). Let \(\mathcal V\) and \(\mathcal T\) be the associated PEBI-grid and Delaunay triangulation, respectively. Let S = {s1,…sj}⊆ P be a subset of the sites in P. The convex hull of S is a k-face of \(\mathcal T\) if and only if \(v_{s_{1},{\ldots } s_{j}}\) is a (d − k)-face of \(\mathcal V\).
Proof
First, assume that the convex hull of S is a k-face of \(\mathcal T\). Then there exists a closed ball B that intersects s1,…,sj, but does not contain any sites from P ∖ S. The center of this ball is equidistant to all sites in S, hence, the intersection \(v_{s_{1}{\ldots } s_{j}}\) is not empty; i.e., it is a PEBI face of P. Let π be the affine space that is orthogonal to the affine space of S and contains the center of B. The space π has dimension (d − k) because the dimension of A(S) is k. All points in π are equidistant to all sites in S, and no points in \(\mathbb R^{d}\setminus {\Pi }\) are equidistant to all sites in S, thus, \(v_{s_{1}{\ldots } s_{j}}\subseteq {\Pi }\). Let 0 < ε = minp∈P∖Sd(B,p) be the minimum distance from the ball B to any sites in P ∖ S. Any points in π that are closer to the center of B than \(\frac {1}{2}\varepsilon \) are on the face \(v_{s_{1}{\ldots } s_{j}}\), hence, the dimension of \(v_{s_{1}{\ldots } s_{j}}\) is the same as π, that is (d − k).
Now assume that \(v_{s_{1}{\ldots } s_{j}}\) is a PEBI (d − k)-face. Since P is generic, there is no sj+ 1 ∈ P ∖ S such that \(v_{s_{1}{\ldots } s_{j}}=v_{s_{1}{\ldots } s_{j} s_{j + 1}}\). In fact, the number of cells must equal j = k + 1 if \(v_{s_{1}{\ldots } s_{j}}\) is to have dimension (d − k). We can therefore find a closed ball centered at some point in \(v_{s_{1}{\ldots } s_{j}}\) that has s1,…,sj on its boundary and does not contain any sites P ∖ S. The convex hull of the k + 1 sites in S is a k-simplex and it is strongly Delaunay, hence, it is a k-face in the Delaunay triangulation. □
The main results of the duality theorem is for j = 2 and j = d + 1. For j = 2 the theorem says that PEBI-cell \(v_{s_{1}}\) and \(v_{s_{2}}\) share a PEBI facet if and only if there is a Delaunay edge between site s1 and s2. For j = d + 1 the theorem says that all PEBI vertices are the center of a circumball of a Delaunay (d + 1)-simplex. Figure 1 shows the duality in 2D.
Rights and permissions
About this article
Cite this article
Berge, R.L., Klemetsdal, Ø.S. & Lie, KA. Unstructured Voronoi grids conforming to lower dimensional objects. Comput Geosci 23, 169–188 (2019). https://doi.org/10.1007/s10596-018-9790-0
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10596-018-9790-0