Jump to content
  • Advertisement
Sign in to follow this  
Matias Goldberg

Rectangle vs Rectangle Continuous collision detection?

This topic is 3693 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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
Advertisement
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
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.

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
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!