Level 0 3 Physics：从串行原型到并行流形与 GPU Constraint Solvers

Source: Dev.to

TL;DR: 在过去的一周里，我们将 Bad Cat: Void Frontier 的物理栈从简单的单线程原型提升到了分阶段的高度并行管线。该栈现在包括

• Level 1 – 在作业系统上运行的 CPU 回退
• Level 2 – 带缓存流形的热启动迭代求解器
• Level 3 – 并行流形生成 + 基于 GPU 的约束求解

为什么采用分阶段的物理路线图？ 💡

游戏物理的设计空间非常广阔。我们采用了逐级递进的方法，以快速获得实用成果，同时为未来的扩展奠定基础：

这种分阶段的方法实现了快速迭代、稳健测试，并在每一步都设定了明确的性能目标。

快速架构概览 🔧

关键阶段

1. Broadphase – 空间网格生成候选对。
2. Parallel Narrowphase – 作业系统对候选对进行划分；每个作业生成局部流形并批量追加。
3. Manifold Cache / Warm‑Start (Level 2) – 将新流形与缓存的流形匹配并应用预热冲量。
4. Constraint Solver –
   • 层 1/2 使用迭代（顺序冲量）求解器。
   • 层 3 将接触处理卸载到确定性的计算着色器。

Level 1 — CPU fallback & Job System 🔁

目标： 确定性的固定时间步长物理以及在 CPU 上可扩展的并行窄相检测。

我们实现的内容

• 固定时间步长积分（TimingSystem 提供 1/60 s 的物理步长）。
• 宽相空间网格，用于限制配对数量。
• 并行窄相实现为一个 Job（physics_job.cpp）：每个工作线程处理一段配对，构建本地 std::vector，并在互斥锁下追加到共享的 manifolds_。

代码片段（概念性）

// Worker‑local: gather manifolds (reserve to reduce reallocations)
std::vector<CollisionManifold> local_manifolds;
local_manifolds.reserve((chunk_end - chunk_start) / 8 + 4);

for (auto& pair : slice) {
    CollisionManifold m;
    if (check_collision(pair, m))
        local_manifolds.push_back(m);
}

// Bulk append under lock (manifold_mutex_ in PhysicsSystem)
{
    std::lock_guard<std::mutex> lock(manifold_mutex_);
    manifolds_.insert(manifolds_.end(),
                     local_manifolds.begin(),
                     local_manifolds.end());
}

为什么这样可行

• 本地累积避免了频繁的同步和分配抖动（我们使用启发式的 reserve）。
• 批量合并保持锁争用低；Job 记录 manifolds_generated 用于诊断。
• 共享的向量和互斥锁通过 PhysicsJobContext 暴露（见 physics_job.cpp）。
• 在我们的实现中，ctx.manifolds 和 ctx.manifold_mutex 被传递给每个 Job，以执行安全的批量合并（热路径中避免使用原子操作）。

Level 2 — 缓存流形与迭代求解器（热启动） ♻️

Level 2 侧重于接触稳定性和求解器效率。

主要特性

这些默认值记录在 docs/specs/engine/systems/physics/constraint_solver.md 中。此类选择在稳定性与 CPU 开销之间取得平衡，能够提供更好的静止接触行为，并在堆叠物体和复杂场景中实现更快的收敛。

第3层 — 并行流形与 GPU 约束求解 ⚡️

对于极高接触数量的场景（可破坏堆叠、拥挤场景），CPU 求解器会成为瓶颈。第3层通过并行化约束处理并可选地将求解器迁移到 GPU 来解决此问题。

两种互补的方法

1. 在 CPU 上并行约束处理

   • 将流形划分，并在可能的情况下并行运行独立的接触求解。
   • 使用空间/所有权启发式来减少刚体写冲突，或在低争用情况下使用原子更新。

2. GPU 计算着色器求解器

   • 将接触打包进 SSBO，运行确定性的定点计算着色器，计算冲量并通过对刚体累加器的原子更新来应用冲量。
   • M6 研究笔记 包含一个原型计算着色器，并讨论了确定性原子累加和定点方法（docs/research/M6_COMPREHENSIVE_RESEARCH.md）。

示例 GLSL 代码片段（概念性）

// per‑contact work item (fixed‑point arithmetic for determinism)
Contact c = contacts[gid];
int rel_vel = compute_relative_velocity_fixed(c);
int impulse = compute_impulse_fixed(c, rel_vel);

// Apply impulse atomically to the bodies involved
atomicAdd(body_impulses[c.bodyA].linear, impulse * c.normal);
atomicAdd(body_impulses[c.bodyB].linear, -impulse * c.normal);

