关于三维布尔运算的几点思考

三维布尔运算概述

三维布尔运算根据三维实体数据结构表达分为CSG布尔运算、Brep布尔运算、三角网格布尔运算等类型。这几种类型算法在不同情境下有不同的优势，根据情况进行选择。但这也不能作为随意选择方案的借口，在不分析实际情况下。

CSG和BRep布尔运算能够保留原始几何拓扑信息，适用于各类设计编辑场景，如建模设计软件中。而三角网格布尔运算也是常见和常用的，由于一些因素，当前实体的表达方式就是三角面网格方式，也需要对这些实体进行编辑，这时候三角网格布尔运算是最佳选择方案。当然也有其他方案，如将三角网格实体拟合为Brep实体，然后使用BRep布尔运算方法进行计算，至于有没有必要，还是上述表达的那样，根据实际情况分析，进行选择取舍。

本文就三角网格布尔运算几点思考进行简单记录。

三角网格布尔运算

三维布尔运算的一个核心思想是得到运算两实体彼此相对内外部分，然后根据布尔运算类型对这些部分进行组合。如实体A与实体B进行计算得到A in B、A out B、B in A、B out A四部分，实体A与实体B求交运算即为A in B + B in A，求并、求差运算类似，求差会涉及到组合前对对应部分进行取反，这里不再赘述。

那么问题来了，如何提高运算得到两实体彼此相对内外部分的效率？

效率提升思考

关于该问题有不少论文、文章、开源库、商业库进行过思考，并形成各自提出的方案，思路主线是怎样降低判断一个三角面与实体的包含关系的运算时间。

目前有空间分区二叉树（BSPTree）和其它搜索树（如八叉树、球体空间位置树）等方案。

BSPTree方式：基于实体本身的几何拓扑数据构造树（三角面所在超平面对实体空间进行分割）

• 优势是在搜索时即可以得到精确的结果；
• 劣势是会产生较多的碎三角面、构造的BSPTree可能不太平衡，当然这两个问题都有方案去应对；

八叉树方式：根据实体空间分布进行八叉树的构造，得到的搜索树比较平衡，搜索得到相关三角面子集后，由三角面子集对目标三角面进行切割，根据切割线（有向）和目标三角面本身的轮廓线（有向）进行路径搜索得到目标三角面在实体内外部分。当然可能没有切割到，这时就需要判断目标三角面是在实体内部还是外部，同样可以利用实体八叉树降低此判断复杂度。

• 优势是根据实体空间分布进行八叉树的构造，得到的搜索树比较平衡，同时不会产生多余的三角面；
• 劣势是计算实现复杂；

如果不进行优化，判断一个三角面与实体的包含关系的时间复杂度为O(N)，而上述两种优化方案复杂度均为O(logN)，但并不意味着效率一样，只是效率的级数一致，但毕竟N和6N还是有倍数差距的。

BSPTree方式优化

在构建实体BSPTree时产生零散的三角面是合理的，也是为了计算精确。目标三角面在BSPTree中进行搜寻过程中由于切割产生了很多零碎的三角面，这个问题可以通过记录新产生的零碎三角面对应的原始三角ID的方式，进行针对性的拟合，达到消除冗余三角面的目的。

至于怎么尽可能保持BSPTree平衡，可以选择与所在超平面与三角面集质心距离最近或较近的三角面作为拆分左右子树的参照三角面

参考

1.三维模型的布尔运算研究
2.几何算法学习实践（三维）
3.3D网格布尔运算开源库