迭代求解器

在构建完所有约束（接触、摩擦、关节）之后，我们得到一个巨大的、耦合的线性互补问题（LCP）：Kλ = b - Jv，并附带 λ 的各种限制（如非负性）。对于一个有成百上千个接触点的复杂场景，一次性精确求解这个巨大的方程组（这被称为直接法）在计算上是不可行的。迭代求解器 (Iterative Solvers) 提供了一种高效得多的替代方案。它不追求一步到位找到精确解，而是通过多次（例如10-20次）简单、快速的迭代，逐步逼近最终的正确解。这种方法的思想简单、实现鲁棒，并且能够自然地处理不等式约束，是所有现代实时物理引擎的核心。

1. 为什么需要迭代？耦合问题

想象一个三个箱子堆叠的场景：A 在 B 上，B 在 C 上。B 的稳定不仅依赖于 C 给它的支撑力，也依赖于 A 施加给它的压力。C 的稳定则依赖于 A 和 B 共同的压力。所有这些约束都是耦合 (coupled) 在一起的。单独求解任何一个约束，而不考虑其他约束的影响，是得不到正确结果的。

迭代求解器正是通过“迭代”来解决这个耦合问题。在每一轮迭代中，它都会重新计算每个约束的冲量，而在计算约束 i 时，它会利用到其他约束 j 在本轮迭代中已经计算出的最新结果。这样，信息（如压力）就可以在约束之间“传播”开来。经过多次迭代，整个系统会逐渐“沉降”到一个满足所有约束的平衡状态。

2. 投影高斯-赛德尔 (PGS) / 顺序脉冲 (SI)

这是迄今为止在游戏物理引擎中最流行、最成功的迭代求解算法。它的名字听起来很复杂，但思想却非常简单直接。

• 顺序 (Sequential): 算法按照一个固定的顺序，逐一处理列表中的每一个约束。
• 脉冲 (Impulse): 对于每个约束，它计算并施加一个可以满足该约束的冲量增量 (impulse delta)。
• 高斯-赛德尔 (Gauss-Seidel): 这是一个经典的迭代方法。其核心思想是，在计算第 i 个未知数时，立即使用在本轮迭代中已经计算出的前 i-1 个未知数的最新值。在我们的上下文中，这意味着当我们求解一个约束的冲量后，我们会立即用这个冲量去更新相关物体的速度。这样，在处理下一个约束时，它就能“看到”前一个约束所产生的效果。
• 投影 (Projected): 这是处理不等式约束（如接触和摩擦）的关键。在计算出冲量增量并累加到总冲量上之后，我们会将结果“投影”到合法的范围内。例如，对于接触约束，累积的法向冲量不能是负数（吸引力），所以我们会 λ_new = max(0, λ_accumulated)。对于摩擦约束，其大小不能超过 μ * λ_normal，所以我们会将其钳制在这个范围内。

PGS/SI 算法流程：

// 求解器主循环
for (int i = 0; i < solver_iterations; ++i) {
    // 遍历所有约束 (例如，先是所有接触约束，然后是所有摩擦约束)
    for (auto& constraint : constraints) {
        // 1. 计算当前速度在约束方向上的分量 (J * v)
        float jv = calculate_jv(constraint, bodyA, bodyB);

        // 2. 计算偏置项 (Baumgarte + Restitution)
        float bias = calculate_bias(constraint);

        // 3. 计算有效质量
        float effectiveMass = constraint.effectiveMass;

        // 4. 计算求解冲量所需的右侧项 (rhs)
        float rhs = -jv + bias;

        // 5. 计算本次迭代的冲量增量
        float delta_lambda = rhs * effectiveMass;

        // 6. 累积冲量并进行“投影”（钳制）
        float old_lambda = constraint.accumulated_impulse;
        constraint.accumulated_impulse += delta_lambda;
        constraint.accumulated_impulse = clamp(constraint.accumulated_impulse, min_limit, max_limit);
        
        // 7. 得到实际施加的冲量
        float applied_lambda = constraint.accumulated_impulse - old_lambda;

        // 8. 立即应用冲量，更新物体的速度
        apply_impulse(bodyA, bodyB, constraint.jacobian, applied_lambda);
    }
}

3. 暖启动 (Warm Starting)

由于时间相干性，下一帧的接触状态很可能与当前帧非常相似。这意味着，满足约束所需的冲量大小也很可能差不多。暖启动就是利用这个思想来加速收敛。

• 核心思想： 在第一轮迭代开始之前，我们不从零冲量开始，而是用上一帧求解得到的最终累积冲量 λ_accumulated 作为本帧的初始猜测值。
• 流程：
  1. 在每帧结束时，缓存所有接触流形中的累积冲量。
  2. 在下一帧，当一个接触流形被复用时，将缓存的冲量作为其 accumulated_impulse 的初始值。
  3. 在第一次迭代开始前，预先将这些初始冲量施加到物体上。
• 效果： 暖启动极大地减少了求解器达到稳定状态所需的迭代次数。对于一个稳定的堆叠场景，有了暖启动，可能只需要1-2次迭代就能完美地解决所有约束。没有暖启动，物体在每一帧开始时都会有轻微的下沉，然后再被推回，导致可见的抖动。

4. 迭代次数与权衡

• 迭代次数 (Iteration Count): 这是一个全局的可调参数，通常在4到20之间。它是在性能和精度/稳定性之间的一个直接权衡。
  • 次数太少： 求解器可能无法完全解决所有约束，导致物体看起来“软”或者有穿透、抖动。
  • 次数太多： 求解器会消耗更多的CPU时间，但模拟结果会更“硬”、更精确、更稳定。

在实践中，开发者通常会根据平台性能和游戏需求来选择一个合适的迭代次数。

总结

迭代求解器是现代物理引擎处理复杂、耦合约束系统的核心技术。以投影高斯-赛德尔 (PGS) / 顺序脉冲 (SI) 为代表的算法，通过多次、快速的迭代，逐步地、合作地求解成千上万个约束。它通过立即应用冲量来在约束间传播信息，通过投影（钳制） 来优雅地处理不等式约束，并通过暖启动来利用时间相干性加速收敛。虽然它是一个近似算法，但它在性能、鲁棒性和实现简单性上取得了无与伦比的平衡，是构建高性能、高稳定性物理世界的关键所在。