Vertex Block Descent

一句话总结

提出 Vertex Block Descent（VBD），用”逐顶点块坐标下降 + Gauss-Seidel 迭代”求解隐式欧拉的变分形式：每次只调整一个顶点、固定其余顶点，通过局部 3×3 系统的牛顿步保证全局变分能量单调下降，从而获得无条件稳定、可截断迭代预算、且比 XPBD / 梯度下降 / 牛顿法收敛更快的 GPU 物理求解器。

研究背景

物理仿真是图形应用的基石，而实时应用对稳定性和性能的要求极高，常常不得不牺牲真实感。已有方法各有短板：

• 隐式欧拉 + 牛顿法：稳定、精度高，但每步要解全局线性系统，代价昂贵；为保证收敛还常需 PSD Hessian 投影和全局线搜索。
• 一阶下降法（GD、下降式仿真）：并行性好、适配 GPU，但采用 Jacobi 式迭代，收敛慢，且需线搜索防止过冲。
• PBD / XPBD：把力转成（软）约束，用 Gauss-Seidel 逐约束更新位置，稳定且可固定迭代次数，非常适合实时。但它有三个固有缺陷：(1) 只保留惯性项的 Hessian、忽略弹性 Hessian，近似误差在大时间步、少迭代时会显著偏离隐式欧拉；(2) 并行化需要对”约束图（对偶图）”着色，对偶图连接数远多于原始顶点图，颜色数多、并行度低；(3) 由于对偶（dual）形式，难以处理高质量比（high mass ratio）场景。

VBD 的目标是同时拿到”位置更新带来的稳定性 + 隐式欧拉的正确收敛 + 优于以往的并行性和性能”，并且能在给定计算预算下（固定迭代次数）保持稳定。

核心方法

全局优化：把隐式欧拉写成变分能量

VBD 建立在隐式欧拉的优化形式上。系统有 \(N\) 个顶点，状态为 \((\mathbf{x}^t, \mathbf{v}^t)\)，一步的位置由最小化变分能量 \(G\) 得到：

\[ \mathbf{x}^{t+1} = \arg\min_{\mathbf{x}} G(\mathbf{x}), \qquad G(\mathbf{x}) = \frac{1}{2h^2}\lVert \mathbf{x}-\mathbf{y}\rVert_M^2 + E(\mathbf{x}) \]

\[ \mathbf{y} = \mathbf{x}^t + h\mathbf{v}^t + h^2 \mathbf{a}_{\text{ext}} \]

第一项是惯性势（含步长 \(h\)、质量加权范数），第二项 \(E(\mathbf{x})\) 是总势能。

关键洞察：逐顶点的局部能量下降等于全局下降

如果一次只动一个顶点 \(i\)、固定其余，那么受影响的只有作用在该顶点上的力元素集合 \(\mathcal{F}_i\)。于是定义顶点 \(i\) 的局部变分能量：

\[ G_i(\mathbf{x}) = \frac{m_i}{2h^2}\lVert \mathbf{x}_i-\mathbf{y}_i\rVert^2 + \sum_{j\in\mathcal{F}_i} E_j(\mathbf{x}) \]

虽然 \(G \neq \sum_i G_i\)（力元素被重复计入），但只改动单个顶点位置时，\(G_i\) 的下降量恰好等于 \(G\) 的下降量。因此只要保证每次调整顶点都让 \(G_i\) 下降，就能保证全局能量 \(G\) 下降——这正是”块坐标下降”，块就是每个顶点的 3 个自由度，故名 Vertex Block Descent。最终用 Gauss-Seidel 迭代扫过所有顶点，速度按隐式欧拉 \(\mathbf{v}^{t+1} = (\mathbf{x}^{t+1}-\mathbf{x}^t)/h\) 反算。

局部求解器：3×3 解析牛顿步

每个顶点只有 3 个自由度，可以负担得起完整二阶信息，用牛顿法解 \(3\times3\) 线性系统：

\[ \mathbf{H}_i \Delta\mathbf{x}_i = \mathbf{f}_i, \qquad \Delta\mathbf{x}_i = \mathbf{H}_i^{-1}\mathbf{f}_i \]

其中力 \(\mathbf{f}_i = -\frac{m_i}{h^2}(\mathbf{x}_i-\mathbf{y}_i) - \sum_{j}\frac{\partial E_j}{\partial \mathbf{x}_i}\)，Hessian \(\mathbf{H}_i = \frac{m_i}{h^2}\mathbf{I} + \sum_j \frac{\partial^2 E_j}{\partial \mathbf{x}_i \partial \mathbf{x}_i}\)。

• 对如此小的系统，解析求逆比 CG / LU / QR 更快更稳。
• 不需要 PSD 投影：即使 \(\mathbf{H}_i\) 非正定，该方向仍指向局部二次近似的极值点，接近惯性与势能梯度平衡的稳定态；而变分隐式欧拉本身只要求 \(dG/d\mathbf{x}=0\)，任何极值点都是合法解。作者在所有实验（含极端压力测试）中都没遇到稳定性/收敛问题。
• 遇到（近）秩亏 Hessian（\(|\det(\mathbf{H}_i)|\le\epsilon\)）时，直接跳过该顶点这一轮的更新，反正邻居更新后它下一轮通常就不再秩亏。
• 线搜索可选但通常不必要：线搜索只需局部验证 \(G_i\) 下降即可保证 \(G\) 下降，无需评估全局系统。实验里线搜索多花 40% 时间却没有可测收益，因此论文结果一律不用线搜索。

阻尼、约束、碰撞、摩擦

• 阻尼：集成简化 Rayleigh 阻尼，同样在 \(3\times3\) 局部系统里操作，复用已算的刚度矩阵。
• 约束：因直接操纵位置，双边约束可直接置值/投影到子空间（解 \(L\times L\) 系统）；单边约束用势能软化处理（如世界盒约束）。
• 碰撞：引入二次穿透势 \(E_c = \frac{1}{2}k_c d^2\)，\(d=\max(0,(\mathbf{x}_b-\mathbf{x}_a)\cdot\hat{\mathbf{n}})\)。边-边碰撞用 CCD，点-面碰撞用 CCD 或 DCD；每 \(n_{\text{col}}\) 轮做一次 CCD 以省时间，法向 \(\hat{\mathbf{n}}\) 假设为常量以简化梯度/Hessian。
• 摩擦：采用 IPC 的摩擦模型，把相对运动投影到切向空间，用平滑过渡函数 \(f_1\) 在静摩擦与动摩擦之间过渡，并对 Hessian 做稳定化近似（不对 \(\lVert \mathbf{u}_c\rVert\) 求导）。

自适应初始化

VBD 允许自由选择迭代初值。简单选项各有问题：用上一步位置（刚材料收敛慢）、用惯性（未收敛时材料显软）、用惯性+加速度（静止接触物体会被初始化成穿透态，浪费迭代还给碰撞检测添压）。论文提出自适应初始化，用上一帧估计的加速度分量 \(\tilde{a}\) 替代外力加速度：

\[ \mathbf{x} = \mathbf{x}^t + h\mathbf{v}^t + h^2\tilde{\mathbf{a}}, \qquad \tilde{\mathbf{a}} = \tilde{a}\,\mathbf{a}_{\text{ext}} \]

\(\tilde{a}\) 根据顶点是否处于”近自由落体”自动在 \([0,1]\) 间取值：自由下落的顶点纳入外力加速度，静止接触的顶点保持原位以避免初始穿透。

加速迭代

用 Chebyshev 半迭代法加速收敛，每完成一轮 Gauss-Seidel 后全局重算位置：

\[ \mathbf{x}^{(n)} = \omega_n(\bar{\mathbf{x}}^{(n)} - \mathbf{x}^{(n-2)}) + \mathbf{x}^{(n-2)} \]

加速比 \(\omega_n = \frac{4}{4-\rho^2\omega_{n-1}}\) 由估计谱半径 \(\rho\in(0,1)\) 决定。由于碰撞能量不连续、刚度大，加速器易过冲，作者提出对正在碰撞的顶点跳过加速（一旦某轮检测到碰撞，后续同一步内始终跳过），既保稳定又几乎不影响弹性收敛。

并行化：给顶点着色而非给约束着色

VBD 通过对顶点图着色实现 Gauss-Seidel 并行，同色顶点不共享任何力元素即可并行。相比 PBD 对约束（对偶图）着色，顶点着色的颜色数少得多（例中：10 顶点 3 色 vs 9 三角形 7 色；3891 顶点 8 色 vs 14802 四面体 76 色），颜色越少串行段越少、并行度越高。

对碰撞这类动态生成的力元素，作者不做重新着色，而是用辅助位置缓冲 xnew：每个局部更新写入辅助缓冲，一轮颜色处理完再拷回主缓冲。这样同色的碰撞顶点退化为（局部）Jacobi 式迭代，其余仍是 Gauss-Seidel。由于同色碰撞对最多一两对、且分处碰撞两侧弹性解耦，这种”跳过重着色”对收敛影响极小（与真正重着色的结果高度相似）。撕裂/断裂等拓扑变化也能兼容：删除力元素无需改色，复制顶点可继承原色。

