Im suffering some major stupidity regarding the method of separating axes and hope someone could help me out. I get the general idea of it but can't get it implemented.

Assuming Im working in 2D, and would like for example to test the collision of an AABB with a tile. Say the tile is a right triangle.

My understanding is I need to check the 3 axes of the right triangle for overlap with the AABB. To do this I need to, for each axis, project the vector between the two objects center points onto the current axis along with the sum of the halfwidth vectors of each object and check if the lengths show overlap. Does that sound remotely correct? If all 3 overlap then there is collision and I should be able to derive the penetration vector from there.

One problem is how do I derive the axes from my right triangle? Do I just use half-width vectors, and if so how do I derive those from the points of the triangle (this is probably very simple but my brain is numb)

Any information would be helpful. Thanks in advance.

The way I learned to do separating axes is to check if all the points of one shape are on one side of the axis, and all the points of the other shape are on the opposite side of the axis.

Note that if the axis goes through a point of a body you should obviously exclude that point from the check.

You may have already figured out the answers to your questions, but if not, here are a couple of thoughts.

In 2d the axes you need to test are the normals to the edges of the (convex) shapes that you're testing. In your case you need to check the normals to the 3 edges of the triangle, and the normals to the 4 edges of the AABB, for a total of 7.

Note however that an axis and its negative are equivalent as far as the separating axis test is concerned, so for the AABB you actually only need to test two edge normals, which are trivially the world x and y axes. So now you're down to 5.

For an arbitrarily oriented edge, the normal is the normalized 'perp' vector for that edge. For a vector x, y, the vector perpendicular to that vector is -y, x (or sometimes y, -x, depending on your convention).

(Note that it's not actually necessary for the normal to be unit-length in order for the separating axis test to work. If that's all you're using it for you could leave it un-normalized.)

So, given an edge formed by vertices v1 and v2, the normal is:

Vector2 edge = v2 - v1;
Vector2 normal(-edge.y, edge.x);
normal.Normalize(); // Optional

One last optimization: if your triangle is a right triangle aligned with the world axes, then two of its normals are parallel to the AABB normals and need not be tested. So now there are only 3 axes to test - the world x and y axes, and the normal to the diagonal edge of the right triangle.

jyk,

Thanks for your reply. Its looking like its working but Im not sure if I have it right for the general case.

One thing that's confusing me is using the normalized normals. If the normal is unit length, doesn't that alter its length when it's projected onto the axis, and therefore mess up the length testing for overlap? After the normalization, isnt it no longer a halfwidth vector?

Another issue is, should I need to precalculate the center point for each tile, depending on its shape?

Also, given an AABB, and the hypotenuse of a right-triangle aligned with the world axes, I need to sum up the magnitudes of the AABB halfwidth vectors they have been projected onto the axis. this ends up being 2 + another sqrts per axis when getting magnitudes(see code below). Is that bad?

Any guidance you could give would be awesome. My collision test code for the AABB class looks like:

Hi arctwelve,

At first glance, your code doesn't look right to me. I haven't examined it carefully though, so perhaps it's an equivalent method - I'm not sure. In any case, it's not the approach I'm familiar with. Also, I can tell you that the general algorithm requires no sqrts() or length computations, so even if your version works you might want to convert to the more 'standard' approach.

My first suggestion is to go to Dave Eberly's site geometrictools.com, go to the 'documentation' section, and look for a .pdf called 'The Method of Separating Axes' (or something close to that). It explains the general algorithm quite clearly.

If you're still having trouble after that, I'll be glad to help. I don't want to make any assumptions about what you do or don't understand, but I'm a little confused by a couple of things in your code. For example, I'm not sure what 'axis.center' means, since an axis is a vector and doesn't really have a position per se. Also, I think I see what you're trying to do with the project() function, but even if it works it's sort of a roundabout way of doing it. Suffice to say, there are better, or at least more standard, ways of doing it.

Again, I'll be glad to help further if I can, so please ask if you need any further clarification.

Hi jyk,

Thanks, I'm looking at Dave Eberly's paper. I'm going to try to implement his algorithm.

Just for reference, I'm looking at the tutorial here:
http://www.harveycartel.org/metanet/tutorials/tutorialA.html

It seems like a least one test (eg one sqrt) for the center distance between the two shapes is required, like in figure 3.

I don't know if you've gotten everything worked out or not, but just as an FYI the SAT test requires no square roots, so if your version requires sqrt() you may be misunderstanding the algorithm.

If you need more help, let me know and maybe I can post some example code.

I haven't got it worked out without square roots.

My main goal is to test for the overlap of an aabb with various convex tile shapes. I want to not only test for true/false overlap, but also get the depth of penetration, so I can project the aabb back to the point of contact.

If you have any code, that would really be a great help. thanks again.