动画

动画（Animation）是一门「让物体变活」的技术。可以理解为模型在不同的时间具有不同的几何形状。根据人眼的视觉暂留效应，动画只需要在一定时间内连续播放多张图片就有物体在连续运动的效果。例如对于视觉暂留只需要 24 fps 就可以达到动画效果，视频的帧率为 24 fps，而虚拟现实需要达到 90 fps 才不会产生眩晕感。

关键帧动画

关键帧动画（Keyframe Animation）包含两个部分，一部分是关键帧（Keyframe），是动画中比较重要的部分。两个关键帧之间是过渡帧（Tweens）。关键帧动画的问题的重要问题就是插值问题。

插值方法有很多，例如线性插值，样条插值等方法。我们希望能有更加自然的插值方式，因此会更多地使用样条插值的方法。

Physical Simulation

牛顿第二定律： $$F=ma$$ 所谓 Physical simulation 就是通过模拟出不同的物理公式来仿真出不同的物理效果。

Mass Spring System

质点弹簧系统中最基本的单元是一根弹簧以及左右连接的两个质点。

假设弹簧没有长度，根据胡克定律可以得到： $${\mathit{f}}_{a\to b}=k_s(\mathit{b}-\mathit{a})$$ 显然有： $${\mathit{f}}_{a\to b}=-{\mathit{f}}_{b\to a}$$ 但实际上弹簧在不受力时也有一定的长度，因此胡克定律应该改写为： $${\mathit{f}}_{a\to b}=k_s\frac{\mathit{b}-\mathit{a}}{\Vert \mathit{b}-\mathit{a}\Vert }(\Vert \mathit{b}-\mathit{a}\Vert -l)$$ 但这种系统会一种震动下去，对于实际的 mass spring system 来说会受到阻力，能量会有衰减。

在 mass spring system 中一个质点的阻力为：

$$\mathit{f}=-k_d\dot{\mathit{b}}$$ 其中 $k_d$ 为 damping coefficient.

这样的描述带来的问题是会让所有的质点运动停下。如果出现一个弹簧的两个端点同时进行匀速直线运动，这个时候外部摩擦力就会让整个运动停下，但是实际上弹簧并没有发生震动，因此我们需要引入内部摩擦力： $${\mathit{f}}_{\mathit{b}}=-k_d\frac{\mathit{b}\mathbf{-}\mathit{a}}{\Vert \mathit{b}-\mathit{a}\Vert }(\dot{\mathit{b}}-\dot{\mathit{a}})\cdot \frac{\mathit{b}-\mathit{a}}{\Vert \mathit{b}-\mathit{a}\Vert }$$ 在这个式子中，我们考虑两个质点间的相对速度（这样可以避免相对运动的问题）。同时，只有在两个质点连线方向上的速度投影才可以引起弹簧长度改变。例如 $a$ 不动，$b$ 相对于 $a$ 做圆周运动，这个时候并没有使弹簧长度发生改变，这个速度不引起弹簧内部的能量损耗。

Structures from Springs

通过这些弹簧进行连接，我们可以得到各种材料。例如，可以使用质点弹簧系统对布料进行模拟：

对于图(a)，不能很好的抵抗切变，同时布料很难被折叠，但是这个结构可以进行折叠（Out-of-planeBending）。因此这样的设计是不合理的。在图(b) 中加入斜的对角线来抵抗切变，但是依然不能解决折叠的问题，并且整个布是各向异性的。在图(c) 中再加入一条对角线，这样就可以抵抗对角线上折叠的力，并且整个布料是各向同性的。但是在水平和垂直方向依然可以折叠。在图(d) 中，都在间隔一个点两个点之间加入一条线，这样就可以抵抗水平和垂直的折叠。在这里，蓝线是比较强的抵抗，但是红线的抵抗比较弱。

Particle Systems

现实生活中很多物体都是由大量的粒子组成的，我们称之为粒子系统。对于粒子系统，可能需要大量的粒子来模拟复杂的现象，并且需要一些加速结构加快粒子作用力的计算。粒子系统的计算分为以下几个步骤：

1. 产生新的粒子（如果有需要）；
2. 计算每一个粒子受到的作用力；
3. 更新每一个粒子的位置和速度；
4. 移除死亡的粒子（如果有需要）；
5. 渲染粒子。

在粒子系统中可以考虑许多力作用，引力和斥力，包括万有引力，电磁力，弹力，推进力。阻尼力包括摩擦力，空气阻力，以及黏力。同时还要考虑碰撞产生的力。

Kinematics

动力学包括正向动力学以及逆向动力学。如下图所示是一个人体骨骼的抽象。在正向动力学中，我们会知道所有关节的旋转角度，推断出尖端所在的位置。在逆向动力学中，已知尖端的位置，需要推断出关节的旋转方式（角度）。

Forward Kinematics

在正向动力学中，计算尖端位置主要通过三角函数进行计算。以下图为例，是一个简单的骨骼系统计算尖端位置的方法。

正向动力学能够方便的控制骨骼方向，并且计算方便，但是得到的物理模拟不一定连续，并且对于艺术家来说，调整工作非常浪费时间。

Inverse Kinematics

反向动力学中，在得到尖端位置后我们需要计算各个关节的旋转角度。下图提供了一个简单关节的计算方式。

在反向动力学中主要面对以下几个问题：

• 解不一定唯一：

• 关节连接越多，计算越麻烦。
• 在某些地方可能不存在解：

目前有很多方法解决这些问题，例如对于 N 连接的 IK 问题：

• 选择初始设定；
• 定义错误度量方式；
• 将错误的梯度作为设定之一；
• 使用梯度下降计算梯度。

单粒子模拟

我们假设粒子在一个力场之中，力场中的任何一个点都定义了这个点处粒子收到的力的大小和方向，目的是在知道粒子的起点后，我们需要计算出力在场中的运动轨迹。

在这样的系统中，我们需要解的是 $x$ 关于 $t$ 的常微分方程，也就是：

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

欧拉方法

欧拉方法（Euler‘s Method）非常的简单且常用，但是往往不稳定，欧拉方法的公式为： $$\begin{array}{rl}{\mathit{x}}^{t+\mathrm{\Delta }t}& ={\mathit{x}}^t+\mathrm{\Delta }t{\dot{\mathit{x}}}^t\\ {\dot{\mathit{x}}}^{t+\mathrm{\Delta }t}& ={\dot{\mathit{x}}}^t+\mathrm{\Delta }t{\ddot{\mathit{x}}}^t\end{array}$$ 欧拉方法错误的多少和步长的选择有关，步长越小，模拟出的路径误差越小。

另一方面，即使是减小步长，在某些力场中依然会有不稳定的情况产生。例如在匀速圆周运动的力场中，粒子可以做匀速圆周运动。但是使用欧拉方法后，模拟出的路径会一步一步远离力场中心。这被称作不稳定性。

错误和不稳定性是衡量路径模拟的指标。错误会在每一步积累，降低路径模拟的准确性。而不稳定性也是影响路径模拟效果的因素之一。目前也有一些方法来解决模拟中的不稳定性。

中点法

中点法的步骤如下：

1. 使用欧拉方法计算下一步粒子的位置；
2. 计算中点下一步移动的梯度；
3. 使用中点的梯度更新该点的位置。

写出数学公式为： $$\begin{array}{rl}{\mathit{x}}^{t+\mathrm{\Delta }t}& ={\mathit{x}}^t+\frac{\mathrm{\Delta }t}{2}({\dot{\mathit{x}}}^t+{\dot{\mathit{x}}}^{t+\mathrm{\Delta }t})\\ {\dot{\mathit{x}}}^{t+\mathrm{\Delta }t}& ={\dot{\mathit{x}}}^t+\mathrm{\Delta }t{\ddot{\mathit{x}}}^t\\ {\mathit{x}}^{t+\mathrm{\Delta }t}& ={\mathit{x}}^t+\mathrm{\Delta }t{\dot{\mathit{x}}}^t+\frac{(\mathrm{\Delta }t{)}^2}{2}{\ddot{\mathit{x}}}^t\end{array}$$

自适应步长

自适应步长的方法可以通过误差分析计算所需要步长的大小，具体的步骤如下：

1. 计算步长为 T 时欧拉方法移动的位置 $x_T$；
   
2. 计算步长为 $\frac{T}{2}$ 时欧拉方法移动的位置 $x_{\frac{T}{2}}$;
3. 计算误差 $\Vert x_T-x_{\frac{T}{2}}\Vert$；
4. 如果误差大于阈值，减小步长并重复以上过程。

隐式欧拉方法

在隐式欧拉方法中，我们需要计算出 ${\mathit{x}}^{t+\mathrm{\Delta }t}$ 以及 ${\dot{\mathit{x}}}^{t+\mathrm{\Delta }t}$ 的结果。可以使用牛顿法求解，但是求解相对不方便。但是具有更好地稳定性。 $$\begin{array}{rl}& {\mathit{x}}^{t+\mathrm{\Delta }t}={\mathit{x}}^t+\mathrm{\Delta }t{\dot{\mathit{x}}}^{t+\mathrm{\Delta }t}\\ & {\dot{\mathit{x}}}^{t+\mathrm{\Delta }t}={\dot{\mathit{x}}}^t+\mathrm{\Delta }t{\ddot{\mathit{x}}}^{t+\mathrm{\Delta }t}\end{array}$$ 这里我们可以对稳定性进行定义。我们使用每一步的误差以及整体累计的误差表示方法的稳定性。误差本身没有太多意义，但是误差的阶可以衡量误差。隐式欧拉方法是 1 阶的，因此每一步的误差为 $\text{Omicron}\left(h^2\right)$，整体累计的误差为 $\text{Omicron}\left(h\right)$. 其中 h 可以看作步长 $\mathrm{\Delta }t$.

Runge-Kutta 方法

RK 方法适合于非线性 ODE 的求解，其中 4 阶的方法（RK4）最为常用：

初始条件： $$\frac{\mathrm{d}y}{\mathrm{d}t}=f(t,y),y\left(t_0\right)=y_0$$ 求解得： $$\begin{array}{rl}& y_{n+1}=y_n+\frac{1}{6}h(k_1+2k_2+2k_3+k_4)\\ & t_{n+1}=t_n+h\end{array}$$ 其中： $$\begin{array}{rl}& k_1=f(t_n,y_n)\\ & k_2=f(t_n+\frac{h}{2},y_n+h\frac{k_1}{2})\\ & k_3=f(t_n+\frac{h}{2},y_n+h\frac{k_2}{2})\\ & k_4=f(t_n+h,y_n+h{k}_3)\end{array}$$

Position-Based 方法

不是基于物理的方法，而是不断的调整物体的位置保证物体运动能够满足最后的要求。这种方法速度快并且简单，但是这种方法无法保证能量守恒。

刚体模拟（Rigid Body Simulation）

刚体不会发生形变，因此刚体中的点会按照同一种方式进行运动。刚体的运动就可以看作一个粒子的模拟。但是在刚体中会对更多的物理量进行模拟： $$\frac{d}{dt}\left(\begin{array}{c}\mathrm{X}\\ \theta \\ \dot{\mathrm{X}}\\ \omega \end{array}\right)=\left(\begin{array}{c}\dot{\mathrm{X}}\\ \omega \\ \mathrm{F}/M\\ \mathrm{\Gamma }/I\end{array}\right)$$ 这里：$X$ 是位置，$\theta$ 是角度，$\dot{X}$ 是速度，$\omega$ 是角速度，$F$ 是力，$M$ 是质量，$\mathrm{\Gamma }$ 是扭矩，$I$ 是转动惯量。

流体模拟（Fluid Simulation）

在流体模拟中，我们有以下基本思想：

• 假设液体由很小的刚体球组成；
• 假设液体不能被压缩（密度是不变的）；
• 一旦某些地方的密度发生改变，就需要通过更改小球的位置保证密度一致；
• 需要知道每一个点的密度的梯度；
• 调整的过程就是梯度下降的过程。

在流体模拟中包含了两种方法，分别是质点法（Lagrangian Approach）和网格法（Eulerian Ap-proach）。质点法就是精确模拟每一个物体随着时间如何进行变换。网格法将整个空间分成多个网格，只考虑每一个网格在每一个时刻的变化。

目前还产生了新的方法，被称为 Hybrid，是结合质点法以及网格法。其主要思想是对于每一个粒子都有其属性，我们让粒子在网格中进行变换，但是在变换后需要将属性重新写回到粒子上。这种方法叫做物质点方法（Material Point Method，MPM）。