三维网格模型实体布尔运算方法的研究与实现

摘要

三维布尔运算技术是计算机三维造型技术中构造复杂实体最为重要和复杂的问题之一，并在三维地理信息系统、虚拟现实、交互式可视化等领域有着重要的应用。因此，对三维布尔运算技术的研究，具有重要的学术意义和应用价值。本文在分析了三维布尔运算技术的基础上，主要围绕以下两大问题来展开研究：(1)基于方向包围盒(Oriented Bounding Box：OBB)碰撞检测算法过程中如何进行快速碰撞检测的效率问题；(2)基于三维网格模型布尔运算算法过程中如何进行精确求交的准确度问题。
　　 针对问题(1)，本文研究了传统的OBB碰撞检测算法，提出了一种改进的基于OBB层次包围盒树的快速碰撞检测算法。算法在继承碰撞检测算法优点的同时，突破了它的局限性，能够处理任意形状多面体之间的碰撞检测问题，节省了一半的存储空间，并且能快速检测出相交三角形对，因此，有效地提高了布尔运算效率。算法预先对矿体表面网格模型进行拓扑化，并在该拓扑结构基础上合理地组织成OBB层次二叉树结构，通过自顶向下原则构建去除叶子包围盒的OBB包围盒树，来实现快速碰撞检测。
　　 针对问题(2)，本文提出了一种基于三维网格模型的布尔运算方法。该算法首先通过基于OBB层次包围盒树的碰撞检测算法，得到实体的相交三角形对。求出两相交三角形之间的交线，建立与三角形的交线拓扑关系。然后通过分类处理三种交线类型来对相交三角形进行区域划分，得到一系列多边形，并对多边形进行三角剖分形成结果区域。最后根据体的包含关系构建关系邻接表，判断多边形区域的相对于其他实体的内外关系并通过网格模型的拓扑关系，定位表面三角网格区域。同时根据交、并、差等布尔操作，对结果区域进行取舍，得到最终结果。实验结果表明该算法能取得很好效果。