GPU 路径在超过 10 k 接触的工作负载上可实现 2–4× 的加速，而 CPU 并行路径则在没有强大 GPU 的硬件上提供更平滑的回退方案。

经验教训与后续步骤

后续步骤

• 为 CPU 并行求解器完善冲突解决启发式。
• 添加分析钩子，根据接触数量自动在 CPU 与 GPU 路径之间切换。
• 扩展 GPU 求解器，使其在一次遍历中处理摩擦和恢复系数。

所有引用的代码均位于仓库的 engine/physics/ 目录下。欢迎提交 PR 或 issue 以提出问题或贡献！

// Compute impulse in fixed‑point arithmetic
compute_impulse_fixed(c, rel_vel);

// Deterministic atomic addition into per‑body accumulators
apply_impulse_atomic(c.bodyA, impulse);
apply_impulse_atomic(c.bodyB, -impulse);

注意： 研究草稿包含关于布局打包、原子累加以及重放和跨平台验证的确定性考虑的细节。

好处

• 对数千个联系人实现大规模并行。
• 确定性的定点算术确保一致的回放。

权衡与安全措施

• 对体累加器的原子更新必须是确定性的且有界的，以保持稳定性。
• 仍然使用热启动和每个流形的预过滤，以减少发送到 GPU 的冗余接触工作。

Performance — targets & results 📊

Target:  50 % 减少静态堆叠场景的求解器工作量；我们的运行显示典型的 **30 %–60 %** 在迭代次数和实际时间上的降低，具体取决于场景。

• GPU offload: 将约束卸载到 GPU 在高接触场景中可以实现 > 5× 的加速，前提是原子累加语义和定点缩放已调校以保证确定性行为。

How to tune (config keys)

These keys are read by PhysicsSystem::init() (see physics_system.cpp) and clamped to safe ranges during initialization. Use the debug UI to monitor Manifolds:, WarmHits: and WarmMiss: counts while tuning.

经验教训与最佳实践 ✅

• 阶段化你的物理设计： 首先在 Level 1 实现正确性，然后加入预热（warm‑starting）和缓存，最后实现并行/GPU 路径。
• 保持窄相位并行在工作线程本地，并通过批量合并最小化同步。
• 对 GPU 求解器使用定点数学，以确保跨平台行为可复现。
• 在堆叠/稳定的场景中，预热能显著提升性能。
• 积极对流形和求解器统计进行仪表化： 我们在调试 UI 中显示流形计数，并记录预热命中/未命中。物理计时使用 SDL_GetPerformanceCounter() 和辅助函数（例如 sdl_elapsed_us），并将阶段计时累加到 stage_timings_accum_.manifold_cache_us 和 stage_timings_accum_.warm_start_us 以供分析。

已验证的代码指针 🔎

文章中的陈述已在以下代码位置和文档中得到验证：

• 并行窄相位 / 作业逻辑： engine/systems/physics/physics_job.cpp（process_pair_and_append、local_manifolds、在 manifold_mutex_ 下的批量合并）。
• 流形缓存 & 预热启动： engine/systems/physics/physics_system.cpp（update_manifold_cache()、warm_start_manifolds()、prune_stale_manifolds()）。
• 求解器循环与迭代限制： engine/systems/physics/physics_system.cpp（求解器迭代循环、solver_iterations_、velocity_iterations_、position_iterations_ 以及限制逻辑）。
• PhysicsSystem::init() 中读取的配置键： physics.solver.iterations、physics.solver.warm_start_factor、physics.solver.velocity_iterations、physics.solver.position_iterations。
• 计时 / 仪表化： 用于测量流形缓存和预热启动时间的 stage_timings_accum_ 字段和 sdl_elapsed_us 包装器。
• 约束 & 求解器数学： docs/specs/engine/systems/physics/constraint_solver.md 与 docs/specs/engine/systems/physics/physics_math.md。

这些引用已在文章中适当位置内联，以便复现。

下一步 🎯

• 继续调优 GPU 求解器的原子策略和确定性累加。
• 探索混合调度（CPU 处理低接触对，GPU 处理大量接触）。
• 为 CPU/GPU 路径之间的确定性添加跨平台验证工具。

致谢

感谢团队本周的快速、专注工作——在 CPU 和 GPU 路径上迭代，并及时在试玩前实现 warm‑starting 和 manifold caching。

作者：Bad Cat Engine Team — Bad Cat: Void Frontier

Tags: #gamedev #physics #cpp #vulkan #parallelism #simulation