Still trying to get my head around SAT in 2d.

I have read and reread tutorials. I am working on a basic 2d allegro game.

Correct me if I am wrong but
The order is
- get the normal of an edge
- project all points from both convex polygons currently being
checked onto that axis
- get two minimums and two maximums
- if intersection occurs check next edge, if not break.

The maths to do this is still fuzzy to me...

So to get the normal for a line segment, or edge, is the dot product?
(x1*x2)+(y1*y2)
But how do I be sure the normal is facing the right direction, as the normal can point two directions, or is this irrelevant?

Then I project all the vertex (?) using ? ...
proj.x = ( dp / (b.x*b.x + b.y*b.y) ) * b.x;
proj.y = ( dp / (b.x*b.x + b.y*b.y) ) * b.y;

Any hints are appreciated...

The dot product is not the normal.

You can get the normal like this:
x = y2 - y1
y = -(x2 - x1)

I don't think it's important which way the normal is facing for this algorithm.

Your projection of the vertex looks correct :)

Quote:Original post by Daan
The dot product is not the normal.

You can get the normal like this:
x = y2 - y1
y = -(x2 - x1)

I don't think it's important which way the normal is facing for this algorithm.

He could ignore the way the normal is facing but then he would need computing the projection of both polygons into the normal. When you know the normal of an edge is pointing outside the polygon, you don't have to project the polygon containing that edge on its normal. The projection of all its vertices on that normal will either be null or negative. You will just need to test if a vertex of the other polygon has a negative projection to detect a collision. That speeds up things.

To project vertices, just do if the normals are all unit-long:


The candidate separating axes are the normals of the two polygons and all the cross products of a normal of the first polygon and a normal of the second.

[Edited by - johnstanp on December 2, 2010 6:40:58 AM]

First, in 2D the possible separating axes are only the normals of the edges. No cross products as stated earlier are needed in 2D! In 3D (for convex polyhedra) you would need to test the cross products of all edges pairs. This makes SAT quite difficult to implement efficiently in 3D since this is basically an O(N^2) problem.

Second, it is much easier to think of the projection in terms of a support function. A support point is the furthest point in a given direction. Then for each normal on one polygon you find the support point on the other polygon in the opposite direction of this normal. Your penetration/separation is the distance of this support point to the plane defined by your current edge. The plane is simple your normal and one of your edge vertices.

For a good implementation you might want to look at Box2D (www.Box2D.org)