Seperating Axis Theorem Code
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:
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 ~
Post: #2(Sep 23, 2010 01:51 PM)mikey Wrote: It uses Dave Eberly's (?) Seperating axis theorem.
Hermann Minkowski
Post: #4
What a handsome fellow!
Howling Moon Software - CrayonBall for Mac and iPhone, Contract Game Dev Work
Possibly Related Threads...
| Thread: | Author | Replies: | Views: | Last Post | |
| rotate around own axis | wonza | 35 | 13,359 |
Oct 10, 2008 05:09 AM Last Post: wonza |
|
| Separating Axis Collision Detection | Joseph Duchesne | 4 | 4,189 |
Dec 22, 2005 10:18 AM Last Post: Leisure Suit Lurie |
|
| Separation axis collision detection | SOUR-Monkey | 5 | 6,077 |
Mar 24, 2005 01:23 AM Last Post: DoG |
|