Voronoi diagram-based algorithm for 3D borehole modeling

doi:10.11996/JG.j.2095-302X.2025030676

Abstract

Abstract:

Geological models derived from three-dimensional geological modeling methods play an indispensable role across various engineering domains. Existing modeling approaches typically partition underground lithological regions through spatial data interpolation, yet they encountered challenges in maintaining topological consistency, thus constraining the reliability and practicality of three-dimensional models. To construct discontinuous structures within geological regions, a new method based on Voronoi diagrams was proposed to automatically generate three-dimensional stratigraphic surface models. In this method, drilling data were first discretized into scattered points, Voronoi diagrams were constructed, and interfaces between different lithological regions were extracted. Subsequently, the deformation of the interfaces was determined by establishing and solving a linear system for the vertices on these interfaces. In addition, a spatial deformation control algorithm was incorporated to enhance the model’s accuracy in representing complex structural features, such as geological faults and folds, thereby improving the performance of the 3D model in practical applications. This approach resolved the topological inaccuracies often encountered in traditional modeling methods for complex geological structures and exhibited a high degree of automation and robustness. Notably, this method demonstrated exceptional adaptability when handling irregular datasets, significantly reducing the need for manual intervention during model adjustments. Experiments on real engineering data confirmed that the resulting model possessed sound geological validity and can reconstruct non-manifold structures that were difficult to model using other methods.

Key words: three-dimensional geological modeling, borehole, voronoi diagram, mesh deformation algorithm, linear system solution

CLC Number:

TP391
P628

HU Xinyang, WANG Pengfei, ZENG Qiong, JIANG Peng, XIN Shiqing, TU Changhe. Voronoi diagram-based algorithm for 3D borehole modeling[J]. Journal of Graphics, 2025, 46(3): 676-685.

Figures/Tables 10

Fig. 1 Voronoi diagram and its corresponding Delaunay triangulation ((a) Point pi and its corresponding Voronoi cell ci, the 2D Voronoi diagram is composed of the edges of all cells; (b) The Delaunay triangulation with points pi)

Fig. 2 Method work flow ((a) Input is a cylindrical borehole profile with different lithologies; (b) After discretizing the borehole data into point data, a Voronoi diagram is constructed to extract faces where adjacent sites have different colors; (c) Feature points are identified and added to the extracted faces as control points for Laplacian deformation; (d) Layer boundaries are determined by solving a system of linear equations to obtain the deformation result)

Fig. 3 Resampling of drill core data (Left image: original drill core data. Point Pi (X) represents the boundary point at the bottom of stratum X on the i-th drill core. Right image: after resampling. The sampling points on both sides of the boundary are equidistant, with a distance of ?)

Fig. 4 The rules for setting constraint points are as follows: This method specifies two types of vertices as constraint points on the Voronoi diagram. Type one includes the stratum boundary points on the original drill cores (e.g., V1), and type two includes the vertices equidistant from three or more regions (e.g., V2)

Fig. 5 Experiments in 2D ((a) The input mesh consists of 162 vertices, with every pair of vertices being adjacent, and contains four red constraint points. To highlight the correspondence of vertices, some vertices are magnified; (b) The position weight of non-constraint points is 0; (c) The position weight of non-constraint points is 1e-3)

Fig. 6 3D drill core modeling results ((a) Visualization of the input data containing 40 drill cores; (b) Construction of the Voronoi diagram from the discretized drill core point data; (c) Subdivision of the Voronoi diagram; (d) Construction and solution of the system of linear equations to update the vertex positions of the mesh, resulting in the boundary interface)

Fig. 7 3D Modeling results ((a) Input consisting of nine boreholes; (b) Non-manifold edge structures emerging on interfaces due to isolated regions after Voronoi diagram construction; (c) Vertices on non-manifold edges are designated as constraint points prior to deformation; (d) Smoothed pinch-out structure obtained after deformation)

Fig. 8 Experiments were conducted to test the method’s ability to preserve topological structures in 2D ((a)~(d) Representative 2D cross-sections of layered structures, pinch-out structures, lens structures, and fault structures were selected for modeling)

Fig. 9 Comparison of modeling results ((a) Kriging interpolation method; (b) Ours)

Table 1 The modeling time schedule of this algorithm

