3D Geological Model Intersection Algorithm Based on Triangular Mesh
-
摘要: 三维地质体模型相交元素之间构成的奇异空间关系与复杂的模型要素形态极大影响了切割算法稳健性及切割结果可靠性.提出一种几何运算与关系表达相统一的地质体三维模型切割算法.算法首先构建交点对象拓扑结构，存储交点与所在三角形单元及空间邻近要素的相对位置关系；然后结合精确谓词法设计完整的边-三角形相交类型分类图，记录27种相交情况与交点位置的对应关系，并在重三角化过程中建立交点调整机制，利用交点对象拓扑结构中关联的空间关系作为上下文约束，有效控制投影降维浮点误差带来的交点位置偏差的不良影响.实验结果表明，算法能够有效处理地质体模型中的三角网退化/近似退化、自相交及共面/近似共面等奇异空间关系，同时具有良好的运算效率.Abstract: The complexity of 3D geological model and the singular spatial relationship among geological intersection objects greatly influenced the robustness and the reliability of intersection algorithm. An efficient and reliable intersection algorithm of complex geological model is proposed in this paper. Firstly, an intersection point topological structure is built to store the relative position between intersection point and adjacent elements. Then combining the exact predicates method, a complete edge/triangle intersection classification figure is designed which records 27 kinds of intersection cases and corresponding intersection point positions; in the process of re-triangulation, the designed adjustment mechanisms make full use of associated spatial relationship as the constraints, adding an additional level of reliability to the algorithm. The experimental results show that our algorithm efficiently handled the degenerate/self-intersection cases in triangular mesh and the tangency/co-planar/near co-planar triangles special cases in intersection process, and could provide a reference for 3D complex geological model intersection analysis.
-
Key words:
- geological model /
- 3D GIS /
- 3D space analysis /
- remote sensing /
- cutting analysis /
- reliability
-
图 1 交点位置关系(a)和三角形对相交示意(b)
Fig. 1. Intersection point position (a) and intersection of two triangles (b)
图 5 PQ三角形ABC异面判断方法示意
Fig. 5. Judgement method for non-coplanar cases of PQ and plane ABC
图 6 PQ与三角形ABC共面位置判断方法示意
Fig. 6. Judgement method for coplanar cases of line PQ and plane ABC
图 10 复杂交线构建示意
a.连接非多叉交线段；b.多叉交线段；c.离散化交线段；d.连接复杂交线
Fig. 10. Constructing complex intersection lines
图 11 重三角化基本思想
a.特殊情况；b.二维空间特殊情况；c.调整；d.二维重三角化；e.映射回三维空间
Fig. 11. The principle of re-triangulation
图 14 共面/近似共面网格切割示意
立方体旋转0.01度; a.输入模型；b.输入模型相交关系；c.切割结果1；d.切割结果2
Fig. 14. Intersection test of coplanar/near coplanar
图 15 自相交情况切割示意
a.自相交输入模型；b.输入模型；c.重三角化结果；d.切割结果
Fig. 15. Intersection test of self-intersection models
图 16 完全退化三角形(a)和近似退化三角形(b)
Fig. 16. Complete degenerate triangles (a) and near degenerate triangles (b)
图 17 网格中退化三角形切割示意
a.完全退化三角形；b.近似退化三角形
Fig. 17. Intersection test of degenerate triangle
图 18 近似退化三角形切割示意
a.原始相交输入模型；b, c, d.切割放大结果
Fig. 18. Intersection result of near-degenerate triangles
图 19 柴达木盆地英西区断层面间求交切割结果示意
a.断层模型；b.模型求交结果；c.断层模型；d.模型求交结果
Fig. 19. Triangular mesh intersection of geological model of Yingxi area in Qaidam basin
图 20 柴达木盆地英西区地质模型
a.地质体模型地层面(T21代表晚第三系-上新统中期地层(N22)；T2代表晚第三系-上新统早期地层(N21)；T3代表晚第三系-中新统地层(N1)；T4代表早第三系-渐新统晚期地层(E32)；K16代表白垩系地层(K16)；K18代表白垩系地层(K18))；b.地质体模型相交情况；c.模型中断层面(0，0-1，S，3，4，5-1，和2均为断层面名称)
Fig. 20. Geological model of Yingxi area in the Qaidam basin
表 1 边-三角形基本拓扑关系分类
Table 1. Edge-triangle detailed topological relationship
基本关系 边-三角形基本拓扑关系 Touch TouchVertex(TV)/TouchEdge(TE)/ TouchFace(TF) Share ShareVertex(SV)/ ShareEdge(SE)/ ShareFace(SF) Across AcrossVertex(AV)/ AcrossEdge(AE)/ AcrossFace(AF) Disjoint Disjoint(DJ) 
下载: 导出CSV
表 2 网格特殊情况处理对比分析
Table 2. Special cases comparison with prior arts
特殊情况 算法 本文算法 OCCT GOCAD TRICUT 共面 是 是 是 否 近似共面 是 是 是 否 自相交 是 否 否 否 退化 是 是 是 否
下载: 导出CSV
表 3 地质模型数据
Table 3. Detailed information of geological model
数据编号 数据名称 三角形数(个) 相交情况(个) 运算时间(ms) 被切割面 切割面 被切割面 切割面 三角形对 交点 本文 GOCAD OCCT 1 0 S 158 30 40 41 12 32 10 187 2 2 4 604 21 75 76 29 540 26 348 3 T4 2 22 830 604 189 190 585 2 900 48 141 4 K18 4 62 061 23 488 496 2 097 4 600 66 300 5 T2 0 86 887 158 506 508 2 786 3 500 69 420 6 T2 0-1 86 887 32 993 1 019 4 308 9 400 165 641
下载: 导出CSV
-
Attene, M., 2014.Direct Repair of Self-Intersecting Meshes.Graphical Models, 76(6):658-668.doi: 10.1016/j.gmod.2014.09.002 Barki, H., Guennebaud, G., Foufou, S., 2015.Exact, Robust, and Efficient Regularized Booleans on General 3D Meshes.Computers & Mathematics with Applications, 70(6):1235-1254.doi: 10.1016/j.camwa.2015.06.016 Coelho, L.C.G., Gattass, M., Figueiredo, L.H.D., 2000.Intersecting and Trimming Parametric Meshes on Finite Element Shells.International Journal for Numerical Methods in Engineering, 47(4):777-800.doi:10.1002/(sici)1097-0207(20000210)47:4<777::aid-nme797>3.0.CO;2-6 Caumon, G., Collon-Drouaillet, P., de Veslud, C.L., et al., 2009.Surface-Based 3D Modeling of Geological Structures.Mathematical Geosciences, 41(8):927-945.doi: 10.1007/s11004-009-9244-2 Elsheikh, A.H., Elsheikh, M., 2014.A Reliable Triangular Mesh Intersection Algorithm and Its Application in Geological Modelling.Engineering with Computers, 30(1):143-157.doi: 10.1007/s00366-012-0297-3 Feito, F.R., Ogayar, C.J., Segura, R.J., et al., 2013.Fast and Accurate Evaluation of Regularized Boolean Operations on Triangulated Solids.Computer-Aided Design, 45(3):705-716.doi: 10.1016/j.cad.2012.11.004 Gottschalk, S., Lin, M.C., Manocha, D., 1996.OBBTree:A Hierarchical Structure for Rapid Interference Detection.Proceedings of ACM Siggraph, New York, 171-180.doi:10.1145/237170.237244 Guo, K.B., Zhang, L.C., Wang, C.J., et al., 2007.Boolean Operations of STL Models Based on Loop Detection.The International Journal of Advanced Manufacturing Technology, 33(5-6):627-633.doi: 10.1007/s00170-006-0487-5 Hoffmann, C.M., 1989.The Problems of Accuracy and Robustness in Geometric Computation.Computer, 22(3):31-39.doi: 10.1109/2.16223 Hua, W.H., Deng, W.P., Liu, X.G., et al., 2006.Improved Partition Algorithm between Triangulated Irregular Network.Earth Science, 31(5):619-623(in Chinese with English abstract). http://en.cnki.com.cn/Article_en/CJFDTOTAL-DQKX200605008.htm Lindenbeck, C.H., Ebert, H.D., Ulmer, H., et al., 2002.TRICUT:A Program to Clip Triangle Meshes Using the Rapid and Triangle Libraries and the Visualization Toolkit.Computers & Geosciences, 28(7):841-850.doi: 10.1016/s0098-3004(01)00110-8 Lo, S.H., Wang, W.X., 2004.A Fast Robust Algorithm for the Intersection of Triangulated Surfaces.Engineering with Computers, 20(1):11-21.doi: 10.1007/s00366-004-0277-3 Li, Z.L., Pan, M., Yang, Y., et al., 2015.Research and Application of the Three-Dimensional Complex Fault Network Modeling.Acta Scientiarum Naturalium Universitatis Pekinensis, 51(1):79-85 (in Chinese with English abstract). http://en.cnki.com.cn/Article_en/CJFDTotal-BJDZ201501009.htm Ming, J., Pan, M., Qu, H.G., et al., 2008.Zigzag Section Cut Algorithm Based on 3D Geological Objects Represented by Triangulated Irregular Network Data.Geography and Geo-information Science, 24(3):37-40 (in Chinese with English abstract). http://en.cnki.com.cn/Article_en/CJFDTOTAL-DLGT200803009.htm Mei, G., Corporation, H.P., 2014.Summary on Several Key Techniques in 3D Geological Modeling.The Scientific World Journal, 2014:1-11.doi: 10.1155/2014/723832 Ragan, D.M., 2009.Structural Geology:An Introduction to Geometrical Techniques.Cambridge University Press, Cambridge, 1-10. Shewchuk, J.R., 1996a.Robust Adaptive Floating-Point Geometric Predicates.Proceedings of the Twelfth Annual Symposium on Computational Geometry, New York, 141-150.doi:10.1145/237218.237337 Shewchuk, J.R., 1996b.Triangle:Engineering a 2D Quality Mesh Generator and Delaunay Triangulator.Lecture Notes in Computer Science, Springer-Verlag, London, 203-222.doi:10.1007/bfb0014497 Schifko, M., Jüttler, B., Kornberger, B., 2010.Industrial Application of Exact Boolean Operations for Meshes.Proceedings of the 26th Spring Conference on Computer Graphics, Slovakia, 165-172.doi:10.1145/1925059.1925089 Tan, Z.H., Wang, L.G., Xiong, S.M., et al., 2012.A New Method for Automatic Generation of Complex Geological Mining Engineer Profile Chart.Journal of Central South University, 43(3):1092-1097(in Chinese with English abstract). http://en.cnki.com.cn/Article_en/CJFDTOTAL-ZNGD201203047.htm Wang, G.C., Xu, Y.X., Chen, X.J., et al., 2015.Three-Dimensional Geological Mapping and Visualization of Complex Orogenic Belts.Earth Science, 40(3):397-406(in Chinese with English abstract). http://www.en.cnki.com.cn/Article_en/CJFDTOTAL-DQKX201503001.htm Xu, N.X., Tian, H., 2009.Wire Frame:A Reliable Approach to Build Sealed Engineering Geological Models.Computers & Geosciences, 35(8):1582-1591.doi: 10.1016/j.cageo.2009.01.002 Yu, H.Y., He, Y.J., 2013.Testing the Intersection Status of Two Triangles.Journal of Graphics, 34(4):54-62 (in Chinese with English abstract). http://www.txxb.com.cn/CN/abstract/abstract323.shtml Yu, J.J., Wang, G.C., Xu, Y.X., et al., 2015.Constraining Deep Geological Structures in Three-Dimensional Geological Mapping of Complicated Orogenic Belts:A Case Study from Karamay Region, Western Junggar.Earth Science, 40(3):407-418, 424(in Chinese with English abstract). http://www.en.cnki.com.cn/Article_en/CJFDTOTAL-DQKX201503002.htm Yang, Y., Li, Z.L., Pan, M., 2014.Clipping Algorithm for Triangulated Irregular Network Based on Topology.Geography and Geo-Information Science, 30(3):21-24(in Chinese with English abstract). http://en.cnki.com.cn/Article_en/CJFDTOTAL-DLGT201403005.htm Zong, Z., Yuan, L.W., Luo, W., et al., 2014.Triangulation Intersection Algorithm Based on Conformal Geometric Algebra.Acta Geodaetica et Cartographica Sinica, 43(2):200-207 (in Chinese with English abstract). http://en.cnki.com.cn/Article_en/CJFDTOTAL-CHXB201402016.htm 花卫华, 邓伟萍, 刘修国, 等, 2006.一种改进的不规则三角网格曲面切割算法.地球科学, 31(5):619-623. http://kns.cnki.net/KCMS/detail/detail.aspx?filename=dqkx200605008&dbname=CJFD&dbcode=CJFQ 李兆亮, 潘懋, 杨洋, 等, 2015.三维复杂断层网建模方法及应用.北京大学学报(自然科学版), 51(1):79-85. http://www.cnki.com.cn/Article/CJFDTOTAL-BJDZ201501009.htm 明镜, 潘懋, 屈红刚, 等, 2008.基于TIN数据三维地质体的折剖面切割算法.地理与地理信息科学, 24(3):37-40. http://www.cnki.com.cn/Article/CJFDTOTAL-DLGT200803009.htm 谭正华, 王李管, 熊书敏, 等, 2012.一种新的复杂地质体采矿工程剖面图自动生成方法.中南大学学报(自然科学版), 43(3):1092-1097. http://www.cnki.com.cn/Article/CJFDTOTAL-ZNGD201203047.htm 王国灿, 徐义贤, 陈旭军, 等, 2015.基于地表地质调查剖面网络基础上的复杂造山带三维地质调查与建模方法.地球科学, 40(3):397-406. http://earth-science.net/WebPage/Article.aspx?id=3033 于海燕, 何援军, 2013.空间两三角形的相交问题.图学学报, 34(4):54-62. http://www.cnki.com.cn/Article/CJFDTOTAL-GCTX201304008.htm 郁军建, 王国灿, 徐义贤, 等, 2015.复杂造山带地区三维地质填图中深部地质结构的约束方法:西准噶尔克拉玛依后山地区三维地质填图实践.地球科学, 40(3):407-418, 424. http://earth-science.net/WebPage/Article.aspx?id=3181 杨洋, 李兆亮, 潘懋, 2014.基于拓扑追踪的不规则三角网裁剪算法.地理与地理信息科学, 30(3):21-24. http://www.cnki.com.cn/Article/CJFDTOTAL-DLGT201403005.htm 宗真, 袁林旺, 罗文, 等, 2014.三角网求交的共形几何代数算法.测绘学报, 43(2):200-207. http://www.cnki.com.cn/Article/CJFDTOTAL-CHXB201402016.htm -
点击查看大图
计量
- 文章访问数: 5012
- HTML全文浏览量: 2174
- PDF下载量: 28
- 被引次数: 0
