计算机应用 ›› 2011, Vol. 31 ›› Issue (06): 1543-1545.DOI: 10.3724/SP.J.1087.2011.01543

• 图形图像技术 • 上一篇    下一篇

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

陈学工,杨兰,黄伟,季兴   

  1. 中南大学 信息科学与工程学院, 长沙 410083
  • 收稿日期:2010-11-24 修回日期:2011-01-15 发布日期:2011-06-20 出版日期:2011-06-01
  • 通讯作者: 杨兰
  • 作者简介:陈学工(1965-),男,湖南长沙人,副教授,博士,主要研究方向:地理信息系统、计算机图形学;杨兰(1984-),女,湖南辰溪人,硕士研究生,主要研究方向:地理信息系统;黄伟(1984-),男,湖南浏阳人,硕士研究生,主要研究方向:地理信息系统;季兴(1985-),男,湖南常德人,硕士研究生,主要研究方向:计算机图形学。
  • 基金资助:
    国家863计划项目

Method of Boolean operation based on 3D grid model

CHEN Xuegong,YANG Lan,HUANG Wei,JI Xing   

  1. School of Information Science and Engineering, Central South University, Changsha Hunan 410083, China
  • Received:2010-11-24 Revised:2011-01-15 Online:2011-06-20 Published:2011-06-01
  • Contact: YANG Lan

摘要: 提出了一种基于三维网格模型的布尔运算方法。首先通过基于方向包围盒(OBB)层次包围盒树的碰撞检测算法,得到实体的相交三角形对;接下来求出两相交三角形之间的交线,建立与三角形的交线拓扑关系;通过分类处理三种交线类型来对相交三角形进行区域划分,得到一系列多边形,并对多边形进行三角剖分形成结果区域;最后根据体的包含关系构建关系邻接表,判断多边形区域的相对于其他实体的内外关系并通过网格模型的拓扑关系,定位表面三角网格区域;同时根据交、并、差等布尔操作,对结果区域进行取舍,得到最终结果。实验结果表明相交部分的岩性与实体的岩性相吻合,验证了该算法的正确性以及可行性。

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

Abstract: 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.

Key words: grid model, Boolean operation, collision detection, intersecting lines topology, region division

中图分类号: