Sign in to follow this  
B G

2d Seperating Axis Theorem

Recommended Posts

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...

Share this post


Link to post
Share on other sites
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 :)

Share this post


Link to post
Share on other sites
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:


for( int unsigned i = 0; i < polygon1.edges.size(); ++i )
{
Vector2 const & normal = polygon1.edges[i].outside_normal;
Vector2 const & vertex = polygon1.edges[i].origin;

for( int unsigned j = 0; j < polygon2.vertices.size(); ++j )
{
Vector2 temp = polygon2.vertices[i];
temp.substract(vertex);
Real projection = dot_product(temp,normal);

if (projection<=0)
{
return COLLISION;
}
}





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]

Share this post


Link to post
Share on other sites
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)

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this