Tell me more ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.
up vote 5 down vote favorite
2

Say you have two Bounding Box Objects each of them storing the current vertices of the box in a vector with all the vertices of the object rotated and translated relative to a common axis.

Here is an image to illustrate my problem:

How can I work out if the two OBB's are overlapping any links to help explain the solution to the problem would be welcome. Nothing too convoluted please...

share|improve this question

3 Answers

up vote 3 down vote accepted

Take a look at SAT (Separating Axis Theorem):

share|improve this answer
The codezealot example is good, but it fails to explain how to deal with the situation in Figure 6; where all projected axii (from edges) overlap, yet the shapes do not collide. The axii perpendicular to those edges must also be tested. This case is also shown in the AABB v Triangle example on this page: metanetsoftware.com/technique/tutorialA.html. – Daniel Mar 12 '12 at 14:50
What? I don't see any axes overlapping in figure 6, and the AABB vs Triangle one just has some overlapping. What do you mean? – TravisG Mar 12 '12 at 22:19
@Heishe, in Figure 6 (codezealot.org/post/images/sat-ex-2.png), every axis parallel to an edge in that picture is overlapping. The only axis that is not overlapping, is one that is perpendicular to an edge (the triangles hypotenuse in this case). – Daniel Mar 13 '12 at 2:18
Oh, yes. Now I see what you mean. But I was under the impression that you always only test axes which are perpendicular to the edges with the algorithm anyways. At least that's how I did it until now. – TravisG Mar 13 '12 at 9:33
up vote 5 down vote

You should definitely look up Separating Axis Theorem. It's for convex objects. There is a rule: "If two convex objects don't intersect, then there is a plane where the projection of these two objects will not intersect".

You can find some examples on the wiki. But it's a little more complicated than for your case.

Something more suitable for your problem can be found here (two cars colliding).

share|improve this answer
up vote 1 down vote

More SAT articles.

The last article on this site comes with complete code, i think it's in FLASH, i've no idea, but i had exactly 0 issues converting it to C++ when i had to use SAT for the first time, shouldn't be hard to do the same for other languages. The only thing you'll have to add is storing of the displacement vector on each calculation (if it's the smallest, ofcourse, you'll understand this when you learn about SAT), the code in this tutorial doesn't do it, so you end up with the last calculated vector.

http://rocketmandevelopment.com/tag/separation-axis-theorem/

Good, old N-Game tutorials. Best SAT theory on the web.

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

share|improve this answer
It's so irritating no one posts the full working source with all the required classes. I ported his code over into a demo of my own but it just doesn't work. :( This is my project so far if anyone could help me debug it that would be great. link – SyntheCypher Mar 13 '12 at 10:35
what do you mean it doesn't work? pay attention to how you're storing your vertices, in the image you have them in a cartesian coordinate system, in the tutorial he stores the vertices as vectors relative to the centroid (all you have to do is subtract centroid from your own vertices or remove the lines where he modifies his own vertices), functions like dot product you can create yourself, you don't need a guide for those, rest should be straight forward, it's not a copy paste material, learn SAT before trying to implement it – dreta Mar 13 '12 at 12:11
This is how I've implemented it: SAT.as, Shape2D.as, What do you mean by centroid? The centre of the polygon such as (x, y)? – SyntheCypher Mar 13 '12 at 13:03
At the moment I have a function getOBB() which returns vertices as detailed in my original image. This is calculated from the a Vector<b2Vec2> containing the vertices of the shape, a angle variable, and a position variable. – SyntheCypher Mar 13 '12 at 13:07
yes, the center, the way this guy creates his polygons is by giving offsets from the center, idk AS3, but from what i see you project your vertices as they are, when calculating dot product try to subtract centroid from the vertices (vector subraction), beside this you aren't checking which separation vector is the smallest still, you only store the last one calculated – dreta Mar 13 '12 at 17:27

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.