collision-detectiondistanceaabbconvex

3D continuous moving AABB against static convex polyhedron collision detection


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: enter image description here

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: enter image description here

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.


Solution

  • Hello yes such an algorithm exists and can be suprisingly fast. It uses the minkowski difference idea however there is no need to compute it completly, you just need a few points from the minkowski difference. The idea is tu use a support function which calculates the furthest point of a shape in a direction. For convex polyhedrons this function is easy to implement but if you are able to describe a non-polyhedron (but still convex) shape then you will also be able to use this algorithm. The algorithm basicly uses GJK to compute how far you can move the origin without intersecting the A - B shape. It does this until the origin is close enough to A - B which means to A and B are almost overlapping it stops. Here is a link to the full algorithm: 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=AOvVaw0OE9mgYb4NPQwAMqzLntRX

    This can be tricky to implemt because of the float errors but is pretty fast.