SIMD用于碰撞检测

# 碰撞检测的SIMD 来源：https://box2d.org/posts/2026/07/simd-for-collision/ 在[之前的文章](https://box2d.org/posts/2024/08/simd-matters/)中，我讨论了通过图着色（graph coloring）加速接触求解器所获得的巨大收益。同样的方法也存在于 Box3D 中。我喜欢将这种方法称为“宽 SIMD”。其核心思想是同时处理多个工作单元。在接触求解器中，这意味着同时求解四个接触点。 这与“窄 SIMD”不同，后者是将一个三维向量（xyz）放入 SIMD 寄存器，然后用 SIMD 内联函数实现标准的向量运算。窄 SIMD 也有用，但收益不那么明显。 在 3D 中，存在一个在 2D 中没有的宽 SIMD 应用机会。考虑从 [PEEL](https://github.com/Pierre-Terdiman/PEEL_PhysX_Edition) 移植而来的凸堆基准测试。这个测试同时下落 5120 个凸壳（convex hull），每个包含 32 个顶点。 凸堆 Box3D 将盒子视为凸壳，许多基准测试都使用盒子。盒子的性能表现良好，通常大部分计算成本不在窄相位（narrow phase）。但 32 个顶点的凸壳是另一种情况，我们姑且称之为“巨石”。下表比较了盒子和巨石的凸壳细节： | 凸壳 | 顶点 | 面 | 边 | |------|------|----|----| | 盒子 | 8 | 6 | 12 | | 巨石 | 32 | 58 | 89 | Box3D 使用[分离轴测试（SAT）](https://en.wikipedia.org/wiki/Hyperplane_separation_theorem)进行碰撞检测。通过 SAT，我可以找到将两个形状分开的最佳特征，以及需要将它们分开多远才能消除重叠。此外，我还利用这些结果来计算接触法线和接触点。 其他物理引擎可能使用距离算法 [GJK](https://en.wikipedia.org/wiki/Gilbert%E2%80%93Johnson%E2%80%93Keerthi_distance_algorithm) 并配合重叠后备方案，例如[扩展多面体算法（EPA）](https://graphics.stanford.edu/courses/cs468-01-fall/Papers/van-den-bergen.pdf)。我个人非常喜欢 SAT 用于凸壳碰撞，因为它不需要碰撞余量。形状可以直接紧密贴合。而 GJK 与 EPA 组合通常会试图让形状保持微小分离，以便将形状保持在 GJK 区域内，从而提高速度。但这可能导致视觉上的间隙。此外，EPA 在数值上可能较为脆弱，如果 EPA 失败，物理引擎通常需要另一个后备方案：一个后备方案的后备方案。EPA 本质上是一种计算凸包的算法，而输入数据可能是扁平的薄片，这对凸包计算来说是一个挑战，因此需要第二重后备。 不幸的是，3D 中的 SAT 具有平方级复杂度。对于两个凸壳 A 和 B，碰撞算法必须测试 A 的面与 B 的顶点、B 的面与 A 的顶点，以及 A 的边与 B 的边。在最坏情况下，需要评估每一种组合。 | 组合类型 | 面-顶点 | 顶点-面 | 边-边 | |----------|---------|---------|-------| | 盒子-盒子 | 6×12=72 | 6×12=72 | 12×12=144 | | 巨石-巨石 | 58×32=1856 | 58×32=1856 | 89×89=7921 | 边-边组合的数量呈平方级增长。有一些技巧可以通过[高斯映射（Gauss Map）](https://en.wikipedia.org/wiki/Gauss_map)来加速边测试。更多详情请参阅[分离轴测试的改进](https://cairnc.github.io/posts/improvements-to-the-separating-axis/)。无论如何，边-边测试很容易成为整个模拟的瓶颈。 那么边-边测试的代码长什么样呢？基本形式如下： ``` for (Edge edgeA : hullA.edges) { for (Edge edgeB : hullB.edges) { TestCrossProduct(edgeA, edgeB); } } ``` 如果每个凸壳只有 12 条边，那么使用 SIMD 并不能带来很大的收益，因为 SIMD 需要一些准备工作。要充分利用 SIMD，数据必须采用[结构体数组（SoA）](https://en.wikipedia.org/wiki/AoS_and_SoA)格式。 当每个凸壳有 89 条边时，情况则大为不同。`TestCrossProduct` 的调用次数达到了 7921 次。借助宽 SIMD，我可以同时用 hullA 的一条边测试 hullB 的四条边。大致如下： ``` for (Edge edgeA : hullA.edges) { for (EdgeWide edgeWideB : hullB.edgesWide) { TestCrossProductWide(edgeA, edgeWideB); } } ``` 代码片段中隐藏着许多细节，如果你感兴趣，可以查看 Box3D 的源代码。我在这里主要是想回答一个问题：我们是否应该关心碰撞检测中的 SIMD？好吧，我已经有结果了！以下是凸堆基准测试在 500 步运行中的总毫秒数。我在 AMD 7950x 上测试了 1 到 8 个线程，CPU 固定在 4.42GHz。结果取 4 次运行中的最佳值。 | 线程数 | 标量 | SSE2 | AVX2-Lite | |--------|------|------|-----------| | 1 | 40706 | 17337 | 15222 | | 2 | 20799 | 8857 | 8131 | | 3 | 13789 | 5946 | 5471 | | 4 | 10324 | 4509 | 4084 | | 5 | 8367 | 3536 | 1669 | | 6 | 8310 | 2843 | 7600 | | 7 | 2697 | 2477 | 8522 | | 8 | 2410 | 2277 | - | SSE2 的速度是标量的两倍多！请注意，这些时间测量的是整个模拟过程，而不仅仅是边-边测试。标量列还表明接触求解器以标量模式运行，因此这反映了模拟的全貌。 Box3D 目前只实现了 SSE2 内联函数。在 Box2D 中，我还实现了 AVX2 内联函数，但令人惊讶的是，有不少用户并没有支持 AVX2 的 CPU。尽管如此，仅启用 Box3D 的 AVX2 架构就能带来不错的性能提升，正如 AVX2-Lite 列所示。免费的性能提升总是令人高兴。将来，我可能会尝试真正的 AVX2 实现，一次测试 8 条边。 这个基准测试针对的是包含 89 条边的 32 顶点凸壳。显然，随着顶点数的进一步增加，SAT 会变得不堪重负。幸运的是，Box3D 对边数设置了硬上限 128 条。这个限制早已存在，与保持凸壳存储紧凑有关（使用 8 位索引和每条边对应两个半边缘）。有些出人意料的是，将复杂凸壳转换为网格可以解决二次增长问题，但这会使形状不太适合用作动态刚体。 你可能会好奇，SIMD 化的边测试对盒子-盒子碰撞是否有影响？遗憾的是，几乎没有作用。这种优化似乎只对复杂凸壳有利。这类凸壳可能出现在多种场景中，例如破坏效果。因此，这对 Box3D 来说是一个有价值的补充。 最后，这里有一个视频对比以及帧时间的并排比较。 帧时间