[help] OBB (Orientated Bounding Box) Collisions

[chriserrorplain]

ok...so after a few hours of pounding my head against the Internet and damning my lacking Maths skills, I need to ask some of you guys if you can help.

I am trying to detect a collision between bounding boxes which can be rotated. I currently have got the corners of box boxes and have also got the min / max x and y, but I am just reeeally struggling in getting the final algorith to return whether they intersect. Any help will so appreciated that I don't think I would be able to put it into words....


ChrisError x

[Xploder]

Hey chris you need to look into projecting boxes onto a line.
If the lines of the squished boxes overlap along all normals, you have a colision.
This method can be used for pretty much any shape: http://gpwiki.org/index.php/VB:Tutor...tion_Detection

[tonypa]

In theory (not talking about separating axes here) 2 rotated boxes are overlapped if at least one side of box A is intersecting with any side of box B. Create lines representing each sides and find if they intersect using lineToLine intersection. This will need 16 tests max (4 sides of box A each tested against 4 sides of box B).

Its also possible that one box is completely inside other box. Not sure if you consider it collision or if its even possible in your game.

[UnknownGuy]

Hey Chris,

From years ago Blink(I believe) posted an example of this. I still have an .fla that I modified using it, which shows it working.

Here it is online in action: http://www.whatboxstudios.com/FK/collision8.swf

And here is the source: http://www.whatboxstudios.com/FK/collision8.fla

The algorithm I never really understood, and it is uses the fact there is a nested movieclip and gets the size of the width once rotated I believe(or some trick like that), which could be done another way.

Hope that helps!

[newblack]

yeah, you definitely don't want to do 16 line intersection tests, this is a simple separating axis test:

1. transform each box's vertices into global coordinates
2. use each adjacent pair of vertices to define an edge vector for each edge
3. define a potentially separating axis as the vector perpendicular to each edge
4. project all vertices onto this axis, storing a minimum and maximum for each box (if you're only interested in whether they are overlapping and not by how much, you only need to solve for the dot product instead of projection)
5. if the 2 ranges don't overlap, the boxes are not intersecting
6. if they do, proceed to the next set (2 vertices -> edge -> normal)
7. if the ranges overlap on all edge normals, they are intersecting

[Incrue]

http://www.metanetsoftware.com/technique/tutorialA.html

or you could use box2d

[chriserrorplain]

thanks for the all the help guys. Trying to dot his has finally forced me to sit down for a few hours and learn the theory and not just find a solution, so I spent a good part fo yesterday working through Tony PA's Vector tutorials with pen and paper, and now later on today I am going to try that link you sent Xploder, it seems very well written and not _too_ complicated. Thanks for all the help guys, btw if you wanna see what it's for, I'm making a MicroMachines-esque game called 'Toy Town Racers' you can see and early alpha of the engine here :

http://www.kill5.com/games/ttr/
(cursors to control car)


ChrisError x

[lesli_felix]

if the distance between a corner of box A and *all* points of box B is less than the diagonal of box B, then they intersect.

remember to run the check the other way around, making sure that no points of box B intersect box A

that should do it.

[lesli_felix]

if the distance between a corner of box A and *all* points of box B is less than the diagonal of box B, then they intersect.

My bad, that would be very approximate.

The best way is to consider one of the boxes level with the ground, then finding intersecting points is easy. I've done this before, I just can't remember how, but it wasn't that difficult.

[dandylion13]

Just for the record, here is the SAT based solution:

http://www.euclideanspace.com/threed...ions/index.htm

If you know your vector math, it's actually pretty easy!