2D Rectangle/Circle Continuous Collision Detection

Question

I'm looking for a fast 2D continuous collision detection algorithm for circles and rotated rects. It needs to determine the time of collision. Both shapes may be moving at high speed, so the algorithm should not assume that one is stationary.

What I found so far (what I'm not looking for):

• I've found several tutorials for swept tests for AABB's, but these all involved axis-aligned (not rotated) rects.
• I've found and implemented a separating axis theorem (SAT) algorithm to determine if rotated rects are intersecting with other rects or circles, but obviously that is not continuous.
• I'm not looking for reduced-time-interval-based tests here; the objects' speeds are potentially very high so that kind of inelegant solution is impractical due to computational costs.

What I already have:

• I already have continuous collision detection between circles implemented (Small, High-Speed Object Collisions: Avoiding Tunneling). Now I just need the circle/rect and rect/rect versions.
• As I said above, I also already have the SAT implemented to detect circle/rect and rect/rect intersection (but obviously that's not continuous).

Thank you very much for your time and help!

Edit: I'm not worried about rotational velocity over the space of a frame.

Answer 1

I forgot to come back to this question when I arrived at an answer, but this has gotten a decent amount of views over time, so better late (even 2 years late) than never! First, prerequisites:

Prerequisites:

First, one has to be able to calculate the time of collision (TOC) of two circles. Step 3 of this question Small, High-Speed Object Collisions: Avoiding Tunneling provides an adequate formula.

Next: be able to find a point/circle TOC: simply take the equation linked above and set one of the circles' radii to 0 to represent the point.

Next: be able to find a point/line segment TOC. A simple way to do this (I'm sure there are better ways, this is just a starting point):

• Shift all relative motion to the point, so you have a moving point and a "stationary" line.
• The point's path (described by a line) intersects the line containing the line segment (or it is parallel). For line/line intersection, takes equations Ax + By = C (for line segment...A=y2-y1, B=x1-x2, and C = x1*y2-x2*y1) and paramaterized equation Px + Vxt and Py + Vyt for moving point and solve for t: (C - APx - BPy) / (AVx + BVy). I chose these forms so I don't have deal with horizontal/vertical cases. If the denom is 0, the lines are parallel.
• Once you have a time/point of intersection, check and see if that point lies on the line segment.

The Solution:

Circle/Rect:

"Reduce" the circle to a point, and "grow" the rectangle by radius r of the circle. The result is that the 4 sides (red) of the rect are translated out (orange) and the corners are expanded out and rounded by radius r. We know how to find the TOC for point/circle and point/line segments, so find the earliest TOC of the point with those 8 shapes representing the surface of our new shape (the 4 orange lines and the 4 blue circles). That is your answer. (There may the collisions with parts of the circles that are not on the surface, but your algorithm will ignore those automatically since the point will already have penetrated the surface at an earlier time). If there is no TOC, then there is no collision. Beware of "past" collisions when the objects are moving away from each other.

Rect/rect:

Start with one rect as the "point" rect and the other as the "side" rect. Find the TOC (if it exists) with each point on the point rect compared to each side of the side rect. That's 16 checks. Switch the rects and repeat for a total of 32 checks. The earliest non-imaginary and non-past TOC (if it exists) is the TOC. Note that any "side-side" collision of two rects can be treated as a "point-side" collision, and that is how this algorithm handles it.

Considerations:

This may all seem extremely inefficient, but keep three things in mind:

• Good broadphase and medium-phase collision detection is important to make sure you are doing all of these expensive calculations as little as possible
• Directional optimizations are possible (e.g. only check a few of those 32 rect/rect pairs that are facing in the appropriate directions)
• These are extreme algorithms, designed for small objects colliding at extraordinary speeds. If the situation truly calls for an algorithm like this (e.g. 2 meter-sized objects colliding at relative speeds of 1000's of km's per second), these "inefficient" algorithms will be much better than most traditional alternatives.

Answer 2

If you already have SAT working, then you can pretty easily extrude an OBB along its linear velocity for a frame (i.e. create a swept OBB). The result will be a polyhedron, so you can use SAT with it. This only handles linear velocity, though, not rotational velocity. That's quite a bit harder because a rotating OBB sweeps out a volume that isn't a polyhedron.

Another thing to look into is the GJK algorithm. It uses a different representation of shapes (i.e. not polygonal) so it may be easier to use with rotational velocity. I'm not familiar with the state of the art here though.

One problem with using swept shapes and high-speed objects is that a collision may be detected even when the objects should miss each other, if their trajectories during the course of a frame happen to intersect. I'm not aware of any approach to solve this other than using finer timesteps, or using 4D (spacetime) collision detection.