•      Sign In
• Create Account

# Generate potential line intersection between two aabb's

Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

9 replies to this topic

### #1slicer4ever  Crossbones+   -  Reputation: 2208

Like
0Likes
Like

Posted 31 July 2012 - 05: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.

Sponsor:

### #2jefferytitan  Members   -  Reputation: 1039

Like
0Likes
Like

Posted 31 July 2012 - 06:43 PM

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.

### #3slicer4ever  Crossbones+   -  Reputation: 2208

Like
0Likes
Like

Posted 31 July 2012 - 09:53 PM

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, 31 July 2012 - 09:54 PM.

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

### #4raigan  Members   -  Reputation: 487

Like
2Likes
Like

Posted 31 July 2012 - 10:29 PM

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

Edited by raigan, 31 July 2012 - 10:30 PM.

### #5jefferytitan  Members   -  Reputation: 1039

Like
1Likes
Like

Posted 31 July 2012 - 10:48 PM

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

### #6raigan  Members   -  Reputation: 487

Like
1Likes
Like

Posted 01 August 2012 - 07:30 AM

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

### #7slicer4ever  Crossbones+   -  Reputation: 2208

Like
0Likes
Like

Posted 01 August 2012 - 08:29 PM

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.
Check out https://www.facebook.com/LiquidGames for some great games made by me on the Playstation Mobile market.

### #8Cornstalks  Crossbones+   -  Reputation: 6807

Like
1Likes
Like

Posted 01 August 2012 - 08:39 PM

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.

Edited by Cornstalks, 01 August 2012 - 08:40 PM.

[ 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 ]

### #9raigan  Members   -  Reputation: 487

Like
0Likes
Like

Posted 01 August 2012 - 11:04 PM

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.

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.

### #10slicer4ever  Crossbones+   -  Reputation: 2208

Like
0Likes
Like

Posted 02 August 2012 - 12: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.

Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

PARTNERS