高斯-赛德尔法实现稳定堆叠的双次冲击波传播

《Proceedings of the ACM on Computer Graphics and Interactive Techniques》：Two-Pass Shock Propagation for Stable Stacking with Gauss-Seidel

提出两阶段冲击传播算法，通过上下两次 passes 处理摩擦接触，存储并应用未使用冲量，显著提升刚性体模拟的稳定性和效率，在复杂堆叠场景中优于传统Gauss-Seidel方法。

　　### 两阶段冲击传播方法在刚体模拟中的应用

在日常生活中和工程领域，物体的堆叠是一种常见的操作，如整理盒子、玩具、书籍和盘子，以及构建模块化房屋和集装箱。为了模拟和分析这些场景，研究人员多年来一直在探索不同的数学模型和算法。刚体动力学模拟在这一过程中扮演着至关重要的角色，因此，开发一种可靠且高效的数值求解算法成为研究的重点。

传统的刚体模拟方法通常分为全局方法和局部方法两大类。全局方法通过求解大规模、稀疏的非线性方程组，一般表现出较好的收敛性。然而，这类方法在实时应用中可能不够高效。相比之下，局部方法，如基于Gauss–Seidel的算法，因其简单、高效和鲁棒性而被广泛采用。然而，这类方法在处理具有摩擦接触的稳定堆叠时存在局限性，因为它们在处理约束时是逐个进行的，导致信息在物体之间传播缓慢，从而可能引发模拟不稳定的问题。

在模拟中，物理引擎如PhysX和Bullet广泛使用了基于Gauss–Seidel的求解器，以实现实时图形和机器人应用。然而，当模拟的物体尺寸较小，例如桌面上的物体，这些基于Gauss–Seidel的方法会面临显著的不稳定性。具体来说，当物体尺寸调整为厘米级别时，PhysX和Bullet需要大量的子步骤才能稳定模拟，甚至会出现明显的视觉伪影。

为了解决这一问题，我们引入了一种称为两阶段冲击传播（Two-Pass Shock Propagation）的新方法。这种方法在保持局部方法优势的同时，能够实现稳定且高效的摩擦堆叠模拟，而无需依赖全局方法。两阶段冲击传播的核心思想是，在上行阶段，将底部物体视为具有无限质量，从而在每个层级上计算并记录未使用的冲量；然后在下行阶段，将这些冲量应用于底部物体，以加快求解过程并提高稳定性。

### 两阶段冲击传播方法的原理

在两阶段冲击传播中，我们首先进行碰撞检测，以收集可能的碰撞点对，并构建一个碰撞约束图。该图展示了物体之间的接触关系，包括方向和层级信息。通过这个图，我们可以按照层级顺序处理约束。在上行阶段，我们逐层处理约束，将底部物体视为无限质量，从而计算并记录未使用的冲量。这些冲量在下行阶段被应用，以修正底部物体的运动状态。

在下行阶段，我们从顶部物体开始，逐层处理约束，将记录的冲量应用于底部物体。这种方法不仅加快了求解过程，还提高了模拟的稳定性。通过这种方式，我们可以在较少的迭代次数内达到收敛，从而显著减少计算资源的消耗。

### 实验结果与性能比较

为了验证两阶段冲击传播方法的有效性，我们进行了广泛的实验。实验中使用的物体尺寸为厘米级别，质量约为50-100克。在所有实验中，时间步长设置为1/60秒，重力加速度为980厘米/秒2。我们比较了多种求解器，包括传统的Gauss–Seidel方法（GS-50、GS-150、GS-500）和基于两阶段冲击传播的方法（2PSP），以及PhysX和Bullet等物理引擎。

实验结果显示，传统的Gauss–Seidel方法在处理小尺寸物体时存在明显的不稳定性，需要大量的子步骤才能消除视觉伪影。相比之下，两阶段冲击传播方法能够在较少的迭代次数内达到稳定的模拟结果，且其残差显著低于传统方法。例如，在堆叠场景中，2PSP仅需约45次迭代即可达到稳定状态，而传统的Gauss–Seidel方法则需要500次迭代。此外，2PSP在处理动态场景时，如倾斜平面和振动场景，也表现出更好的稳定性和更低的残差。

### 方法的实现与优势

在实现两阶段冲击传播方法时，我们基于PhysX的框架，利用其摩擦约束的公式。通过构建碰撞约束图，我们能够高效地处理物体之间的相互作用。在上行阶段，我们逐层处理约束，并将底部物体视为无限质量，从而计算并记录未使用的冲量。在下行阶段，我们将这些冲量应用于底部物体，以修正其运动状态。

这种方法的一个显著优势是其计算效率。通过两阶段处理，我们能够减少所需的迭代次数，从而降低计算成本。此外，两阶段冲击传播方法不需要额外的步骤，如时间一致性记录或睡眠机制，这使得其实现更为简单，并且易于集成到现有的基于Gauss–Seidel的方法中。

### 方法的局限性与未来工作

尽管两阶段冲击传播方法在许多场景中表现出色，但其在处理复杂的装配场景时仍存在一定的局限性。例如，涉及圆形拱门等需要支撑的结构时，全局方法可能更为有效。此外，当场景主要由动态物体组成时，两阶段冲击传播的效果可能不如预期。在这种情况下，其他技术如睡眠机制可能面临类似的挑战。

未来的工作可以包括进一步研究两阶段冲击传播方法在不同场景中的适用性，以及探索其与其他优化技术的结合。例如，利用梯度自由的方法（如CMA）进行优化，可以提供一种更鲁棒的替代方案。通过这种方法，我们可以在模拟过程中进行大量并行计算，从而提高整体性能。

总之，两阶段冲击传播方法为刚体模拟提供了一种新的思路，能够有效解决传统局部方法在处理摩擦堆叠时的不稳定性问题。通过两阶段处理，我们能够在保持高效的同时，实现更精确的模拟结果。这种方法不仅适用于静态场景，也适用于动态场景，为未来的物理模拟和控制策略训练提供了有力的支持。