SIMD for Collision
SIMD for Collision
In a previous post, SIMD Matters, I discussed the big wins I got from graph coloring to make the contact solver faster. That same approach exists in Box3D. I like to call this approach “wide SIMD”. The idea is to process multiple work units at the same time. In the contact solver, this means solving four contact points at the same time. This is different from “narrow SIMD”, where a 3-vector (xyz) is put into a SIMD register and then standard vector math is expressed as SIMD intrinsics. Narrow SIMD can be useful, but the gains are not as obvious.
在之前的文章《SIMD 的重要性》(SIMD Matters) 中，我讨论了通过图着色技术显著提升接触求解器速度的成果。同样的方法也存在于 Box3D 中。我喜欢将这种方法称为“宽 SIMD”(wide SIMD)。其核心思想是同时处理多个工作单元。在接触求解器中，这意味着同时求解四个接触点。这与“窄 SIMD”(narrow SIMD) 不同，后者是将一个 3 维向量 (xyz) 放入 SIMD 寄存器，然后将标准向量数学表达为 SIMD 内在函数。窄 SIMD 虽然有用，但收益并不明显。
In 3D, there is an opportunity for using wide SIMD that doesn’t exist in 2D. Consider the convex pile benchmark ported from PEEL. This benchmark drops 5120 convex hulls, each with 32 points. Box3D treats boxes as hulls, and many of the benchmarks use boxes. The performance with boxes has been good, and typically most of the cost is not in the narrow phase. But the 32-point hull is a different beast. Let’s call it “boulder”. The table below shows the hull details for a box compared to the boulder.
在 3D 领域，存在一种 2D 中所没有的利用宽 SIMD 的机会。以从 PEEL 移植的凸包堆叠基准测试为例，该测试会掉落 5120 个凸包，每个凸包有 32 个点。Box3D 将长方体视为凸包，且许多基准测试都使用长方体。长方体的性能表现一直很好，通常大部分开销并不在窄相检测阶段。但 32 点的凸包则是另一回事，我们称之为“巨石”(boulder)。下表展示了长方体与“巨石”的细节对比。
| Hull | Vertices | Faces | Edges |
|---|---|---|---|
| Box | 8 | 6 | 12 |
| Boulder | 32 | 59 | 89 |
Box3D uses the Separating Axis Test (SAT) for collision detection. Using SAT, I can find the best features to use for pushing the shapes apart and precisely how far apart they need to be pushed to remove overlap. Furthermore, I use these results to compute the contact normal and the contact points. Other physics engines may use the distance algorithm GJK instead, with an overlap fallback such as the Expanding Polytope Algorithm (EPA).
Box3D 使用分离轴定理 (SAT) 进行碰撞检测。通过 SAT，我可以找到将形状推开所需的最佳特征，并精确计算出为了消除重叠需要推开的距离。此外，我利用这些结果来计算接触法线和接触点。其他物理引擎可能会改用 GJK 距离算法，并配合重叠回退机制，例如扩展多面体算法 (EPA)。
I’m a big fan of SAT for convex hull collision because it doesn’t require a collision margin. Shapes can rest directly on each other. The GJK and EPA combo usually tries to keep shapes slightly separated to keep them in the GJK region, which is faster. This can lead to visual gaps. Also, EPA can be numerically brittle, and often physics engines will need a fallback if EPA fails: a fallback for the fallback. EPA is essentially an algorithm for computing a convex hull, and the input data can be flat slivers. That is a challenging scenario for convex hull computation. Hence the need for a second fallback.
我非常推崇将 SAT 用于凸包碰撞，因为它不需要碰撞余量，形状可以直接静止接触。GJK 和 EPA 的组合通常试图让形状保持轻微分离，以使其处于 GJK 区域内，这样速度更快，但这会导致视觉上的缝隙。此外，EPA 在数值上可能很脆弱，物理引擎通常需要在 EPA 失败时提供回退方案，甚至需要“回退的回退”。EPA 本质上是一种计算凸包的算法，而输入数据可能是扁平的碎片，这对凸包计算来说是一个极具挑战性的场景，因此需要第二个回退方案。
Unfortunately, SAT in 3D has quadratic complexity. With two hulls A and B, the collision algorithm must test the faces of hull A against the vertices of hull B, the faces of hull B against the vertices of hull A, and the edges of hull A against the edges of hull B. In the worst case, every combination must be evaluated.
不幸的是，3D 中的 SAT 具有二次复杂度。对于两个凸包 A 和 B，碰撞算法必须测试 A 的面与 B 的顶点、B 的面与 A 的顶点，以及 A 的边与 B 的边。在最坏的情况下，必须评估每一种组合。
| Combination | Face-Vertex | Vertex-Face | Edge-Edge |
|---|---|---|---|
| Box-Box | 6 | 6 | 144 |
| Boulder-Boulder | 59 | 59 | 7921 |
The number of edge-edge combinations grows quadratically. There are some tricks to speed up the edge tests using the Gauss Map. See Improvements to the Separating Axis Test for more details. Regardless, the edge-edge test can easily dominate the entire simulation. So what does this edge-edge code look like? At a basic level, it looks like this:
边与边的组合数量呈二次方增长。利用高斯映射 (Gauss Map) 可以通过一些技巧来加速边测试（详情请参阅《分离轴测试的改进》）。无论如何，边与边的测试很容易占据整个模拟过程的主导地位。那么这段边测试代码是什么样的呢？在基础层面上，它看起来像这样：
for (Edge edgeA : hullA.edges) {
for (Edge edgeB : hullB.edges) {
TestCrossProduct(edgeA, edgeB);
}
}If there are just 12 edges in each hull, doing SIMD on this is not a big win because SIMD requires some setup work. For SIMD to work well, the data needs to be in structure of arrays format (SoA). With 89 edges in each hull, the story changes drastically. There are 7921 calls to TestCrossProduct. With wide SIMD, I can test one edge of hullA against four edges of hullB simultaneously. It looks sort of like this:
如果每个凸包只有 12 条边，使用 SIMD 并不会带来太大收益，因为 SIMD 需要一些设置工作。为了让 SIMD 发挥良好作用，数据需要采用结构数组 (SoA) 格式。当每个凸包有 89 条边时，情况就大不相同了。此时会有 7921 次 TestCrossProduct 调用。通过宽 SIMD，我可以同时测试 hullA 的一条边与 hullB 的四条边。它看起来大致如下：
for (Edge edgeA : hullA.edges) {
for (EdgeWide edgeWideB : hullB.edgesWide) {
TestCrossProductWide(edgeA, edgeWideB);
}
}There are a lot of hidden details in the snippet, and you can look at the Box3D code if you are curious. But I’m here to answer the question: should we care about SIMD for collision detection? Well, I have results! These are the results for the convex pile benchmark with the total milliseconds for a 500-step run. I tested 1 to 8 threads on an AMD 7950x with the CPU pegged at 4.42GHz. The results are the best of 4 runs.
这段代码片段中隐藏了许多细节，如果你感兴趣，可以查看 Box3D 的源代码。但我在这里是为了回答这个问题：我们应该关心碰撞检测的 SIMD 优化吗？好吧，我有结果了！以下是凸包堆叠基准测试在 500 步运行中的总耗时（毫秒）。我在 AMD 7950x 上进行了测试，CPU 锁定在 4.42GHz，测试了 1 到 8 个线程。结果取 4 次运行中的最佳值。
| Threads | Scalar | SSE2 | AVX2-Lite |
|---|---|---|---|
| 1 | 40706 | 17337 | 15762 |
| 2 | 20799 | 8857 | 8131 |
| 3 | 13789 | 5946 | 5471 |
| 4 | 10324 | 4509 | 4084 |
| 5 | 8359 | 3675 | 3361 |
| 6 | 6958 | 3106 | 2843 |
| 7 | 6006 | 2697 | 2477 |
| 8 | 5292 | 2410 | 2277 |
SSE2 is over twice as fast as scalar! Keep in mind these timings are for the entire simulation, not just the edge-edge test. The scalar column also indicates that the contact solver runs in scalar mode. So this is the full picture of the simulation. Box3D only implements SSE2 intrinsics. In Box2D I have AVX2 intrinsics as well, but there were a surprising number of users without AVX2-capable CPUs. Nevertheless, just enabling the AVX2 architecture in Box3D gives a nice gain, as indicated in the AVX2-Lite column. Free performance gains are great to see.
SSE2 的速度比标量快了两倍多！请记住，这些时间是整个模拟过程的耗时，而不仅仅是边测试。标量列也表明接触求解器是在标量模式下运行的，因此这反映了模拟的整体情况。Box3D 目前仅实现了 SSE2 内在函数。在 Box2D 中我也有 AVX2 内在函数，但令人惊讶的是，有相当多的用户使用的 CPU 不支持 AVX2。尽管如此，正如 AVX2-Lite 列所示，仅在 Box3D 中启用 AVX2 架构就能带来不错的收益。能看到免费的性能提升总是件好事。
In the future, I may try a real AVX2 implementation testing 8 edges at a time. This benchmark represents a 32-point hull with 89 edges. Surely SAT will be overrun as the point count grows further. Well, fortunately, Box3D has a hard 128-edge limit. This limit already existed and has to do with keeping the hull storage compact (8-bit indices and two half-edges per edge). Somewhat surprisingly, converting complex hulls to meshes can solve the quadratic growth problem, but it makes the shape less suitable for a dynamic body.
未来，我可能会尝试真正的 AVX2 实现，一次测试 8 条边。这个基准测试代表了一个拥有 89 条边的 32 点凸包。随着点数的进一步增加，SAT 肯定会不堪重负。好在 Box3D 有一个 128 条边的硬性限制。这个限制早已存在，主要是为了保持凸包存储的紧凑性（8 位索引和每条边两个半边）。令人惊讶的是，将复杂凸包转换为网格可以解决二次增长问题，但这会使形状不太适合作为动态刚体。
You may wonder if the SIMD edge tests moved the needle on box-box. Sadly it has almost no effect. This optimization seems to only benefit complex hulls. Such hulls can come up in several scenarios, such as destruction. So it is a worthy addition to Box3D. Finally, here is a video comparison and a side-by-side of the frame timings.
你可能想知道 SIMD 边测试对长方体碰撞是否有帮助。遗憾的是，它几乎没有影响。这种优化似乎只对复杂凸包有益。这类凸包在某些场景（如物体破碎）中会出现，因此它是 Box3D 中一项值得添加的功能。最后，这里是视频对比和帧时间对比。