Jump to content

  • Log In with Google      Sign In   
  • Create Account

Banner advertising on our site currently available from just $5!


1. Learn about the promo. 2. Sign up for GDNet+. 3. Set up your advert!


Separating Axis Theorem


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
7 replies to this topic

#1 Trox   Members   -  Reputation: 134

Like
0Likes
Like

Posted 30 December 2007 - 05:32 PM

http://www.codeproject.com/KB/GDI-plus/PolygonCollision.aspx?print=true I'm using the example given above as the main basis of my reading. In it, it shows the below psuedo code which is what I am following. For each edge of both polygons { Find the axis perpendicular to the current edge. Project both polygons on that axis. If these projections don't overlap, the polygons don't intersect (exit...) } I know how to find the axis perpendicular to the edge, however I am unsure how to project the polygons onto the axis. I've read that you just do a vector projection of each vertice on each polygon. The articles say to find the min and max values of the pojection for each polygon. If the min or max of one polygon is between the min and max of the other polygon then there is a possible collision. However, when I started thinking about it, a vector projection returns a vector, not a scalar. How then can you get a min and max value from the projection? I thought about scalar projections as well since it returns a scalar, however, when I checked the code provided at the link above it uses a vector projection. I know I could just use the code provided at CodeProject, but I would perfer to understand the reasoning behind everything.

Sponsor:

#2 Hardwire   Members   -  Reputation: 194

Like
0Likes
Like

Posted 30 December 2007 - 09:25 PM

You take only the size of the projection. To do it, you make a dotproduct of the axis vector and a vector pointing from [0,0] to a vertex of the polygon. It will give you a scalar. Then you iterate over all vertices of your polygon and take minimum and maximum of these scalars. It will determine an interval. Then you do the same thing with the second polygon and it will also give you an interval. If these intervals overlap, then these polygons overlap along this axis.

Looking at your link this is what they do, just look at the function ProjectPolygon.

You also might find useful other links to SAT: http://physics.hardwire.cz/index.php?action=show&parent_id=45&sortby=order

#3 Trox   Members   -  Reputation: 134

Like
0Likes
Like

Posted 31 December 2007 - 04:30 AM

So then I just continue what I am doing and take the magnitude of the calculated projection vectors :) Thanks.

#4 scgames   Members   -  Reputation: 2014

Like
0Likes
Like

Posted 31 December 2007 - 08:48 AM

Quote:
Original post by Trox
So then I just continue what I am doing and take the magnitude of the calculated projection vectors :) Thanks.
You don't need to take the magnitude of any vector; the projections themselves are already scalars.

