current community

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.
up vote 1 down vote favorite

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.

share|improve this question
1  
BTW, rotated rects/boxes are usually called OBBs (oriented bounding boxes), not AABBs...as the rotation means they're no longer axis-aligned. :) –  Nathan Reed Nov 13 '13 at 23:56
 
Thank you very much, I fixed that terminology and now you gave me something else to search for :) –  MindSeeker Nov 13 '13 at 23:58
add comment

1 Answer

up vote 2 down vote

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.

share|improve this answer
 
Thanks for your help! The problem with extruding an OBB along its linear velocity for a frame is that it merely gives a collision, not a time of collision (which I want). You addressed one other consequence of this in your third paragraph: false positives. I'll take a look at GJK and spacetime algorithms and report back if either looks appropriate for my situation, thank you for very much for your help! –  MindSeeker Nov 14 '13 at 0:14
 
Also: not worried about rotational velocity in the space of a frame. –  MindSeeker Nov 14 '13 at 0:17
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.