collision-detection - 3D continuous moving AABB against static convex polyhedron collision detection

Question

I am currently trying to implement a simple continuous collision detection system. I wondered whether it was possible, for a moving AABB, to compute the distance it can translate in an arbitrary direction d before it intersects a convex polyhedron. Here is a simple explanation in 2D:

What I want here is the length of the green lines (the orange AABB is the initial position, and the red AABB is the position where both colliders intersect).

This is also equivalent to trying to raycast the minkowski difference A⊕-B from the origin in the direction d, where A is my static convex polyhedron and B my moving AABB:

But computing a minkowski difference seems to be really performance-consuming, so I would like to know if a fast algorithm for doing that exists.

When Googling, I saw an algorithm to do that called GJK, but it only seems to return the overall minimum distance, and not the directional distance.

Thanks in advance for your answers!

PS: Please excuse my poor english and my total lack of artistic talent using paint.

Answer 1

你好，是的，这样的算法存在并且速度惊人。它使用了 minkowski 差分思想，但是不需要完全计算它，您只需要从 minkowski 差分中提取几个点。这个想法是你使用一个支持函数来计算一个形状在一个方向上的最远点。对于凸多面体，这个函数很容易实现，但是如果你能够描述一个非多面体（但仍然是凸的）形状，那么你也可以使用这个算法。该算法基本上使用 GJK 来计算在不与 A - B 形状相交的情况下您可以将原点移动多远。它这样做直到原点足够接近 A - B，这意味着 A 和 B 几乎重叠它停止。这是完整算法的链接：https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&ved=2ahUKEwjx38Cx0u7jAhXG4IUKHQHGD4YQFjAAegQIABAC&url=http%3A%2F%2Fdtecta.com%2Fpapers%2Fjgt04raycast.pdf&usg=AOvVawLOE9mgYb4NPQwAMq

由于浮动错误，这可能很难实现，但速度非常快。