基于曲面方程的三角形网格求交算法(1).doc

基于曲面方程的三角形网格模型求交方法陈振1 汤军1,2 廖环宇1 明廷宝1 梁宏1 陈俊飞1 刘圆圆1 （1. 长江大学地球科学学院，湖北武汉 430100）（2. 长江大学油气资源勘探教育部重点实验室，湖北武汉 430100）摘 要 在应用GIS不规则三角网的地层建模、表达和分析的研究过程中，会涉及到大量复杂的三角网格模型的求交运算。本文提出了一种基于曲面方程的三角形网格模型求交算法。该算法首先通过三维点要素，插值拟合出两个曲线方程，然后求解方程组获得交线方程，再将该交线分别投影到三角形网格上，获得顺序的投影三角形组，最后对两个三角形组做求交运算。该算法能快速有效排除不相交三角形，同时对候选三角形和三角形交线依次记录，大大减少了运算时间。关键字 三角网 表面模型 曲线方程 交线 投影中国法分类号：TP ； 文献标志码：A1 引言随着地质信息计算机模拟技术和可视化技术的发展，三维地层建模及可视化技术是空间地理信息化建设的关键技术之一，并成为数学地质、石油勘探、岩土工程，GIS与计算机技术等多个领域的研究前沿和热点1。在涉及三维地质体模拟与分析的领域中, 表面模型是重要的三维数据模型之一。表面模型是用3D 空间实体的几何表面模拟、表达实体, 侧重于3D 空间实体的外部形态表示, 如地质层面、断层剖面、地形表面等。一般来说, 几何表面模型的表示主要是Rainald Lohner（1996）提出的曲面方程和多边形曲面两种方法2。参数曲面主要由特定的数学方程来确定, 便于编辑和控制, 多用于设计领域；多边形曲面则由分布在实体表面的离散点集生成的多边形面元的集合构成, 离散点一般来源于实际采集的三维空间点信息, 面元大多采用三角形面元, 表面用不规则三角网（TIN）表示。长江大学2014年大学生创新创业训练计划资助（编号：104892014006）第一作者：陈振，1991年生，男，长江大学本科在读，专业为地理信息系统，E-mail:.通讯作者：汤军，教授，硕士生导师，研究方向：油气资源定量评价，地理信息系统。多边形曲面广泛应用于工程领域的三维可视化和分析计算。本文主要讨论两个曲面相交的问题，对此，传统的方法是将曲面模型所包含的所有三角形进行两两相交测试，如毕林、王李管等在2008年提出的网格模型布尔运算算法，但随着三维技术的不断发展，三维网格模型的复杂度不断增加，所包含的三角形数量也不断飙升3。这使得人们考虑先剔除已知不相交的三角形以减少求交的计算量的方法，并成为提高不规则三角网求交算法效率的有效途径之一。为此有潘振宽、崔树娟等提出的层次包围盒法4，刘丽萍、王琰提出的包围盒编码法5，张少丽、王毅刚等提出的空间分解法6等。层次包围盒法需要将模型对象建立最小包围盒，某些情况下求交效率不太理想。包围盒编码法则是通过空间编码将三角形相交情况逻辑化，但在剔除不相交三角形上效果不理想。空间分解法虽然在整体上剔除不相交三角形效果较好，但在剔除同一空间网格的三角形时任需要借助其他的方法，有时仍需要用到包围盒法简化结果，使得算法复杂度增加，运算效率不太高。针对以上方法的不足，如果能找到一种方法，不但能在三角形求交之前删减三角形数量，而且在获得两个三角形交线时能顺序存放，那将能更快连接成交线，得到所需的结果。基于此思想，本文将提出一种新的曲面求交算法：基于曲面方程的三角形网格求交算法。首先通过组成三角形网格的三维点要素，分别插值拟合出两个待求交的三角形网格的曲线方程，求解方程组获得交线方程，将该交线分别投影到两个三角形网格上，获得顺序的投影三角形组，最后对两个三角形组做求交运算。交线作为两个曲面相交部分，在表面模型的构建以及后续的空间分析中都起着至关重要的作用。因此，可靠快速的不规则三角网求交法，是三角网表面模型建模分析的基本算法之一。表面模型构建过程中，交线是不同表面相交的边界部分，该部分一定会构成一个有序的线段链或者线段环。于是对于两个不规则三角网求交的算法则主要包括三部分：（1）确定相交不规则三角形对；（2）求取对应三角形对的交线线段；（3）把各交线线段连接成链或者环7。2 算法原理2.1 求解曲面交线模型首先获取生成三角形网格模型的具有三维坐标的点要素（Xk,Yk,Zk）k=1,2,3，N，再应用插值算法8将点要素拟合成面要素，并得出曲面方程z=fa(x,y)和z=fb(x,y)，联立方程，求解得到交线方程式y=g(x)和z=h(x)。2.2 获取交线投影的三角形组2.2.1 求取交线与三角形网格模型的一个交点，作为开始获取交线的起点将求交的两个三角形网格模型记分别为V1、V2，获取中的V1，求得其三角形总数k，并通过顶点坐标求得每个三角形面的参数方程 z=fm(x,y)（x1xx2,y1yy2,m=1,2,k），算法流程图如图1所示：图1 获取起点和初始三角形流程图Figure 1 Flow chart of obtaining the starting point and initial triangle2.2.2 从P1P2P3开始求得交线投影的三角形组Nn从交点p(x,y,z)开始，做交线在该P1P2P3面上的投影，投影线必经过P1P2P3的一条边上一点A1,如P1P2（经过端点P1可看做经过以该点作为左端点的边P1P2上），并将该P1P2P3记为三角形组中的序号为1，找到另一个以P1P2为边的P1P2P49，并以A1为起点，重复上述过程，直到交线投影到某三角形内部，该三角形序号为n（nk),获得三角形组Nn；2.2.3 通过三角形网格模型V2获取三角形组Mm重复2.1和2.2步骤，获取交线投影在三角形网格模型V2上三角形组成的的三角形组Mm；2.3对三角形组Nn和Mm依次做求交运算对Nn和Mm做循环运算：令i=0，j=0开始判断：Ni和Mj是否有交线True则记下交线两端点坐标(x,y,z)依次放入点集point中；j=j+1,循环判断Falsej=j-1i+1循环判断最终按照point顺序连点成线，获得三角形网格模型交线。3 实例介绍本文算法已运用在笔者开发的地层油气藏三维可视化系统中，地层与断层相交是地质建模过程中必定会碰到的问题，此实例首先分别显示地层V1的三角形网格模型和断层V2的三角形网格模型（如图2），计算显示两个三角形网格交线投影，并最终显示三角形网格交线（如图3）。图2 地层V1、断层V2的三角形网格模型Figure 2 Triangular mesh model of stratum-V1and fault-V2图3 交线投影与相交显示Figure3Theprojectionofintersectionandintersectiondisplay4 结语本文提出的新算法，主要从计算速度方面改进了三维空间模型的布尔运算算法，通过曲面函数求解的方法，将计算范围大大缩小，并通过建立数组的方式来规范连接对象的运算顺序，将海量的三角形求交运算大幅度地缩减，从而有效快速地求取两个三角形网格的交线。本算法主要有3个方面的优势：（1）通过曲面方程计算剔除不相交三角形，不用考虑三角形的空间拓扑关系；（2）将投影三角形依次存储、计算，避免了不必要的循环操作，提高了运算效率；（3）将三角形相交时获取的交点顺序存储、连接，即可得两个三角形网络模型的交线。实验结果表明：该算法思路清晰，易于实现，计算速度快和稳定性强，基本能满足三维地质建模过程中三角形网络求交运算。参考文献1 朱良峰,潘信,吴信才.三维地质建模及可视化系统的设计与开发J.岩土力学,2006,27(5):828-832Zhu L F,Pan X,Wu X C.The design and development of system of the 3D geological modeling and visualizationJ. Rock and Soil mechanics,2006,27(5):828-8322 Rainald Lohner.Regridding surface triangulationsJ.Computational Physics, 1996, 126( 1) : 1- 10.3 毕林,王李管,陈建宏,冯兴隆.三维网格模型的空间布尔运算J.华中科技大学学报;自然科学版,2008,36(5):82-85Bi L,Wang L G,Chen J H,Feng X L.The spatial boolean operation of 3D mesh modelJ.Journal of Huazhong University of Science and Technology;Natural Science Edition,2008,36(5):82-854 潘振宽,崔树娟,张继萍.基于层次包围盒的碰撞检测方法J.青岛大学学报:自然科学版,2005,18(1):23 -25Pan Z K,Cui S J,Zhang J P.Collision detection algorithm based on hierarchical bounding boxJ.Journal of Qingdao University:Natural Science Edition,2005,18(1):23 -255 刘丽萍, 王琰.基于包围盒编码的曲面求交算法J.沈阳理工大学学报, 2008, 27(2):11-18Liu L P,Wang Y.Algorithm for Surface Intersections Based on Box EncodingJ.Journal of Shenyang Ligong University, 2008, 27(2):11-18.6 张少丽,王毅刚,陈小雕.基于空间分解的三角网格模型求交方法J.计算机用,2009,29(10):2671-2673Zhang S L,Wang Y G,Chen X D.A method for obtaining the intersections of triangular mesh model based on the spatial decompositionJ.For Computer,2009,29(10):2671-2673.7 尹长林,喻定权.一种基于拓扑搜索的三角网求交算法J.计算机工程与应用,2006,(36):209-211 Yin C L,Yu D Q.Rapid Topological Searching-based Intersection Algorithm of Triangulated NetworksJ.Computer Engineering and Applications,2006,(36):209-2118 易琳,袁林旺,盛业华,李润超.V-代约束的结构保持空间插值算法距J 武汉大学学报;信息科学版,2015,40(6):823-828YI Lin, YUAN Linwang, SHENG Yehua, LI Runchao. V-Neighborhood Interation-Constrained Structure-Preserving Spatial Interpolation MethodJ. Geomatics and Information Science of Wuhan University, 2015, 40(6): 823-8289 刘建军,赵文豪,蒯希,杨眉.一种基于TIN的地形特征点生成方法J.地理信息世界,2015,22(1):91-93Liu J J,Zhao W H,Kuai X,Yang M.A Terrain Feature Points Generation Method Based on TINJ.Geomatics World,2015,22(1):91-93A method for obtaining the intersections in triangular mesh model based on the surface equationCHEN Zhen1 TANG Jun1,2 LIAO Huan-Yu1 MING Ting-Bao1 LIANG Hong1 CHEN Jun-Fei1 LIU Yuan-Yuan1（1. College of Geosciences,Yangtze University,Wuhan Hubei 430100）（2. Key Laboratory of Exploration Technologies for Oil and Gas Resources, Ministry of Education,Yangtze University,Wuhan Hubei 430100）AbstractWith the GIS formation modeling based Triangulated Irregular Network, expression and analysis, it is involved a lot of complicated calculations in the triangular mesh intersection model. This paper was presented an method of calculation in triangular mesh intersection model which based on the surface equati