突破性能瓶颈：用 WebGPU Compute Shader 实现十万级粒子的高效物理碰撞
在 Web 端实现十万级别（100,000+）粒子的实时物理模拟与碰撞检测，传统的 CPU 方案甚至常规的 WebGL 渲染管线都显得无能为力。CPU 面对 $O(N^2)$ 的碰撞检测复杂度会瞬间卡死，而 WebGL 缺乏通用的计算能力（Compute Shader），难以优雅地处理复杂的数据写回与状态更新。
随着 WebGPU 标准的推进，Compute Shader（计算着色器） 为前端带来了真正的 GPU 通用计算能力（GPGPU）。本文将深入探讨如何利用 WebGPU Compute Shader，结合 GPU 空间哈希网格（Spatial Hash Grid） 算法，将十万级粒子的物理碰撞检测优化至 60 帧满帧运行。
为什么传统 GPU 方案仍会卡顿？
即使将粒子渲染搬到了 GPU，如果采用最直观的“双重循环”在 Compute Shader 中进行两两碰撞检测，每个线程负责一个粒子并遍历其他所有粒子，其算法复杂度依然是 $O(N^2)$。当 $N = 100,000$ 时，每一帧需要进行 100 亿次 距离计算。这会直接导致 GPU 算力耗尽，引发浏览器 TDR（显卡重置超时）崩溃。
为了将复杂度降低到 $O(N)$，我们必须在 GPU 上构建空间索引。最适合 GPU 架构的方法就是 空间哈希网格（Spatial Hash Grid）。
GPU 空间哈希网格算法设计
空间哈希的核心思想是：将 2D/3D 空间划分为网格，网格单元的大小等于或略大于粒子的最大碰撞直径。每个粒子根据其坐标，只需计算自身所在网格及相邻的周围网格（2D 空间下为相邻的 9 个网格，3D 空间下为 27 个），从而规避了与全场粒子的无效碰撞对比。
在 WebGPU 中，构建和查询该网格的完整流水线如下：
[ 1. 粒子状态更新 ] -> [ 2. 空间网格原子计数 ] -> [ 3. 前缀和（Prefix Sum）计算 ] -> [ 4. 粒子重排/填充桶 ] -> [ 5. 邻域碰撞检测与物理更新 ]
数据结构定义 (WGSL)
首先，我们需要在 WGSL 中定义粒子和网格的数据结构。由于 WebGPU 内存对齐规则（16字节对齐），结构体字段的设计需要格外小心。
struct Particle {
position: vec2<f32>,
velocity: vec2<f32>,
radius: f32,
mass: f32,
// 补齐 16 字节对齐
padding: vec2<f32>,
}
struct GridCell {
count: u32,
offset: u32,
}
@group(0) @binding(0) var<storage, read_write> particles: array<Particle>;
@group(0) @binding(1) var<storage, read_write> gridCells: array<GridCell>;
// 用于存储重排后的粒子索引，避免大结构体频繁复制
@group(0) @binding(2) var<storage, read_write> cellParticleIndices: array<u32>;
核心实现步骤
第一步：网格原子计数（Grid Counting）
在此阶段，我们通过计算每个粒子所在的网格 ID，并使用 atomicAdd 来统计每个网格内包含多少个粒子。
struct GridParams {
gridSize: vec2<f32>,
cellSize: f32,
particleCount: u32,
}
@group(1) @binding(0) var<uniform> params: GridParams;
@group(1) @binding(1) var<storage, read_write> cellCounters: array<atomic<u32>>;
// 将世界坐标转化为网格一维索引
fn getGridIndex(pos: vec2<f32>) -> u32 {
let gridPos = vec2<u32>(pos / params.cellSize);
return gridPos.x + gridPos.y * u32(params.gridSize.x);
}
@compute @workgroup_size(64)
fn count_particles(@builtin(global_invocation_id) global_id: vec3<u32>) {
let index = global_id.x;
if (index >= params.particleCount) { return; }
let p = particles[index];
let cellIdx = getGridIndex(p.position);
// 使用原子操作安全递增网格计数
atomicAdd(&cellCounters[cellIdx], 1u);
}
第二步：并行前缀和（Prefix Sum / Scan）
为了将无序的粒子按网格顺序紧凑地存入一个连续数组（桶）中，我们需要计算每个网格在全局数组中的起始偏移量（Offset）。这本质上是一个前缀和计算。
对于超大规模网格，可以使用 Blelloch Scan 算法实现工作组内及跨工作组的并行求和。如果网格数量较小（如 128x128），甚至可以单线程在一个 Dispatch 内快速完成，但为了追求极限性能，推荐使用双调排序（Bitonic Sort）或 GPU 并行扫描。
计算完成后，gridCells[i].offset 将存储第 i 个网格在 cellParticleIndices 数组中的起始写入位置。
第三步：填充网格索引桶（Reordering）
现在，我们再次遍历粒子，根据前缀和给出的偏移量，将粒子的原始索引写入到对应的网格“桶”中。
@group(1) @binding(2) var<storage, read_write> localCellCounters: array<atomic<u32>>;
@compute @workgroup_size(64)
fn bucket_particles(@builtin(global_invocation_id) global_id: vec3<u32>) {
let index = global_id.x;
if (index >= params.particleCount) { return; }
let p = particles[index];
let cellIdx = getGridIndex(p.position);
// 获取当前粒子在该网格内部的相对偏移
let localOffset = atomicAdd(&localCellCounters[cellIdx], 1u);
// 计算全局绝对写入位置
let globalOffset = gridCells[cellIdx].offset + localOffset;
cellParticleIndices[globalOffset] = index;
}
第四步：邻域碰撞检测与物理模拟
有了空间哈希网格，每个粒子在进行碰撞检测时，只需要检索它周围的 $3 \times 3$ 个网格单元。
@compute @workgroup_size(64)
fn resolve_collisions(@builtin(global_invocation_id) global_id: vec3<u32>) {
let index = global_id.x;
if (index >= params.particleCount) { return; }
var p = particles[index];
let cellCoord = vec2<i32>(p.position / params.cellSize);
// 遍历相邻的 9 个网格 (2D)
for (var y = -1; y <= 1; y++) {
for (var x = -1; x <= 1; x++) {
let neighborCoord = cellCoord + vec2<i32>(x, y);
// 边界检查
if (neighborCoord.x < 0 || neighborCoord.y < 0 ||
neighborCoord.x >= i32(params.gridSize.x) || neighborCoord.y >= i32(params.gridSize.y)) {
continue;
}
let neighborCellIdx = u32(neighborCoord.x) + u32(neighborCoord.y) * u32(params.gridSize.x);
let cell = gridCells[neighborCellIdx];
// 遍历该网格内的所有粒子
for (var i = 0u; i < cell.count; i++) {
let otherIndex = cellParticleIndices[cell.offset + i];
if (otherIndex == index) { continue; } // 跳过自身
var other = particles[otherIndex];
// 执行弹性碰撞检测与响应
let dir = other.position - p.position;
let dist = length(dir);
let minDist = p.radius + other.radius;
if (dist < minDist && dist > 0.0) {
let normal = dir / dist;
let overlap = minDist - dist;
// 简易位置解穿透
p.position -= normal * overlap * 0.5;
// 动量交换计算...
let relativeVelocity = other.velocity - p.velocity;
let velAlongNormal = dot(relativeVelocity, normal);
if (velAlongNormal < 0.0) {
let restitution = 0.8; // 弹性系数
let impulseScalar = -(1.0 + restitution) * velAlongNormal / (1.0 / p.mass + 1.0 / other.mass);
p.velocity -= (impulseScalar / p.mass) * normal;
}
}
}
}
}
// 边界碰撞与位置积分
p.position += p.velocity * 0.016; // dt = 16ms
// 写回全局缓存
particles[index] = p;
}
WebGPU 独有的性能优化 Trick
为了在 WebGPU 中榨干硬件的最后一滴性能，还需要注意以下几个工程细节：
1. 内存布局对齐（Alignment）
WGSL 的 std140 / std430 布局要求非常严格。在创建 GPU 缓冲区时，务必保证结构体的大小是其最大成员对齐密度的整数倍。例如，上面定义的 Particle 结构体，由于包含了 vec2<f32> 成员，需要通过增加 padding 确保结构体整体尺寸为 16 字节的倍数。错误的对齐会导致 WebGPU 在创建 Pipeline 时报出隐蔽的编译错误。
2. 利用工作组共享内存（Workgroup Shared Memory）
在进行高频数据交换的阶段（如前缀和计算或临近粒子搜索），可以使用 @workgroup_size 配合 var<workgroup> 声明共享内存。将频繁访问的数据一次性从 Storage Buffer 拷贝到 Shared Memory 中，能使带宽利用率提升数倍。
3. 使用 Indirect Draw 优化管线切换
如果粒子系统伴随动态的粒子消亡（生成与销毁），不需要将粒子数量回传给 CPU。可以直接利用 WebGPU 的 Indirect Dispatch / Indirect Draw。由 Compute Shader 将存活的粒子计数直接写入到一个 GPUBuffer 中，后续的渲染管线直接读取该 Buffer 作为绘制参数，从而消除了昂贵的 CPU-GPU 同步延迟。
总结
通过 WebGPU Compute Shader 配合空间哈希网格算法，碰撞检测的复杂度成功从 $O(N^2)$ 降到了 $O(N)$。在现代主流独立显卡上，该方案可以轻松在 2-3 毫秒内完成 150,000 个粒子的物理碰撞迭代，配合 WebGPU 的 Render Pipeline，能让前端开发者在浏览器中实现媲美原生桌面级游戏引擎的沙盒物理特效。