Separating Axis Theorem For The Rest Of Us.

[avansc]

ps: i got a little rushed posting this. will complete later.

Separating Axis Theorem For The Rest Of Us.
- Andre van Schalkwyk

Index:
1. Foreword.
2. Separating Axis Theorem.
2.1 For Mathematicians.
2.2 For The Rest of US.
3. The Mathematics.
3.1 Vector Magnitude.
3.2 Vector Normalization.
3.3 Vector Dot Product.
3.4 Vector Projection.
4. Pseudo Code
4.1 Vector Class
4.2 Rectangle Class.
4.3 Separating Axis Theorem Class.
5. In closing.

1. Foreword:
This article is written in response to the recent interest in the Separating Axis Theorem
and the increasing opinion that guides and tutorials about the topic are lacking and cryptic at best.
This guide is not the end all to collision detection but aims to give a solid foundation to the
understanding and implementation to S.A.T. This guide also does not attempt to be the optimum
solution or try to be efficient, it is the Programmers job to take care of that.

2. Separating Axis Theorem.
The Separating Axis Theorem is a set of mathematical properties that we can use to calculate
whether polygons overlap.

2.1 For Mathematicians.
The Separating Axis Theorem states that if we project the all the vectors/vertices of the polygons
onto all the normals of the edges of the polygons, and none of the spaces of the 2 polygons vector
projections share a common subspace we know that the 2 polygons don’t overlap.

2.2 For The Rest of US.
Phew! What a mouth full. I’ll do my best to explain what that all means in a way that avoids using
an mathematical terms and that breaks it down into layman's terms.



If we look down every line of the two polygons and we can see a separation we know that the polygons
do not over lap. As in this pic, we can see if we look down that slanted line of the triangle, there is a gap
between the “shadows” or projections of the 2 polygons. The line that the “shadows” or projections fall
on is the normal vector of the slanted line of the triangle, it is also perpendicular to it. When we find a line
that these “shadows” or projection paces, do not overlap or share a subspace, we can then deduce that the
two polygons do not over lap. of we went through every line in every polygon and we did not find a “gap”,
we then can deduce that the do in fact overlap.

3. The Mathematics.
In order to implement the Separating Axis Theorem you need to at least know some basic vector
mathematics. It would be very beneficial for you to understand it, in the even that you want to optimize
or expand on this basic implementation.

You only need to know 4 basic equations and they are in order of increasing complexity.
vector magnitude, vector normalization, vector dot product and lastly vector Projection. Some of the
equations rely on others to work.

Note: x and y represent vector components.

3.1 Vector Magnitude.
Vector Magnitude is a formula that returns a scalar of the length of the vector.

mag = sqrt(x^2 + y^2);

3.2 Vector Normalization.
Vector Normalization makes a vector have magnitude 1, but keep the same direction. this is done
by dividing each vector component but the vector magnitude.

float mag = vec->magnitude();
vec->x = vec->x / mag;
vec->y = vec->y / mag;

3.3 Vector Dot Product.
The dot product returns another scalar. It can be used to find the angles between vectors and has
multiple uses in geometry. The dot product takes 2 vectors and returns a scalar.

dot_prod = A->x * B->x + A->y * B->y;

3.4 Vector Projection.
For the most part this is what is at the heart of the Separating Axis Theorem. Vector projection can
be thought of this way.

if you have a perfectly flat surface, with a light perfectly above you, shining light down, and you take
a pencil and put some putty on one end, and stick it on the surface, and you let it tilt over in some direction.
The shadow on the surface of the pencil is the projected pencil vector onto the surface vector. A vector
projection produces a another vector.

Projecting vector A onto vector B

proj_x = dot_prod(A, B) / B->x / magnitude(B)^2
proj_y = dot_prod(A, B) / B->y / magnitude(B)^2

4. Pseudo Code
I will add some code here. Please do not copy and paste this code and expect it to work. It may,
but don’t expect it. I do not have functions that take multiple vector parameters to calculate
mag/dot/projection and so forth. I have setup my Vector (cVec2) class to handle all that.
IE. if you wanted to project vector A onto B, you would do it in this fashion.

projection_vector = A->v_Proj(B);

Also note that i never calculate normals since i only use rectangles and you dont need to. and you only
need to test 2 lines on each rectangle instead of 4 since 2 are parallel.


4.1 Vector Class

Code: Select all

#ifndef _cVec2_h
#define _cVec2_h

class cVec2
{
public:
	cVec2();
	cVec2(float x, float y);
	~cVec2();

	void Normalize();
	float Magnitude();
	float v_Dot_Prod(cVec2 *vec);
	cVec2 *v_Proj(cVec2 *vec);
	
	float x, y;
};

#endif

4.2 Rectangle Class.

Code: Select all

#ifndef _cRect_h
#define _cRect_h

class cRect
{
public:
	cRect();
	cRect(float x, float y, float w, float h);
	
	void calc_World_Coords();
	
	cVec2 *center;
	float w, h, ang;
	cVec2 *world_coords[4];
};

#endif

/*
 * This just make world coordinates. you need those to be able
 * to calculate the vectors in order to do SAT.
 */

void cRect::calc_World_Coords()
{
	float deg = this->ang/180*PI;

	/*
	 x' = cos(theta)*x - sin(theta)*y 
	 y' = sin(theta)*x + cos(theta)*y
	 */
	
	this->world_coords[0] = new cVec2((cos(deg) * -this->w - sin(deg) * -this->h)+this->center->x,
									  (sin(deg) * -this->w + cos(deg) * -this->h)+this->center->y);
	
	this->world_coords[1] = new cVec2((cos(deg) * -this->w - sin(deg) * this->h)+this->center->x,
									  (sin(deg) * -this->w + cos(deg) * this->h)+this->center->y);
	
	this->world_coords[2] = new cVec2((cos(deg) * this->w - sin(deg) * this->h)+this->center->x,
									  (sin(deg) * this->w + cos(deg) * this->h)+this->center->y);
	
	this->world_coords[3] = new cVec2((cos(deg) * this->w - sin(deg) * -this->h)+this->center->x,
									  (sin(deg) * this->w + cos(deg) * -this->h)+this->center->y);
	
}

4.3 Separating Axis Theorem Class.

Code: Select all

bool SAT::intesect(cRect *A, cRect *B)
{
	
	A->calc_World_Coords();
	B->calc_World_Coords();
	
	cRect *list[3];
	list[0] = A;
	list[1] = B;
	list[2] = A;
	cVec2 *p;
	
	float t1;
	float t2;
	float min;
	float max;
	
	for(int i = 0;i < 2;i++)
	{
		for(int a = 0;a < 2;a++)
		{
			p = new cVec2(list[i]->world_coords[a+1]->x - list[i]->world_coords[a]->x, list[i]->world_coords[a+1]->y - list[i]->world_coords[a]->y);
			p->Normalize();
		
			t1 = list[i]->world_coords[a]->v_Proj(p)->Magnitude();
			t2 = list[i]->world_coords[a+1]->v_Proj(p)->Magnitude();
			min = min(t1, t2);
			max = max(t1, t2);
		
			float proj[4];
		
			for(int b = 0;b < 4;b++)
			{
				proj[b] = list[i+1]->world_coords[b]->v_Proj(p)->Magnitude();
			}
		
			if(!this->umbrellas(min, max, proj))
				return false;
		}
	}
	   
	return true;
}

bool SAT::umbrellas(float min, float max, float proj[])
{
	bool less = false;
	bool more = false;
	
	printf("%2.2f , %2.2f\n", min, max);
	
	for(int loop = 0;loop < 4;loop++)
	{
		if(proj[loop] >= min && proj[loop] <= max)
		{
			return true;
		}else if(proj[loop] < min)
		{
			less = true;
		}else if(proj[loop] > max)
		{
			more = true;
		}
	}
	
	if(less && more)
		return true;
	
	return false;
}

5. In closing.
I hope that this guide was useful to you. if you have any suggestions please feel free to contact me and let me know about it.

[Pickzell]

haha cool, this would be useful if I knew more than a quarter of shit about vectors.

[XianForce]

If any of you want another guide, with pictures, I found an interesting one:

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

Note: I didn't make that... I just found it and thought it'd be useful if you needed a bit more than avansc's guide.

[RyanPridgeon]

Do you know how I would find the exact position of the collision?

Because I need this to calculate torque. thanks

[Maevik]

