Seperating Axis Theorem Code

Member
Posts: 281
Joined: 2009.04
Post: #1
I have spent the last few weeks creating this C++ function and I'd like to share it with everyone here. The code is properly (I think) commented but definitely works. Use it for whatever you want.

This particular function will tell you if a AABB and a triangle are intersecting but can easily be modified (see the comments at the start of the triangle box function) to use any 3D n-vertex shapes.

It uses Dave Eberly's (?) Seperating axis theorem.


I have optimized it a little (obj1flag,obj2flag) but not any more than that.

Enjoy:



Code:
int checkCollisionOnAxis(vector<vector3D> obj1, vector<vector3D>obj2, vector3D axis, float obj1flag, float obj2flag)
{
    // first project all of the vertices onto the axis;
    
    float min1, max1; // the two minimum and maximum projections for object 1
    float min2, max2; //  the two minimum and maximum projections for object 2
    min1 = min2 = INFINITY;
    max1 = max2 = -INFINITY;
    
    
    int counter; // this is used to iterate through all of the vertices of both objects
    
    
    
    obj11D.resize(0); // clears both arrays of projected vertices
    obj21D.resize(0); // "        "        "    "    "            "
    
    
    for ( counter = 0; counter < obj1.size(); counter++)
        // for every vertex in object 1...
        obj11D.push_back(axis.dot(obj1.at(counter)) / axis.sqrlen()  );
        // project it onto the axis specified and then store the result in obj11D
    
    
    
    
    for ( counter = 0; counter < obj11D.size(); counter++)
    {
        // now check if all of the projected 1D vertices are the min or max
        
        if (obj11D.at(counter) < min1)
            min1 = obj11D.at(counter);
        
        if (obj11D.at(counter) > max1)
            max1 = obj11D.at(counter);
        
        
    }
    

    for ( counter = 0; counter < obj2.size(); counter++)
        obj21D.push_back(axis.dot(obj2.at(counter)) / axis.sqrlen()  );
    // do the same: project the vertices of the second object onto the same axis...
    
        
        
        for ( counter = 0; counter < obj21D.size(); counter++)
        {
            //    .. and find the min and max of those vertices.
            
            
            if (obj21D.at(counter) < min2)
                min2 = obj21D.at(counter);
            
            if (obj21D.at(counter) > max2)
                max2 = obj21D.at(counter);
            
            
        

        
        
    }

            

    
    // The following code was used as a graphical demonstration of the projections... see if you can see how it works
    /*glPointSize(5.0f);
    
    glBegin(GL_LINES);
    glColor3f(1.0f, 0.0f, 0.0f);
    glVertex3f(min1,0.0f,-5.0f);
    glColor3f(1.0f, 0.5f, 0.5f);
    glVertex3f(max1,0.0f,-5.0f);
    glColor3f(0.0f, 1.0f, 0.0f);
    glVertex3f(min2,1.0f,-5.0f);
    glColor3f(0.5f, 1.0f, 0.5f);
    glVertex3f(max2,1.0f,-5.0f);
    glEnd();
    */
    
    // the next piece of code simply checks if the two minimum and maximum values intersect, if they do, return 1
    
    if (min1 <= max2 && min1 >= min2) // min1 is inside 2
        return 1;
    
    if (max1 <= max2 && min1 >= min2) // max1 is inside 2
        return 1;
    
    
    if (min2 <= max1 && min2 >= min1) // min2 is inside 2
        return 1;
    
    if (max2 <= max1 && min2 >= min1) // max2 is inside 2
        return 1;
    
    
    // they don't intersect: return 0
    
    
    return 0;    
}
int triangleBox(vector3D p0, vector3D p1,vector3D p2, vector3D position, vector3D halfwidth)
{
    
    
    
    /*Perform the SAT test on:
    
    
     - 3 AABB axes, which are the global axes
     - 1 triangle normal
     - 9 cross products, between each edge of the triangle and the three global axes
     */
    
    
    //
    
    // CALCULATE the vertex's positions. THis can be easily modified to be OBB code, or any object's code
    
    vector3D v0(position.x - halfwidth.x,position.y - halfwidth.y, position.z - halfwidth.z);
    vector3D v1(position.x - halfwidth.x,position.y - halfwidth.y, position.z + halfwidth.z);
    vector3D v2(position.x + halfwidth.x,position.y - halfwidth.y, position.z + halfwidth.z);
    vector3D v3(position.x + halfwidth.x,position.y - halfwidth.y, position.z - halfwidth.z);
    vector3D v4(position.x - halfwidth.x,position.y + halfwidth.y, position.z - halfwidth.z);
    vector3D v5(position.x - halfwidth.x,position.y + halfwidth.y, position.z + halfwidth.z);
    vector3D v6(position.x + halfwidth.x,position.y + halfwidth.y, position.z + halfwidth.z);
    vector3D v7(position.x + halfwidth.x,position.y + halfwidth.y, position.z - halfwidth.z);
    
    vector <vector3D> box; // these are just names to be intuitive
    vector <vector3D> tri; // "        "    "        "    "  "    "
    
    tri.push_back(p0); // if one didn't know how many vertices there would be in the first object a loop would have to be used to transfer the points in the parameter list into the object vertex list
    tri.push_back(p1);
    tri.push_back(p2);
    
    // same with the second object
    
    box.push_back(v0);
    box.push_back(v1);
    box.push_back(v2);
    box.push_back(v3);
    box.push_back(v4);
    box.push_back(v5);
    box.push_back(v6);
    box.push_back(v7);
    
    
    if (checkCollisionOnAxis(box,tri,vector3D(1.0f,0.0f,0.0f),previousshape,newshape) == 0) // the projections don't overlap so we can leave
    {
        //cout << "seperated on x";
        return 0;
        
    }
    
    
    if (checkCollisionOnAxis(box,tri,vector3D(0.0f,1.0f,0.0f),previousshape,newshape) == 0) // the projections don't overlap
    {
        //    cout << "seperated on y";
        return 0;
    }
    if (checkCollisionOnAxis(box,tri,vector3D(0.0f,0.0f,1.0f),previousshape,newshape) == 0) // the projections don't overlap
    {
        //    cout << "seperated on z";
        return 0;
    }
    
    
    
    if (checkCollisionOnAxis(box,tri,(p2 - p0) * (p1 - p0),previousshape,newshape) == 0) // the triangles normal
    {
    //    cout << "seperated on triangles normal";
        return 0;
    }
    
    
    if (checkCollisionOnAxis(box,tri,(vector3D(1.0f,0.0f,0.0f) )* (p1 - p0),previousshape,newshape) == 0) // the triangles normal
    {
        //cout << "seperated on the cross product of the X and triangle's edge 1";
        return 0;
    }
    
    
    
    if (checkCollisionOnAxis(box,tri,(vector3D(1.0f,0.0f,0.0f) )* (p2 - p0),previousshape,newshape) == 0) // the triangles normal
    {
        //cout << "seperated on the cross product of the X and triangle's edge 2";
        return 0;
    }
    
    if (checkCollisionOnAxis(box,tri,(vector3D(1.0f,0.0f,0.0f) )* (p1 - p2),previousshape,newshape) == 0) // the triangles normal
    {
        //cout << "seperated on the cross product of the X and triangle's edge 3";
        return 0;
    }
    
    
    
    
    
    
    
    
    
    
    if (checkCollisionOnAxis(box,tri,(vector3D(0.0f,1.0f,0.0f) )* (p1 - p0),previousshape,newshape) == 0) // the triangles normal
    {
        //cout << "seperated on the cross product of the Y and triangle's edge 1";
        return 0;
    }
    
    
    
    if (checkCollisionOnAxis(box,tri,(vector3D(0.0f,1.0f,0.0f) )* (p2 - p0),previousshape,newshape) == 0) // the triangles normal
    {
        //cout << "seperated on the cross product of the Y and triangle's edge 2";
        return 0;
    }
    
    if (checkCollisionOnAxis(box,tri,(vector3D(0.0f,1.0f,0.0f) )* (p1 - p2),previousshape,newshape) == 0) // the triangles normal
    {
        //cout << "seperated on the cross product of the Y and triangle's edge 3";
        return 0;
    }
    
    
    
    
    
    
    
    
    
    if (checkCollisionOnAxis(box,tri,(vector3D(0.0f,0.0f,1.0f) )* (p1 - p0),previousshape,newshape) == 0) // the triangles normal
    {
        //cout << "seperated on the cross product of the Y and triangle's edge 1";
        return 0;
    }
    
    
    
    if (checkCollisionOnAxis(box,tri,(vector3D(0.0f,0.0f,1.0f) )* (p2 - p0),previousshape,newshape) == 0) // the triangles normal
    {
        //cout << "seperated on the cross product of the Y and triangle's edge 2";
        return 0;
    }
    
    if (checkCollisionOnAxis(box,tri,(vector3D(0.0f,0.0f,1.0f) )* (p1 - p2),previousshape,newshape) == 0) // the triangles normal
    {
        //cout << "seperated on the cross product of the Y and triangle's edge 3";
        return 0;
    }
    
    

    
    
    
    //    cout << "not seperated";
    
    
    
    
    
    
    
    
    return 1;
    
    
    
    

    
}

~ Bring a Pen ~
Quote this message in a reply
Moderator
Posts: 3,579
Joined: 2003.06
Post: #2
(Sep 23, 2010 01:51 PM)mikey Wrote:  It uses Dave Eberly's (?) Seperating axis theorem.

Hermann Minkowski
Quote this message in a reply
Member
Posts: 281
Joined: 2009.04
Post: #3
Thanks Smile

~ Bring a Pen ~
Quote this message in a reply
Moderator
Posts: 453
Joined: 2008.04
Post: #4
What a handsome fellow!

Howling Moon Software - CrayonBall for Mac and iPhone, Contract Game Dev Work
Quote this message in a reply
Member
Posts: 54
Joined: 2010.10
Post: #5
It gets worse, Mikey. Your sig is gonna run out of stack space and crash too... Smile

Paul Johnson
Great Little War Game
Quote this message in a reply
Member
Posts: 227
Joined: 2008.08
Post: #6
(Sep 23, 2010 01:51 PM)mikey Wrote:  It uses ... Seperating axis theorem.

Pretty ubiquitous these days.
Quote this message in a reply
Post Reply 

Possibly Related Threads...
Thread: Author Replies: Views: Last Post
  rotate around own axis wonza 35 13,263 Oct 10, 2008 05:09 AM
Last Post: wonza
  Separating Axis Collision Detection Joseph Duchesne 4 4,165 Dec 22, 2005 10:18 AM
Last Post: Leisure Suit Lurie
  Separation axis collision detection SOUR-Monkey 5 6,027 Mar 24, 2005 01:23 AM
Last Post: DoG