Generate potential line intersection between two aabb's

Math and Physics Programming

Started by slicer4ever July 31, 2012 11:56 PM

8 comments, last by slicer4ever 11 years, 8 months ago

6,773

Author

July 31, 2012 11:56 PM

Hello ppl, i'm working on some collision code for AABBxAABB along a path.

my first thought was to generate 8 lines for each corner of the AABB which is moving to x location, and the destination is offset by the aabb corner, and if their is a hit, then we move the AABB to the hitpoint - corner offset.

The problem with this method, is if i move through a smaller object, it can be completely missed by the aabbxaabb path function, so my current idea that i'm working on, is creating a single potential line that is most likly to intersect the other AABB. but i have only a vague idea how to pull this off.

here's an image of what i'd like to do:

Check out https://www.facebook.com/LiquidGames for some great games made by me on the Playstation Mobile market.

jefferytitan

2,525

August 01, 2012 12:43 AM

I am not an expert, but I believe that the point of considering the volume swept by the object is to check the whole volume for collisions, not just the lines on the edges. For example, you can test for collisions using 6 planes (the 4 sides in blue plus the two black end caps). There are also better algorithms documented out there, but the names escape me at the moment.

slicer4ever

6,773

Author

August 01, 2012 03:53 AM

so basically, if i understand you, generate a convex object to represent the volume of the entire path that the aabb will move through, and test that? that can work decently, as my sub collision system uses convex objects as a basis for better collision modeling/detection.

is their any paper on the subject for generating such a volume with 3D aabb cube's you could link me to, i can't seem to find anything.

Check out https://www.facebook.com/LiquidGames for some great games made by me on the Playstation Mobile market.

raigan

1,122

August 01, 2012 04:29 AM

If you *only* need AABB-vs-AABB, there is a very simple exact solution: you can perform a single ray-vs-AABB test.

Given AABBs A and B, with positions pA,pB, velocities vA,vB, and halfwidth vectors rA,rB: test the ray pA + t*(vA - vB) against the AABB centered at pB with halfwidth (rA+rB).

(It's late so I may have mixed something up, but the general idea is correct: shrink A down to a point, grow B by the amount you shrunk A, then sweep A (now a point) along its velocity relative to B)

If you need to sweep an AABB vs other convex shapes, I would recommend a swept separating axis theorem-based approach, it's perfect for exactly this job; this doc explains it pretty well I think: http://members.gamed...ATalgorithm.doc

Here's another tutorial which might be of interest: http://back2basic.ph...ision_using_SAT

jefferytitan

2,525

August 01, 2012 04:48 AM

@raigan: Thanks, SAT was what I was trying to recall!

raigan

1,122

August 01, 2012 01:30 PM

Seriously, if you only need AABB-AABB, use the ray-vs-AABB approach... it's much simpler!

slicer4ever

6,773

Author

August 02, 2012 02:29 AM

Seriously, if you only need AABB-AABB, use the ray-vs-AABB approach... it's much simpler!

Check out https://www.facebook.com/LiquidGames for some great games made by me on the Playstation Mobile market.

Cornstalks

7,033

August 02, 2012 02:39 AM

thanks mate, only one object is in motion, so i'll try your approach for sweeping A to B enlarged.

Just a note: even if both objects are in motion, you can take advantage of "relativity" here. Pretend A and B are both moving (with velocities vA and vB). Now when you do a swept collision test, you are allowed to pretend that one is standing still and one is moving. You can do it, for example, by pretending you are at object A. From object A's perspective, it isn't moving. Everything else is (by -vA, actually). So when you do the sweep test, just pretend A's velocity is 0 and B's velocity is vB - vA.

I know you said only one is moving, but this can be handy in the future.

[size=2][ I was ninja'd 71 times before I stopped counting a long time ago ] [ f.k.a. MikeTacular ] [ My Blog ] [ SWFer: Gaplessly looped MP3s in your Flash games ]

raigan

1,122

August 02, 2012 05:04 AM

[quote name='raigan' timestamp='1343827819' post='4965198']
Seriously, if you only need AABB-AABB, use the ray-vs-AABB approach... it's much simpler!

thanks mate, only one object is in motion, so i'll try your approach for sweeping A to B enlarged.
i'm just trying to wrap my mind around the idea of how enlarging b by A means i can successfully test the ray.
[/quote]

This should describe exactly the ray and AABB you need to test: the ray origin is pA and direction is (vA - vB); the AABB center is pB and halfwidth vector is (rA+rB).

The box positions are pA,pB, the box velocities are vA,vB, and the box halfwidth vectors are rA,rB. (I may have the relative velocities backwards, maybe you need to use (vB - vA), but the idea is that even if both boxes are moving, you can perform the test relative to one of them, and in that frame of reference only the other box is moving).

If you want to understand how you can shrink one box and grow the other, I think the term to google is "configuration space obstacle"? Or minkowski sum. If you consider two circles and sketch it out, it might make more sense.

slicer4ever

6,773

Author

August 02, 2012 06:52 PM

thanks for the info guys, i've got this up and working perfectly now=-).

Check out https://www.facebook.com/LiquidGames for some great games made by me on the Playstation Mobile market.

Generate potential line intersection between two aabb's

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Generate potential line intersection between two aabb's

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines