跳转到内容
Jason's Study

Baraff-Witkin 1998 — 让布料模拟敢走大时间步

是什么

Baraff-Witkin 1998 是布料模拟从玩具规模走进电影/游戏管线的关键工程论文。日常类比：以前算一片布料像踩自行车下陡坡——必须每秒踩 3000 下才能保持平衡（显式积分小步走），稍微大力一点就连人带车飞出去（数值发散）。这篇论文换了一辆带变速箱的电动车，每秒踩 30 下就稳稳走完同一段路。

技术上一句话：用隐式 Euler 时间积分 + 改造过的共轭梯度（modified CG）解线性系统 + 把约束直接嵌进 CG 迭代里，把布料这种典型 stiff ODE 系统的可用时间步从 1/3000 秒放大到 1/30 秒。

为什么重要

不理解这篇，下面这些事都没法解释：

  • 为什么 Maya nCloth、Marvelous Designer、Houdini Vellum 早期版本都长一个样——它们的骨架就是这套
  • 为什么《Geri 的游戏》《玩具总动员 2》能让角色穿真衣服——Pixar 1998-2000 年用的就是这个算法
  • 为什么后来的 Position Based Dynamics（muller-2007-pbd）、XPBD（macklin-2016-xpbd）总把自己定义成”和 Baraff-Witkin 的对照”——它们都是在反思隐式路线
  • 为什么”stiff ODE”这个数值分析名词会出现在图形学论文里——布料的抗拉伸刚度比抗弯曲高 4-5 个数量级，这正是 stiff 的定义

核心要点

整套方案三块拼起来：

  1. 隐式 Euler 推进时间：显式法用”当前位置算力 → 推下一帧位置”，遇到大刚度立刻发散；隐式法用”下一帧位置算力 → 反推下一帧位置”，等价于解一个隐式方程。代价是每步要解一个大型稀疏线性系统，但允许时间步放大几十到几百倍。

  2. modified CG 解约束系统：粒子约束（钉点、贴附移动表面）通常用 Lagrange 乘子或罚函数处理，前者把矩阵变非对称、后者引入新刚度。Baraff-Witkin 直接在 CG 每次迭代里把约束方向上的残差和搜索方向投影掉——CG 跑多少步约束都精确满足，不再当软约束。

  3. 二次形式的内能 + 配套阻尼：传统 metric-tensor 方法把 stretch/shear/bend 写成四次能量，求二阶导（Hessian）很贵；这里用一种 quadratic 写法，Hessian 简单稀疏，阻尼力还特地写成”不会惩罚刚体平移/旋转”的形式。

加上自适应步长控制，30Hz 动画平均每帧只跑 2-3 步，6000 节点的系统每步 CG 只需 50-100 次迭代。

为什么这一步要解线性系统

把隐式 Euler 写成方程：

M (v_{t+1} − v_t) = h · F(x_t + h·v_{t+1}, v_{t+1})

未知数 v_{t+1} 同时出现在等号两边。把右边的 F 在 x_t, v_t 附近做一阶 Taylor 展开（这就是”半隐式”做法），整理后得到形如：

(M − h·∂F/∂v − h²·∂F/∂x) · Δv = h · F(x_t, v_t) + h² · ∂F/∂x · v_t

左边那个矩阵就是布料的 Jacobian，对 6000 节点系统是 18000×18000 稀疏对称矩阵。CG 正是为这种规模量身定做的。

实践案例

案例 1：30×30 桌布挂在两个钉点

把 stretch 刚度设极大（比如 5000 N/m），shear/bend 设中等（5-50 N/m），重力一开。

  • 显式 Euler：步长必须降到 1/3000 秒以下才不爆炸；放到 1/300 秒立刻看到布料像橡皮筋一样剧烈抖动后飞散
  • 隐式 Euler（这篇）：步长直接放到 1/30 秒还稳定，能看到布料自然下垂、形成两条对称的悬链曲线

这个对照是体会”stiff ODE 的代价”最直观的实验，也是论文 Figure 5 的真实场景。

案例 2：Pixar 用它做电影里的衣服

1998 年发表前，工业界跑一帧高分辨率衣服动辄数十分钟，根本进不了管线。这套方法把 2600 节点桌布做到 SGI Octane R10000 上 ~2 秒/帧，4530 节点长裙 10 秒/帧，6450 节点衬衫 8-14 秒/帧——第一次让”角色穿衣服”成为可调度的渲染任务而不是研究 demo。

案例 3：游戏引擎里的披风/裙摆

直接照搬 Baraff-Witkin 在游戏里已经过时——隐式 Euler 是一阶方法、数值阻尼很重，60 帧实时下布料看起来像泡在糖浆里。但它的核心思想被两条路线接住：

  • Position Based Dynamics（Müller 2007）把”解隐式系统”换成”直接把粒子位置投影到约束流形上”
  • XPBD（Macklin 2016）补了 PBD 的刚度依赖步长的毛病，让 PBD 在数学上等价于一个 implicit 步

你今天在 Unreal/Unity 里看到的布料组件，骨架还是 Baraff-Witkin 的拓扑：粒子 + 约束 + 隐式风格的步进。

案例 4：Marvelous Designer 的 2D 板片到 3D 服装

这套软件让设计师在 2D 平面画板片、缝合线，再”穿”到角色身上自动垂坠成型。底层模拟器要在缝合那一瞬间承受极端强约束（缝合线两端粒子瞬间被拉到一起），显式法必爆。Marvelous 早期版本的求解器就是 Baraff-Witkin 风格的 implicit + 投影约束，只是把 modified CG 的”投影掉某个粒子的位置自由度”扩展成”投影掉两个粒子相对位置”——本质是同一招。

踩过的坑

  1. 误以为 implicit 一定意味着精度高：implicit Euler 是一阶方法，会引入大量数值阻尼，看起来稳定但布料能量会被持续吞掉、出现过度阻尼、缺少应有的高频抖动。要保留弹性细节得换 IMEX 或 BDF2 / midpoint 方法。

  2. 把 stretch 刚度系数当外参反复调：原文强调 stretch 系数应固定大、靠 implicit 求解吸收硬度；显式实现里把 stretch 调小来防爆是反模式，会得到橡皮一样松垮的布料。复现时务必坚持 quadratic + 大刚度的搭配。

  3. 直接套现成 CG 而忘了改造：约束是通过在每次 CG 迭代里把约束方向上的残差/搜索方向投影掉实现的，普通 CG 会把约束当软约束最后违反。实现时必须替换 inner product 与搜索方向更新两个步骤。

  4. 忽视 self-collision 和 cloth/cloth 碰撞：原文只用 penalty spring 处理 cloth/cloth，刚度调高就会反过来再次让系统变 stiff 而拖慢 CG，且 fast tunneling 仍可能漏检。后续 Bridson 2002 才补上 continuous collision detection + impact zones。

  5. 阻尼力的 Jacobian 写错：原文把 stretch/shear/bend 阻尼写成不会惩罚刚体运动的形式，复现时若直接 −kẋ 简单粘性阻尼会把整片布的平移/旋转都拖慢，看起来像在糖浆里。

  6. 时间步自适应没做好就退化成定步长：论文用一个简单 heuristic 缩放步长，遇到剧烈碰撞要立刻缩步否则 CG 不收敛；忽略自适应控制时性能会比论文报告差几个数量级。

适用 vs 不适用场景

适用：

  • 离线/近实时布料模拟（电影、过场动画、高质量预渲染）
  • 任何 stiff 弹性系统的隐式积分模板（薄壳、毛发、橡胶都能套）
  • 想理解为什么”约束直接投影”比”加 Lagrange 乘子”更工程友好——这是该方法最被低估的洞见

