游戏模拟——Position based dynamics

基本积分方法
Verlet 算位置
Verlet 算速度

PBD
基于位置的方法解碰撞
算法流程
求解器借用的思想
关于动量守恒
约束投影
简单约束举例

一些模拟方法（大多数刚性体模拟器）使用基于冲量的方法并直接操纵速度。
PBD是一种省略了速度层的直接作用于位置的控制方法，方法的主要优点是它的可控性、性能、数值稳定，在游戏开发领域应用很广，近年的UE chaos底层也采用了PBD方法。

Verlet积分

基本积分方法

积分方法的阶数一般是看泰勒展开中导数的最高项。n阶方法的误差是\(O(h^{n+1}\。
值得一提的是，explicit euler、semi-implicit euler都是一阶方法。
积分方法讨论的通常是给定一个函数S(t，然后我们没有办法得到S(t的解析式（假定这里是和时间有关的函数），此时我们通过一些方法来对S(t 做近似，达到一个我们给定一个时刻的数据，可以推算其他时刻数据的效果，这里一切的理论基础都是泰勒展开，然后进行各种化简。
这里用图来表示，小红色的矩形代表积分过程，左边是explicit euler，右边是semi-implicit euler。

Verlet 算位置

verlet积分是一种牛顿运动方程的积分方法，他的积分方法有着良好的数值稳定性，对比简单的欧拉方法没有显著的额外计算成本。

\[ x _{t+\Delta t} = x_t + v(t\Delta t + \frac{1}{2}a(t\Delta t^2 + \frac{1}{6}b(t\Delta t^3 + O(\Delta t^4 \]

\[ x _{t-\Delta t} = x_t - v(t\Delta t + \frac{1}{2}a(t\Delta t^2 - \frac{1}{6}b(t\Delta t^3 + O(\Delta t^4 \]

\[ x _{t+\Delta t} = 2 x_t - x _{t-\Delta t} + a(t\Delta t^2 + O(\Delta t^4 \]

我们可以将\(t+\Delta t\ 当成当前帧所在的时刻，那么t就是上一帧，\(t-\Delta t\就是上上一帧，我们只需要两个位置信息和上一帧的力信息，就可以得到当前帧的位置信息，并且这个位置信息是三阶精度的，误差四阶精度，wiki百科中提到，这个方法这里的误差是局部误差，并且公式中的加速度是根据精确解计算的，全局误差（即累积误差）与时间步长的平方（Δt^2）成正比。虽然局部离散化误差为 4 阶，但由于微分方程的2阶，全局误差为 2 阶，我们将它定义为2阶方法。

Verlet 算速度

接下来是求速度信息，
两者求差，消去二阶项得到

\[ x(t+\Delta t−x(t−\Delta t=2v(t\Delta t+ \frac{1}{3}b(t\Delta t^3 \]

\[ v(t = \frac {x(t+ \Delta t - x(t - \Delta t}{2\Delta t} + \frac{b(t\Delta t^3}{3\Delta t} \]

\[v(t = \frac {x(t+ \Delta t - x(t - \Delta t}{2\Delta t} + O(\Delta t^2 \]

这个算上一帧速度的方法是一阶精度二阶误差的。
在他的原始方法里推算当帧的速度用的中值定理+近似，导致速度一定是不准的，得出速度公式为

\[v(t+\Delta t = \frac {x(t+ \Delta t - x(t}{\Delta t} + O(\Delta t \]

\[ \frac {x(t+\Delta t−x(t}{\Delta t} =v(t+ \frac{1}{2}a(t\Delta t + \frac{1}{6}b(t\Delta t^2 \]

所以如果\(\frac{1}{2}a(t\Delta t + \frac{1}{6}b(t\Delta t^2\作为误差，误差就是\(O(\Delta t\的。

\[v(t+\Delta t = v(t + \frac {a(t+a(t+ \Delta t}{2} \Delta t \]

a的\(t+\Delta t\是一般来说是一个和位置有关的函数，先求了位置，接下来这里面都是已知量了。

PBD

基于力的方法解碰撞

过冲问题

显式积分法，也称为开环法或单步法，广泛用于求解科学和工程各个领域的常微分方程 (ODE。然而，这些方法可能会遇到过冲问题，这会导致不准确或不稳定的解决方案。
产生原因：
1、两刚体相交过深导致计算出来的力太大，求解的初始条件残差太大
2、时间步长太大
3、高频振荡：在求解涉及高频振荡的 ODE 时，显式方法可能难以准确捕获这些振荡，从而导致超调。在这种情况下，使用对刚性系统更稳定的隐式积分方法会有所帮助。
4、误差累积：使用显式方法时，误差会随着时间的推移而累积，从而导致显着的超调。

基于位置的方法解碰撞

算法流程

约束的索引一般使用j
我们对于其中一个约束有：

定义约束函数C 顶点数目为3nj，位置信息为xyz，所有的数据总量就是3nj，约束函数就是读取这个3nj的数据算出一个实数
约束函数影响的顶点的索引，nj个索引
定义这个约束的刚度值
定义这个约束是等式约束和不等式约束
等式约束比较强硬，要满足约束函数等于0，不等式约束则是约束函数大于等于0就行，kj定义了这个约束的刚度，刚度越大这个约束要越快被满足。

每个循环开始，先通过力算速度，在通过算出的速度算位置，计算出一个预测的速度、位置。
然后在根据这个预测的位置情况进行碰撞约束的生成。
然后走一个固定的迭代次数，做约束投影，让p，其实就是位置，落在正确的满足约束函数的地方，因为有多个约束，其实这里就是一个多个约束方程的方程组。
约束投影完了只有得到正确的位置，然后根据投影后的位置和上一次迭代的位置算一下速度（这里和verlet简单的算速度方法很像），然后把投影后的位置更新到位置数据里。
最后在(16行根据摩擦(friction和恢复(restitution系数修改速度。

他的稳定性不取决于时间步长，而是取决于约束函数的样子。
这个求解器并不像以往的显式或者隐式积分器，而是处于一种中间态，如果每个时间步只跑一个迭代他看起来像explict，而添加迭代次数，可以更像隐式积分方案。

求解器借用的思想

\[C = |p_1-p_2| - d \]

这里的非线性，其实指的是他这个方程组的未知数不是一次的，有绝对值的话，可以理解成平方再开方，一般的迭代法解线性方程组使用jacobi、gauss-seidel迭代方法，他们的未知数有多个，但是都是一次的。
但是在这里作者是借用了GS方法的思想，来解一个非线性方程组。
原gauss-seidel迭代法是，我们一整个方程组，然后从第一条方程开始，代入一个初值，然后方程左边算出第一个未知数X，然后这个X算出来后会直接替换掉下面方程组求解时用到X的地方，第二条方程算出Y，也是一样的，先满足一条方程，然后将它的影响带到下一条方程，经过固定次数的迭代后，系统的未知数们会收敛，就求解成功了。

关于动量守恒

PBD方法里提到了动量守恒的话题，PBD本身方法的流程他是想说明按照他的流程走，只要约束函数定义时候是动量守恒的，那么结果是动量守恒的。
如果你这个系统最后输出的结果是没有违背动量守恒的基础，那么将看到一些不期待的运动，这里坐着定义为 Ghost force，看着就像有力量拖着物体旋转物体一样。

因此我们沿着约束函数梯度的方向去影响整个系统他最后满足约束了约束函数（满足这个内部力的性质），他的最后就是动量守恒的。
这里我需要说的详细的一点，因为我自己也对动量守恒这块比较困惑：
我的理解是PBD本身其实和动量守恒不沾边，主要是约束函数的定义是动量守恒的，你沿着约束函数的梯度去影响系统最后达到了约束函数，那么约束函数的最终状态是动量守恒的，我们拿这个状态去做表现，表现就是动量守恒的，但是如果我们因为很多约束，最后求解没成功，有很多约束没满足，那么最后的表现就是不动量守恒的。
如果我们定义了一个动量不守恒的C，最后求解成功了，那么表现出来也就是动量不守恒的，如果胡乱定义了一个约束还要求动量守恒其实没有讨论的必要。

约束投影

首先对于一个等式约束我们要求的就是这个状态代入约束函数后输出一个0
即

\[C(p+\Delta p = 0 \]

\[C(p+\Delta p \approx C(p + \nabla_p C(p \cdot \Delta p \]

我们要把delta P限制在约束函数的梯度方向即

\[\Delta p = \lambda \nabla_p C(p \]

得到

\[\Delta p = - \frac{C(p}{|\nabla_pC(p|^2} \nabla_p C(p \]

而对于单个点p_i来说，前面的系数λ是一样的，后面的梯度方向则变成了这个delta P在单个点的分量，其实是梯度的某几个维度，也就是关于pi的偏导数
前面的系数用s表示，

\[\Delta p_i = - s \nabla_{p_i} C(p \]

\[ s = \frac{C(p}{\sum_j {|\nabla_{p_j}C(p |^2}} \]

特别注意下维度：
这里的p是指所有的点的位置，维度是点的数量 n * 3，其中delta P会保证和约束函数的梯度一样的方向，约束函数的梯度也是一个 n * 3的向量。

简单约束举例

这里就不举例了，可以查看参考文章里面的距离约束
https://zhuanlan.zhihu.com/p/48737753

编程笔记 » 游戏模拟——Position based dynamics