前言
一种快速判断空间中三角形与 box 相交的方法，出自论文：Tomas Akenine-Moller. Fast 3D triangle-box overlap testing. A. K. Peters, Ltd. 2002.
前言
一种快速判断空间中三角形与 box 相交的方法，出自论文：Tomas Akenine-Moller. Fast 3D triangle-box overlap testing. A. K. Peters, Ltd. 2002.
预备篇
该论文的理论基础来自分离轴理论（separating axis theorem， AST），AST 常用于检测两凸多边形是否相交。一句话描述 AST 即为：若两多边形能用一条直线分隔开，则两多边形不相交。如何判断该直线存在即为 AST 的关键。常用的判断方法为找出两多边形所有边向量（多边形相邻两点构成的向量，顺时针或逆时针都行）的法向量，使用向量点积分别计算两多边形在各法向量上的投影（一般以多边形上的点和原点构成一个向量与法向量做点积），从而得到两个投影集合，判断两集合是否相交（找出两个集合的最大值和最小值，若最小值大于最大值，则不相交），若不相交，则 AST 中的直线存在，即两多边形不相交，若相交，则继续判断在其它法向量上的投影，若所有法向量上的投影都相交，则两凸多边形相交。AST 常用于二维下判断两凸多边形的相交情况，三维下的情况比较复杂。
正文篇
该论文给定 13 个向量，若 box 的边和三角形的边在这 13 个向量中的投影均相交，则认为 box 与三角形相交。为简化运算，box 直接假定为轴向包围盒（axis-aligned bounding box， AABB），坐标轴原点为 box 中心，由于可以将普通 box 通过旋转平移等一系列变换，变成以原点为中心的 AABB， 所以该假定是有效的。设三角形的顶点为 \(v_0, v_1, v_2\) ，box 的一半长宽高为 \(h_x, h_y, h_z\) ，则这 13 个向量分别为 \(e_0(1, 0, 0), e_1(0, 1, 0), e_2(0, 0, 1)\) ，三角形的法向量 \(n\) （通过三角形两边向量叉乘得到），剩下九个向量分别为 \(a_{ij} = e_i \times f_j , i,j \in \{0, 1, 2\}\) ，其中 \(f\) 为三角形的边向量 \(f_0 = v_1 - v_0, f_1 = v_2 - v_1, f_2 = v_0 - v_2\) ， \(\times\) 代表向量叉乘。若直接这样一个个的计算投影是否相交，虽然能达到目的，但快速就无法体现了，所以作者根据向量计算方法和一些策略将其中一些需要计算投影的地方极大的简化了，所以加快的计算速度。具体简化过程为：
首先来看最后九个向量，\(a_{00} = e_0 \times f_0 = (0, -f_{0z}, f_{0y})\) ，三角形三个顶点在在该向量上的投影分别为：
\(p_0 = a_{00} \cdot v_0 = (0, -f_{0z}, f_{0y}) \cdot v_0 = v_{0z}v_{1y} - v_{0y}v_{1z}\)
\(p_1 = a_{00} \cdot v_1 = (0, -f_{0z}, f_{0y}) \cdot v_1 = v_{0z}v_{1y} - v_{0y}v_{1z} = p_0\)
$p_2 = a_{00} v_2 = (0, -f_{0z}, f_{0y}) v_2 = (v_{1y} - v_{0y})v_{2z} - (v_{1z} - v_{0z})v_{2y} $
由于 \(p_0 == p_1\)， 所以在求最大最小值时只需要做一次比较，接着求 box 在该向量上的投影，box 中心在原点，所以投影半径 \(r\) 可以以一种简单的方式求出：
\(r = h_x|a_{00x}| + h_y|a_{00y}| + h_z|a_{00z}| = h_y|a_{00y}| + h_z|a_{00z}|\)
计算投影是否重合也很简单：
\(if(min(p_0, p_2) > r \ || \ max(p_0, p_2) < -r) \quad return \ false\) 否则两者投影相交，继续计算其它向量。
三个轴向单位向量 e 中的投影是否重合就更好判断了，完全不需要计算投影，只需要计算三角形的最小 AABB，判断两个 AABB 是否相交即可（取两个 AABB 最小的顶点和最大的顶点，从三维上判断最小是否的大于最大的即可，若任意一个维度上最小的比最大的大，则两者不相交），
至于判断最后一个向量——三角形的法向量上的投影是否重合，相当于判断三角形所在平面是否与 box 相交。判断 box 与平面相交有一种简单快速的方式，即通过公式 \(|d| <= a_1 |n \cdot A^1| + a_2|n \cdot A^2| + a_3 |n \cdot A^3|\) ，其中 \(d\) 为 box 中心到平面的距离（中心点到平面上一点构成的向量与平面法向量做点积），\(n\) 为平面法向量，\(A^1\) 为 box 侧面法向量，对于 AABB 可为 \((1, 0, 0)\)，\(a_1\) 为 box 中心到侧面的距离，对于 AABB 可为 \(h_x\)，同理 \(A^2\) 为 box 顶面法向量，对于 AABB 可为 \((0, 1, 0)\)，\(a_2\) 为 box 中心到顶面距离，对于 AABB 可为 \(h_y\)，\(A^3\) 为 box 正面法向量，对于 AABB 可为 \((0, 0, 1)\)，\(a_3\) 为 box 中心到正面距离，对于 AABB 可为 \(h_z\)，即在 AABB 中，该公式可简化为 \(|d| <= h_x|n_x| + h_y|n_y| + h_z|n_z|\) ，满足该公式，即可判定平面与 AABB 相交。
如此 13 个向量全部判断完毕，如全都相交，则可认定三角形与长方体相交，若其中一个不相交，则三角形与长方体不相交。三维的都能判断，二维的三角形与矩形相交判断就更简单了，分成两类法向量后，利用向量运算先简化运算量，再计算投影是否相交即可。
附录
还有一种根据距离判断两个 AABB 是否相交的办法，即先取两个 AABB 的中心 \((x_1, y_1, z_1)\) 和 \((x_2, y_2, z_2)\)，然后计算两个中心点之间的三个维度的距离，将 x 维度的距离与两个AABB 的 \(h_x\) 之和比较，若中心点 x 维度的距离较大，则不相交。即：\(if (|x_1 - x_2| > h_{x1} + h_{x2}) \quad return \ false\) ，否则比较 y 维度， z 维度，若所有都小，则两 AABB 相交。这种方式是 Shaun 在一次面试中被问到没答出后在网上找到的答案，其实感觉和比较最小最大顶点也差不多，都是从不相交出发，因为直接判断相交基本不可能，而不相交很容易判断，把所有的不相交情况判断完，那就只剩相交了，可惜面试官只想要这种方案 ╮(╯▽╰)╭。
