GAMES103笔记 Lecture4 刚体碰撞（Rigid Body Contacts）

质点碰撞检测和响应

在考虑刚体碰撞之前，我们先考虑更简单的问题：如何判断一个质点与其他物体的碰撞，以及在检测到碰撞后应该如何处理这次碰撞。

用SDF判断是否发生碰撞

第二次课上我们已经接触过符号距离函数（SDF, signed distance function）。符号距离函数表示点 $x$ 到目标几何体的带符号的最短距离，可以发现符号距离函数的定义就非常适合做碰撞检测， $\Phi(x)<0$ 表示点在几何体内（发生碰撞）， $\Phi(x)>0$ 表示点在几何体外（没有碰撞）。

对于过点 $p$ 且法向量为 $n$ 的平面，空间中任意一点 $x$ 到平面的SDF为： $\Phi(x)=(x-p) \cdot N$

$\Phi(x)>0$ 表示点在平面上面（与法向量同侧），$\Phi(x)<0$ 表示点在平面下面（在法向量的另一面）。

除了平面，在游戏中用于处理碰撞的简单几何体还有球、圆柱体、长方体、胶囊体等。

简单几何体之间可以用布尔运算组合出更复杂的形状。

布尔求交的情况下，如果每个SDF都小于0则说明点在组合的几何体内，并且组合几何体的SDF等于几个SDF中最大的那个（绝对值最小的）。如果点在组合几何体外则无法直接由子物体的SDF得到组合几何体的SDF。

布尔求并的情况下，只要有一个SDF都小于0就说明点在组合的几何体内，此时同样无法直接由子物体的SDF得到组合几何体的SDF，图中描黄的部分是原来圆的边界，但在组合后在几何体的内部，导致点在临近黄色边界时取到的最小SDF出现偏差。不过在点靠近组合后的外边界（上图中描绿的部分）的时候可以取最小的那个SDF来当做组合几何体的SDF。如果点在组合几何体外，则可以得到准确的SDF。

关于碰撞检测还有一些更普适的方法，这次的课上只讲了SDF，后续如果讲了其他方法我会把链接贴在这里。

用Penalty Method做碰撞响应

判断碰撞发生之后，需要做出响应，改变物体的运动状态。

在物理世界中，碰撞时物体会受到弹力的作用，因此一个很直接的想法就是用力来改变物体的运动。

Quadratic Penalty Method

检测到质点进入物体，即 $\Phi(x)<0$ 时，给物体施加向外的力 $f=-k\Phi(x)\mathbf{N}$ 。

我们希望质点以最快的方向离开物体，所以 $f$ 的方向与 $\nabla \Phi(x)$ 相同。对于平面来说就是法向量的方向。

力的大小和基于胡克定律的弹簧模型是一样的，相当于在物体越过边界后拥有了与距离的绝对值的二次方成正比的弹性势能，所以称该方法为Quadratic Penalty方法。

Quadratic Penalty方法显然存在一个问题，物体进去之后才施加向外的力被弹出来，容易出现穿模现象。

Quadratic Penalty Method With a Buffer

直接有效的解决办法是加个缓冲，只要靠近物体就开始施加向外的力。

加缓冲后穿模的问题得到缓解，但在实践中仍然存在有问题。 $k$ 太小会导致物体速度改变太慢，还是会出现进去以后才出来的情况，而 $k$ 太大的话将导致物体出来速度太大（overshooting）。

可以想到，$k$ 的大小不好调节的本质原因就因为是这是一个类似弹簧的模型，力的大小始终和距离的绝对值成正比，而现实世界显然不是这样的。

Log-Barrier Penalty Method

Log-Barrier Penalty 方法更接近现实世界的物理规律。

将 SDF 放在分母上，再用一个参数 $\rho$ 来控制力的大小。在距离很小的情况下，受到的力将会增长到非常大的数值。

如果将点在无穷远处的能量看做 $0$ ，将力函数对位移求积分算能量会发现 $E=-\int fd[\Phi (x)]=-\int \rho \frac{1}{\Phi(x)} \mathbf{N} d[\Phi (x)]=-\rho log \Phi(x) \mathbf{N}$ ，与 $log \Phi(x)$ 成正比，所以称此方法为 Log-Barrier Penalty 方法。

Log-Barrier Penalty 方法假设了 $\Phi(x)$ 永远都不会小于0，虽然很符合物理规律，然而在计算机中我们只能一个时间步一个时间步地计算，如果在一个时间步内物体就穿过了表面，力的方向就反过来了。此外，Log-Barrier Penalty 方法仍然存在overshooting的问题。所以 Log-Barrier Penalty 方法要求时间步步长必须足够小。

小结

Penalty方法的优势是容易实现，碰撞后用力改变物体运动的方式符合真实的物理规律，缺点是需要调节到合适的时间步步长来避免overshooting，而且难以模拟斜着撞过来的物体的水平速度因摩擦力衰减。

用Impulse Method做碰撞响应

除了从底层模拟物理规律，还可以从表象上来模拟物体的运动。

Penalty 方法施加的力需要经过一小段时间才能起作用，Impulse（冲量）方法在检测到碰撞的瞬间就改变物体的位置和动量（速度）。

