转载自：<https://web.archive.org/web/20161004195055/http://howlingmoonsoftware.com/wordpress/enhanced-collision-algorithms-for-chipmunk-6-2>
翻译见后文

There are some notable limitations with Chipmunk’s current code that a lot of people run into. Deep poly/poly or poly/segment collisions could produce a lot of contact points with wacky positions and normals which were difficult to filter sensibly. This was preventing me from implementing smoothed terrain collision feature that I wanted (fix the issue where shapes can catch on the “cracks” between the endpoints of segment shapes). Also, until recently line segment shapes couldn’t collide against other line segment shapes even if they had a nice fat beveling radius. They can now thanks to a patch from LegoCylon, but they have the same issues as above, generating too many points with wacky normals. I also had no way to calculate the closest points between two shapes preventing the implementation of polygon shapes with a beveling radius. Yet another issue is that the collision depth for all of the contacts is assigned the minimum separating distance determined by SAT. This can cause contacts to pop when driven together by a large force. Lastly, calculating the closest points is also a stepping stone on the way to get proper swept collision support in Chipmunk in the future.

For some time now, I’ve been quietly toiling away on a Chipmunk branch to improve the collision detection and fix all of these issues. I’ve implemented the GJK/EPA collision detection algorithms as well as a completely new contact point generation algorithm. After struggling on and off for a few months with a number of issues (getting stuck in infinite recursion/loops, issues with caching, issues with floating point precision, suboptimal performance, etc… ugh), it finally seems to be working to my expectations! The performance is about the same as my old SAT based collision code, maybe 10% faster or slower in some cases. Segment to segment collisions work perfectly as do beveled polygons. Smoothed terrain collisions are even working, although the API to define them is a little awkward right now.

All collision types.
Beveled line segments colliding with other shapes!

GJK:

The aptly named Gilbert–Johnson–Keerthi algorithm is what calculates the closest points between two convex shapes. My implementation preserves the winding of the vertexes it returns which helps avoid precision issues when calculating the separating axis of shapes that are very close together or touching exactly. With the correct winding, you can assume the edge you are given lies along a contour in the gradient of the distance field of the minkowski difference. I’ve also modified the bounding box tree to cache GJK solution. Then in the next frame, you can use that as the starting point. It’s a classic trick that makes GJK generally require only a single iteration per pair of colliding objects.

GJK example
GJK is rather abstract, but it calculates the closest points between two shapes by finding the distance between the minkowski difference of two shapes (the red polygon) and the origin (the big red dot). If you look closely, the red shape is a flipped version of the pentagon with the little triangle tacked on to all it’s corners. It’s one of the coolest and most bizarre algorithms I’ve ever seen. 😀 I’ll probably make a blog entry about my implementation eventually too.

EPA:

EPA stands for Erik-Peterson-Anders… Nah, it stands for Expanding Polytope Algorithm and is a very close cousin to GJK. While GJK can detect the distance between two shapes, EPA is what you can use to find the minimum separating axis when they are overlapping. It’s sort of the opposite of the closest points. It gives you the distance and direction to slide the two shapes to bring them apart (as well as which points on the surface will be touching). It’s not quite as efficient as GJK and it’s an extra step to run which has the interesting effect of making collision detection of beveled polygons more efficient than regular hard edged ones. This is one thing I’m not completely happy with. Polygon heavy simulations will generally run slower than with 6.1 unless you enable some beveling. It’s not a lot slower, but I don’t like taking steps backwards. On the other hand, it will be much easier to apply SIMD to the hotspots shared by the GJK/EPA code than my previous SAT based code.

Contact Points:

Having new collision detection algorithms is neat and all, but that didn’t solve the biggest (and hardest) issue; my contact point generation algorithm sucked! Actually, it worked pretty good. It has stayed mostly unchanged for 6 years now, but it has also accumulated some strange workarounds for rare conditions that it didn’t handle well. The workarounds sometimes produced strange results (like too many contact points or weird normals…). They also made it practically impossible to add the smoothed terrain collision feature.

In the new collision detection code, polygon to polygon and polygon to segment collisions are treated exactly the same. They pass through the same GJK/EPA steps and end up being passed to the same contact handling code as a pair of colliding edges. It handles collisions with endcaps nicely, always generates either 1 or 2 contact points for the pair, and uses the minimum separating axis for the normals. It’s all very predictable and made the smoothed terrain collisions go pretty easily. It only took me about 10 iterations of ideas for how to calculate the contact points before I got something I was happy with. -_- It really ended up being much, much harder than I expected for something that seems so simple in concept.