实验用例	三角面片数量/ K	运行时间/ms
用例1	10	295
	50	1549
	100	3614
用例2	10	113
	50	963
	100	2368

References 38

[1]	LI X, ZHENG D H, FENG M, et al. Information geography: the information revolution reshapes geography[J]. Science China Earth Sciences, 2022, 65(2): 379-382.
[2]	WANG G W, HUANG L. 3D geological modeling for mineral resource assessment of the Tongshan Cu deposit, Heilongjiang province, China[J]. Geoscience Frontiers, 2012, 3(4): 483-491.
[3]	ZHANG X Y, ZHANG J Q, TIAN Y P, et al. Urban geological 3D modeling based on papery borehole log[J]. ISPRS International Journal of Geo-Information, 2020, 9(6): 389.
[4]	WANG J M, ZHAO H, BI L, et al. Implicit 3D modeling of ore body from geological boreholes data using hermite radial basis functions[J]. Minerals, 2018, 8(10): 443.
[5]	LU G Y, WONG D W. An adaptive inverse-distance weighting spatial interpolation technique[J]. Computers & Geosciences, 2008, 34(9): 1044-1055.
[6]	BOISSONNAT J D, CAZALS F. Natural neighbor coordinates of points on a surface[J]. Computational Geometry, 2001, 19(2/3): 155-173.
[7]	HILLIER M J, SCHETSELAAR E M, DE KEMP E A, et al. Three-dimensional modelling of geological surfaces using generalized interpolation with radial basis functions[J]. Mathematical Geosciences, 2014, 46(8): 931-953.
[8]	GUO J T, WANG J M, WU L X, et al. Explicit-implicit- integrated 3-D geological modelling approach: a case study of the Xianyan Demolition Volcano (Fujian, China)[J]. Tectonophysics, 2020, 795: 228648.
[9]	DE KEMP E A. Visualization of complex geological structures using 3-D Bézier construction tools[J]. Computers & Geosciences, 1999, 25(5): 581-597.
[10]	POPOVS K, SAKS T, JĀTNIEKS J. A comprehensive approach to the 3D geological modelling of sedimentary basins: example of Latvia, the central part of the Baltic Basin[J]. Estonian Journal of Earth Sciences, 2015, 64(2): 173-188.
[11]	LYU M M, REN B Y, WU B P, et al. A parametric 3D geological modeling method considering stratigraphic interface topology optimization and coding expert knowledge[J]. Engineering Geology, 2021, 293: 106300.
[12]	OLIVER M A, WEBSTER R. A tutorial guide to geostatistics: computing and modelling variograms and kriging[J]. CATENA, 2014, 113: 56-69.
[13]	RIVOIRARD J. Which models for collocated cokriging ?[J]. Mathematical Geology, 2001, 33(2): 117-131.
[14]	MARINONI O. Improving geological models using a combined ordinary-indicator kriging approach[J]. Engineering Geology, 2003, 69(1/2): 37-45.
[15]	GAUS I, KINNIBURGH D G, TALBOT J C, et al. Geostatistical analysis of arsenic concentration in groundwater in Bangladesh using disjunctive kriging[J]. Environmental Geology, 2003, 44(8): 939-948.
[16]	CALCAGNO P, CHILÈS J P, COURRIOUX G, et al. Geological modelling from field data and geological knowledge: part I. Modelling method coupling 3D potential-field interpolation and geological rules[J]. Physics of the Earth and Planetary Interiors, 2008, 171(1/4): 147-157.
[17]	SMIRNOFF A, BOISVERT E, PARADIS S J. Support vector machine for 3D modelling from sparse geological information of various origins[J]. Computers & Geosciences, 2008, 34(2): 127-143.
[18]	GONÇALVES Í G, KUMAIRA S, GUADAGNIN F. A machine learning approach to the potential-field method for implicit modeling of geological structures[J]. Computers & Geosciences, 2017, 103: 173-182.
[19]	AVALOS S, ORTIZ J M. Geological modeling using a recursive convolutional neural networks approach[EB/OL]. [2024-05-08]https://arxiv.org/abs/1904.12190.
[20]	OKABE A, BOOTS B, SUGIHARA K, et al. Spatial tessellations: concepts and applications of Voronoi diagrams[M]. 2nd ed. New York: Wiley, 2000: 72-75.
[21]	GAVRILOVA M L, ROKNE J. Updating the topology of the dynamic Voronoi diagram for spheres in Euclidean d-dimensional space[J]. Computer Aided Geometric Design, 2003, 20(4): 231-242.
[22]	LORENSEN W E, CLINE H E. Marching cubes: a high resolution 3D surface construction algorithm[M]// WOLFE R. Seminal Graphics: Pioneering Efforts That Shaped the Field. New York: ACM, 1998: 347-353.
[23]	JU T, LOSASSO F, SCHAEFER S, et al. Dual contouring of hermite data[C]// The 29th Annual Conference on Computer Graphics and Interactive Techniques. New York: ACM, 2002: 339-346.
[24]	TURNER A K. Challenges and trends for geological modelling and visualisation[J]. Bulletin of Engineering Geology and the Environment, 2006, 65(2): 109-127.
[25]	LI J, LIU P R, WANG X Y, et al. 3D geological implicit modeling method of regular voxel splitting based on layered interpolation data[J]. Scientific Reports, 2022, 12(1): 13840. DOI PMID
[26]	DAI H L, LIU Z, HU J P. Multi-scale 3D geological digital representation and modeling method based on octree algorithm[C]// The 6th International Conference on Wireless Communications Networking and Mobile Computing. New York: IEEE Press, 2010: 1-3.
[27]	WU L X. Topological relations embodied in a generalized tri-prism (GTP) model for a 3D geoscience modeling system[J]. Computers & Geosciences, 2004, 30(4): 405-418.
[28]	GONG J Y, CHENG P G, WANG Y D. Three-dimensional modeling and application in geological exploration engineering[J]. Computers & Geosciences, 2004, 30(4): 391-404.
[29]	CAUMON G, GRAY G, ANTOINE C, et al. Three-dimensional implicit stratigraphic model building from remote sensing data on tetrahedral meshes: theory and application to a regional model of La Popa Basin, NE Mexico[J]. IEEE Transactions on Geoscience and Remote Sensing, 2013, 51(3): 1613-1621.
[30]	SHI W Z. Development of a hybrid model for three- dimensional GIS[J]. Geo-Spatial Information Science, 2000, 3(2): 6-12.
[31]	TAO J G. A new integrated data structure for 3D GIS based on CSG and TIN[C]// 2009 International Conference on Test and Measurement. New York: IEEE Press, 2009: 153-156.
[32]	姚裕友, 张高峰, 徐本柱, 等. 变容量限制质心Power图的计算[J]. 图学学报, 2021, 42(3): 492-500.
	YAO Y Y, ZHANG G F, XU B Z, et al. Computation method of variable capacity constrained centroidal Power diagram[J]. Journal of Graphics, 2021, 42(3): 492-500 (in Chinese).
