Separating Axis Theorem For The Rest Of Us.

Whether you're a newbie or an experienced programmer, any questions, help, or just talk of any language will be welcomed here.

Moderator: Coders of Rage

Post Reply
User avatar
avansc
Respected Programmer
Respected Programmer
Posts: 1708
Joined: Sun Nov 02, 2008 6:29 pm

Separating Axis Theorem For The Rest Of Us.

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

Image

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.
Some person, "I have a black belt in karate"
Dad, "Yea well I have a fan belt in street fighting"
User avatar
Pickzell
Chaos Rift Junior
Chaos Rift Junior
Posts: 233
Joined: Sat May 16, 2009 10:21 am

Re: Separating Axis Theorem For The Rest Of Us.

Post by Pickzell »

haha cool, this would be useful if I knew more than a quarter of shit about vectors.
I'm an altogether bad-natured Cupid.
XianForce
Chaos Rift Devotee
Chaos Rift Devotee
Posts: 767
Joined: Wed Oct 29, 2008 8:36 pm

Re: Separating Axis Theorem For The Rest Of Us.

Post by 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.
User avatar
RyanPridgeon
Chaos Rift Maniac
Chaos Rift Maniac
Posts: 447
Joined: Sun Sep 21, 2008 1:34 pm
Current Project: "Triangle"
Favorite Gaming Platforms: PC
Programming Language of Choice: C/C++
Location: UK
Contact:

Re: Separating Axis Theorem For The Rest Of Us.

Post by RyanPridgeon »

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

Because I need this to calculate torque. thanks
Ryan Pridgeon
C, C++, C#, Java, ActionScript 3, HaXe, PHP, VB.Net, Pascal
Music | Blog
User avatar
Maevik
Chaos Rift Junior
Chaos Rift Junior
Posts: 230
Joined: Mon Mar 02, 2009 3:22 pm
Current Project: www.keedepictions.com/Pewpew/
Favorite Gaming Platforms: PC
Programming Language of Choice: C++
Location: Long Beach, CA

Re: Separating Axis Theorem For The Rest Of Us.

Post by 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.
My love is like a Haddoken, it's downright fierce!
XianForce
Chaos Rift Devotee
Chaos Rift Devotee
Posts: 767
Joined: Wed Oct 29, 2008 8:36 pm

Re: Separating Axis Theorem For The Rest Of Us.

Post by XianForce »

Maevik wrote: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.
User avatar
avansc
Respected Programmer
Respected Programmer
Posts: 1708
Joined: Sun Nov 02, 2008 6:29 pm

Re: Separating Axis Theorem For The Rest Of Us.

Post by 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
Some person, "I have a black belt in karate"
Dad, "Yea well I have a fan belt in street fighting"
qpHalcy0n
Respected Programmer
Respected Programmer
Posts: 387
Joined: Fri Dec 19, 2008 3:33 pm
Location: Dallas
Contact:

Re: Separating Axis Theorem For The Rest Of Us.

Post by 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
Chaos Rift Devotee
Chaos Rift Devotee
Posts: 767
Joined: Wed Oct 29, 2008 8:36 pm

Re: Separating Axis Theorem For The Rest Of Us.

Post by XianForce »

qpHalcy0n wrote: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
Respected Programmer
Respected Programmer
Posts: 387
Joined: Fri Dec 19, 2008 3:33 pm
Location: Dallas
Contact:

Re: Separating Axis Theorem For The Rest Of Us.

Post by 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".
User avatar
Maevik
Chaos Rift Junior
Chaos Rift Junior
Posts: 230
Joined: Mon Mar 02, 2009 3:22 pm
Current Project: www.keedepictions.com/Pewpew/
Favorite Gaming Platforms: PC
Programming Language of Choice: C++
Location: Long Beach, CA

Re: Separating Axis Theorem For The Rest Of Us.

Post by 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!
My love is like a Haddoken, it's downright fierce!
User avatar
lotios611
Chaos Rift Regular
Chaos Rift Regular
Posts: 160
Joined: Sun Jun 14, 2009 12:05 pm
Current Project: Game engine for the PC, PSP, and maybe more.
Favorite Gaming Platforms: Gameboy Micro
Programming Language of Choice: C++

Re: Separating Axis Theorem For The Rest Of Us.

Post by 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.
"Why geeks like computers: unzip, strip, touch, finger, grep, mount, fsck, more, yes, fsck, fsck, fsck, umount, sleep." - Unknown
Post Reply