GAMES102 Lecture 22 Animation (cont.)

这里回顾GAMES101 Lecture 22，动画与模拟（求解常微分方程，刚体与流体）。

课程主页：

• https://sites.cs.ucsb.edu/~lingqi/teaching/games101.html

课程作业：

• http://games-cn.org/forums/topic/allhw/

课程视频：

• https://www.bilibili.com/video/BV1X7411F744?spm_id_from=333.337.search-card.all.click

本讲内容

• 单粒子模拟；
  • 显式欧拉法；
  • 不稳定和改进；
• 刚体模拟；
• 流体模拟；

单粒子模拟

• 首先研究单个粒子的运动，然后推广到大量粒子；
• 假设粒子的运动由作为位置和时间函数的速度矢量场确定：$v(x, t)$；

图示：

现在的问题是计算该例子的轨迹。

ODE

轨迹可以由常微分方程决定：

$$\frac{d x}{d t}=\dot{x}=v(x, t)$$

我们可以通过使用前向数值积分求解 ODE（假设初始粒子位置为$x_0$），一个经典的方法是欧拉法。

欧拉法

欧拉法的特点如下：

• 简单迭代；
• 常用；
• 很不准确；
• 常常变得不稳定；

核心计算公式如下：

$$\begin{aligned} \boldsymbol{x}^{t+\Delta t} &=\boldsymbol{x}^t+\Delta t \dot{\boldsymbol{x}}^t \\ \dot{\boldsymbol{x}}^{t+\Delta t} &=\dot{\boldsymbol{x}}^t+\Delta t \ddot{\boldsymbol{x}}^t \end{aligned}$$

其中$\Delta t$为步长。

欧拉法的问题

欧拉法有两个问题：

• 不准确；
  • 随着时间步长$\Delta t$的增加而增加；
• 不稳定；
  • 是一个常见的、严重的问题，会导致模拟发散；

欧拉法的误差

欧拉法的问题是，每一步都有误差，所以误差会累积：

欧拉法的不稳定性

欧拉法的另一个问题是不稳定，例如使用欧拉法模拟下图的螺旋线，无论步长多大，最后的轨迹都不会是螺旋线：

小结

通过有限差分的数值积分求解会导致两个问题：

• 误差：
  • 每个时间步的误差都会累积；
  • 随着模拟的进行，精度会降低；
  • 但精度在图形应用程序中可能并不重要；
• 不稳定性：
  • 错误可能会复合，导致模拟发散，即使底层系统没有发散；
  • 缺乏稳定性是模拟中的一个基本问题，不容忽视；

对抗不稳定性

对抗不稳定的一些方法

• 中点法/修正欧拉
  • 起点和终点的平均速度；
• 自适应步长
  • 递归地比较步长和半步长，直到误差可以接受；
• 隐式方法
  • 使用下一个时间步的速度；
• 基于位置/Verlet 集成
  • 在时间步后限制粒子的位置和速度；

中点法

• 计算欧拉步骤；
• 在欧拉步骤的中点计算导数；
• 使用中点导数更新位置；

计算公式：

$$\begin{aligned} x_{\text {mid }} &=x(t)+\Delta t / 2 \cdot v(x(t), t) \\ x(t+\Delta t) &=x(t)+\Delta t \cdot v\left(x_{\text {mid }}, t\right) \end{aligned}$$

中点法之所以效果好，是因为使用了二阶项：

$$\begin{aligned} \boldsymbol{x}^{t+\Delta t} &=\boldsymbol{x}^t+\frac{\Delta t}{2}\left(\dot{\boldsymbol{x}}^t+\dot{\boldsymbol{x}}^{t+\Delta t}\right) \\ \dot{\boldsymbol{x}}^{t+\Delta t} &=\dot{\boldsymbol{x}}^t+\Delta t \ddot{\boldsymbol{x}}^t \\ \boldsymbol{x}^{t+\Delta t} &=\boldsymbol{x}^t+\Delta t \dot{\boldsymbol{x}}^t+\frac{(\Delta t)^2}{2} \ddot{\boldsymbol{x}}^t \end{aligned}$$

自适应步长

自适应步长基于误差估计选择步长的技术
，非常实用的技术，可能需要非常小的步长，算法如下：

• 重复直到错误低于阈值：
  • 计算大小为$T$的欧拉步长$x_T$；
  • 计算大小为$T/2$的欧拉步长$x_{T/2}$；
  • 计算误差$| x_T-x_{T/2} | $；
  • 如果（误差 > 阈值）减小步长并重复该步骤；

隐式欧拉法

• 非正式地称为后向方法；
• 在当前步使用后来的导数；

计算方法：

$$\begin{aligned} \boldsymbol{x}^{t+\Delta t} &=\boldsymbol{x}^t+\Delta t \dot{\boldsymbol{x}}^{t+\Delta t} \\ \dot{\boldsymbol{x}}^{t+\Delta t} &=\dot{\boldsymbol{x}}^t+\Delta t \ddot{\boldsymbol{x}}^{t+\Delta t} \end{aligned}$$

隐式方法需要：

• 求解$\boldsymbol{x}^{t+\Delta t} $和$\boldsymbol{x}^{t } $的非线方程；
• 使用求根算法，例如牛顿法；
• 但可以提供更好的稳定性；

如何确定/量化“稳定性”？

• 使用局部误差（每一步）/总累积误差（整体）；
• 绝对值无关紧要，但关于步长的阶数很重要；
• 隐式欧拉的阶数为1，这意味着
  • 局部误差为$O(h^2)$；
  • 全局误差为$O(h)$；
  • 其中$h$是步长，即$\Delta t$；
• $O(h)$的理解
  • 如果我们将$h$减半，我们可以预期误差也会减半；

龙格库塔法

龙格库塔法是用于求解ODE的一系列高级方法：

• 特别擅长处理非线性；
• 它的四阶版本使用最广泛，又名RK4；

公式：

初始条件：

$$\frac{d y}{d t}=f(t, y), \quad y\left(t_0\right)=y_0$$

RK4解：

$$\begin{aligned} y_{n+1} &=y_n+\frac{1}{6} h\left(k_1+2 k_2+2 k_3+k_4\right) \\ t_{n+1} &=t_n+h \end{aligned}$$

其中：

$$\begin{aligned} k_1 &=f\left(t_n, y_n\right) \\ k_2 &=f\left(t_n+\frac{h}{2}, y_n+h \frac{k_1}{2}\right) \\ k_3 &=f\left(t_n+\frac{h}{2}, y_n+h \frac{k_2}{2}\right) \\ k_4 &=f\left(t_n+h, y_n+h k_3\right) \end{aligned}$$

基于位置

思想：

• 在修改欧拉前步后，约束粒子的位置以防止发散、不稳定的行为；
• 使用约束位置来计算速度；
• 这两种想法都会耗散能量，使得结果稳定；

优点缺点：

• 快速简单；
• 不基于物理，耗散能量（有一定错误）；

刚体模拟

简单案例：

• 类似于模拟粒子；
• 只需考虑更多属性；

公式：

$$\frac{d}{d t}\left(\begin{array}{c} \mathrm{X} \\ \theta \\ \dot{\mathrm{X}} \\ \omega \end{array}\right)=\left(\begin{array}{c} \dot{\mathrm{X}} \\ \omega \\ \mathrm{F} / \mathrm{M} \\ \Gamma / I \end{array}\right)$$

其中：

• $\mathrm{X}$：位置；
• $\theta$：旋转角度；
• $\omega$：角速度；
• $\mathrm F$：力；
• $\Gamma$：力矩；
• $ I$：惯性动量；

流体模拟（基于位置的方法）

• 假设水是由小的刚体球体组成；
• 假设水不能被压缩（即恒定密度）
  ；
• 因此，只要密度在某处发生变化，就应该通过改变粒子的位置来“校正”；
• 需要知道任何地方密度关于位置的梯度；
• 然后利用梯度下降更新；

欧拉与拉格朗日

• 模拟大量物体的两种不同观点；
  • 拉格朗日：质点法；
    • 摄影师全程跟踪同一只鸟；
  • 欧拉法：网格法；
    • 摄影师是静止的，只能拍下所有经过某一帧的鸟；

拉格朗日视角：

欧拉视角：

另外也可以将这两个视角结合，具体见课件。