Sign in to follow this  
Matias Goldberg

Rectangle vs Rectangle Continuous collision detection?

Recommended Posts

Hi all! I've been searching for a continuous AABB vs AABB (2D) collision detection routine without luck (besides the trick of splitting the movement in several steps and do discrete collision detection). I want to believe I'm using the wrong key words in google I'm already writting one to gain some time. But there might be more efficient ways than the one I figgured out. Can someone point me to the right resources? Thanks! Dark Sylinc PS: I'm NOT looking for discrete collision detection. There's already a lot of info about it.

Share this post


Link to post
Share on other sites
I think you could do it as 8 ray-box checks. Check the 4 corners of box A against box B, then check the corners of box B against box A with opposite velocity.

Depending on how you do the ray-box check, it might miss if the boxes are already intersecting, but you could check for that at the beginning easily.

Share this post


Link to post
Share on other sites
Thanks, that's what I'm doing.
Actually I figgured out how to optimize it. I just use two ray-checks + finding if the boxes are already intersecting + checking if we really need to check corners of box B with box A in opposite direction.
It's just a less brute-force attempt to do it. And it's working great so far. But may be there was a way better to do it ;)

Thanks
Dark Sylinc

Share this post


Link to post
Share on other sites
You shouldn't need to use a feature-based test for this (that is, testing individual corners or edges of the box). Just use the SAT (separating axis test); it's well documented, and is fairly easy to implement for axis-aligned boxes.

I think there's even a description of the algorithm (along with sample code) in one of the articles in the 'collision detection' section of the article archives here on GDNet.

Share this post


Link to post
Share on other sites
Quote:
Original post by DekuTree64
Hmm, I think you could do one ray check actually, using the bloated shape technique. Add box A's extents onto box B's extents, and then treat box A as a point.
That's correct (the 'CSO raytracing' technique and the aforementioned continuous separating axis test are really just two different views of the same algorithm).

Share this post


Link to post
Share on other sites
Quote:
Original post by jyk
You shouldn't need to use a feature-based test for this (that is, testing individual corners or edges of the box). Just use the SAT (separating axis test); it's well documented, and is fairly easy to implement for axis-aligned boxes.

I think there's even a description of the algorithm (along with sample code) in one of the articles in the 'collision detection' section of the article archives here on GDNet.


Thanks! but looking here: http://www.harveycartel.org/metanet/tutorials/tutorialA.html
SAT is used for discrete collision tests.

Then it says:
Quote:
SECTION 5: Fast-Moving Objects

As mentioned above, small and/or fast-moving objects can produce problems when using a static collision test. There are several approaches that can be taken to handle such objects -- the simplest is to constrain your game design so that such objects aren't needed.

If you absolutely must have them, there are two common methods to deal with small and/or fast-moving objects:
swept-collision tests, and multisampling.


I find Multisampling an awfull technique. Sweeptests looks like a good approach

Yet I'm happy with my results: I've been doing some benchmarks and my approach is 2.2x faster than an 8-ray (brute-force) cast.
But I keep my mind open.

Thanks for the advice though
Dark Sylinc

Share this post


Link to post
Share on other sites
I think the raytracing approach is going to break down if you have rotation, though. :-/

If you don't allow rotation, your best bet might be to generate the two swept shapes and doing the SAT.

How many tests per second can you do with your code? With the naive version? Is it a performance bottleneck for your application?

Share this post


Link to post
Share on other sites
Quote:
Original post by ben_garney
I think the raytracing approach is going to break down if you have rotation, though. :-/

Most probably. Luckily me, they won't rotate

Quote:
Original post by ben_garney
How many tests per second can you do with your code? With the naive version? Is it a performance bottleneck for your application?

I've already made up a simple bench test. I'll post the results when I run it (I'm not in my PC right now).

Cheers
Dark Sylinc

Share this post


Link to post
Share on other sites
Quote:
Thanks! but looking here: http://www.harveycartel.org/metanet/tutorials/tutorialA.html
SAT is used for discrete collision tests.
The tutorial you mention only covers the discrete SAT (IIRC), but the SAT can be extended to support continuous collision detection as well. (Again, I believe there's an example implementation somewhere in the article archives here on GDNet.)

You might find it more straightforward to implement the test as DekuTree64 suggested, for which you'd only need a ray-box raytracing function. In any case, even though you say your current implementation seems to be working, you might post a description of it; it may be that the algorithm you're using has failure cases that you haven't encountered yet (and that we might be able to point out).

Share this post


Link to post
Share on other sites
The results:

Worst case scenario:
Algorithm 01: 7.890.504 collision tests per second
Algorithm 02: 9.182.391 collision tests per second
Brute-force: 4.168.923 collision tests per second

Best case scenario:
Algorithm 01: 23.755.091 collision tests per second
Algorithm 02: 10.597.205 collision tests per second
Brute-force: 17.203.685 collision tests per second

"Algorithm 02" actually has an add-on which algorithm 01 doesn't have. I've been thinking, doing some maths, and if I'm right, it should be working always. But if I'm wrong, it could cause false negatives.

These tests were run on an Athlon64X2 5000+ @2661Mhz (using one core). 32-Bit OS version. Times were measured using QueryPerformanceCounter.

As you'll see, A01 performs well on all situation, where A02 doesn't. The add-on A02 has is computationally expensive, but it can avoid us doing a lot of ray castings, there's where the performance difference lies.

What is the difference between "Best case" and "Worst case" scenarios? Both benchs were made by repeating the same collision test 50.000.000 times.
"Worst case" is a case were all 8 rays were casted (because there is no collision)
"Best case" is a case were the 1st ray fails the collision test and therefore we can stop right now.

Quote:
Original post by jyk
SAT can be extended to support continuous collision detection as well. (Again, I believe there's an example implementation somewhere in the article archives here on GDNet.)

Besides the Swept algorithm? or that's the one you're talking about?
I'm still searching for that GDNet article. If someone finds it, I would appreciate if he/she could post it.
I found a Gamasutra article about the Swept test. Is that what you mean?

Quote:
Original post by jyk
In any case, even though you say your current implementation seems to be working, you might post a description of it; it may be that the algorithm you're using has failure cases that you haven't encountered yet (and that we might be able to point out).


That's what I'm afraid of. I'm writing a description of it. Be patient, in a while I'll post it

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this