一种基于三角网的地质体三维模型切割方法
|
摘要
三维地质体模型相交元素之间构成的奇异空间关系与复杂的模型要素形态极大影响了切割算法稳健性及切割结果可靠性.提出一种几何运算与关系表达相统一的地质体三维模型切割算法.算法首先构建交点对象拓扑结构,存储交点与所在三角形单元及空间邻近要素的相对位置关系;然后结合精确谓词法设计完整的边-三角形相交类型分类图,记录27种相交情况与交点位置的对应关系,并在重三角化过程中建立交点调整机制,利用交点对象拓扑结构中关联的空间关系作为上下文约束,有效控制投影降维浮点误差带来的交点位置偏差的不良影响.实验结果表明,算法能够有效处理地质体模型中的三角网退化/近似退化、自相交及共面/近似共面等奇异空间关系,同时具有良好的运算效率.
The complexity of 3Dgeological 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 3Dcomplex geological model intersection analysis.
The complexity of 3Dgeological 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 3Dcomplex geological model intersection analysis.
引文
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:AHierarchical 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).
Lindenbeck,C.H.,Ebert,H.D.,Ulmer,H.,et al.,2002.TRI-CUT: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).
Ming,J.,Pan,M.,Qu,H.G.,et al.,2008.Zigzag Section Cut Algorithm Based on 3DGeological Objects Represented by Triangulated Irregular Network Data.Geography and Geo-information Science,24(3):37-40(in Chinese with English abstract).
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).
Wang,G.C.,Xu,Y.X.,Chen,X.J.,et al.,2015.ThreeDimensional Geological Mapping and Visualization of Complex Orogenic Belts.Earth Science,40(3):397-406(in Chinese with English abstract).
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).
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).
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).
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).
花卫华,邓伟萍,刘修国,等,2006.一种改进的不规则三角网格曲面切割算法.地球科学,31(5):619-623.
李兆亮,潘懋,杨洋,等,2015.三维复杂断层网建模方法及应用.北京大学学报(自然科学版),51(1):79-85.
明镜,潘懋,屈红刚,等,2008.基于TIN数据三维地质体的折剖面切割算法.地理与地理信息科学,24(3):37-40.
谭正华,王李管,熊书敏,等,2012.一种新的复杂地质体采矿工程剖面图自动生成方法.中南大学学报(自然科学版),43(3):1092-1097.
王国灿,徐义贤,陈旭军,等,2015.基于地表地质调查剖面网络基础上的复杂造山带三维地质调查与建模方法.地球科学,40(3):397-406.
于海燕,何援军,2013.空间两三角形的相交问题.图学学报,34(4):54-62.
郁军建,王国灿,徐义贤,等,2015.复杂造山带地区三维地质填图中深部地质结构的约束方法:西准噶尔克拉玛依后山地区三维地质填图实践.地球科学,40(3):407-418,424.
杨洋,李兆亮,潘懋,2014.基于拓扑追踪的不规则三角网裁剪算法.地理与地理信息科学,30(3):21-24.
宗真,袁林旺,罗文,等,2014.三角网求交的共形几何代数算法.测绘学报,43(2):200-207.
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:AHierarchical 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).
Lindenbeck,C.H.,Ebert,H.D.,Ulmer,H.,et al.,2002.TRI-CUT: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).
Ming,J.,Pan,M.,Qu,H.G.,et al.,2008.Zigzag Section Cut Algorithm Based on 3DGeological Objects Represented by Triangulated Irregular Network Data.Geography and Geo-information Science,24(3):37-40(in Chinese with English abstract).
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).
Wang,G.C.,Xu,Y.X.,Chen,X.J.,et al.,2015.ThreeDimensional Geological Mapping and Visualization of Complex Orogenic Belts.Earth Science,40(3):397-406(in Chinese with English abstract).
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).
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).
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).
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).
花卫华,邓伟萍,刘修国,等,2006.一种改进的不规则三角网格曲面切割算法.地球科学,31(5):619-623.
李兆亮,潘懋,杨洋,等,2015.三维复杂断层网建模方法及应用.北京大学学报(自然科学版),51(1):79-85.
明镜,潘懋,屈红刚,等,2008.基于TIN数据三维地质体的折剖面切割算法.地理与地理信息科学,24(3):37-40.
谭正华,王李管,熊书敏,等,2012.一种新的复杂地质体采矿工程剖面图自动生成方法.中南大学学报(自然科学版),43(3):1092-1097.
王国灿,徐义贤,陈旭军,等,2015.基于地表地质调查剖面网络基础上的复杂造山带三维地质调查与建模方法.地球科学,40(3):397-406.
于海燕,何援军,2013.空间两三角形的相交问题.图学学报,34(4):54-62.
郁军建,王国灿,徐义贤,等,2015.复杂造山带地区三维地质填图中深部地质结构的约束方法:西准噶尔克拉玛依后山地区三维地质填图实践.地球科学,40(3):407-418,424.
杨洋,李兆亮,潘懋,2014.基于拓扑追踪的不规则三角网裁剪算法.地理与地理信息科学,30(3):21-24.
宗真,袁林旺,罗文,等,2014.三角网求交的共形几何代数算法.测绘学报,43(2):200-207.