AGIPC: Adaptive In-Solve Algebraic Coarsening for GPU IPC

一句话总结

在不改动网格拓扑的前提下，于每步 Newton 迭代内以纯代数方式把细网格线性系统”聚合”成粗系统求解，让 GPU 版 IPC 接触仿真在保持视觉一致的同时最高提速约 3 倍。

研究背景

• 领域现状：隐式时间积分配合 IPC（Incremental Potential Contact）能稳健处理刚性材料、大变形与复杂摩擦接触，是当前物理仿真的主力方案；但每个时间步都要反复求解由能量 Hessian 和梯度导出的大型稀疏非线性系统，代价随自由度（DoF）数量 \(n\) 近似以 \(O(n^2)\) 增长，高分辨率场景开销极大。
• 核心痛点：降 DoF 的两条主流路线在 GPU 上都不好用。其一是自适应重网格（remeshing），它显式改变连通性和顶点编号，破坏 IPC 势垒能量所需的 \(C^2\) 连续性、易引入自交、内存访问不规则，通常只能等 Newton 收敛后再补做变量重映射；其二是自适应子空间法，虽能做到”求解内”（in-solve）降维，但依赖显式稠密基的构造与维护，数据结构不规则、粗系统 Hessian 稠密，且需要保守的超额显存预分配，仍偏 CPU 中心，GPU 效率受限。
• 本文 idea：把自适应性重新表述为一个”选择性代数边坍缩”过程——细网格连通性始终保持静态，只让”细到粗”的映射随迭代变化。用并行 warp 级哈希把细节点聚合成粗”超节点”，再通过 GPU 归约核把细尺度梯度与 Hessian 代数地映射、累加成粗系统。这样既避开拓扑改动、保住势垒连续性，又得到规则、GPU 友好的数据布局。

方法

整体框架：从一张固定的细网格出发，每个 Newton 迭代内依次完成”打标签决定哪些边可坍缩 → 并行聚合出细到粗映射 → 代数地组装粗系统 → 用 PCG 解粗系统 → 把位移延拓回细网格并做少量全分辨率 CG 修正”，其间接触检测与势垒计算始终在细网格上进行以保证 \(C^2\) 连续。

flowchart LR
  A["细网格梯度/Hessian"] --> B["按 Green 应变增量打边标签"]
  B --> C["warp 哈希聚合出细到粗映射"]
  C --> D["代数组装粗系统 Hc, gc"]
  D --> E["PCG 求解粗系统"]
  E --> F["延拓回细网格 + 少量全分辨率 CG 修正"]
  F --> G["细网格上做接触检测与线搜索"]

关键设计：

1. 边坍缩与代数聚合（是什么/怎么做）。为每条边赋一个二值标签 \(\tau_e \in \{0,1\}\)：标 1 表示可坍缩，标 0 表示受保护以保留局部细节；默认全标 1，满足变形判据的边被置 0。并行聚合算法只沿标 1 的边把细节点合并成粗超节点。系统组装完全代数化：粗梯度按 \(g_c = \sum_{f \in child(c)} g_f\) 累加，Hessian 的 \(3\times3\) 块按 \((map(i), map(j))\) 映射后用并行哈希归约求和，等价于 Galerkin 投影 \(H_c = U H_f U^T\)、\(g_c = U g_f\)，其中 \(U\) 是由聚合映射定义的限制算子。借助分段归约等 GPU 原语，这一步很快，且省去了维护显式粗网格或动态子空间基的麻烦。

2. 自适应坍缩判据（为什么这么做）。是否保护一条边取决于”运动学一致性”，用求解内 Green 应变增量 \(\Delta G = G_i - G_{i-1}\) 的 Frobenius 范数 \(\lVert \Delta G \rVert_F\) 度量局部变形强度，其中 \(G = \tfrac{1}{2}(F^T F - I)\)，\(F\) 为单元变形梯度。若某边相邻单元的应变增量超过阈值就把该边置为保护。这样能在快速变形、高频弹性波区域自动保留分辨率，在近刚性/准静态区域激进粗化。由于弹性波在单个 Newton 迭代内也能传播很远，判据每次 Newton 迭代都重新评估；因连通性静态，边-单元邻接可预计算，标记步骤高效且适用于杆、壳、体网格。

