技术博客

Jolt 的 broad phase:四叉树与 JobSystem 的适配

第 63 / 149 篇 · 2026-09-12 · godot · 物理引擎Jolt性能优化

分类第 3 篇测过 Jolt 的整体收益(同场景物理耗时降到四成),并埋了一个问题:单 island 并行解释不了全部差距,另一半在哪。答案的一半就在 broad phase。Godot Physics 的 broad phase 是八叉树(GodotOctree),每帧把所有脏节点重插一遍再平衡;Jolt 用的是自己实现的四叉树,维护策略完全不同——不追求树时刻最优,追求更新足够便宜。便宜到一定程度,"大规模更快"就不再依赖求解器的并行,从找接触这一步就开始领先。

四叉树的维护策略:多层 + 层间迁移

Jolt 的 QuadTree(Jolt 源码 Physics/Collision/BroadPhase/BroadPhaseQuadTree.cpp)有两个关键设计:

纯四叉、节点紧凑。 每个内部节点固定 4 个孩子,叶子存 body ID 数组,所有节点连续存储。对比八叉树,节点扇出小、单节点缓存行利用率高,树遍历时的 cache miss 更少。对 broad phase 这种"每帧走很多遍、每次只读一点点"的负载,缓存布局就是硬性能。

多棵层级树,body 按移动活跃度分层。 引擎同时维护若干棵四叉树(Jolt 文档为 4 层),body 按"最近移动了多少"住在某一层:刚插入或大幅移动的停在上层树,连续几个 step 没怎么动的逐步下沉到底层树。下沉是增量、摊销的——Update 时顺手处理一部分,不追求一次到位。查询和 pair 收集时每层树各查一遍,层间用 body ID 排序去重,保证同一对 body 不会被两个层各报一次。

直觉:下沉到底层的 body 都是静止的,它们在树里的位置长期有效,等于"重平衡的需求被静止性吃掉了"。场景里 90% 的 body 是静止的静态物——它们几乎不产生任何树维护成本。Godot 的八叉树没有这个区分,静态物也照常在每帧的更新循环里占一份。

pair 收集:先剪枝,再求交

pair 的产出流程是:对每个刚移动的 body,用它的 AABB 在每层树上查询交叠候选。真正生成 pair 前要过两道过滤:

  1. BroadPhaseLayer 过滤:body 除了 32 位 collision layer,还映射到一个粗粒度 BroadPhaseLayer(静态、动态等大分类)。静态-静态这种永远不会产生响应的 pair,在树查询阶段就被剪掉,连候选都不生成。这是对"全场景静态物"最有效的压缩;
  2. ObjectLayer 过滤:就是我们熟悉的 32 位 layer/mask 双向 AND(分类第 7 篇展开),在候选生成时兜底。

两道工序的位置有讲究:BroadPhaseLayer 是"整棵子树可能都不用走"的剪枝,发生在遍历中;ObjectLayer 是逐对判断,发生在遍历后。贵的过滤先做、便宜的过滤后做,总成本 $O(\text{树查询}) + O(\text{幸存候选})$。Godot Physics 只有后一道,前一道没有对应的抽象。

JobSystem 适配:把 Jolt 的任务铺到 Godot 的线程池

Jolt 内部的并行点(pair 收集、island 求解)不直接创建线程,而是通过 JPH::JobSystem 接口发任务。Godot 的适配在 modules/jolt_physics/jolt_job_system.cpp:实现这个接口,把每个 job 包成回调塞进 Godot 的 WorkerThreadPool,用信号量实现 Jolt 要求的 barrier 语义——"这批 job 全部完成前,某个后续 job 不许开始"。

这个适配层薄,但语义要对齐:Jolt 的 job 允许在任意线程执行、允许嵌套 spawn,Godot 的 WorkerThreadPool 恰好也是"任务 + 依赖信号量"的模型,映射几乎一一对应。真正要小心的是饥饿:物理线程自己也可能被当成 worker 去跑 job(Jolt 支持调用线程参与执行),如果 job 实现里有阻塞等待,而所有 worker 都在等同一个 barrier,就死锁。适配层把"参与执行"的入口做对,是这类桥接代码里最常见的坑。

把账算总:四成从哪来

同场景一千个盒子(第 3 篇的实测设定),Jolt 的耗时构成大致是:

  • broad phase 维护:多层树 + 摊销迁移 vs 每帧全量重插——静止盒子几乎免费;
  • pair 生成:BroadPhaseLayer 剪枝砍掉绝大多数静态-静态候选 vs 全过 ObjectLayer;
  • pair 收集 + island 求解:JobSystem 铺满多核 vs Godot 求解器单线程。

前两笔在小场景是负收益(多层树和 JobSystem 有固定开销,几十个 body 摊不薄——第 3 篇说过小场景 Jolt 反而略慢),后一笔随规模超线性放大。所以"Jolt 什么时候值得开"这个问题的工程答案没变:看场景里活跃刚体的规模,不看 benchmark 的平均值。

适配层要兜的底还有一个说过的:四叉树查询用 128 深固定栈,编辑器里堆几百个 body 不 step 会把树压到不平衡,查询漏检。Godot 的对策是每加 128 个 body 主动 OptimizeBroadPhase() 一次(第 3 篇引过那段注释)。用 Jolt 后 broad phase 的"怪行为"基本都能映射回这两个实现假设,排查时先查这里。

Jolt 四叉树 broad phase:结构、迁移与剪枝 四叉树 2 层示意(实际多层) 按象限递归划分,节点紧凑连续存储 多层树 + 层间迁移 新插入/大幅移动停上层,静止的逐步下沉,更新摊销 pair 收集:查询 AABB 走每层树,层内 ID 排序去重 BroadPhaseLayer 树级剪枝 → ObjectLayer 逐对过滤 Godot 侧:JoltJobSystem 把 job 铺进 WorkerThreadPool barrier 用信号量;128 深栈假设 → try_optimize 兜底 大规模快的来源:更新摊销 + 剪枝 + 并行 pair/island——不是单点魔法,小场景固定开销反而吃亏

本文基于 Jolt 5.x 源码 BroadPhaseQuadTree.cpp、QuadTree.cpp 与 Godot 4.4 modules/jolt_physics/jolt_job_system.cpp。层数、默认 BroadPhaseLayer 划分等细节以所用 Jolt 版本为准。