An accurate intersection method based on irregular triangular networks and its application in 3D geological modeling
-
摘要:
针对目前三维地质模型求交方法中精确度不高、数值计算存在误差等问题,本研究提出一种基于不规则三角网、融合浮点精度与精确精度的地质体精确求交算法,具体流程如下:首先,构建不规则三角网(TIN) 的方向包围盒(OBB)层次树,通过快速碰撞检测筛选出有效相交三角形对集合,大幅缩减后续计算范围;其次,将相交三角形对分解为边 − 三角形求交单元,建立包含交点空间位置状态(onVertex(顶点上);onEdge(边上);inTriangle(面内))及对应实体(点、边、面)
ID 的交点位置关系结构,既消除交点坐标的冗余计算,又通过位置状态与实体ID 匹配精准判别重复交点(如:onVertex 状态下匹配顶点ID ;onEdge 状态下匹配边ID );最后,根据拓扑正确性需求动态选择精度模式:若浮点精度可维持拓扑正确,则采用投影降维的约束 Delaunay 三角化(CDT)方法完成重三角化;若出现交点位置偏移(如面内点投影至边外)、点重合或交线段虚假相交等偏差,则切换至有理数表示的精确精度,通过约束点插入(面内点将三角形拆分为3个新三角、边上点将相邻三角形拆分为4个新三角)与约束线段插入(处理相交线段并执行边交换规则:凸四边形直接换边、凹四边形待排队换边)实现重三角化,确保重构结果的拓扑一致性。实验结果表明,本研究求交算法可以很好地支撑三角网的求交运算,算法转换至精确精度的次数少,具有较好的计算效率及较高的鲁棒性。算法平均时间花销优于GOCAD软件,能够满足大多数不规则三角网复杂地质模型间求交计算的需要。Abstract:Aiming at the problems of low accuracy and numerical calculation errors in the current intersection methods for 3D geological models, this paper proposes a precise intersection algorithm for geological bodies based on the
Irregular Triangular Network (TIN) and integrating floating-point precision with exact precision. The specific process is as follows: First, a hierarchical tree of Oriented Bounding Boxes (OBB) for the TIN is constructed, and a set ofeffectively intersecting triangle pairs is screened out through fast collision detection, which greatly reduces the scope of subsequent calculations. Second, the intersecting triangle pairs are decomposed into edge-triangle intersection units, and an intersection position relationship structure is established. This structure includes the spatial position states of intersections (onVertex : on the vertex,onEdge : on the edge,inTriangle : inside the face) and the IDs of corresponding entities (points, edges, faces). It not only eliminates redundant calculations of intersection coordinates but also accurately identifies duplicate intersections by matching position states with entity IDs (e.g., matching vertex IDs in theonVertex state and edge IDs in theonEdge state). Finally, the precision mode is dynamically selected according to the requirements of topological correctness: if floating-point precision can maintain topological correctness, theConstrained Delaunay Triangulation (CDT) based on projection dimension reduction is used to complete retriangulation; if deviations such as intersection position offsets (e.g., an in-face point projected outside the edge), point coincidence, or false intersection of intersection line segments occur, the algorithm switches to exact precision represented by rational numbers. Retriangulation is realized throughconstrained point insertion (an in-face point splits a triangle into three new triangles, and an on-edge point splits adjacent triangles into four new triangles) andconstrained line segment insertion (processing intersecting line segments and implementing edge swap rules: direct edge swapping for convex quadrilaterals and queued edge swapping for concave quadrilaterals), so as to ensure the topological consistency of the reconstructed results.Experimental results show that the intersection algorithm proposed in this paper can effectively support the intersection operation of triangular networks. The algorithm requires fewer conversions to exact precision, and has good computational efficiency and high robustness. The average time consumption of the algorithm isbetter than that of GOCAD, and it can meet the needs of intersection calculation between most complex geological models based on irregular triangular networks. -
表 1 实验结果对比
Table 1. Comparison of the experimental results
三角形数/个 求交情况 运算时间/ms 模型1 模型2 相交三角形/对 交点/个 转换/次 本研究算法 GOCAD软件 简单立方体求交 12 12 56 42 0 9 13 地质体地层面间 2182 2 71 71 0 587 2047 断层面与断层面 61712 604 249 251 6 1986 5500 -
[1] 陈麒玉, 荀磊, 崔哲思, 等. 三维地质建模技术的最新进展和发展趋势[J]. 地质科技通报, 2025, 44(3): 373-387.CHEN Q Y, XUN L, CUI Z S, et al. Recent progress and development trends of three-dimensional geological modeling[J]. Bulletin of Geological Science and Technology, 2025, 44(3): 373-387. (in Chinese with English abstract [2] 程浪, 王康健, 唐明, 等. 复杂地质建模技术赋能张集井田智能化建设[J]. 智能矿山, 2024(10): 51-59.CHENG L, WANG K J, TANG M, et al. Complex geological modeling technology empowers intelligent construction of Zhangji mine field[J]. Journal of Intelligent Mine, 2024(10): 51-59. (in Chinese with English abstract [3] 李梅, 姜展, 姜龙飞, 等. 三维可视化技术在智慧矿山领域的研究进展[J]. 煤炭科学技术, 2021, 49(2): 153-162.LI M, JIANG Z, JIANG L F, et al. Research progress on 3D visualization technology for intelligent mine[J]. Coal Science and Technology, 2021, 49(2): 153-162. (in Chinese with English abstract [4] CAUMON G, COLLON-DROUAILLET P, LE CARLIER DE VESLUD C, et al. Surface-based 3D modeling of geological structures[J]. Mathematical Geosciences, 2009, 41(8): 927-945. doi: 10.1007/s11004-009-9244-2 [5] LI Z, ZHU Q, GOLD C. Digital terrain modeling: principles and methodology[M]. Boca Raton: CRC Press, 2004. [6] 李宏达, 吴志春, 柏瑞, 等. 复杂脉状矿体精细化三维建模方法探讨[J]. 地质科技通报, 2025, 44(4): 379-390.LI HONGDA, WU ZHICHUN, BAI RUI, et al. Discussion on fine 3D modeling method of complex vein-type ore body[J]. Bulletin of Geological Science and Technology, 2025, 44(4): 379-390. (in Chinese with English abstract [7] MEI G. Summary on several key techniques in 3D geological modeling[J]. The Scientific World Journal, 2014, 2014(1): 723832. [8] LEE P Z, YANG C H, YANG J R. Fast algorithms for computing self-avoiding walks and mesh intersections over unstructured meshes[J]. Advances in Engineering Software, 2004, 35(2): 61-73. doi: 10.1016/j.advengsoft.2003.11.001 [9] 花卫华, 邓伟萍, 刘修国, 等. 一种改进的不规则三角网格曲面切割算法[J]. 地球科学, 2006, 31(5): 619-623.HUA W H, DENG W P, LIU X G, et al. Improved partition algorithm between triangulated irregular network[J]. Earth Science, 2006, 31(5): 619-623. (in Chinese with English abstract [10] 蒋钱平, 唐杰, 袁春风. 基于平均单元格的三角网格曲面快速求交算法[J]. 计算机工程, 2008, 34(21): 172-174.JIANG Q P, TANG J, YUAN C F. Fast triangle mesh surface intersection algorithm based on uniform grid[J]. Computer Engineering, 2008, 34(21): 172-174. (in Chinese with English abstract [11] SCHIFKO M, JÜTTLER B, KORNBERGER B. Industrial application of exact Boolean operations for meshes[C]//Proceedings of the 26th Spring Conference on Computer Graphics. Budmerice Slovakia. ACM, 2010: 165-172. [12] FEITO F R, OGAYAR C J, SEGURA R J, et al. Fast and accurate evaluation of regularized Boolean operations on triangulated solids[J]. Computer-Aided Design, 2013, 45(3): 705-716. doi: 10.1016/j.cad.2012.11.004 [13] BIERMANN H, KRISTJANSSON D, ZORIN D. Approximate Boolean operations on free-form solids[C]//Proceedings of the 28th Annual Conference on Computer Graphics and Interactive Techniques. ACM, 2001: 185-194. [14] SMITH J M, DODGSON N A. A topologically robust algorithm for Boolean operations on polyhedral shapes using approximate arithmetic[J]. Computer-Aided Design, 2007, 39(2): 149-163. doi: 10.1016/j.cad.2006.11.003 [15] 毕林, 王李管, 陈建宏, 等. 三维网格模型的空间布尔运算[J]. 华中科技大学学报(自然科学版), 2008, 36(5): 82-85.BI L, WANG L G, CHEN J H, et al. Spacial Boolean operations of 3D mesh model[J]. Journal of Huazhong University of Science and Technology (Nature Science Edition), 2008, 36(5): 82-85. (in Chinese with English abstract [16] ELSHEIKH A H, ELSHEIKH M. A reliable triangular mesh intersection algorithm and its application in geological modelling[J]. Engineering with Computers, 2014, 30(1): 143-157. doi: 10.1007/s00366-012-0297-3 [17] 明镜, 潘懋, 屈红刚, 等. 基于TIN数据三维地质体的折剖面切割算法[J]. 地理与地理信息科学, 2008, 24(3): 37-40.MING J, PAN M, QU H G, et al. Zigzag section cut algorithm based on 3D geological objects represented by triangulated irregular network data[J]. Geography and Geo-Information Science, 2008, 24(3): 37-40. (in Chinese with English abstract [18] 刘金义, 张燕. 统一于三角面片的可靠多面体布尔集合运算[J]. 工程图学学报, 2002, 23(1): 53-62.LIU J Y, ZHANG Y. Robust polyhedral Boolean set operations achieved by triangle-based representations[J]. Journal of Engineering Graphics, 2002, 23(1): 53-62. (in Chinese with English abstract [19] 兰向荣, 潘懋, 王占刚, 等. 基于TIN的体布尔算法及其地质应用[J]. 地理与地理信息科学, 2008, 24(4): 6-10.LAN X R, PAN M, WANG Z G, et al. Boolean algorithm on 3D models based on TIN and implementation on 3D geological modeling[J]. Geography and Geo-Information Science, 2008, 24(4): 6-10. (in Chinese with English abstract [20] 曹伟, 陆长德. 多面体模型布尔运算算法及其稳定性[J]. 西安工业学院学报, 1997, 17(1): 18-23.CAO W, LU C D. Boollean set operation algorithm and robustness on B rep object[J]. Journal of Xi’an Technological University, 1997, 17(1): 18-23. (in Chinese) [21] 唐敏, 董金祥, 李海龙, 何志均. 非正则精确模型的布尔操作[J]. 软件学报, 1999, 10(12): 1291-1297.TANG M, DONG J X, LI H L, HE Z J. Boolean operation of non-regular precise geometric models[J]. Journal of Software, 1999, 10(12): 1291-1297. (in Chinese with English abstract [22] 尹长林, 喻定权. 一种基于拓扑搜索的三角网求交算法[J]. 计算机工程与应用, 2006, 42(36): 209-211.YIN C L, YU D Q. Rapid topological searching-based intersection algorithm of triangulated networks[J]. Computer Engineering and Applications, 2006, 42(36): 209-211. (in Chinese with English abstract [23] 丁祖鹏, 张雨晴, 王俊杰, 等. 基于自注意力机制生成对抗网络的三维储层建模方法[J]. 地质科技通报, 2025, 44(4): 391-402.DING ZUPENG, ZHANG YUQING, WANG JUNJIE, et al. A self-attention enhanced generative adversarial network approach for three-dimensional reservoir modeling[J]. Bulletin of Geological Science and Technology, 2025, 44(4): 391-402. (in Chinese with English abstract [24] GUIGUE P, DEVILLERS O. Fast and robust triangle-triangle overlap test using orientation predicates[J]. Journal of graphics tools, 2003, 8(1): 25-32. [25] 李宁, 田震, 张立华, 等. 优化的三角网格曲面求交算法[J]. 辽宁工程技术大学学报(自然科学版), 2013, 32(9): 1269-1273.LI N, TIAN Z, ZHANG L H, et al. Optimization algorithm for triangular mesh surface intersection[J]. Journal of Liaoning Technical University (Natural Science), 2013, 32(9): 1269-1273. (in Chinese with English abstract [26] 陈志杨, 倪栋梁. 采用图形加速的三角网格实时切分[J]. 计算机应用与软件, 2016, 33(3): 163-166.CHEN Z Y, NI D L. Triangular mesh real-time cutting using graphics acceleration[J]. Computer Applications and Software, 2016, 33(3): 163-166. (in Chinese with English abstract [27] GOTTSCHALK S, LIN M C, MANOCHA D. OBBTree: A hierarchical structure for rapid interference detection[C]//. Proceedings of the 23rd Annual Conference on Computer Graphics and Interactive Techniques. 1996: 171-180. [28] CHANG J W, WANG W P, KIM M S. Efficient collision detection using a dual OBB-sphere bounding volume hierarchy[J]. Computer-Aided Design, 2010, 42(1): 50-57. doi: 10.1016/j.cad.2009.04.010 [29] WANG H J, ZHANG X L, ZHOU L Q, et al. Intersection detection algorithm based on hybrid bounding box for geological modeling with faults[J]. IEEE Access, 2020, 8: 29538-29546. doi: 10.1109/ACCESS.2020.2972317 [30] DE FLORIANI L, MAGILLO P, PUPPO E. Data structures for simplicial multi-complexes[M]//Advances in spatial databases. Berlin, Heidelberg: Springer Berlin Heidelberg, 1999: 33-51. [31] DE BERG M, VAN KREVELD M, OVERMARS M, et al. Computational geometry: Algorithms and applications[M]. Berlin, Heidelberg: Springer Berlin Heidelberg, 2008. [32] VAN OOSTEROM P, STOTER J. 5D data modelling: full integration of 2D/3D space, time and scale dimensions[C]//International Conference on Geographic Information Science. Berlin: Springer, 2010: 310-324.VAN OOSTEROM P, STOTER J. 5D data modelling: full integration of 2D/3D space, time and scale dimensions[C]//International Conference on Geographic Information Science. Berlin: Springer, 2010: 310-324. [33] MAGALHÃES S V G, FRANKLIN W R, ANDRADE M V A. Fast exact parallel 3D mesh intersection algorithm using only orientation predicates[C]//Proceedings of the 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. Redondo Beach CA USA. ACM, 2017: 1-10. [34] RICHARD SHEWCHUK J. Adaptive precision floating-point arithmetic and fast robust geometric predicates[J]. Discrete & Computational Geometry, 1997, 18(3): 305-363. [35] GEORGE P L, BOROUCHAKI H. Delaunay triangulation and meshing: Application to finite elements[M]. Hermés science, 1998. [36] BARBER C B, DOBKIN D P, HUHDANPAA H. The quickhull algorithm for convex hulls[J]. ACM Transactions on Mathematical Software, 1996, 22(4): 469-483. doi: 10.1145/235815.235821 [37] PAUL CHEW L. Constrained delaunay triangulations[J]. Algorithmica, 1989, 4(1): 97-108. [38] SHEWCHUK J R. Triangle: Engineering a 2D quality mesh generator and Delaunay triangulator[M]//Applied computational geometry towards geometric engineering. Berlin, Heidelberg: Springer Berlin Heidelberg, 1996: 203-222. [39] RUPPERT J. A delaunay refinement algorithm for quality 2-dimensional mesh generation[J]. Journal of Algorithms, 1995, 18(3): 548-585. doi: 10.1006/jagm.1995.1021 [40] LIU H, WANG J, ZHANG W, et al. MILP-StuDio: MILP instance generation via block structure decomposition[J]. Advances in Neural Information Processing Systems, 2024, 37: 54357-54395. -
下载:
