Monday, December 19, 2011

SAT Collision Part 2

In this collision tutorial, we will take more in detail with how exact we get the normals and how we get the intervals.  However, I will not be going in detail regarding vector math needed to understand this, although it is simple and I will eventually post blogs regarding them.

Down to business.  Our shape is composed of vertices.  In the case of this rectangle, there is four vertices, in red, and four normals, in brown.  The vertices are self explanatory and the normals describe the orientation or the way a side of the triangle is facing.  Take note that the vertices are defined such that the center of the triangle, not indicated in the picture, is at position(0,0) and all vertices defining the vertex is relative to this location; just like in a normal coordinate system.

Now, to get the normal for a side of the rectangle we take two vertices defining an edge of the rectangle and subtract them.  Further, we swap the x, and y components and negate the new y component.  Then we normalize that normal so that it has a length of one.  

some pseudo-code:
Vertex{ double x, double y}
Normal{ double x, double y}
Rectangle{
     Vertex vtx[4];//four vtx define a rectangle
     Normal normal[4];
}

for(int i=0,j=0; i<4; i++){ //loop through all vertices for
     if(i == j) {
          j++;  //used to ensure that our indices are not referencing the same vtx
          if(j > 3) j=0;  //make sure we are not about of bounds to prevent memory issues
     }
     Vertex a = Rectangle.vtx[i];
     Vertex b = Rectangle.vtx[j];
     Vertex c = b - a; //the normal is the difference of a and b resuting in c
      Normal N = Normal(c.y, -c.x);  //the component of the normal must be swapped in 2D
      N.normalize();
      Rectangle.normal[i] = N;
}

In the next part, we will talk about the getting the intervals.

Introduction to SAT

When writing games, collision detection is important, especially one that is fast and robust.  True, you can get away with having a simple rectangular collision detection where your checking if two squares overlay, but that becomes less reliable when objects in your application/game are moving fast and many

I good collision detection system is SAT or  Separating axis theorem.  It says that if two convex shapes' (shapes that do not invaginate) projections along their respective normals does not overlap then the shapes do not overlay.  More clearly, if there is any project that separates the two shapes, then there is a collision.
That is it. However, this requires further explanation.  A convex shape is like a rectangle, an octagon, or any shape that does not fold into itself.  When using SAT, we use its normals, denoted by brown lines, to project two convex shapes while comparing to see if the two's intervals overlap.

If an overlap exist, then a collision is occurring.


Here we see that two shapes normals have been used to project the intervals of the respective shape.  By intervals I mean that the vertexes used to define the individual convex shape has all been projected along the normals (a total of four) using dot product between the normal and vertices so as to find a range or the intervals of the shape.  This interval finding is done for each normal.  Then, the range of the two shapes are compared to see if the overlap, more on this later.  Take note of the image of the right, note that we have an overlap at the top and at the bottom.  This is because the projected intervals of the two overlap.  However, this is not a collision; to be a true collision, all four projects of any shape must not be separate.  So if we have any separation, therefore any project not overlapping, then there is no collision.

C++ Interface

In this tutorial we will discuss interfaces in C++ and why one would be of benefit.  First off, an interface serves as a means to have a commonality of usage for varies objects.  What I mean by that is that say you have a class representing a basketball and a class that represents a soccer ball, it is understood that both are used for playing but how they are played with is different.  That difference of how they are used for playing is where interfaces come in.

An Interface provides a common way of using a class of type basketball and a class of type soccer ball without having will being able to refer to each different object(basketball or soccer ball) with the same interface.

Okay okay, this is confusing so let us take a couple of examples.

Without an interface, to have an object of basketball and soccer ball perform the same behavior, playing, you could do this:


class BasketBall{
public:
     void play(){
          cout << "playing with basketball" << endl;
     }
};
class SoccerBall{
public:
     void play(){
            cout << "playing with basketball" <<endl;
     }
}
int main(){
     BasketBall* bbball = new BasketBall();
     bball->play();
     delete bball;

     SoccerBall *sball = new SoccerBall();
     sball->play();
     delete sball;
     return 0;
}

From the preceding, we declared two class and declare two objects: bball and sball.  Take note that the two objects have a common usage.  That is all well and good, but the cost is that if you have a function that is used to execute the play method of these two functions, then you have to declare two functions of the type of the two respective objects.  


class BasketBall{
public:
     void play(){
          cout << "playing with basketball" << endl;
     }
};
class SoccerBall{
public:
     void play(){
            cout << "playing with basketball" <<endl;
     }
}
void executeBasketBallPlay(BasketBall* ball){
     ball->play();
}
void executeSoccerPlay(SoccerBall* ball){
     ball->play();
}
int main(){
     BasketBall* bbball = new BasketBall();
    executeBasketBallPlay(bball);
     delete bball;

     SoccerBall *sball = new SoccerBall();
     executeSoccerPlay(sball);
     delete sball;
     return 0;
}

Here we see that it is inefficient to have two separate functions that will execute essentially the same type of behavior from different class types.  So, the prudent thing to do would be to design a more efficient way of interacting with our balls (hey, that is kind of funny).  So, by now we have noted that our two class a common interface: the play method.  So we need to design a way to have other functions or classes in our code to respect this common interface/commonality between these two balls.

So here we go.

//here we define an interface, it is nothing more than a class with only pure
//virtual functions, denoted by the virtual keyword and the "=0" suffix
class PlayInterface {
public:

     virtual void play() = 0;
};


class BasketBall : public PlayInterface {
public:
     void play(){
          cout << "playing with basketball" << endl;
     }
};
class SoccerBall : public PlayInterface {
public:
     void play(){
            cout << "playing with basketball" <<endl;
     }
}

void executePlay(PlayInterface* ball){
     ball->play();
}

int main(){
     BasketBall* bbball = new BasketBall();
     executePlay (bball);
     delete bball;

     SoccerBall *sball = new SoccerBall();
     executePlay(sball);
     delete sball;
     return 0;
}

Now we have significantly increased the effectiveness of our code because we have only on method that will execute a simple command: playing with balls.  What this does is that executePlay takes a valid object of type of any type so long as it derives or implements PlayInterface, if it does then it executes it.

This is beneficial in many ways but namely because it allows use to not care about type matching and allows us to focus on common behaviors of objects.