The implementation works somewhat similarly to Erin Catto’s contact clipping algorithm, although adding support for beveling (without causing popping contacts) and contact id’s made it quite a bit harder. There are some pretty significant differences now. Perhaps that is another good post for another day.

Coming to a Branch Near You!

The branch is on GitHub here if you want to take a peek and poke around. It’s been a pretty big change, and hasn’t been extensively tested yet. I wouldn’t recommend releasing anything based on it quite yet, but it should be plenty stable for development work, and should even fix a number of existing issues. I’d certainly appreciate feedback!

全文翻译（使用有道机器翻译）：

Chipmunk当前的代码有一些值得注意的限制，很多人都会遇到这些限制。深度poly/poly或poly/segment碰撞会产生大量具有古怪位置和法线的接触点，难以合理地过滤。这阻碍了我执行我想要的平滑地形碰撞功能(修复形状可以捕捉到分段形状端点之间的“裂缝”的问题)。此外，直到最近，线段形状不能与其他线段形状碰撞，即使它们有一个很好的斜角半径。他们现在可以感谢乐高赛昂的补丁，但他们有同样的问题，与古怪的法线产生太多的点。我也没有办法计算两个形状之间最接近的点，从而防止实现具有斜面半径的多边形形状。然而，另一个问题是，所有触点的碰撞深度都是由SAT确定的最小分离距离。这可能导致触点在受到很大的力驱动时爆裂。最后，计算最近点也是在未来的《花栗鼠》(注：指Chipmunk，pymunk基于Chipmunk)中获得适当的扫掠碰撞支持的垫脚石。

一段时间以来，我一直在花栗鼠分支上默默工作，以改进碰撞检测并修复所有这些问题。我已经实现了GJK/EPA碰撞检测算法以及一个全新的接触点生成算法。在与一些问题(陷入无限递归/循环，缓存问题，浮点精度问题，次优性能等问题)断断续续地挣扎了几个月之后，它终于达到了我的期望!性能与我以前基于SAT的碰撞代码大致相同，在某些情况下可能快10%或慢10%。段与段之间的碰撞就像斜面多边形一样完美。平滑的地形碰撞甚至可以工作，尽管定义它们的API现在有点笨拙。

所有碰撞类型。
斜面线段与其他形状碰撞!

GJK:

Gilbert-Johnson-Keerthi算法是计算两个凸形之间最近点的算法。我的实现保留了它返回的顶点的缠绕，这有助于在计算非常接近或完全接触的形状的分离轴时避免精度问题。有了正确的缠绕，你可以假设你得到的边缘是沿着闵可夫斯基差距离场梯度的等高线。我还修改了边界框树来缓存GJK解决方案。然后在下一帧中，你可以用它作为起点。这是一个经典的技巧，使得GJK通常只需要对每一对碰撞对象进行一次迭代。

GJK例子
GJK相当抽象，但它通过寻找两个形状(红色多边形)的闵可夫斯基差与原点(大红点)之间的距离来计算两个形状之间的最近点。如果你仔细观察，红色的形状是五边形的翻转版本，所有的角上都有一个小三角形。这是我见过的最酷、最奇怪的算法之一。😀我可能最终也会写一篇关于我的实现的博文。

EPA:

EPA代表埃里克-彼得森-安德斯，不，它代表扩展多面体算法，是GJK的近亲。虽然GJK可以检测两个形状之间的距离，但EPA可以用于在它们重叠时找到最小分离轴。这和最近的点正好相反。它给你的距离和方向滑动两个形状，使他们分开(以及哪些点在表面上将接触)。它不像GJK那么有效，而且它是一个额外的步骤，它有一个有趣的效果，使斜面多边形的碰撞检测比常规硬边多边形更有效。这是我不太满意的一件事。多边形繁重的模拟通常会比6.1运行得慢，除非你启用一些斜面。它并没有慢很多，但我不喜欢倒退。另一方面，将SIMD应用于GJK/EPA代码共享的热点要比我以前基于SAT的代码容易得多。

接触点:

拥有新的碰撞检测算法固然很简单，但这并不能解决最大(也是最难)的问题;我的接触点生成算法烂透了!实际上，效果还不错。6年来，它基本上保持不变，但它也积累了一些奇怪的解决方案，用于处理一些罕见的情况。变通方法有时会产生奇怪的结果(比如太多的接触点或奇怪的法线……)。这也使得添加平滑地形碰撞功能变得不可能。

在新的碰撞检测代码中，多边形到多边形和多边形到线段的碰撞被完全相同地处理。它们通过相同的GJK/EPA步骤并最终被通过