3. 自适应仿射嵌入（解决什么问题）。若每个粗节点只给 3 个平移 DoF，无法表达聚合体内部的相对旋转，会导致人为刚化和角动量损失。为此对聚合了较多细节点的粗节点额外赋予仿射 DoF：以齐次静止坐标构造局部仿射基 \(A_f = \bar{X}_f \otimes I_3\)，得到 \(g_c = \sum_f A_f g_f\)、\(H_c = \sum_f A_f H_f A_f^T\)，使粗节点拥有 12 个 DoF（平移、旋转、缩放、剪切）。为平衡开销与精度，仅当聚合体内细节点数超过阈值（经验值 32）时才启用仿射嵌入，否则用标准 3-DoF 映射。

4. 后坍缩修正与接触处理。解出粗系统 \(H_c d_c = -g_c\) 后，用限制算子转置把位移延拓回细网格 \(d_f = U^T d_c\)，保持对称性并与 Galerkin 投影一致。由于粗解未必捕捉所有高频细节，再在全分辨率细系统上跑少量共轭梯度迭代（后坍缩，实践中少于 10 次即可），作用类似多重网格的光滑器。接触检测与势垒评估始终在细网格上做，接触梯度与 Hessian 在代数坍缩之前就装入细系统，从而所有接触约束都被保留进粗系统。

实验结果

主实验为在同一 squishy ball 场景（约 6.2 万顶点）下改变材料 Young’s 模量，对比 AGIPC 与 StiffGIPC 的总仿真时间与加速比。材料越硬、变形越快衰减、活跃 DoF 越少，自适应坍缩收益越大：最硬时取得约 3.3 倍加速且视觉无法区分；软材料因大范围持续变形而坍缩空间小、加速有限。

场景（Young’s 模量）	StiffGIPC 总时长 / s	AGIPC 总时长 / s	加速比
1e4（软）	695.6	372.9	1.87
1e5	560.2	233.3	2.40
1e6	356.8	118.6	3.01
1e7（硬）	489.9	148.4	3.30

其余实验以文字补充：与几何多重网格（GMG）在相同 Newton 容差下的框架级对比中，GMG 需要多得多的 Newton 迭代，60 帧总时长约为本文的 7.5 倍；与 AmgX 的求解器级对比中，AmgX 单独作为线性求解器收敛慢，作为 PCG 预条件子虽显著减少迭代数，但每步构建开销高，整体仍慢于 StiffGIPC 与本文。可扩展性测试里，把 1 万到 17.4 万顶点的布料落到 ABD 球上，全分辨率仿真运行时间随分辨率超线性增长，而本文增长明显更缓。此外还通过对 Hessian 只存上三角、无栈 BVH 遍历等工程优化进一步加速整条管线。

亮点与局限

• 亮点：
  • 把自适应降维彻底代数化，细网格连通性静态、只改映射，天然规避了重网格的拓扑不连续与不规则内存访问，保住了 IPC 势垒的 \(C^2\) 连续与力守恒，得到有效的下降方向。
  • 声称是首个完全 GPU 优化的自适应 IPC 求解器，在软/硬材料、变时间步、混合仿真（含 ABD 刚体）与上千物体的大规模场景中都取得最高约 3 倍加速且视觉一致。
  • 仿射嵌入以极小额外基构造开销（实测 < 10 ms）恢复旋转运动，避免了纯平移聚合的人为刚化。
• 局限：
  • 采用固定的 Green 应变增量阈值，并非对所有变形状态最优，且在极端变形/高刚度场景对数值噪声敏感（论文中的扭曲 mat 需调松阈值）。
  • 代数坍缩只减小线性系统规模，不改底层网格离散，因此 Hessian 组装与碰撞检测仍在全分辨率网格上进行；在接触密集、单个物体主导的场景（如漏斗海豚、多米诺）这些阶段会主导运行时间，削弱自适应收益。
  • 聚合依赖单个物体内的拓扑连通性，无法跨物体边界聚合，因此在大量小物体、碰撞密集的场景中坍缩被限制在每个物体内部。

延伸思考

• 论文把”自适应坍缩判据”与多重网格里的”按频率分离误差”做了类比：应变增量大的边视作高频误差保留在细层、其余聚合到粗层，这一视角提示可以把该判据与更成熟的 AMG 粗化/光滑理论结合，甚至用学习到的信号动态调阈值（作者也把动态阈值列为未来方向）。
• 作者提出把”持续接触对”当作跨物体聚合的候选，从而突破”聚合被困在单物体内”的限制——这对多米诺、颗粒堆积一类场景潜力很大，但如何在坍缩后仍保证接触势垒的 \(C^2\) 连续与线搜索可行性是关键难点。
• 由于碰撞检测与 Hessian 组装在高接触场景成为瓶颈，后续要想进一步提速，需要把”降 DoF”从线性求解阶段延伸到接触处理与几何阶段，这与近年 GPU IPC（GIPC、StiffGIPC）的整体优化方向一致。