Allegro.cc - Online Community

Allegro.cc Forums » Programming Questions » Collision Detection (SAT)

This thread is locked; no one can reply to it. rss feed Print
Collision Detection (SAT)
someone972
Member #7,719
August 2006
avatar

I read this tutorial about the Separating Axis Theorem. I understand the theory, I just don't know how to implement the axis checking.??? If anyone could help me out it would be greatly appreciated.

EDIT: Nevermind, I finally figured it out.

Update:
How to do polygon-polygon collision detection:

Hopefully this helps anyone who comes across this post, I used the information in this tutorial, modifying the code to make it work, and the explanation of SAT in the link above.
It is necessary to understand the theory if you want to understand the code, or you can just use the code if you don't need any modifications.

Take note that this only detects a collision, it doesn't provide any response, and it is only for polygon-polygon collisions, round objects have a different implementation.

First we want an object that holds an x-y coordinate:

class vector2d
{
public:
       int x,y;
};

We then need to create an object that will hold the polygon data:

class polygon2d
{
 public:
        std::vector<vector2d> verticies; //this can be replaced with another
                                         //type of container if necessary
        int num_verticies;
};

So far this should be pretty straight forward. Now we need the function that checks for collisions, it will be explained at the end:

1int collision_detect(polygon2d& p1, polygon2d& p2)
2{
3 vector2d axis;
4 double tmp,minA,maxA,minB,maxB;
5 
6 for(int i = 0; i < p1.num_verticies;i++)
7 {
8 if(i == 0)
9 {
10 axis.x = p1.verticies[p1.num_verticies-1].y - p1.verticies[0].y;
11 axis.y = p1.verticies[0].x - p1.verticies[p1.num_verticies-1].x;
12 }
13 else
14 {
15 axis.x = p1.verticies[i-1].y - p1.verticies<i>.y;
16 axis.y = p1.verticies<i>.x - p1.verticies[i-1].x;
17 }
18 minA = maxA = p1.verticies[0].x * axis.x + p1.verticies[0].y * axis.y;
19 for(int i = 1; i < p1.num_verticies; i++)
20 {
21 tmp = p1.verticies<i>.x * axis.x + p1.verticies<i>.y * axis.y;
22 if (tmp > maxA)
23 maxA = tmp;
24 else if (tmp < minA)
25 minA = tmp;
26 }
27 minB = maxB = p2.verticies[0].x * axis.x + p2.verticies[0].y * axis.y;
28 for(int i = 1; i < p2.num_verticies; i++)
29 {
30 tmp = p2.verticies<i>.x * axis.x + p2.verticies<i>.y * axis.y;
31 if (tmp > maxB)
32 maxB = tmp;
33 else if (tmp < minB)
34 minB = tmp;
35 }
36 if (maxA < minB || minA > maxB)
37 return 0;
38 }
39 for(int i = 0; i < p2.num_verticies;i++)
40 {
41 if(i == 0)
42 {
43 axis.x = p2.verticies[p2.num_verticies-1].y - p2.verticies[0].y;
44 axis.y = p2.verticies[0].x - p2.verticies[p2.num_verticies-1].x;
45 }
46 else
47 {
48 axis.x = p2.verticies[i-1].y - p2.verticies<i>.y;
49 axis.y = p2.verticies<i>.x - p2.verticies[i-1].x;
50 }
51 minA = maxA = p1.verticies[0].x * axis.x + p1.verticies[0].y * axis.y;
52 for(int i = 1; i < p1.num_verticies; i++)
53 {
54 tmp = p1.verticies<i>.x * axis.x + p1.verticies<i>.y * axis.y;
55 if (tmp > maxA)
56 maxA = tmp;
57 else if (tmp < minA)
58 minA = tmp;
59 }
60 minB = maxB = p2.verticies[0].x * axis.x + p2.verticies[0].y * axis.y;
61 for(int i = 1; i < p2.num_verticies; i++)
62 {
63 tmp = p2.verticies<i>.x * axis.x + p2.verticies<i>.y * axis.y;
64 if (tmp > maxB)
65 maxB = tmp;
66 else if (tmp < minB)
67 minB = tmp;
68 }
69 if (maxA < minB || minA > maxB)
70 return 0;
71 }
72 return 1;
73};

This function returns 1 if there was a collision, 0 if there wasn't.

And now on to explaining it.

First:

vector2d axis;
double tmp,minA,maxA,minB,maxB;

Axis is the coordinate that all the sides are projected onto. MinB, maxB, minA and maxA are the points that are projected the farthest apart, this is explained better later on.

http://www.allegro.cc/files/attachment/593933

Next:

for(int i = 0; i < p1.num_verticies;i++)
{
 ...
}

This will loop through all the sides of the polygon, if you read the information on the page linked at the very top, you will know that all these sides need to be colliding for a collision to occur.

http://www.allegro.cc/files/attachment/593934

Next:

if(i == 0)
{
    axis.x = p1.verticies[p1.num_verticies-1].y - p1.verticies[0].y;
    axis.y = p1.verticies[0].x - p1.verticies[p1.num_verticies-1].x;
}
else
{
    axis.x = p1.verticies[i-1].y - p1.verticies<i>.y;
    axis.y = p1.verticies<i>.x - p1.verticies[i-1].x;
}

These lines of code will determine the axis from the side being suppiled from the for loop.

http://www.allegro.cc/files/attachment/593935

To be continued...

______________________________________
As long as it remains classified how long it took me to make I'll be deemed a computer game genius. - William Labbett
Theory is when you know something, but it doesn't work. Practice is when something works, but you don't know why. Programmers combine theory and practice: Nothing works and they don't know why. -Unknown

De Baimbo
Member #8,944
August 2007
avatar

Interesting tecnique, but why should I create a new class "vector2d" instead of using a normal array, e.g. coords[2], to store the x and y coordinates of a vertex?
I'm almost a newbie so that question may sound stupid, but so far arrays worked well for my collisions.

nonnus29
Member #2,606
August 2002
avatar

The choice on how represent vectors is completely arbitrary. You'll see different projects do it with arrays or structs of individual coordinates. It does make interoperating with things difficult at times; like if you want to use ODE (open dynamics engine) with your code and you've coded math one way and they've done it another.

Nice pictures by the way, did you make them?

Go to: