iDevGames Forums
Seperating Axis Theorem Code - Printable Version

+- iDevGames Forums (http://www.idevgames.com/forums)
+-- Forum: Development Zone (/forum-3.html)
+--- Forum: Game Programming Fundamentals (/forum-7.html)
+--- Thread: Seperating Axis Theorem Code (/thread-8133.html)



Seperating Axis Theorem Code - mikey - Sep 23, 2010 01:51 PM

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;
    
    
    
    

    
}



RE: Seperating Axis Theorem Code - AnotherJake - Sep 23, 2010 11:13 PM

(Sep 23, 2010 01:51 PM)mikey Wrote:  It uses Dave Eberly's (?) Seperating axis theorem.

Hermann Minkowski


RE: Seperating Axis Theorem Code - mikey - Sep 24, 2010 02:22 AM

Thanks Smile


RE: Seperating Axis Theorem Code - AndyKorth - Sep 24, 2010 07:55 AM

What a handsome fellow!


RE: Seperating Axis Theorem Code - Applewood - Oct 9, 2010 03:12 PM

It gets worse, Mikey. Your sig is gonna run out of stack space and crash too... Smile


RE: Seperating Axis Theorem Code - Oddity007 - Oct 9, 2010 03:25 PM

(Sep 23, 2010 01:51 PM)mikey Wrote:  It uses ... Seperating axis theorem.

Pretty ubiquitous these days.