检测到进入物体，即 $\Phi(x) < 0$ 后，首先立即将物体沿着最近的f方向移动到物体表面，更新 $x^{new}=x+|\Phi(x)|\mathbf{N}=x-\Phi(x)\nabla\Phi(x)$

然后继续检查速度是否指向物体内部，如果 $\mathbf{v} \cdot \mathbf{N} \geq 0$ ，说明在之前的时间步中已经修改过质点的速度，它已经要出去了，不用做任何处理。

如果 $\mathbf{v} \cdot \mathbf{N}<0$ ，将速度正交分解， $\{\begin{aligned}&\mathbf{v_N}=(\mathbf{v}\cdot\mathbf{N})\mathbf{N}\\&\mathbf{v_T}=\mathbf{v}-\mathbf{v_N}\end{aligned}$

然后分别更新 $\{\begin{aligned}&\mathbf{v_N}=-\mu_N\mathbf{v_N} \\&\mathbf{v_T}=a\mathbf{v_T}\end{aligned}$

其中 $a,\mu_N \in [0,1]$ ，因为我们希望质点离开碰撞的物体，竖直方向上的速度反向要反过来，但因为能量守恒定律，出去的速度的绝对值不能超过进入时的速度。

由于摩擦力的存在，水平方向上的速度需要衰减。

a的计算

根据摩擦力定律（Amontons-Coulomb Friction Laws，参考https://en.wikipedia.org/wiki/Friction）， $F_f<=\mu_T F_N$ ，$\mu_T$ 为摩擦力系数，所以

$\left|\mathbf{v}{\mathbf{T}}^{\text {new }}-\mathbf{v}{\mathbf{T}}\right| \leq \mu_{\mathbf{T}}\left|\mathbf{v}{\mathbf{N}}^{\text {new }}-\mathbf{v}{\mathbf{N}}\right| $

整理得

$(1-a)\left\|\mathbf{v}_{\mathbf{T}}\right\| \leq \mu_{\mathbf{T}}\left(1+\mu_{\mathbf{N}}\right)\left\|\mathbf{v}_{\mathbf{N}}\right\|$

$a \leq 1-\frac{\mu_{\mathbf{T}}\left(1+\mu_{\mathbf{N}}\right)\left\|\mathbf{v}_{\mathbf{N}}\right\|}{\left\|\mathbf{v}_{\mathbf{T}}\right\|}$

模拟时上式可取等号。又由于 $a\geq0$ ，所以取 $a = \max \left(1-\frac{\mu_{\mathbf{T}}\left(1+\mu_{\mathbf{N}}\right)\left\|\mathbf{v}_{\mathbf{N}}\right\|}{\left\|\mathbf{v}_{\mathbf{T}}\right\|}, 0\right)$

摩擦力系数 $\mu_T$ 需要手动设定。

小结

Impulse方法的优点是能做到对摩擦力和反弹的精确控制，但对于非质点物体需要做一些额外的处理。

刚体用Impulse方法更多，衣服和弹性体用Penalty方法更多。

刚体碰撞检测和响应

刚体的碰撞比质点更复杂一些。

刚体的碰撞检测

可以暴力地解决碰撞检测的问题。遍历刚体表面上的每一个点看 SDF 是否小于0，即可判断是否发生碰撞。

用 Impulse 方法做刚体碰撞响应

将 Mesh 上每一个点的位置表示为质心位置加上一个向量 $\mathbf{x_i}=\mathbf{x}+R\mathbf{r_i}$

则点的速度等于质心速度加线速度 $\mathbf{v_i}=\mathbf{v}+\omega \times R\mathbf{r_i}$

有了 $\mathbf{v_i}$ 就可以直接用 Impulse 方法对碰撞点进行处理，得到碰撞点的新速度 $\mathbf{v}_i^{new}$ 。

但我们的最终目的是更新整个刚体的速度 $\mathbf{v}$ 和角速度 $\mathbf{\omega}$ 。

Impuse 方法没有通过计算力或冲量的方式改变速度，而是直接改变了碰撞点的速度。我们假设是因为一个冲量 $j$ 使 $\mathbf{v_i}$ 变成了$\mathbf{v}_i^{new}$ ，再反过来用 $\mathbf{v_i}$ 和$\mathbf{v}_i^{new}$ 推算 $j$ 应该是多少。

假设冲量 $j$ 作用在碰撞点上，它会同时改变刚体的速度和角速度，根据上一讲介绍的刚体动力学可以得到 $\mathbf{v}^{new}=\mathbf{v}+\frac{1}{M}\mathbf{j}$ （假设作用在碰撞点和作用在质心上对整个刚体速度改变的效果一样）和 $\mathbf{\omega}^{new}=\mathbf{\omega}+I^{-1}(R\mathbf{r_i}\times \mathbf{j})$

再把用冲量 $j$ 求出来的 $\mathbf{v}^{new}$ 和 $\mathbf{\omega}^{new}$ 代入到 点速度=刚体速度+线速度 的式子中。

上图中蓝色箭头的那一步把 $\mathbf{v}+\mathbf{\omega}\times R \mathbf{r}_i$ 合成了 $\mathbf{v}_i$ , 而最后一步只是交换了叉乘的顺序。

这个式子中有两个叉乘，不好整理，接下来将叉乘写成矩阵乘法的形式，对叉乘的第一个向量按照下图的规则改成矩阵。

代入进去，然后把 j 前面的部分整个当成一个矩阵K，最后可以得到：

这样，我们就成功从 Impulse 方法算出来的 $\mathbf{v_i}$ 和$\mathbf{v}_i^{new}$ 反推出冲量 $j$ 。

最后只需要将冲量 $j$ 应用打刚体上去即可。

用 Impulse 方法做刚体碰撞响应的整个流程如下图所示。

还有个几个小问题。

如果有多个点同时碰撞怎么办，为了减小计算量，只需要计算这些点的位置的平均值，把位置的平均值当做碰撞点做碰撞处理。

物体掉在地面上时在重力和弹力作用下会一直抖动（oscillation），解决办法是检测到物体即将进入静止状态时将反弹系数 $\mu_N$ 变小。

为什么 Impulse 方法只更新了速度没有更新位置？这是一个非线性问题，之后讲约束的时候回再回来讨论。

用Shape Matching做刚体碰撞响应

论文：Muller et al. 2005. Meshless Deformations Based on Shape Matching. TOG (SIGGRAPH).

Shape Matching 方法先把刚体的每个顶点都当做可以自由移动的顶点，对每个点做单独的碰撞处理。然后通过最小化 MSE（均方误差）的方法求出把它们聚拢回刚体的形状。

$y_i$ 是聚拢前的顶点位置， $c$ 是聚拢后的质心， $R$ 是聚拢后的旋转矩阵， $c+Rr_i$ 是聚拢后的顶点位置。

这里放宽要求让R可以为任意矩阵，记为A（推测这么做是为了方便让 MSE 取到极值）。

这里 MSE 的表达式比较简单，直接求导数等于 0 的点就是极值点。

$\mathbf{c}$ 的表达式比较简单，直觉上也能理解，聚拢前的中心和聚拢后的中心点相同。

这里求出来的A是任意矩形，但我们希望最后刚体能维持原来的形状，还需要做一个 Polar Decomposition 。

奇异值分解告诉我们任何一个矩形（线性变换）都可以被分解为一个旋转（正交矩阵 $V^T$ ）、一次坐标轴方向的缩放（对角矩阵 $D$ ）、再加一次旋转（正交矩阵 $U$ ）。修改一下这个表达式：

$A=UDV^T=(UV^T)(VDV^T)$

右边的 $VDV^T$ 可以看做一次沿任意方向的缩放（形变），而左边的 $UV^T$ 是一次对形变后的图形的旋转（注意矩阵乘法从右往左读）。

重新将该分解记为 $A=RS$ ， $R$ 对应旋转矩阵，$S$ 对应形变矩阵。

关于Polar Decomposition 的更多信息可参考 Franca, Leopoldo P. “An algorithm to compute the square root of a 3× 3 positive definite matrix.” Computers & Mathematics with Applications 18.5 (1989): 459-466.", 作业代码中已经给了实现。

刚才求出来的A是任意矩形，做完 Polar 分解后直接舍弃掉形变矩阵，保留旋转矩阵代入 $c+Rr_i$ 就能得到聚拢后的顶点位置。

Shape Matching 的整体流程

Shape Matching小结

优点：

1. 容易实现
2. 容易和点的模型结合在一起，包括衣服、软体、基于粒子的流体

缺点：

1. 存在其他约束的情况下，很难保证所有的约束都满足

Shape Matching 适合摩擦力约束不是很重要的情况，比如衣服和扣子的模拟。

总结

本次讲了刚体碰撞的检测和响应。先从质点碰撞的检测和响应开始，碰撞检测部分只讲了用 SDF 的方法，后续应该还有一次专门讲碰撞的课。碰撞响应部分讲了两种方法，模拟弹力的 Penalty 方法和直接修改速度的 Penalty 方法。然后讲了 Impulse 方法如何用于模拟刚体碰撞。由于 Impulse 只能修改碰撞点的速度，需要用修改后碰撞点的速度反推冲量$j$ ，最后再用刚体动力学的方法更新刚体的速度和角速度。除了 Impulse 方法，还讲了剑走偏锋的 Shape Matching 方法，先假设每个顶点都可以自由移动，对每个顶点单独处理，再用最小化均方误差的方法将它们聚拢回来。

最后放上我的作业一的效果演示

上传视频封面

好的标题可以获得更多的推荐及关注者

不好意思，传错了。Unity 内置的四元数是 (x, y, z, w)，为什么虚部在最后面啊喂！这个是之前在 Unity 中把四元数的实部和虚部填反了得到的结果，正确的结果应该是下面这个。

上传视频封面

Impulse 方法模拟刚体碰撞

上一篇：GAMES103笔记 Lecture3 刚体动力学（Rigid Body Dynamics）

下一篇：GAMES103笔记 Lecture5 基于物理的布料模拟（Physics-based Cloth Simulation）

GAMES103 系列笔记目录