## 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 ~
Moderator
Posts: 3,567
Joined: 2003.06
Post: #2
(Sep 23, 2010 01:51 PM)mikey Wrote:  It uses Dave Eberly's (?) Seperating axis theorem.

Hermann Minkowski
Member
Posts: 281
Joined: 2009.04
Post: #3
Thanks

~ Bring a Pen ~
Moderator
Posts: 450
Joined: 2008.04
Post: #4
What a handsome fellow!

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

Paul Johnson
Great Little War Game
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.