碰撞检测篇提到 broad phase 会按 island 过滤候选对。island(岛)是 Chaos 里最影响性能的数据结构:一个由约束(接触/关节)连通起来的刚体集合构成一个岛,岛与岛之间完全独立——独立求解、独立休眠、独立并行。这篇讲岛的构建、维护和解耦带来的收益。代码在 Engine/Source/Runtime/Experimental/Chaos/Private/Chaos/PBDRigidsSolver.cpp 和 PBDRigidsIslands.cpp(UE5.3)。
岛从哪来:约束图的连通分量
物理世界的一张约束图:顶点是刚体,边是约束(接触对、关节)。图的连通分量就是一个个岛。数学上很干净——岛 $I$ 里的任意两个刚体存在约束路径相连,不同岛之间没有任何约束,所以岛 $I$ 的运动方程和别的岛完全解耦:
$$\text{solve}(I_k) \perp \text{solve}(I_j),\quad k \neq j$$
这个解耦是三个优化的根源:岛可以并行求解(互不依赖)、岛可以独立休眠(内部全部静止就整岛冻结)、岛可以独立跳过 broad phase 复筛(没有成员变动时接触对集合不会变)。
岛不是静态划分的——FPBDRigidsIslands::UpdateIslands 每帧根据约束图的变动增量维护。新接触出现可能把两个岛合并(一个箱子滚下山撞到山脚的箱子堆),接触消失或关节断裂可能把岛切开。Chaos 的实现不做全图重扫,用并查集(union-find)式的增量合并加周期性验证:新约束进来先 union,每帧结束检查断边导致的分裂。
求解阶段的并行化
FPBDRigidsEvolutionGBF::Solve 拿到 island 列表后,求解是逐岛独立的迭代循环。PBD 求解内部对每个岛的约束做若干轮 Gauss-Seidel 式投影——注意 Gauss-Seidel 本身是顺序算法(第 $i$ 个约束的投影依赖第 $i-1$ 个刚更新的位置),无法在一个岛内并行;但岛之间没有数据依赖,把岛分给不同线程就是天然完美的并行任务。
这里的并行粒度权衡值得说清楚。更细粒度的并行(约束级着色,把同岛约束按冲突图染色后并行)理论上限更高,但 bookkeeping 成本大、Load balance 差(岛大小不均时线程空转)。Chaos 选了岛级并行——实现简单、无数据竞争、任务粒度粗。代价是最大岛的规模决定了并行效率上限:一个 500 刚体的塔吊场景加一个独立的小箱子,前者是一个岛只能单线程啃,后者和别的岛并行。Stat Chaos 里的 island 统计能看到每帧最大岛——优化物理并行度的第一步往往是别让一个巨型岛独占一切(关节别乱连,物理约束组件能断就断)。
任务调度本身走 Chaos::FPBDRigidsSolver::ParallelFor 系接口,底层接 UE 的 TaskGraph(TaskGraph 那篇讲过 NamedThread/AnyThread 模型)。物理求解是 AnyThread 任务的典型场景——不依赖特定线程,worker 池里谁空谁拿。
休眠:整岛冻结的正确性
休眠(Sleeping)是物理引擎最大的性能来源:静止的物体不该耗任何 CPU。判据听上去简单——岛的速度全部低于阈值若干帧就休眠。但要分清两个层次:
- 岛级休眠的前提:所有成员速度低于阈值(线速度、角速度各有一个阈值,
PhysicsSettings里SleepThreshold一族)。注意是全部成员——塔吊上一只苍蝇在爬,整座塔都不能睡; - 唤醒的传播:休眠岛收到外部作用(新接触、施加冲量、关节另一端动了)必须整岛唤醒,而且唤醒要传播。新物体掉进休眠的箱子堆,接触对把新物体和堆顶箱子连起来,union 操作把两个岛合并,堆里的每个箱子都要被标醒。漏一个就是经典 bug:箱子堆底层不响应撞击,被穿透。
Chaos 的唤醒机制走 IslandData 里的 sleeping flag + event 队列:外力作用先标 dirty,帧首 ApplyInputs 阶段统一把脏岛的 sleeping 状态翻转。这和 GT/PT 的脏属性机制是同一个设计模式——所有状态变化先进队列,固定时机统一应用,避免遍历中改结构的混乱。
岛过滤对 broad phase 的加速
回到碰撞检测篇那个过滤:休眠岛成员之间的接触对不需要重新窄相位——它们的相对位形没变,持久流形(persistent manifold)直接复用。这对"一堆静止箱子 + 一个活动物体"的场景是决定性的:活动物体只和少量休眠箱子产生新候选对,箱子互相之间的 $O(k^2)$ 接触全部跳过。没有 island 这层抽象,休眠优化只能做到单物体粒度,一堆静止箱子互相之间的 broad phase 还是省不掉。
实测与排查
p.Chaos.Solver.Islands.Print类 debug 命令 dump 当前 island 列表,配Stat Chaos看 island 数量和最大岛尺寸;- 物理耗时高但 island 统计正常:查单个岛内约束数——关节链(ragdoll 几十条约束)是一个岛,Gauss-Seidel 顺序求解它就是单线程瓶颈,解法是减少迭代数(
p.Chaos.Solver.Iterations)或接受它; - 休眠异常(该睡的没睡):
SleepThreshold被调太低、或持续有微小外力(浮点噪声级的风力、动画驱动的关节扰动)戳着岛。p.Chaos.DebugDraw.Sleep可视化休眠状态; - 该醒的没醒:大概率是唤醒传播漏了——检查是不是有新接触路径没被 union 进岛,5.x 早版本有过接触生成时漏标 island dirty 的 bug,升级小版本能修。
源码入口
- 岛数据结构:
Chaos/PBDRigidsIslands.h的FPBDRigidsIslands,看UpdateIslands的增量合并逻辑; - 求解并行化:
PBDRigidsEvolutionGBF.cpp的Solve函数,看 island 列表怎么被ParallelFor分发; - 休眠/唤醒:
PBDRigidsSolver.cpp里UpdateSleepState相关路径。
岛机制给物理引擎的启示可以推广到任何仿真系统:把世界划分成无耦合的连通分量,并行、冻结、跳过都是这个划分的免费副产品。做粒子系统、布料仿真、人群模拟,先找自己的"约束图"和"岛",性能问题的一半答案在里面。