Can anyone explain to me what the x and y of the vector represent? Every tutorial I've read on SAT is ambiguous with this, perhaps because it should be obvious. That being said I'm failing to understand how these two values fully describe a vector that has:
location (x and y?)
direction
magnitude (assuming vector is not normalized, in which case we know the magnitude)

Clarification on this would be greatly appreciated.

[XianForce]

Can anyone explain to me what the x and y of the vector represent? Every tutorial I've read on SAT is ambiguous with this, perhaps because it should be obvious. That being said I'm failing to understand how these two values fully describe a vector that has:
location (x and y?)
direction
magnitude (assuming vector is not normalized, in which case we know the magnitude)

Clarification on this would be greatly appreciated.

First off, don't take anything I say as fact, because I may be wrong, but from what I understand, the x and y components represent the location from the origin, so that the magnitude would be the square root of x^2 + y^2 (considering the origin as (0, 0)). So basically whatever angle that vector makes, would be direction.

[avansc]

^yea,

It depends really in what context you are using a vector.
For example, if i was to describe a rectangle in 2D space i could do it one of 2 ways.

vec rect = { {10,10}, {10,20}, {20,20}, {20,10} ]; // describes a rectangle centered at {15,15} with width and heigh of {10,10} <- can use a vector to describe that.

In this version its a little more tricky to do rotations, because you need to do a few translations(moving all coordinates) to get it to rotate about its own axis.

a different way would be to describe the rectangle as follows.

rectangle center vec = {15,15} // center location
rectangle hWH vec = {5,5} // half width and height

now the hWH does not represent a location with respect to the origin {0,0} but to the origin {15,15}

Also, a in a context like velocity or acceleration you might have something like {10, -5},
all that the refers to is that the object will be translated or accelerated in that direction and magnitude byt what ever time quanta you use. or pass.
usually its something like

void update(double dT)
{
pos.x += vel.x*dT;
pos.y += vel.y*dT;
// or if you have the ops over loaded
pos += vel*dt;
}

if you wanna know more about working with velocities vs acceleration, look at second order runge kutta. often called RK2

[qpHalcy0n]

It's worth noting that in math and computer graphics a vector does NOT have position. Ever. A vector is positionless and only describes direction.

A point describes location but not direction.

In libraries, people use vectors and points interchangeably because they're 3-tuples or duples. So please note that difference.

[XianForce]

It's worth noting that in math and computer graphics a vector does NOT have position. Ever. A vector is positionless and only describes direction.

A point describes location but not direction.

In libraries, people use vectors and points interchangeably because they're 3-tuples or duples. So please note that difference.

In math 0.o... In math a 'vector quantity' is a quantity with direction AND magnitude I thought? Least that's what all my teachers have always told me...

[qpHalcy0n]

No, now that would be not correct (but not necessarily incorrect either).

Alot of times professors tangle up nomenclature or in order to illustrate a point skew the actual meaning of something in order to make it clearer as to what they're talking about. A vector by definition is merely a direction with a definite length. This does not necessarily preclude a terminal or initial point. So you'd think that in order to have length the vector would have to be "bound" by some constraint (that being a point). This is true....HOWEVER....a vector with a length of one at an initial position of {-2, 1, 0}, {200, -124, 23483.0}, or {32, -18734.8, -23489.0} is the same exact vector regardless of position (it's definition has not changed). A vector is given definition by reference, but not by inheritance. In other words, a vector does not possess these properties by nature of itself, it possesses them by nature of its reference frame. This is a more analytical approach.

So by definition, one only needs to specify direction and length to have a vector. This does not require a reference point, therefore vectors do not necessarily have position. They have position if you give them one, but this is not their definition. This would be more accurately called a "ray".

[Maevik]

Thanks for clearing this up guys. I guess my biggest misunderstanding was that a vector does not necessarily have a location, and it's magnitude and direction can be obtained from the x and y.

I found this page to be really helpful in clearing up most of what I didn't / but needed to know to grasp SAT: http://tutorial.math.lamar.edu/Classes/ ... asics.aspx

Hopefully someone else will find it usefull :D

Thanks again guys. Best community ever!

[lotios611]

I found another tutorial. From what I've read so far, it seems to explain SAT pretty good. I was totally lost before reading this. Now I understand a bit more.