Sign in to follow this  
slicer4ever

Generate potential line intersection between two aabb's

Recommended Posts

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:

[img]http://i49.tinypic.com/5duq87.png[/img]

Share this post


Link to post
Share on other sites
I am not an expert, but I believe that the point of considering the volume swept by the object is to check the [i]whole volume[/i] 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.

Share this post


Link to post
Share on other sites
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. Edited by slicer4ever

Share this post


Link to post
Share on other sites
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: [url="http://members.gamedev.net/oliii/TheSweptSATalgorithm.doc"]http://members.gamed...ATalgorithm.doc[/url]

Here's another tutorial which might be of interest: [url="http://back2basic.phatcode.net/?Issue_%231:2D_Convex_Polygon_Collision_using_SAT"]http://back2basic.ph...ision_using_SAT[/url] Edited by raigan

Share this post


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

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.

Share this post


Link to post
Share on other sites
[quote name='slicer4ever' timestamp='1343874574' post='4965379']
thanks mate, only one object is in motion, so i'll try your approach for sweeping A to B enlarged.
[/quote]
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. Edited by Cornstalks

Share this post


Link to post
Share on other sites
[quote name='slicer4ever' timestamp='1343874574' post='4965379']
[quote name='raigan' timestamp='1343827819' post='4965198']
Seriously, if you only need AABB-AABB, use the ray-vs-AABB approach... it's much simpler!
[/quote]

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.

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