这一章描述了各种几何体的相交，距离，扫略计算
最近点计算
最近点计算通过给入一个点$p$和一个几何体$D$，要求找到$D$上距离$p$的最近点。
我们假定$p$在几何体外部。内部点某些算法可能会得到不正确的结果。
大部分的最近点算法都很简单。可以直接看“参考”一节的工具书。我这里只记录一些有巧思的和比较复杂的。
到OBB的最近点
一般的想法是将点旋转成相对于OBB的位置，将问题转换为求点到AABB最近点问题。然后算出最近点后再旋转回去。
但其实可以通过OBB的轴直接计算：
到三角形的最近点
需要通过Barycentric计算得到。首先推导Barycentric的计算公式：
注意到$(1)$式中可以使用任意两个量表示另外一个量。所以重心坐标本质上只需要两个量就可以了。
使用面积计算的缺点是，当点在三角形外时，无法知道其在三角形的哪个voronoi域中。但我们通过选取按照特定顺序的向量计算来获取这个信息：
我们首先需要计算$\vec{D} = \vec{AB} \times \vec{BC}$（注意是按照顶点顺序，代码上是cross(pts[1]-pts[0], pts[2]-pts[1])。这个向量后面帮我们判断三角形面积的符号。
我们假设$\vec{D}\ne 0$。
$$ \begin{aligned} & \vec{D_a} = \vec{PB} \times \vec{PC} \\ & \vec{D_b} = \vec{PC} \times \vec{PA} \\ & \vec{D_c} = \vec{PA} \times \vec{PB} \\ & S = ||\vec{D}||^2 = \vec{D}\cdot\vec{D} \\ & S_a = \vec{D_a}\cdot\vec{D} \\ & S_b = \vec{D_b}\cdot\vec{D} \\ & S_c = \vec{D_c}\cdot\vec{D} \\ & \alpha = \frac{\vec{D_a}\cdot\vec{D}}{\vec{D}\cdot\vec{D}} = \frac{\frac{1}{2}|\vec{D_a}||\vec{D}|\cos{\theta}}{\frac{1}{2}|\vec{D}|^2} = \pm \frac{\frac{1}{2}|\vec{D_a}||\vec{D}|}{\frac{1}{2}|\vec{D}|^2} = \pm \frac{||\vec{D_a}||}{||\vec{D}||} = \pm \frac{A_a}{A} \\ & 同理可以得到： \\ & \beta = \pm \frac{||D_b||}{||D||} \\ & \gamma = \pm \frac{||D_c||}{||D||} \\ \end{aligned} $$这样得到的重心坐标会带有符号（注意$\alpha$的计算中，由于$\vec{D_a}$和$\vec{D}$不是同向就是异向，所以$\cos{\theta}$只能是$\pm1$）。而这个符号正是我们判断Voronoi域的关键。注意观察上图：
- 如果P在三角形内，那么满足重心坐标有效的条件
- 如果P在某个边的Voronoi域内，那么$S_i$中有一个值是负的，其他两个是正的（也就是说$\alpha,\beta,\gamma$里有一正两负）。P在负的那个对应边的Voronoi域。比如图上$S_a$就是负的，那么P就在$A$点的对边的Voronoi域中
- 如果P在某个点的Voronoi域内，那么$S_i$中有两个值是负的，一个是正的。P在正的那个对应角的Voronoi域。比如图上$S_a$和$S_b$都是负的，但是$S_c$是正的。那么P就在C点的Voronoi域中
得知了P在哪个Voronoi域中，我们可以非常清晰地知道如何求P到三角形的最近点：
- 如果在边的Voronoi域中，直接求P到此边（线段）的最近点
- 如果在角的Voronoi域中，那最近点就是这个角
其实真正实现上，如果P在边的Voronoi域中（即只要找到任意一个$S_i \lt 0$），那么直接求这个边的最近点即可。因为角的最近点可以退化成求和这个角连接的任意一条边的临近点。这样算法可能可以提前退出，减少运算量。
那么对于三维空间中任意点到三角形的最近点。首先将点投影到三角形所在平面上，然后用上述方法找最近点即可。
四面体(Tetrahedron)最近点算法
可以对每个三角面做一次三角形最近点算法，在结果中取取最近点。
但更好的方法是使用推广到3D中的Barycentric公式，配合推广的三角形最近点算法得到：
假设四棱锥顶点为ABCD，求到P点的最近点。
首先必须假定：从外部看，所有三角面的顶点顺序是一致的（CW或CCW）
然后为了方便理解，假定底面的向量叉积得到的法线是指向四棱锥内部的（这一点代码中无需保证。只要所有面的叉积产生的法线一致朝外/内就行，而这一点已由上面的假设确定。我们最后只看异号的数量）
$$ \begin{aligned} & A_A = \vec{BC}\times \vec{CD} \cdot \vec{BP} \\ & A_D = \vec{AB}\times \vec{BC} \cdot \vec{AP} \\ & A_B = \vec{AC}\times \vec{CD} \cdot \vec{AP} \\ & A_C = \vec{AB}\times \vec{BD} \cdot \vec{AP} \\ & A = \vec{AB} \times \vec{BC} \cdot \vec{AD} \\ & \lambda_A = \frac{A_A}{A} \\ & \lambda_B = \frac{A_B}{A} \\ & \lambda_C = \frac{A_C}{A} \\ & \lambda_D = \frac{A_D}{A} \\ \end{aligned} $$注意底面的两个向量也要按照面环绕顺序选取，以保证最后符号的准确性。
那么根据上面的假设，如果$\lambda_i \gt 0$，那么表示P点在朝向四棱锥内的方向。如果所有$\lambda_i$都大于0。那么P就在四棱锥内部。此时重心坐标成立。
如果存在负号的重心坐标。那么显然，P在Voronoi域内。注意四棱锥的Voronoi域有16个：
- Face Regions (4)：每个三角形面的正上方空间
- Edge Regions (6)：从 6 条边向外延伸的空间
- Vertex Regions (4)：从每个 4 个角顶点向外延伸的空间
上图中橘色是四棱锥，红色是面的Voronoi域（只画了三个）。蓝色是角的Voronoi域。除此之外的全是边的Voronoi域：
蓝色的是边的Voronoi域，沿着边的两端无限延伸。只是这里画的像是有界限一样。
那么我们就可以通过$\lambda _i$和$S_{abcd}$的异号数目来判断点P在哪个Voronoi域内：
- 0个异号：点在四面体里面，重心坐标有效
- 1个异号：点在对应面的Voronoi域内
- 2个异号：点在对应边的Voronoi域内
- 3个异号：点在对应顶点的Voronoi域内
和三角形最近点算法一样，当检测到存在异号之后，就退化成点P到使用对应面所在的三角形的最近点问题，这样可以提前退出算法。
注意，我们之前假设从外部看所有面的顶点顺序都是一致的。但由于四面体的性质，这不可能成立。至少会有一个面的顺序和别的面不一样。
你可以在每次算$S_i$的叉乘时看其和$\vec{AB} \times \vec{BC}$的方向是否一致，不一致就取反。但有一个更聪明的方法:
- 选定某个顶点（比如$A$）
- 计算$S$的时候，使用从此顶点出发的两个边向量（比如$\vec{AB},\vec{AC}$）进行叉乘
- 计算$S_i$的时候，叉乘中不使用面上的两个向量，而也是从此顶点出发，取一个边向量（如$\vec{AB}$）以及和P点连接的向量（这里是$\vec{AP}$）进行叉乘（叉乘的顺序也有讲究，要保证当P在四面体时结果为正，这点可以直接从几何图形上得到）：
可以得到
一般凸多面体最近点算法
使用GJK算法。这个算法很重要，得后面单独开一章说。
距离计算
绝大部分距离计算都可以转换为到最近点的距离问题。变相地将问题化简为最近点问题
扫略计算
参考公式大全即可。没什么好说的。绝大部分使用Minkowski和可解。