三维网格模型的布尔运算方法  

Method of Boolean operation based on 3D grid model

作　　者：陈学工[1] 杨兰[1] 黄伟[1] 季兴[1] 

机构地区：[1]中南大学信息科学与工程学院,长沙410083

出　　处：《计算机应用》2011年第6期1543-1545,1584,共4页journal of Computer Applications

基　　金：国家863计划项目(2006AA06Z114)

摘　　要：提出了一种基于三维网格模型的布尔运算方法。首先通过基于方向包围盒(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 intersecting 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.

关 键 词：网格模型 布尔运算 碰撞检测 交线拓扑 区域划分 

分 类 号：TP391.41[自动化与计算机技术—计算机应用技术]