布尔运算（Boolean Operations）是三维建模领域的基础能力：挖孔需要差集，合并零件需要并集，求公共部分需要交集。看起来只是“加加减减”，但真正实现过的人都知道，这是计算几何中最著名的“雷区”之一。问题不在于算法思想有多复杂，而在于浮点误差导致的各种退化情况——共面、共边、顶点恰好落在对方三角形内部等边界条件，会让朴素的实现产出一堆碎片、非流形边甚至直接陷入死循环。本文围绕并集、交集、差集三种运算，系统梳理鲁棒算法的核心思路。
一、布尔运算的数学本质：半空间分类与定向问题
从数学上看，网格布尔运算可以归结为一个分类问题。假设有两个封闭的三角网格A和B，我们想知道A的每个三角形位于B的内部还是外部，同样地也要判断B的每个三角形相对于A的位置。得到分类结果后，三种运算的取舍规则非常直观：
// 伪代码：基于内外的分类规则 // Union(A, B) = A外部的三角形 + B外部的三角形 + 相交产生的新面 // Intersection(A, B) = A内部的三角形 + B内部的三角形 + 相交产生的新面 // Difference(A, B) = A外部三角形 + B内部三角形(翻转法向) + 相交产生的新面
注意差集运算中有一个容易被忽略的细节：保留下来的B内部三角形必须翻转法向。因为原本“B朝外”的面，挖掉A之后变成了空洞的内壁，朝向反了。如果忘记翻转，得到的结果虽然几何上正确，但法向混乱，后续渲染和3D打印切片都会出问题。
这里还有一个前提条件必须强调：参与运算的网格必须是封闭（watertight）且定向一致的。所谓封闭，即每条边恰好被两个三角形共享；定向一致，则是指相邻三角形的公共边方向相反。很多从建模软件导出的模型其实不满足这个条件，直接拿去做布尔运算，再好的算法也救不回来。因此一个健壮的实现通常先做网格修复，再进入运算流程。
二、相交计算与退化情况：鲁棒性的主战场
分类的第一步是求两个网格的交线。具体做法是遍历A、B的三角形对，用三角形与三角形相交测试（Möller算法是经典选择）求出交线段，再把这些线段串接成闭合环。这一步的计算量是O(n·m)，n和m分别是两个网格的三角形数，工程上一定会配合包围盒层次结构（AABB树）做加速，否则两个十万面片的模型相减就能把CPU吃满。
真正的难点在于退化情况。理想情况下，交线干净利落地穿过三角形；但现实中浮点误差会让你遇到：顶点恰好落在对方三角形的边上、两条三角形恰好共面、交线段长度小到接近机器精度。这些情况下，直接比较浮点数等于零几乎必然出错。例如判断一个点是否在平面上：
// 脆弱的写法：直接比较浮点数
if (dot(point - plane.origin, plane.normal) == 0.0) {
// 点在平面上，实际代码几乎永远走不到这里
}
// 鲁棒的写法：引入相对容差
double dist = dot(point - plane.origin, plane.normal);
double eps = 1e-9 * (length(point - plane.origin) + plane.offsetNorm);
if (fabs(dist) < eps) {
// 认为共面，进入专门的共面处理分支
}
容差的选择本身也是一门学问。固定阈值在模型尺寸差异巨大时会失效——一个以毫米为单位的手办模型和一个以米为单位的建筑模型，合理的eps相差三个数量级。更稳妥的做法是使用相对误差，即让容差跟随参与运算的坐标幅度缩放，或者在运算前把两个模型都归一化到单位包围盒内，运算完再缩放回去。
共面三角形是最麻烦的一类退化。两个模型有一块面完全贴合（比如两个方体拼在一起），此时既不能简单归为“内部”也不能归为“外部”，必须对共面区域做二维层面的多边形裁剪（相当于降级成2D布尔运算），再根据两个三角形的法向是同向还是反向，决定共面部分在结果中的去留。主流库如CGAL在这一步投入了大量代码来处理各种组合情况，这也是它体积庞大却备受欢迎的原因。
三、精确算术与工程化方案：从BSP树到成熟库的选择
要彻底解决浮点误差问题，业界给出的答案是精确几何谓词（Exact Geometric Predicates）。思路是：判断点在平面的哪一侧这类几何谓词，用有理数或扩展精度算术来计算，保证结果绝对正确；而坐标存储仍然可以用浮点数，只在高精度内存中传递。Shewchuk的适应性浮点算法是经典实现，它先用浮点快速算，如果误差可能影响符号判定，再升级到精确计算，兼顾了速度和正确性。C++生态中的CGAL正是以“精确内核”著称，代价是运行速度比纯浮点实现慢好几倍。
如果不追求从零造轮子，工程上有几条现成的路线可选。第一条是CGB（Constructive Solid Geometry）风格的BSP树方案，把每个模型递归剖分成空间二分树，布尔运算转化为树的合并。它的优点是天然支持多次连续运算，缺点是剖分会导致三角形数量爆炸，多次运算后面数呈指数增长。第二条是直接使用开源库，选择相当丰富：
- CGAL Boolean Operations：鲁棒性天花板，基于Nef Polyhedron或多面体核，能处理非流形结果，适合对正确性要求极高的场景，如学术研究和工业CAE。
- libigl：头文件库，接口简洁，基于MeshArrangement实现，速度快，适合集成到C++项目中做交互式编辑。
- Cork / MeshBoolean：轻量实现，适合学习算法原理，但对退化输入的容忍度一般。
- Three-BSP-CSG / three-csg-ts：Web端方案，配合Three.js使用，方便在浏览器里做在线建模。
以libigl为例，一个典型的差集运算调用只需几行代码：
#include <igl/copyleft/cgal/mesh_boolean.h>
Eigen::MatrixXd VA, VB, VC;
Eigen::MatrixXi FA, FB, FC;
// 加载或构造 VA/FA 与 VB/FB ...
// 类型参数 MeshBooleanType::Minus 表示差集
igl::copyleft::cgal::mesh_boolean(
VA, FA, VB, FB,
igl::copyleft::cgal::MeshBooleanType::Minus,
VC, FC);
// VC/FC 即为 A - B 的结果网格
最后谈一点实践建议。布尔运算的调试非常依赖可视化手段，建议在开发阶段把分类结果染色显示（A独有部分红色、B独有部分蓝色、交线绿色），问题一眼就能看出来。遇到运算结果破碎时，优先检查输入网格是否封闭、是否有重复顶点和零面积三角形，很多时候问题不在算法而在数据。如果项目允许引入依赖，直接用CGAL或libigl；只有在需要深度定制（比如特殊拓扑保持）时，才值得自己实现完整的鲁棒布尔运算——这是一项公认的高投入工程，libigl作者曾坦言他们的实现历经多次重写才达到可用水准。