GPU 实现

映射到 GPU 两级并行：块级并行处理每个顶点，线程级并行计算各力元素的力与 Hessian 并在共享内存里归约求和。相比”一个线程处理一个顶点”，这种方式因优化了内存访问模式（同块线程共享对公共顶点的全局访问），带来近一个数量级的性能提升。

实验结果

测试平台：AMD Ryzen 5950X + NVIDIA RTX 4090，碰撞用 Embree 在 CPU 上处理，并行循环用 CUDA。体积物体用 Neo-Hookean，布料用 StVK，弹性杆用线性弹簧；固定帧时 1/60 秒、固定迭代次数。

• 大规模测试：216 个带触手的软球（4800 万顶点、1.51 亿四面体）落入茶壶堆叠，平均每步 3.6 秒；10368 个可变形物体（3600 万顶点、1.24 亿四面体）掉落成堆，平均每步 4.2 秒；两者都有超过 100 万个活跃碰撞，运动稳定、快速形成静态堆叠并保持静止接触。
• 压力测试：拧麻花两根细梁（97K 顶点、复杂自碰撞与摩擦）；被完全压平的犰狳、顶点随机撒到球面的茶壶都能迅速恢复原形；斯坦福兔被拉伸后突然释放仍稳定；甚至每帧只用单次迭代（\(h=1/60\)，\(n_{\max}=1\)）也能产生稳定的极端拉伸形变。
• 收敛率对比：与 GD、Block Jacobi、牛顿法（CPU Cholesky / GPU CG）、拟牛顿（Laplacian 预条件）比较。VBD 每次迭代因是 Gauss-Seidel + 顶点块（相当于用对角 Hessian 块做预条件）而收敛快于 GD（Jacobi）与 Block Jacobi；牛顿法单次迭代收敛最好但太慢，实际落后；加速版 VBD 全面领先。单线程 CPU 实验证明其优势不仅来自 GPU 并行。
• 对比 XPBD：相同 240 迭代/帧下，VBD 更稳定且更快（0.031 vs 0.32 秒/帧）；XPBD 需更小时间步 + 更频繁碰撞检测才能接近。高质量比上（1:2000 的重立方体压轻立方体），XPBD 即使无限刚度也会把小立方体压穿，而 VBD 无此问题。

贡献与局限

贡献：

• 提出逐顶点块坐标下降求解隐式欧拉变分形式，局部下降可证保证全局能量单调下降，实现无条件稳定且能收敛到隐式欧拉解。
• 给出弹性体动力学的全套要素（阻尼、约束、碰撞、摩擦），并利用 VBD 的初值自由度设计自适应初始化。
• 顶点着色并行 + “跳过重着色”处理动态碰撞 + GPU 两级并行实现，并行度和性能显著优于 XPBD 和一阶下降法。
• 讨论并展示了向粒子仿真（顶点换成粒子）、刚体仿真（顶点换成 6-DoF 刚体）、统一仿真（不同表示通过能量势耦合）的推广。

局限：

• 是局部迭代的下降法，不适合需要全局处理的问题；信息在系统中的传播速度受顶点连接与迭代次数限制，因此对高分辨率刚硬系统收敛慢，此时全局牛顿法可能更优。
• 碰撞基于穿透势（惩罚力），无法保证无穿透（维持接触力本身就需要一点穿透）；余维物体和自碰撞的能量定义仍有挑战。
• 作为 primal 求解器易处理高质量比，但难处理高刚度比（1:10000 时收敛很差）。
• 尚未支持基于冲量的碰撞、以及浮力等非碰撞型信息交换，留作未来工作。

延伸思考

VBD 的核心思想——”把全局隐式积分拆成一个个可独立、可证下降的顶点子问题”——本质上是把优化里的块坐标下降嫁接到物理时间积分上，既拿到了 PBD 位置更新的稳定与可截断，又靠局部完整 Hessian 修正了 XPBD 的近似误差。它模糊了”约束求解器”和”能量最小化求解器”的边界：不必把力转成约束，也不必解全局系统。值得关注的是它作为通用非线性求解器的定位（friction 这类非保守力也能无缝处理），以及它对 GPU 架构的天然贴合——顶点着色带来的少颜色数是其相对 XPBD 性能优势的关键。其”局部性”既是并行优势也是刚硬/高分辨率场景的软肋，如何与全局/多重网格方法互补，是把 VBD 推向更硬材料与更大规模的自然方向（后续的 Augmented VBD 正是沿此思路演进）。