An exact intersection method for triangulated irregular network and its application to 3D geological modeling
-
摘要:
针对目前三维地质模型求交方法中精确度不高、数值计算存在误差等问题，提出一种基于不规则三角网、融合浮点精度与精确精度的地质体精确求交算法。首先，构建不规则三角网（TIN） 的方向包围盒（OBB）层次树，通过快速碰撞检测筛选出有效相交三角形对集合，大幅缩减后续计算范围。其次，将相交三角形对分解为边 − 三角形求交单元，建立包含交点空间位置状态（onVertex（顶点上）；onEdge（边上）；inTriangle（面内））及对应实体（点、边、面）
ID 的交点位置关系结构，既消除交点坐标的冗余计算，又通过位置状态与实体ID 匹配精准判别重复交点（如：onVertex 状态下匹配顶点ID ；onEdge 状态下匹配边ID ）。最后，根据拓扑正确性需求动态选择精度模式：若浮点精度可维持拓扑正确，则采用投影降维的约束 Delaunay 三角化（CDT）方法完成重三角化；若出现交点位置偏移（如面内点投影至边外）、点重合或交线段虚假相交等偏差，则切换至有理数表示的精确精度，通过约束点插入（面内点将三角形拆分为3个新三角、边上点将相邻三角形拆分为4个新三角）与约束线段插入（处理相交线段并执行边交换规则：凸四边形直接换边、凹四边形待排队换边）实现重三角化，确保重构结果的拓扑一致性。结果表明，提出的求交算法可以很好地支撑三角网的求交运算，算法转换至精确精度的次数少，具有较好的计算效率及较高的鲁棒性。算法平均时间花销优于GOCAD软件，能够满足大多数不规则三角网复杂地质模型间求交计算的需要。Abstract:To address the problems of low accuracy and numerical errors in the current intersection methods for 3D geological models, this paper proposes a precise intersection algorithm for geological bodies based on the triangulated irregular network (TIN) and integrating floating-point arithmeticwith exact arithmetic. The specific process is as follows: First, a oriented bounding box (OBB) hierarchy for the TIN is constructed, and a set of effectively intersecting triangle pairs is identified through fast collision detection, thereby greatly reducing the scope of subsequent calculations. Second, the intersecting triangle pairs are decomposed into edge-triangle intersection tests, and an intersection positional-relationship data structure is established. This structure includes the spatial position states of intersections (atVertex: at a vertex, onEdge: on an edge, inTriangle: inside the face) and the IDs of corresponding entities (points, edges, faces). It not only eliminates redundant computations of intersection coordinates but also accurately identifies duplicate intersections by matching positional states with entity IDs (e.g., matching vertex IDs in the atVertex state and edge IDs in the onEdge state). Finally, the precision mode is selected dynamically according to the requirements of topological correctness: if floating-point precision can maintain topological correctness, projection-based constrained delaunay triangulation (CDT) is used to perform retriangulation; if deviations such as intersection position offsets (e.g., an inTriangle point projected outside the edge), point coincidence, or spurious intersections between intersection segments occur, the algorithm switches to exact precision represented by rational numbers. Retriangulation is carried out through constrained point insertion (an inTriangle point splits a triangle into three new triangles, and an onEdge point splits adjacent triangles into four new triangles) and constrained 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), thereby ensuring the topological consistency of the reconstructed results. Experimental results show that the proposed algorithm effectively supports intersection operation on triangular networks, requires infrequent conversions to exact precision, and exhibits good computational efficiency and high robustness. The average runtime is lower than that of GOCAD, and the method meets the intersection requirements of most complex geological models based on triangulated irregular networks.
-
图 1 三角形对相交
onVertex. 交点位于三角形的顶点上；onEdge. 交点位于三角形的边上；inTriangle. 交点位于三角形内部；T1，T2. 三角形；P1，P2. 交点；下同
Figure 1. Intersection of two triangles
图 2 基于浮点数三角形重构（ABC为三角形；P1～P4均为约束点；下同）
Figure 2. Retriangulating based on floating point number
图 7 地质体地层面间求交
Figure 7. Intersection between stratigraphic planes of a geological body
表 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 
下载: 导出CSV
-
[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, US: CRC Press, 2004. [6] 李宏达, 吴志春, 柏瑞, 等. 复杂脉状矿体精细化三维建模方法探讨[J]. 地质科技通报, 2025, 44(4): 379-390.LI H D, WU Z C, BAI R, 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. [S. l.]: 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, et al. 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 Z P, ZHANG Y Q, WANG J J, 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. [S. l.]: [S. n.], 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]. [S. l.]: 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. -
下载:
点击查看大图
计量
- 文章访问数: 74
- PDF下载量: 100
- 被引次数: 0
