图形学笔记（二十）粒子、刚体、流体的模拟—— 欧拉方法、Errors 和 Instability、中点法、自适应步长、隐式欧拉方法、Runge-Kutta方法、刚体与流体模拟（质点法、网格法、MPM）

大家好，欢迎来到IT知识分享网。

1 Single Particle Simulation 单个粒子模拟

1.1 单个粒子的运动

首先研究一个粒子的运动然后泛化到大多数粒子。

1.2 Euler’s Method 欧拉方法

可以使用欧拉方法对给定初始位置和速度场的点求解经过时间t后所处的位置。

特点 欧拉方法是一种简单的迭代方法，经常被使用、不准确、大多数都不稳定。
$$\begin{gathered} x^{t+\Delta t}=x^t+\Delta t{\dot{x}}^t \\ {\dot{x}}^{t+\Delta t}={\dot{x}}^t+\Delta t{\ddot{x}}^t \end{gathered}$$

1.2.1 欧拉方法的errors（误差）

使用数值计算的方法积分，errors会累计，最后的Euler积分结果会很差。

如下所示，但是$\Delta t$越大，误差越大。

1.2.2 欧拉方法的instability（不稳定性）

1. 误差随着时间步长 $\Delta t$ 的增加而增加。
2. 不稳定性是一个普遍且严重的问题，它能造成模拟diverge。

1.2.3 Errors 和 Instability

通过数值积分求解会导致两个问题：Errors和Instability。

每一步的errors会累计，随着模拟的进行，accuracy会下降，但是可以增大步长来环节这个问题，所以误差errors在图形应用中不是关键问题。

instability会导致diverge（不管怎么模拟都可能和正确的结果相差较远），缺乏稳定性是仿真中的基本问题，不容忽视

1.3 克服不稳定性的方法

1.3.1 Midpoint Method 中点法

1. 使用欧拉方法计算，点到达A( a )。
2. 使用欧拉方法计算上一步起始点与A点的导数( b )。
3. 使用中点的导数来重新更新位置( c )。

上面的过程对应下面的式子如下

$$\begin{gathered} x_{mid}=x(t)+\Delta t/2\cdot v(x(t),t) \\ {x}_{t+\Delta t}=x(t)+\Delta t\cdot v(x_{mid},t) \end{gathered}$$

1.3.2 Adaptive Step Size 自适应步长法

方法

1. 使用步长为T计算一个欧拉步骤来获得$x_T$。
2. 计算两个欧拉步骤，步长为T/2，获得$x_{T/2}$。
3. 计算error $||x_T-x_{T/2}||$。
4. If(error > threshold)减少步长并重复上面的步骤。

Adaptive是基于error估计选择步长的方法，非常实用，但可能得到的步长会很小。

1.3.3 Implicit Eurler Method 隐式欧拉方法

也被称作后向方法，使用下一时间的导数来计算当前的步骤。

$$\begin{gathered} x^{t+\Delta t}=x^t+\Delta t{\dot{x}}^{t+\Delta t} \\ {\dot{x}}^{t+\Delta t}={\dot{x}}^t+\Delta t{\ddot{x}}^{t+\Delta t} \end{gathered}$$

求解非线性的$x^{t+\Delta t}、{\dot{x}}^{t+\Delta t}$较为困难，可以认为在这个时刻位置知道且已知下一个时刻的加速度，使用求根公式来求解。也可以使用优化方法来解出来。

定义与量化”stability”的方法

• 使用局部截断误差（每个$\Delta$的误差）/ 总截断累积误差（整体累加后的误差）来研究稳定性。
• 研究数的大小无意义，有意义的事研究它们的阶。
• 隐式欧拉方法的阶数为1，意味着局部截断误差为$O(h^2)$且全局阶段误差为$O(h)$（h就是步长，定义为$\Delta t$）。

O(h)的理解:如果将 h 减半，预期误差也会减半。

1.3.4 Runge-Kutta Families

Runge-Kutta方法是一系列用于求解 ODE 的高级方法。

特点

• 擅长处理非线性问题。
• 它的四阶版是使用最广泛的，又名 RK4。

如下所示，h就是步长，这个方法相当于推广的中点法。

1.3.5 Position-Based / Verlet Integration

这是一种不基于物理的方法，通过调整物体的位置使物体满足某种性质。

主要思想

• 在修改欧拉前步（forward-step）之后，约束粒子的位置以防止divergent、不稳定的现象。
• 使用约束位置计算速度。
• 这两种思想都会耗散能量，使其具有稳定性。

特点 快速又简单，不是基于物理模拟的，不满足能量守恒。

2 Rigid Body Simulation 刚体模拟

刚体模拟与模拟单个粒子相似，只需额外考虑一些属性，如下所示。

3 Fluid Simulation 流体模拟

3.1 简单的基于位置的流体模拟方法

关键思想

1. 认为水是由刚体小球组成的。
2. 认为水是不可压缩的。
3. 只要某处的密度海绵，就需要通过改变粒子的位置来“纠正”。
4. 需要知道任何位置的密度的梯度。
5. 使用梯度下降法来进行更新。

3.2 Lagrangian vs Eulerian 质点法与网格法

3.3 Material Point Method（MPM）

MPM是一种混合的(Hybrid)，结合Eulerian和Lagrangian的方法。

• Lagrangian：认为粒子带有材质属性。
• Eulerian：使用网格来做数值积分。
• lnteraction：粒子将属性传递给网格，网格执行更新，然后插值回粒子。