不适用：

  • 60 帧实时游戏布料 → 用 PBD / XPBD，一步投影更便宜
  • 需要精确能量守恒的科研场景 → 隐式 Euler 数值阻尼太重，改用 IMEX / 辛积分
  • 流体/不可压缩材料 → 该方法是为薄壳设计的，体积不可压约束需要不同策略
  • 需要二阶以上时间精度 → 隐式 Euler 只到一阶

历史小故事（可跳过）

  • 1986-1992：Terzopoulos 等人把布料建模为可变形曲面 PDE，用有限元 + ADI 隐式法跑过原型，但工程化不足
  • 1992-1996：Carignan、Breen、Volino、Eberhardt 系列工作用显式积分 + mass-spring 或 Kawabata 实测数据得到逼真悬挂效果，每帧动辄数十分钟
  • 1998：Baraff 与 Witkin 在 SIGGRAPH 把 implicit Euler + modified CG + 直接约束打包成工程上可落地的方案，从此布料模拟脱离玩具规模进入工业管线
  • 1999：Desbrun 把同一思想搬到网格平滑（desbrun-1999-implicit-fairing），证明隐式步进不止适用于布料
  • 2002：Bridson 补碰撞检测，2007 Müller 提出 PBD，2016 Macklin 提出 XPBD——都是在这条隐式路线上演进或反思

David Baraff 后来去了 Pixar 做技术总监，把这套方法和后来的衣服碰撞处理一起做进了内部模拟器 Fizt；Andrew Witkin 长期在 CMU 教物理仿真，2010 年去世，他的笔记《Physically Based Modeling》仍是入门最经典的教材。两人共同的特点是愿意把数学算法写成工程师能直接读的伪代码，这份品味让这篇论文 28 年后还在被新生读。

学到什么

  1. stiff 系统的代价决定了积分器选择——刚度比软度高 4-5 个数量级时，显式法每步代价被时间步惩罚抵消，隐式法稳赢
  2. 约束有三种处理方式：罚函数（最简单、引入新刚度）、Lagrange 乘子（最精确、矩阵变大）、直接投影（这篇的方法，最工程友好）。选择取决于你能改求解器多深
  3. CG 是稀疏对称系统的默认武器：内存友好、迭代次数和有效 condition number 的平方根成正比，对结构化稀疏特别快
  4. 一阶方法 + 数值阻尼是隐式 Euler 的隐藏代价，工程上常常用得到稳定，但代价是”看起来对、能量在偷偷漏”
  5. 理论 → 算法 → 工程 → 反思，每一步隔 8-10 年。1986 PDE → 1998 这篇 → 2007 PBD → 2016 XPBD
  6. 数值方法的好坏从不只看精度阶数——隐式 Euler 是一阶却赢了 RK4，因为对 stiff 系统稳定性才是瓶颈，精度可以靠步长换

一段最容易被误解的细节

很多人读完会以为”隐式 Euler 比显式 Euler 精度更高”——错。两者都是一阶时间精度，它们的真正差别在于稳定性区域。显式 Euler 的稳定性区域是负实轴上一个有限的小圆盘，时间步必须满足 h·λ_max < 2（λ_max 是 Jacobian 最大特征值）；隐式 Euler 的稳定性区域是整个左半复平面，任何步长都稳定。这就是为什么大刚度系统（λ_max 巨大）显式法被时间步逼到无法工作，而隐式法可以放飞步长——付出的代价不是精度，是每步要解线性系统。

延伸阅读

关联

  • desbrun-1999-implicit-fairing —— 同一年隔壁组用同一隐式套路解决网格平滑
  • catmull-clark-1978 —— 表面细分基础，给布料网格提供拓扑
  • kajiya-1986-rendering-equation —— 同样属于”图形学里的方程派”经典
  • muller-2007-pbd —— 后续 PBD 路线的起点，常被拿来与本文对比
  • macklin-2016-xpbd —— PBD 的修正版，让步长无关刚度

反向链接