三维网格模型的布尔运算方法
陈学工;杨兰;黄伟;季兴
【摘 要】提出了一种基于三维网格模型的布尔运算方法.首先通过基于方向包围盒(OBB)层次包围盒树的碰撞检测算法,得到实体的相交三角形对;接下来求出两相交三角形之间的交线,建立与三角形的交线拓扑关系;通过分类处理三种交线类型来对相交三角形进行区域划分,得到一系列多边形,并对多边形进行三角剖分形成结果区域;最后根据体的包含关系构建关系邻接表,判断多边形区域的相对于其他实体的内外关系并通过网格模型的拓扑关系,定位表面三角网格区域;同时根据交、并、差等布尔操作,对结果区域进行取舍,得到最终结果.实验结果表明相交部分的岩性与实体的岩性相吻合,验证了该算法的正确性以及可行性.%A kind of Boolean operational method based on a three-dimensional grid model was proposed. Firstly, through collision detection algorithm based on hierarchical bounding box tree of Oriented Bounding Box (ORB), the intersecting triangles could be got. Through the intersection test of the triangles, the intersecting lines could be obtained and the intersecting lines topology relations with the triangles could be established. Secondly, a regional division for the interse cting triangles was made through processing the three types of intersecting lines, so as to get a series of polygons, and carry out Delaunay triangulations for polygon to get the result area. Lastly, relation adjacency list was constructed based on solid containing relations, the polygon's internal relation and external relation with other entities were judged, and the triangles were located according to the mesh model topology relations. Simultaneously, according to such Boolean operations as the intersection, union, and differences, according to the grid model topology relations were judged, the position of the triangles were judged and then the final results could be obtained. Experimental results show that this algorithm can achieve better results. Experimental results show that the lithology of intersecting parts is consistent with the entities and can verify the correctness and feasibility of the algorithm.
咖啡季节【期刊名称】《计算机应用》
试行条例【年(卷),期】2011(031)006
【总页数】4页(P1543-1545,1584)
【关键词】网格模型;布尔运算;碰撞检测;交线拓扑;区域划分
王朝抢劫案【作 者】陈学工;杨兰;黄伟;季兴
【作者单位】中南大学信息科学与工程学院,长沙410083;中南大学信息科学与工程学院,长沙410083;中南大学信息科学与工程学院,长沙410083;中南大学信息科学与工程学院,长沙410083
【正文语种】中 文
【中图分类】TP391.41
0 引言
布尔运算在矿山软件中有着重要的应用。如在三维地质建模中，对实体模型之间的布尔运算;在地下采矿中，三维巷道的实体联合运算;在露天工程测量中，三维表面模型的布尔运算。同时，布尔运算也是三维造型技术中构造复杂实体最为重要和复杂的问题之一。目前，三维布尔运算取得了一系列进展，但仍存在一些关键问题。文献［1］提出了基于三维
实体(Stereo Lithography，STL)模型的布尔运算算法，该算法通过提取相交环来提高布尔运算的稳定性。文献［2］提出基于复式可定向的网格模型实现布尔运算，该方法能解决开闭网格模型的布尔运算情况，在一定程度上提高了的布尔运算效率，但在三角形相交测试上有待改进。文献［3］提出了一种基于不规则三角网(Triangulated Irregular Network，TIN)模型的体布尔运算方法，采用碰撞检测手段提高了效率，但存在精度问题。从上述可知，布尔运算主要目标在于算法的稳定性，效率以及所运算结果的精确性。
针对上述问题，本文提出一种基于网格模型的布尔运算算法。该算法采用碰撞检测手段有效地对有序的网格模型进行布尔运算，将布尔运算的复杂问题分解为三种三角形基本类型，分类处理这些类型，使问题得到简化，并在实际的矿业软件中能有效处理组合实体的情况，取得了良好的效果。
1 体布尔运算
1.1 主要思路
鄢礼华布尔运算是对多个三维实体进行求交、并和差等运算，假设A、B分别表示两个实体，根据计算机图形学及计算几何学知识，可将这些运算采用式(1)来实现［4］:
其中:A in B和A out B分别表示实体A的表面处于实体B内和外的部分，(B in A)－1指B的表面在实体A内的部分的补集。同理可得到其他的操作符号的含义。由于体的表示是基于三角网格模型的，因此，布尔运算的计算最终归于对体的每个三角形的操作。实现体的布尔运算步骤如下:
1)建立实体的方向包围盒(Oriented Bounding Box，OBB)树，通过OBB混合包围盒技术进行相交检测，获取相交三角形对;
2)求取三角形对的交线段，并对当前三角形中的所有交线段进行连接，并构造交线与三角形的拓扑关系;
3)跟踪和定位交线边，并对交线进行类型分类;
4)分类处理不同类型的交线，并形成多边形区域;
5)判断多边形区域相对于其他实体的内外关系，依据网格模型的拓扑关系，定位表面三角网格区域，确定结果区域;
6)结果区域重组，形成布尔运算结果。
1.2 快速碰撞检测
采用文献［5］中提出的基于OBB层次包围盒树的碰撞检测算法，快速剔除明显不相交的三角面片。与该OBB包围盒技术不同的是，代替粗糙的两个叶子节点之间的包围盒重叠测试，而直接进行精确的包围盒与三角形的相交测试［6］和三角形与三角形的相交测试，使包围盒存储需求降低近50%，进而全面优化和提升算法的执行速度和效率［7］。如图1所示，摘除叶子节点的包围盒，并将其相关信息储存在父节点中。
图1 改进的包围盒树
1.3 交线的求取
交线的求取采用文献［8］中提出的两两三角形求交线算法来实现。根据OBB检测出来的相交三角形对，求取三角形T1、T2之间的交线，如图2所示，分别计算T1、T2在平面交线L的交点坐标I1、I2和I1'、I2'，并求出重叠线段点坐标。将求解出的交线段在T1、T2中分别进行索引，这样对于两相交的三角形，只需进行一次三角形相交求解，同时标记当前三角形为相交三角形，便于后续操作。
图2 三角形交线重叠区间的计算
1.4 建立交线拓扑
布尔运算是通过交线段重新划分三角形所形成的区域来实现的，因此，交线段的拓扑关系至关重要。由于通过当前三角形与另外实体所有三角形的求交出的交线是一组方向杂乱的交线段组，因此，在对三角形区域划分前，需确定所得到的交线段间的连接关系。设当前三角形T的所有交线段为I，当前交线边为e，下一条交线边为e'，新的交线边组L，则交线连接的步骤如下所示:
1)任取交线组I中一条交线边e，并将e从I中删除，判断I中是否有与e的终点编号相同的交线边e'，若存在，则将e'连接到e的末端，同样将e'从I中删除，否则取下一条交线边，重复此次操作。如在图3(a)中，首先任选取边e4，搜索出边e3与e4的末端点重合，则将e3连接到e4后，同理跟踪连接e2，将新形成的交边并入L中。
2)若交线组I中仍存在交线边，则可能存在与交边e的初始点可连接的交线边，此时，判断I中是否存在与e的初始点相同的交线边e'，若存在，则将e'连接到e初始端，将e'从I删除，
重复此次操作。如图3(a)中的交线段e5可与交线e4→e3→e2的初始点连接，因此所形成最终交线边为l1:e5→e4→e3→e2。
3)判断交线组I的记录是否为空，若不为空，则说明当前三角形T中存在着多条不连续交线边，需重复第1)～2)步，直到I中的所有交线边为空。如图3(b)中的e0、e1交线段可组成另一条交线边l2，至此所有的交线边都已连接完毕。
http 代理
图3 交线段的连接
若交线的某一中间顶点在三角形边上，此时交线所划分的区域已经被分割开，同样，也要将该交线分裂成多条交线(如图3(c)中l1交线上中间有一顶点在T的边上，将l1分裂成l1和l3)。当交线中某一交线段与三角形边重合时，那么该交线段对T的区域划分没有影响，因此可以将该交线段忽略，无需连接到交线中来，对应的交线被分裂成多条交线(如图3(c)中l2交线中的线段e)。
dnf王刚对于已排好序的交线边，在三角形中的位置关系可总结为三种基本类型，如图4所示，分别为跨角类型、跨边类型和环形类型。在复杂的相交三角形中，所得到的交线是这三种基本
类型的组合。针对以上三种交线类型以及交线边不可能存在相交的情况前提下，以三角形边方向为参照基准，分别计算各交线边在三角形中的具体位置，并判断其所属类型，便于后续的区域划分操作。
图4 交线边在三角形中的三种基本类型
设当前三角形T为逆时针方向，T的三条边为ej(j∈{0，1，2})，T中的交线边集为L，用li表示一条交线边(0≤i＜n，n为交线边的数目)，那么交线边位置与类型确定步骤以图5为例进行说明。在图5(a)中，T中存在交线l1、l2，在e0边上有p1、p2和p3，对p1、p2和p3进行排序得到如图所示编号，其中(i，j)指示当前点所在边i上，并且边i上的序号为j。根据交线边在三角形中的三种基本类型可知，l1为跨角类型，l2为跨边类型。对于图5(c)中的l1和l3，两交线的共同点p编号相同，如图5(b)所示，为了使每条交线首尾顶点在T上边的编号唯一，只需计算q和r点到边e0末尾点的欧氏距离，并按距离值从小到大进行编号。
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议