Problems with SAT Collision Detection
- by DJ AzKai
I'm doing a project in one of my modules for college in C++ with SFML and I was hoping someone may be able to help me.
I'm using a vector of squares and triangles and I am using the SAT collision detection method to see if objects collide and to make the objects respond to the collision appropriately using the MTV(minimum translation vector)
Below is my code:
//from the main method
int main(){
// Create the main window
sf::RenderWindow App(sf::VideoMode(800, 600, 32), "SFML OpenGL");
// Create a clock for measuring time elapsed
sf::Clock Clock;
srand(time(0));
//prepare OpenGL surface for HSR
glClearDepth(1.f);
glClearColor(0.3f, 0.3f, 0.3f, 0.f); //background colour
glEnable(GL_DEPTH_TEST);
glDepthMask(GL_TRUE);
//// Setup a perspective projection & Camera position
glMatrixMode(GL_PROJECTION);
glLoadIdentity();
//set up a 3D Perspective View volume
//gluPerspective(90.f, 1.f, 1.f, 300.0f);//fov, aspect, zNear, zFar
//set up a orthographic projection same size as window
//this mease the vertex coordinates are in pixel space
glOrtho(0,800,0,600,0,1); // use pixel coordinates
// Finally, display rendered frame on screen
vector<BouncingThing*> triangles;
for(int i = 0; i < 10; i++)
{ //instantiate each triangle;
triangles.push_back(new BouncingTriangle(Vector2f(rand() % 700, rand() % 500), 3));
}
vector<BouncingThing*> boxes;
for(int i = 0; i < 10; i++)
{ //instantiate each box;
boxes.push_back(new BouncingBox(Vector2f(rand() % 700, rand() % 500), 4));
}
CollisionDetection * b = new CollisionDetection();
// Start game loop
while (App.isOpen())
{
// Process events
sf::Event Event;
while (App.pollEvent(Event))
{
// Close window : exit
if (Event.type == sf::Event::Closed)
App.close();
// Escape key : exit
if ((Event.type == sf::Event::KeyPressed) && (Event.key.code == sf::Keyboard::Escape))
App.close();
}
//Prepare for drawing
// Clear color and depth buffer
glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);
// Apply some transformations
glMatrixMode(GL_MODELVIEW);
glLoadIdentity();
for(int i = 0; i < 10; i++)
{
triangles[i]->draw();
boxes[i]->draw();
triangles[i]->update(Vector2f(800,600));
boxes[i]->draw();
boxes[i]->update(Vector2f(800,600));
}
for(int j = 0; j < 10; j++)
{
for(int i = 0; i < 10; i++)
{
triangles[j]->setCollision(b->CheckCollision(*(triangles[j]),*(boxes[i])));
}
}
for(int j = 0; j < 10; j++)
{
for(int i = 0; i < 10; i++)
{
boxes[j]->setCollision(b->CheckCollision(*(boxes[j]),*(triangles[i])));
}
}
for(int i = 0; i < triangles.size(); i++)
{
for(int j = i + 1; j < triangles.size(); j ++)
{
triangles[j]->setCollision(b->CheckCollision(*(triangles[j]),*(triangles[i])));
}
}
for(int i = 0; i < triangles.size(); i++)
{
for(int j = i + 1; j < triangles.size(); j ++)
{
boxes[j]->setCollision(b->CheckCollision(*(boxes[j]),*(boxes[i])));
}
}
App.display();
}
return EXIT_SUCCESS;
}
(ignore this line)
//from the BouncingThing.cpp
BouncingThing::BouncingThing(Vector2f position, int noSides)
: pos(position), pi(3.14), radius(3.14), nSides(noSides)
{
collided = false;
if(nSides ==3)
{
Vector2f vert1 = Vector2f(-12.0f,-12.0f);
Vector2f vert2 = Vector2f(0.0f, 12.0f);
Vector2f vert3 = Vector2f(12.0f,-12.0f);
verts.push_back(vert1);
verts.push_back(vert2);
verts.push_back(vert3);
}
else if(nSides == 4)
{
Vector2f vert1 = Vector2f(-12.0f,12.0f);
Vector2f vert2 = Vector2f(12.0f, 12.0f);
Vector2f vert3 = Vector2f(12.0f,-12.0f);
Vector2f vert4 = Vector2f(-12.0f, -12.0f);
verts.push_back(vert1);
verts.push_back(vert2);
verts.push_back(vert3);
verts.push_back(vert4);
}
velocity.x = ((rand() % 5 + 1) / 3) + 1;
velocity.y = ((rand() % 5 + 1) / 3 ) +1;
}
void BouncingThing::update(Vector2f screenSize)
{
Transform t;
t.rotate(0);
for(int i=0;i< verts.size(); i++)
{
verts[i]=t.transformPoint(verts[i]);
}
if(pos.x >= screenSize.x || pos.x <= 0)
{
velocity.x *= -1;
}
if(pos.y >= screenSize.y || pos.y <= 0)
{
velocity.y *= -1;
}
if(collided)
{
//velocity.x *= -1;
//velocity.y *= -1;
collided = false;
}
pos += velocity;
}
void BouncingThing::setCollision(bool x){
collided = x;
}
void BouncingThing::draw()
{
glBegin(GL_POLYGON);
glColor3f(0,1,0);
for(int i = 0; i < verts.size(); i++)
{
glVertex2f(pos.x + verts[i].x,pos.y + verts[i].y);
}
glEnd();
}
vector<Vector2f> BouncingThing::getNormals()
{
vector<Vector2f> normalVerts;
if(nSides == 3)
{
Vector2f ab = Vector2f((verts[1].x + pos.x) - (verts[0].x + pos.x), (verts[1].y + pos.y) - (verts[0].y + pos.y));
ab = flip(ab);
ab.x *= -1;
normalVerts.push_back(ab);
Vector2f bc = Vector2f((verts[2].x + pos.x) - (verts[1].x + pos.x), (verts[2].y + pos.y) - (verts[1].y + pos.y));
bc = flip(bc);
bc.x *= -1;
normalVerts.push_back(bc);
Vector2f ac = Vector2f((verts[2].x + pos.x) - (verts[0].x + pos.x), (verts[2].y + pos.y) - (verts[0].y + pos.y));
ac = flip(ac);
ac.x *= -1;
normalVerts.push_back(ac);
return normalVerts;
}
if(nSides ==4)
{
Vector2f ab = Vector2f((verts[1].x + pos.x) - (verts[0].x + pos.x), (verts[1].y + pos.y) - (verts[0].y + pos.y));
ab = flip(ab);
ab.x *= -1;
normalVerts.push_back(ab);
Vector2f bc = Vector2f((verts[2].x + pos.x) - (verts[1].x + pos.x), (verts[2].y + pos.y) - (verts[1].y + pos.y));
bc = flip(bc);
bc.x *= -1;
normalVerts.push_back(bc);
return normalVerts;
}
}
Vector2f BouncingThing::flip(Vector2f v){
float vyTemp = v.x;
float vxTemp = v.y * -1;
return Vector2f(vxTemp, vyTemp);
}
(Ignore this line)
CollisionDetection::CollisionDetection()
{
}
vector<float> CollisionDetection::bubbleSort(vector<float> w) {
int temp;
bool finished = false;
while (!finished) {
finished = true;
for (int i = 0; i < w.size()-1; i++) {
if (w[i] > w[i+1]) {
temp = w[i];
w[i] = w[i+1];
w[i+1] = temp;
finished=false;
}
}
}
return w;
}
class Vector{
public:
//static int dp_count;
static float dot(sf::Vector2f a,sf::Vector2f b){
//dp_count++;
return a.x*b.x+a.y*b.y;
}
static float length(sf::Vector2f a){
return sqrt(a.x*a.x+a.y*a.y);
}
static Vector2f add(Vector2f a, Vector2f b)
{
return Vector2f(a.x + b.y, a.y + b.y);
}
static sf::Vector2f getNormal(sf::Vector2f a,sf::Vector2f b){
sf::Vector2f n;
n=a-b;
n/=Vector::length(n);//normalise
float x=n.x;
n.x=n.y;
n.y=-x;
return n;
}
};
bool CollisionDetection::CheckCollision(BouncingThing & x, BouncingThing & y)
{
vector<Vector2f> xVerts = x.getVerts();
vector<Vector2f> yVerts = y.getVerts();
vector<Vector2f> xNormals = x.getNormals();
vector<Vector2f> yNormals = y.getNormals();
int size;
vector<float> xRange;
vector<float> yRange;
for(int j = 0; j < xNormals.size(); j++)
{
Vector p;
for(int i = 0; i < xVerts.size(); i++)
{
xRange.push_back(p.dot(xNormals[j], Vector2f(xVerts[i].x, xVerts[i].x)));
}
for(int i = 0; i < yVerts.size(); i++)
{
yRange.push_back(p.dot(xNormals[j], Vector2f(yVerts[i].x , yVerts[i].y)));
}
yRange = bubbleSort(yRange);
xRange = bubbleSort(xRange);
if(xRange[xRange.size() - 1] < yRange[0] || yRange[yRange.size() - 1] < xRange[0])
{
return false;
}
float x3 = Min(xRange[0], yRange[0]);
float y3 = Max(xRange[xRange.size() - 1], yRange[yRange.size() - 1]);
float length = Max(x3, y3) - Min(x3, y3);
}
for(int j = 0; j < yNormals.size(); j++)
{
Vector p;
for(int i = 0; i < xVerts.size(); i++)
{
xRange.push_back(p.dot(yNormals[j], xVerts[i]));
}
for(int i = 0; i < yVerts.size(); i++)
{
yRange.push_back(p.dot(yNormals[j], yVerts[i]));
}
yRange = bubbleSort(yRange);
xRange = bubbleSort(xRange);
if(xRange[xRange.size() - 1] < yRange[0] || yRange[yRange.size() - 1] < xRange[0])
{
return false;
}
}
return true;
}
float CollisionDetection::Min(float min, float max)
{
if(max < min)
{
min = max;
}
else return min;
}
float CollisionDetection::Max(float min, float max)
{
if(min > max)
{
max = min;
}
else return min;
}
On the screen the objects will freeze for a small amount of time before moving off again. However the problem is is that when this happens there are no collisions actually happening and I would really love to find out where the flaw is in the code. If you need any more information/code please don't hesitate to ask and I'll reply as soon as possible
Regards,
AzKai
