PBD计算迭代的几种算法评估

这种迭代的本质思想，是将微分方程，转换为差分方程的数学方法，通过变为差分问题，使得PBD迭代有序（或者说有梯度）趋向于目标位置，本文简单介绍一下PBD的常用迭代计算方法。

欧拉积分

欧拉积分也是现在常用的游戏引擎的默认迭代方法，其特点就是算的快，而且理解简单，计算快速在游戏行业非常重要，但是缺点就是牺牲了一定的稳定性，或者说是欧拉积分的不稳定性是累加的，这个特性决定了在物理仿真尤其是精确物理仿真，需要慎重使用这个方法

显式欧拉积分（向前欧拉）

在显式欧拉中，\(x_n\)和\(y_n\)分别用于处理表达当前步骤的求和求解

\( y_{n+1} = y_n + h \cdot f(x_n, y_n)\)

隐式欧拉积分（向后欧拉）

\( y_{n+1} = y_n + h \cdot f(x_{n+1}, y_{n+1})\)

显式欧拉方法不同的是，隐式欧拉方法在更新解时需要通过迭代来求解 \(y_{n+1}\)。通常，可以使用牛顿迭代法等方法来找到 \(y_{n+1}\)。这使得隐式欧拉方法更稳定，适用于一些显式方法可能失效的情况，但每个步骤的迭代过程会增加计算复杂性。

半隐式欧拉积分

半隐式欧拉方法（Semi-Implicit Euler method）结合了显式和隐式欧拉方法的特点。其中，一部分的更新是显式的，而另一部分则是隐式的

\begin{align*}
&\text{Explicit step: } \\
&y_{n+1}^* = y_n + h \cdot f(x_n, y_n) \\
&\text{Implicit step: } \\
&y_{n+1} = y_n + h \cdot f(x_{n+1}, y_{n+1}^*)
\end{align*}

在这里，首先进行显式步骤，使用当前步骤的解\(x_n\)和\(y_n\)更新一个中间值 \(y^*_{n+1}\)​。然后，在隐式步骤中，使用中间值 \(y^*_{n+1}\)​ 和下一个步骤的位置 \(x_{n+1}\) 来更新最终的解 \(y_{n+1}\)。这种方法在一些情况下可以提高数值稳定性，并减少对求解器的依赖，但仍然保持了一定的计算效率。

Verlet积分

Verlet积分是一种用于模拟分子动力学和其他模拟中的数值积分方法，特别适用于保持物理系统能量守恒的问题，在PBD算法中，更加适合用于做每一步的迭代计算，和欧拉积分只考虑当前和下一时刻（或者上一时刻和当前时刻）不同，Verlet积分同时考虑上一时刻、当前时刻、下一时刻，也是我们使用模拟的首选。

\begin{align*} &\text{初始化:} \\ &\quad y_0, v_0 \quad \text{(初始位置和速度)} \\ &\text{时间步:} \\ &\quad y_{n+1} = 2y_n – y_{n-1} + h^2 \cdot a_n \quad \text{(更新位置)} \\ &\quad v_{n+1} = \frac{y_{n+1} – y_{n-1}}{2h} \quad \text{(更新速度)} \\ &\quad a_n = f(y_n) \quad \text{(计算加速度)} \\ \end{align*}

注意 yn 是位置，vn 是速度，an​ 是加速度，h 是时间步长

另外有一种写法是这样的：\( y_{n+1} = y_n + (y_n – y_{n-1}) + h^2 \cdot a_n \) 其本质是一样的

补充velocity-verlet：

\begin{align*}
&\text{初始化:} \\
&\quad x_0, v_0, a_0 \quad \text{(初始位置、速度和加速度)} \\
&\text{时间步:} \\
&\quad x_{n+1} = x_n + v_n h + \frac{1}{2} a_n h^2 \quad \text{(更新位置)} \\
&\quad a_{n+1} = f(x_{n+1}) \quad \text{(计算新位置的加速度)} \\
&\quad v_{n+1} = v_n + \frac{1}{2}(a_n + a_{n+1}) h \quad \text{(更新速度)} \\
\end{align*}

注意 yn 是位置，vn 是速度，an​ 是加速度，h 是时间步长，Velocity Verlet算法通过对位置和速度的多个步骤进行迭代，同时保持了较好的数值稳定性和能量守恒性

优势：

1. 数值稳定性： Verlet积分在保持能量守恒和数值稳定性方面表现良好，特别适用于模拟保守系统。
2. 简单易实现： 实现相对简单，不需要对速度进行显式的计算，只需要更新位置即可。
3. 较小的计算量： 相对于RK4，Verlet积分需要的计算量较小，对于一些实时性要求高的应用更具优势。

劣势：

1. 积分误差： 对于一些非保守系统，Verlet积分的数值误差可能会累积，导致长时间模拟时的不稳定性。
2. 对变化较大的时间步长敏感： 对于变化较大的时间步长，可能需要额外的处理以保持数值稳定性。

Runge–Kutta methods

Runge-Kutta常常称之为龙格-库塔算法或RK4（4表示阶层，一般来说4阶就可以了），是一种利用泰勒展开思想的算法去高精度迭代逼近目标值的计算方法，其相比欧拉和Verlet积分而言，精确度更高，结果更加准确，单也会牺牲一部分精度去实现，其本质是泰勒的展开的四阶公式。

\begin{align*} k_1 &= h \cdot f(x_n, y_n) \\ k_2 &= h \cdot f(x_n + \frac{h}{2}, y_n + \frac{k_1}{2}) \\ k_3 &= h \cdot f(x_n + \frac{h}{2}, y_n + \frac{k_2}{2}) \\ k_4 &= h \cdot f(x_n + h, y_n + k_3) \\ y_{n+1} &= y_n + \frac{1}{6} \cdot (k_1 + 2k_2 + 2k_3 + k_4) \end{align*}

优势：

1. 高阶准确性： RK4是一个四阶的方法，相对于低阶方法（如欧拉方法）具有更高的数值精度，特别是在处理非线性系统时表现较好。
2. 适用于多种系统： 适用于各种类型的微分方程，包括非保守和刚体动力学系统。

劣势：

1. 计算量较大： 相对于Verlet积分，RK4需要更多的计算，涉及对速度和加速度的显式计算。
2. 可能不稳定： 对于一些刚性系统或者存在较大梯度的系统，需要小心选择时间步长以防止数值爆炸或数值耗散。

详细理解

请复习，泰勒展开和一些基本微积分知识，同时复习牛顿三大定律，胡克定律等基本力学定理

方法选择

选择依据： 选择数值积分方法应基于具体问题的物理特性、数值稳定性需求和计算性能需求。Verlet积分通常用于保守系统，RK4用于高精度求解，而欧拉方法则在简单性和一些特定场景下可能更实用。