Jiang X, Peng Q, Cheng X, et al. Efficient Booleans algorithms for triangulated meshes of geometric modeling[J]. Computer-aided Design and Applications, 2016, 13(4): 419-430.
更多introduction的介绍可以直接看原文，这里主要介绍文中使用的具体实现。
更个过程分为两个阶段：两个mesh之间的相交检测和布尔运算。如下图Fig2。
这篇文章的主要贡献点如下：
相交检测在布尔运算中是很重要的一布。
对于两个相交的mesh而言，相交部分的空间的大小是小的。octree能够利用空间划分加速相交测试。
给定两个网格\(S_A\)和\(S_B\)。\(Box_A\)和\(Box_B\)分别为\(S_A\)和\(S_B\)的最小AABB。公式如下：
\(Box_B\)可以用相同方式计算。两个的交集如下：
为了保证能够把相交三角形都包含在内部，对上面的式子进行了扩展，如下：
其中\(l\)为\(S_A\)和\(S_B\)中的最长边。
这一节主要介绍了浮点型计算精度引发的一些问题。
相交线计算的时候需要考虑两种情况，共面还是不共面，针对共面问题，可以转换为2D 三角形相交问题。这里主要介绍不共面时候相交线的计算。
通常情况下，有三种相交情况（如下图所示）：
三种交点的权重比为：EndP > EdgeP > FaceP。
算法的详细伪代码如下：
Algorithm 1 Calculate intersection lines
for each pair of triangles (T1, T2) do
for each edge e \in T1 do
m = Intersection(e, T2);
if (exist_intersection(e, T2) && m* = Intersection(e, T2))
Properties(m) = Properties(m*) = Priority(m,m*)
Coordinate(m*) = Coordinate(m)
end for
for each edge e \in T2 do
m = Intersection(e, T1)
if (exist_intersection(e, T1) && m* = Intersection(e, T1))
Properties(m) = Properties(m*) = Priority(m,m*)
Coordinate(m*) = Coordinate(m)
end for
end for
相交的三角形上，通常会有多个相交线段，这些相交线段将三角形划分为多个多边形面。（如何划分？？）接下来这些多边形需要被三角化。
文中的方法分为两部分：
本文中仅对属于相交三角形的点进行了区分。
假设mn为\(\Delta abc\)和\(\Delta def\)的交线。这两个三角形分别属于不同的mesh。\(n_{abc}\)和\(n_{def}\)分别是\(\Delta abc\)和\(\Delta def\)的法向量，具体为\((x_{n1}, y_{n1}, z_{n1})\), \((x_{n2}, y_{n2}, z_{n2})\)。\(p(x_1,y_1,z_1)\)和\(q(x_2,y_2,z_2)\)分别是\(\Delta abc\)和\(\Delta def\)的上面的一个点。那么平面方程如下：
上图中，两个三角形相交于m，n点，对a，c，e，d点的内外位置进行判断。a位于包含\(\Delta def\)的mesh的内部，d位于包含\(\Delta abc\)的mesh的内部。c，e点位于外部。对于退化的相交场景，至少一个三角形的一个点在另一个三角形对应的mesh上。当相交三角形的所有顶点都进行了判断，分别标记了“in”，“out”，“on”，下面就要进行sub-meshes的创建。
不同类型的mesh定义：
那么不同布尔操作的结果如下：
具体伪代码类似如下：
计算过程示意图如下：
PaperRead - Efficient Booleans algorithms for triangulated meshes of geometric modeling
原文：https://www.cnblogs.com/grass-and-moon/p/13368247.html