碰撞点求解（一）：最近内部顶点法

[phenomLi]

前言

好久没有更新物理引擎相关的文章了，因为这段时间都在忙其他事情，当然初心还是不能忘的。不过物理引擎相关的文件夹也好久没有打开了，现在看起来竟然有一点陌生。
想了一下，这样零零散散地写意义不是很大，因此我决定接下来会好好整理一下与物理引擎有关的文章，最好整合成几个系列，国内物理引擎技术的教程或讲解都太少了，大多数都是只涉及点皮毛或者泛泛而谈之后就太监了，但我相信对这方面感兴趣的人是有不少的，因此坚持更新，总会有人需要的。

什么是碰撞点

碰撞点，顾名思义便是两个物体发生碰撞或者接触的点。碰撞点是处理碰撞的关键，因为这取决了碰撞之后求解器计算出的冲量要应用于物体的哪个位置，在物体的不同位置应用冲量往往会产生截然不同的效果，比如在物体质心施加冲量物体会笔直地飞出去，而在偏离质心的位置施加冲量则会产生不同程度的旋转。执行完碰撞检测算法（如SAT）我们通常只会得到碰撞法线和穿透深度，而碰撞点，需要我们单独计算。

在现实世界中，两个正方体相接触，下面的红点就是碰撞点：

现实中碰撞点十分直观自然，我们可以一眼看出。然而在计算机中计算碰撞点并不是一件简单的事情，因为计算机的世界是离散的，往往我们检测到碰撞时两个物体已经发生了相交，如下图所示：

在相交的情况下，情况便变得复杂了。两物体相交时产生了几个都可以作为碰撞点的“候选点（即图中的黄点）”，因此我们要从这些点中筛选出真正的碰撞点。那么我们把所有黄点都作为碰撞点行不行呢？当然是不行的，因为在现实中（2d），两个凸多边形发生碰撞不可能会产生多于 2 个的碰撞点（不信你自己在脑中模拟一下），因此我们的碰撞点最少会有一个，最多只有两个。

最近内部顶点法

碰撞点求解，（据我所知）主流方法有两种，今天我们要介绍的是比较简单好理解的一种，这种方法没有名字（可能有，但我不知道），因此我给它取了个名字叫 closest-internal-vertices-method（最近内部顶点法）。该方法的核心思想十分简单，就是求两个物体彼此间距离最近的顶点。怎么评估顶点与对象的相近程度呢？我们可以用向量投影，将顶点投影到碰撞法线上，投影值越大表示距离越近。

假设有两碰撞对象为 A，B ，碰撞法线为 n，求解 A，B 间的碰撞点，该算法主要分为 3 步：

1. 找出 A 中在 n 上投影值最大的顶点 a ，检查顶点 a ，若 a 在另一对象内部，则将 a 加入到碰撞点
2. 找出与 a 相邻的投影第二大的顶点 b ，若 b 在另一对象内部，则将 b 加入到碰撞点
3. 若此时碰撞点数量 < 2，取反法线，对 B 重复 1，2 步

我们用上图的来举个例子：

其中 A 顶点分别为 1，2，3，4，B 顶点为 5，6，7，8，法线为（0，1）。

首先，我们将 A 的所有顶点投影到 n 上，计算其投影最大的顶点。这里我们可以很容易地看出，顶点 3 在 n 上投影最大。同时，顶点 3 在 B 内部，因此我们可以确定顶点 3 是一个碰撞点。

之后，我们要检测顶点 3 的相邻投影第二大的顶点，即顶点 2 和顶点 4 ，然而顶点 2 和顶点 4 不在 B 的内部，因此可以排除。

此时碰撞点数量为 1 < 2，因此我们对 B 进行同样操作。将 B 的所有顶点投影到 -n 上，现在顶点 5 和顶点 6 在 -n 上投影皆为最大，我们任取一个即可（因为之后都会检测相邻顶点）。检测顶点 5 ，发现不在 A 内部，排除。

只检查顶点 5 的相邻顶点 6，发现不在 A 内部，故排除。

这里虽然顶点 7 是顶点 5 的相邻顶点，但我们可以不用检查 ，因为顶点 7 在 -n 的投影显然比顶点 6 要小。

因此该碰撞的碰撞点只有一个，就是顶点 3 。这和现实情况相吻合，说明了算法的正确性。

同理，我们可以举上图的另一个例子，得到其碰撞点如下：

此时碰撞点有两个，为顶点 2，4。

当然有不少情况中，所有碰撞点都在同一物体上：

最近内部顶点算法的缺陷

该方法不但直观，易于理解，但是该算法有一个比较耗时的步骤就是要判断顶点在对象内。除此之外，该算法在处理某些边界条件下，会显得不够准确。

考虑以下情况：

该情况下发生的碰撞两个对象并没有相互包含的顶点，算法会得出碰撞点数量为 0 。这显然是不合理的，当然这种情况有点极端，通常出现在高速运动物体的碰撞中，如果在没有 CCD（连续碰撞检测）下使用最近内部顶点算法处理这种情况的话，就会出现错误。

另外，最近内部顶点算法不能单独计算出每一个碰撞点的穿透深度，因此不能对穿透深度做出修正。如有以下碰撞：

最近内部顶点算法可计算出两碰撞点，然而两碰撞点实际上有着不同的穿透深度：

d1，d2 分别为两碰撞点的真实穿透深度。在 SAT 计算出的整体穿透深度只有 d1，因此如果忽略碰撞点间穿透深度的差异，对所有碰撞点在求解器中应用 d1，将会获得失真的碰撞模拟。

当然在绝大部分情况下，最近内部顶点算法计算碰撞点已经够用了。当时当追求更好性能和更好精度时，我们应该寻求更好的碰撞点求解算法。