[33]	孟宪海, 成文迪, 徐博, 等. 基于Voronoi最小邻近点集的Delaunay三角化方法[J]. 图学学报, 2013, 34(6): 36-41.
	MENG X H, CHENG W D, XU B, et al. A Delaunay triangulation algorithm based on minimum Voronoi neighbors[J]. Journal of Graphics, 2013, 34(6): 36-41 (in Chinese).
[34]	张娟, 杜全叶. 增删点后的Voronoi图生成算法[J]. 图学学报, 2013, 34(1): 46-49.
	ZHANG J, DU Q Y. The generating algorithm of Voronoi after adding and deleting points[J]. Journal of Graphics, 2013, 34(1): 46-49 (in Chinese).
[35]	HERT S, SEEL M. dD convex hulls and Delaunay triangulations[EB/OL]. [2024-05-08]https://doc.cgal.org/5.6.1/Manual/index.html.
[36]	NEALEN A, IGARASHI T, SORKINE O, et al. Laplacian mesh optimization[C]// The 4th International Conference on Computer Graphics and Interactive Techniques in Australasia and Southeast Asia. New York: ACM, 2006: 381-389.
[37]	SORKINE O, COHEN-OR D. Least-squares meshes[C]// The Shape Modeling Applications. New York: IEEE Press, 2004: 191-199.
[38]	GROSS M, BUSSOD G, GABLE C W, et al. Progress report on the development of a geologic framework model capability to support GDSA[R]. Los Alamos: Los Alamos National Laboratory, 2019.