Continuous Collision Detection in 3D for Two Convex Polyhedra

Question

For a collision check I need to calculate time when two convex polyhedra intersect if one of them is moving along a straight line. Currently, I have:

1. Input: Convex polyhedron defined as a set of points of one object A and its movement direction.
2. Input: Convex polyhedron defined as a set of points of second object B
3. Calculate Minkowski sum of the two sets of points C, |C| = |A| * |B|
4. Calculate triangulated convex hull of C (using QuickHull)
5. Line intersection against triangles of the convex hull and store minimum and maximum distance along line.

This all works, but is slow. Especially the step to calculate the triangulated convex hull.

I wonder if there is a faster way to calculate the ray-convex polyhedron intersection from the set of points without calculating the triangulated convex hull. I could get the input as planes (plane equations) if it helps.

Answer 1

Solved by separation axis theorem:

1. Input: convex collision volumes as both points and plane equations
2. For each plane in both collision volumes, calculate shift along the movement direction when each plane becomes a separation plane (vertices of the other collision volume are all in front of the plane).
3. Calculate interval of shift when there is no separation plane. This can be done in place by keeping track of minimum and maximum values encountered.

Compared to the original solution:

• Theoretical complexity down from O(N log N) to O(N), where N = |C| = |A| * |B|
• Works in place - no memory allocation