计算机应用 ›› 2011, Vol. 31 ›› Issue (05): 1198-1201.

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

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

陈学工1,马金金1,邱华1,付金华2,肖克炎3   

  1. 1.中南大学 信息科学与工程学院, 长沙410083
    2.中南大学 软件学院, 长沙410083
    3.中国地质科学院 矿产资源研究所,北京100037
  • 收稿日期:2010-11-01 修回日期:2010-12-25 发布日期:2011-05-01 出版日期:2011-05-01
  • 通讯作者: 马金金
  • 作者简介:陈学工(1965-),男,湖南新化人,副教授,博士,主要研究方向:计算机图形学、地理信息系统;马金金(1985-),男,江苏南通人,硕士研究生,主要研究方向:计算机图形学、地理信息系统;邱华(1985-),女,贵州贵阳人,硕士研究生,主要研究方向:地理信息系统;付金华(1984-),男,河南信阳人,硕士研究生,主要研究方向:地理信息系统;肖克炎(1964-),男,湖南常德人,研究员,博士,主要研究方向:矿产资源评价、地理信息系统。
  • 基金资助:

    国家863计划项目(2006AA06Z114);中南大学研究生创新项目(2010ssxt029)。

Steady algorithm for Boolean operation of 3D mesh model

CHEN Xue-gong1, MA Jin-jin1, QIU Hua1, FU Jin-hua2, XIAO Ke-yan3   

  1. 1.School of Information Science and Engineering, Central South University, Changsha Hunan 410083, China
    2.School of Software Engineering, Central South University, Changsha Hunan 410083, China
    3.Institute of Resources, Chinese Academy of Geological Sciences, Beijing 100037, China
  • Received:2010-11-01 Revised:2010-12-25 Online:2011-05-01 Published:2011-05-01

摘要: 给出一种稳定、高效的三维网格模型的布尔运算算法。该算法首先,基于网格模型原始的拓扑关系,结合层次包围盒相交检测实现网格模型相交区域快速定位;然后,采用改进的空间三角形求交算法求解离散交线段数据,并对单个三角形重新进行Delaunay三角剖分;最后,通过建立交线段与相交三角形间的拓扑关系对交线快速跟踪提取,通过局部区域快速分类组合,实现三角网格模型的精确布尔运算。该算法能有效地处理各种特殊情况且运行稳定;程序实现简单,实例证明符合工程需求。

关键词: 网格模型, 布尔运算, 三角形求交, 拓扑关系

Abstract: This paper proposed a stable and precise algorithm for 3D mesh model. Firstly, the algorithm, based on the original topology of mesh model, realized quick location of intersectional area of mesh curve by combining the intersection test of the layers of nodes bounding box. Then the algorithm utilized the improved triangular intersection algorithm to calculate the discrete intersectional segments and re-triangulates every intersectional triangle. Through building the topology of intersectional segments and triangles, the algorithm could quickly trace and pick up the discrete segments, and classify and combine the local area, and realize the precise Boolean operation. The algorithm could effectively deal with all kinds of instances, and could be implemented in programs easily. And the experimental results prove that the algorithm accords with requirements of the project.

Key words: mesh model, Boolean operation, triangular intersection, topology relation