Remember that the dot product (which is what we're using here) returns a scalar, which is exactly what we're looking for.

Can you post the bit of code that's causing you confusion?

#5 Trox   Members   -  Reputation: 134

Like
0Likes
Like

Posted 31 December 2007 - 11:58 AM

Its the conversion from the algorithm to code. A vector projection does not return a scalar like you are saying.

If you project vector A onto vector B you use the formula:

[ A * (A dot B) ] / ( [ magnitute(A) ] ^ 2 )
In general its a vector times a scalar divided by a scalar which returns a vector. That is why I am confused. I know that a vector projection returns a vector. I also know that the vector projection formula isn't simply the dot product of two vectors. In all the code examples I've found the dot product is being used instead of the vector projection formula above. Why?

This is the code I am using, though its the thought process above that has confused me.

This is my implementation of the SAT

/**
* Foreach edge of the polygons
* {
* I) Find the axis perpendicular to the edge
* a) Take the left hand normal
* II) Project both polygons onto that axis
* Instantiate min and max values for each polygon
* Foreach polygon
* {
* Foreach vertice on the polygon
* {
* a) Project the vertice onto the axis
* b) Take the length of the projection
* c) Compare the current min and max values to the length of the projection, keeping the better corresponding values
*
* Overlap conditions
*
* _______ _______ Projection Shadow
* |-----|
* |-----| No Overlap
* A B C D
*
* _______ _______ Projection Shadow
* |-----|
* |-----| No Overlap
* C D A B
*
* __________________ Projection Shadow
* |----------|
* |----------| Overlap
* A C B D
*
* __________________ Projection Shadow
* |----------|
* |----------| Overlap
* C A D B
* }
* }
* III) If the projections don't overlap, the polygons don't intersect (exit the loop)
* a) If the min or max of one polygon is between the min and max of the other polygon, then a collision exists
* }
**/
private void SeparatingAxisTheorem(Polygon a, Polygon b)
{
bool exitLoops = false;
Polygon[] polygons = new Polygon[]{a, b};
foreach (Polygon p in polygons)
{
Vector[] edges = p.Edges;
foreach (Vector edge in edges)
{
Vector axis = edge.LeftOrthogonal;
const int numberOfPolygons = 2;
float[] polygonMin = new float[numberOfPolygons];
float[] polygonMax = new float[numberOfPolygons];
for (int i = 0; i < numberOfPolygons; i++)
{
polygons[i].ProjectOnTo(axis, ref polygonMin[i], ref polygonMax[i]);
}
/**
* For the above examples
* A = polygonMin[0]
* B = polygonMax[0]
* C = polygonMin[1]
* D = polygonMax[1]
**/
System.Diagnostics.Debug.Print(polygonMin[0] + ", " + polygonMax[0] + " " + polygonMin[1] + ", " + polygonMax[1]);
if (
(polygonMin[0] < polygonMax[0] && polygonMax[0] < polygonMin[1] && polygonMin[1] < polygonMax[1])
||
(polygonMin[1] < polygonMax[1] && polygonMax[1] < polygonMin[0] && polygonMin[0] < polygonMax[0])
)
{
// No collision exists, exit the loop
exitLoops = true;
MessageBox.Show("Collision not found!");
}
if (exitLoops)
break;
}
if (exitLoops)
break;
}
// A collision was found!
MessageBox.Show("Collision found!");
}

Polygon helper functions used above

public void ProjectOnTo(Vector v, ref float min, ref float max)
{
min = 1f;
max = -1f;
if(needEdgeUpdate)
CreateEdges();
foreach (Vector vertice in m_Edges)
{
Vector projectedVector = vertice.VectorProjectOnto(v);
float projectedLength = projectedVector.Length;
if (projectedLength < min)
min = projectedLength;
else if (projectedLength > max)
max = projectedLength;
}
}

Vector helper functions used above

public float Length
{
get { return (float)Math.Sqrt(m_X * m_X + m_Y * m_Y); }
}

public Vector LeftOrthogonal
{
get { return new Vector(-m_Y, m_X); }
}

public Vector VectorProjectOnto(Vector v)
{
return v.ScalarMultiply(this.DotProduct(v) / v.Length * v.Length);
}

public float DotProduct(Vector v)
{
return m_X * v.X + m_Y * v.Y;
}


#6 scgames   Members   -  Reputation: 2014

Like
0Likes
Like

Posted 31 December 2007 - 12:10 PM

Ok, I think it's just the terminology that's causing confusion here...

When I use the term 'projection' in the context of the SAT, I'm referring to the scalar projection of one vector onto another, which can be calculated using the dot product.

To illustrate, here's some pseudocode showing how to project a polygon onto an axis:
Range ProjectPolygon(Vector verts[], Vector axis)
{
float min = FLOAT_MAX;
float max = -FLOAT_MAX;

for (each Vector in verts) {
float dot = dot_product(vert, axis);
min = minimum(min, dot);
max = maximum(max, dot);
}

return Range(min, max);
}
And that's really all there is to it.

'Hope that clears things up a bit.

#7 Trox   Members   -  Reputation: 134

Like
0Likes
Like

Posted 31 December 2007 - 12:20 PM

That is exaclty what the confusion was. Thats why my first post mentioned the difference between the scalar and the vector projections. Thanks for the help.

#8 scgames   Members   -  Reputation: 2014

Like
0Likes
Like

Posted 31 December 2007 - 12:41 PM

Quote:
Original post by Trox
That is exaclty what the confusion was. Thats why my first post mentioned the difference between the scalar and the vector projections. Thanks for the help.
Oops, sorry - by the time I got to the end of the thread I had forgotten the mention of scalar vs. vector projections in your original post :)




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS