收稿日期
：2010 － 11 － 24；
修回日期
：2011 － 01 － 21。
基金项目
：
国家
863
计划项目
（ 2006AA06 Z114） 。
作者简介
：
陈学工
（ 1965 － ） ，
男
，
湖南长沙人
，
副教授
，
博士
，
主要研究方向
：
地理信息系统
、
计算机图形学
；
杨兰
（ 1984 － ） ，
女
，
湖南辰溪
人
，
硕士研究生
，
主要研究方向
：
地理信息系统
；
黄伟
（ 1984 － ） ，
男
，
湖南浏阳人
，
硕士研究生
，
主要研究方向
：
地理信息系统
；
季兴
（ 1985 － ） ，
男
，
湖南常德人
，
硕士研究生
，
主要研究方向
：
计算机图形学
。
文章编号
： 1001 － 9081（ 2011） 06 － 1543 － 03 doi： 10． 3724 /SP． J． 1087． 2011． 01543
三维网格模型的布尔运算方法
陈学工
，
杨 兰
，
黄 伟
，
季 兴
（
中南大学 信息科学与工程学院
，
长沙
410083）
( cacerlin@ 126． com)
摘 要
：
提出了一种基于三维网格模型的布尔运算方法
。
首先通过基于方向包围盒
（ OBB）
层次包围盒树的碰撞
检测算法
，
得到实体的相交三角形对
；
接下来求出两相交三角形之间的交线
，
建立与三角形的交线拓扑关系
；
通过分
类处理三种交线类型来对相交三角形进行区域划分
，
得到一系列多边形
，
并对多边形进行三角剖分形成结果区域
；
最
后根据体的包含关系构建关系邻接表
，
判断多边形区域的相对于其他实体的内外关系并通过网格模型的拓扑关系
，
定位表面三角网格区域
；
同时根据交
、
并
、
差等布尔操作
，
对结果区域进行取舍
，
得到最终结果
。
实验结果表明相交部
分的岩性与实体的岩性相吻合
，
验证了该算法的正确性以及可行性
。
关键词
：
网格模型
；
布尔运算
；
碰撞检测
；
交线拓扑
；
区域划分
中图分类号
： TP391． 41
文献标志码
：A
Method of Boolean operation based on 3D grid model
CHEN Xue-gong， YANG Lan， HUANG Wei， JI Xing
( School of Information Science and Engineering， Central South University， Changsha Hunan 410083， China)
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
0
引言
布尔运算在矿山软件中有着重要的应用
。
如在三维地质
建模中
，
对实体模型之间的布尔运算
；
在地下采矿中
，
三维巷
道的实体联合运算
；
在露天工程测量中
，
三维表面模型的布尔
运算
。
同时
，
布尔运算也是三维造型技术中构造复杂实体最
为重要和复杂的问题之一
。
目前
，
三维布尔运算取得了一系
列进展
，
但仍存在一些关键问题
。
文献
［1］
提出了基于三维
实体
（ Stereo Lithography，STL）
模型的布尔运算算法
，
该算法
通过提取相交环来提高布尔运算的稳定性
。
文献
［2］
提出基
于复式可定向的网格模型实现布尔运算
，
该方法能解决开闭
网格模型的布尔运算情况
，
在一定程度上提高了的布尔运算
效率
，
但在三角形相交测试上有待改进
。
文献
［3］
提出了一
种基于不规则三角网
（ Triangulated Irregular Network，TIN）
模
型的体布尔运算方法
，
采用碰撞检测手段提高了效率
，
但存在
精度问题
。
从上述可知
，
布尔运算主要目标在于算法的稳定
性
，
效率以及所运算结果的精确性
。
针对上述问题
，
本文提出一种基于网格模型的布尔运算
算法
。
该算法采用碰撞检测手段有效地对有序的网格模型进
行布尔运算
，
将布尔运算的复杂问题分解为三种三角形基本
类型
，
分类处理这些类型
，
使问题得到简化
，
并在实际的矿业
软件中能有效处理组合实体的情况
，
取得了良好的效果
。
1
体布尔运算
1． 1
主要思路
布尔运算是对多个三维实体进行求交
、
并和差等运算
，
假
设
A、B
分别表示两个实体
，
根据计算机图形学及计算几何学
知识
，
可将这些运算采用式
（ 1）
来实现
［4］
：
A
∩
B = A in B + B in A
A
∪
B = A out B + B out A）
A － B = A out B + （ B in A）
－
{
1
（ 1）
其中
： A in B
和
A out B
分别表示实体
A
的表面处于实体
B
内
和外的部分
，（ B in A）
－1
指
B
的表面在实体
A
内的部分的补
集
。
同理可得到其他的操作符号的含义
。
由于体的表示是基于
第
31
卷第
6
期
2011
年
6
月
计算机应用
Journal of Computer Applications
Vol． 31 No． 6
June 2011
