bounded box collision detection in opengl

Question

Here is the overlay of the program. I'm working in visual studio 10 , c++ with opengl/glut. I am trying to create a maze(which i generate from an input file). Then i import two models from 3dstudio max with a obj loader(glm). And one of the models(mo) will be moving around the maze. So i added a bounding box around him and also around the walls of the labyrinth . I also drawn the box around mo and it seems to move/rotate along with the character. But for some reason (maybe i'm not doing it in the right place) collision test never detects anything. I will let the code do the talking , and if you have any questions i'll be glad to straighten them out.Prepare for code now.

//bounding boxes
struct BoundingBox
{
    Vector3D max;
    Vector3D min;
};
BoundingBox *box_mo;
BoundingBox *static_box[400];

void initbox(BoundingBox *b){
    b->min.x=100000;
    b->min.y=100000;
    b->min.z=100000;
    b->max.x=-100000;
    b->max.y=-100000;
    b->max.z=-100000;
}

BoundingBox *CreateCollisionBox(GLMmodel *model,GLMgroup *object){
/* GLM doesn't store each vertex together with the object that owns it. It doesn't have that notion. In GLM object don't have vertex, they have triangles. And each triangle is actually an index in the triangle list of the object.*/
    BoundingBox *boxx=(BoundingBox*)malloc(sizeof(BoundingBox));
    initbox(boxx);
    for(int i=0;i<object->numtriangles;i++){
// for each vertex of the triangle pmodel1->triangles[object->triangles[i]]
// calculate min and max
        for(int j=0;j<3;j++){
            GLuint index=model->triangles[object->triangles[i]].vindices[j];
            GLfloat x = model->vertices[index*3 +0];
            GLfloat y = model->vertices[index*3 +1];
            GLfloat z = model->vertices[index*3 +2];
            if(boxx->min.x>x) boxx->min.x =x;
            if(boxx->min.y>y) boxx->min.y =y;
            if(boxx->min.z>z) boxx->min.z =z;

            if(boxx->max.x<x) boxx->max.x =x;
            if(boxx->max.y<y) boxx->max.y =y;
            if(boxx->max.z<z) boxx->max.z =z;
        }
    }
    return boxx;
}

void AddCollisionBox(GLMmodel *model,GLMgroup *object){
    //box[boxindex]=CreateCollisionBox(model,object);
    box_mo=CreateCollisionBox(model,object);
    //boxindex++;
}
// A GLMmodel has a chained list of groups, each group representing an object. 
// Each object has a name (the name you gave it in 3D Studio Max or Gmax).
// Let's you have 10 walls in your scene a few other objects as well and you want to 
// create collision boxes just for the walls and you do not want to make a collision box 
// for one of your objects. You could name all your walls
// like this: Wall1, Wall2, ..., Wall10. If you wanted to add collision boxes just to them 
// you could go through all objects in the scene and if their name contains "Wall" add them.
// with this one: strstr
// Basicly this function does just that: if you want to add boxes for the walls you would call it like this: DefineCollisionBoxes(model,"Wall"); 
void DefineCollisionBoxes(GLMmodel *model,char *name){
    GLMgroup *group = model->groups;
    while(group){
        if(strstr(group->name,name))
            AddCollisionBox(model,group);
        group=group->next;
    }
}

bool Collision(BoundingBox *b,GLfloat x,GLfloat y,GLfloat z){
    return x <= b->max.x && x>= b->min.x && y<= b->max.y && y>= b->min.y && z<= b->max.z && z >= b->min.z;
}

bool CollisionTest(BoundingBox *a,BoundingBox *b){
    /*bool collision=false;
    for(int i=0;i<static_boxes;i++){
        for(float x=static_box[i]->min.x, y=static_box[i]->min.y,z=static_box[i]->min.z ;x<=static_box[i]->max.x && y<=static_box[i]->max.y && z<=static_box[i]->max.z;x+=0.1,y+=0.1,z+=0.1){
            if(Collision(a,x,y,z) == true)
                collision=true;
        }
    }
    return collision;*/
    if(a->min.x <= b->max.x && a->max.x >= b->min.x && a->min.z <= b->max.z && a->max.z >= b->min.z && a->min.y <= b->max.y && a->max.y >= b->min.y)
        return true;
    return false;
}

void drawBox(BoundingBox *b){
    glColor3f(1,1,1);
    glBegin(GL_LINE_LOOP);
    glVertex3f(b->max.x,b->max.y,b->min.z);
    glVertex3f(b->min.x,b->max.y,b->min.z);
    glVertex3f(b->min.x,b->min.y,b->min.z);
    glVertex3f(b->max.x,b->min.y,b->min.z);
    glEnd();

    glBegin(GL_LINE_LOOP);
    glVertex3f(b->max.x,b->min.y,b->max.z);
    glVertex3f(b->max.x,b->max.y,b->max.z);
    glVertex3f(b->min.x,b->max.y,b->max.z);
    glVertex3f(b->min.x,b->min.y,b->max.z);
    glEnd();

    glBegin(GL_LINE_LOOP);
    glVertex3f(b->max.x,b->max.y,b->min.z);
    glVertex3f(b->max.x,b->max.y,b->max.z);
    glVertex3f(b->min.x,b->max.y,b->max.z);
    glVertex3f(b->min.x,b->max.y,b->min.z);
    glEnd();

    glBegin(GL_LINE_LOOP);
    glVertex3f(b->max.x,b->min.y,b->max.z);
    glVertex3f(b->min.x,b->min.y,b->max.z);
    glVertex3f(b->min.x,b->min.y,b->min.z);
    glVertex3f(b->max.x,b->min.y,b->min.z);
    glEnd();
}


//display function
void display(){
    glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);
    //setup view
    glMatrixMode(GL_MODELVIEW);
    glLoadIdentity();
    camera.render
    //read from file, create walls and characters 
    //place model mo in front of the third person camera always
    Vector3D positionn;
    positionn = camera.position + camera.forward*5;

    glPushMatrix();
    glColor3f(0.88f,0.75f,0.49f);
    //here i move my character and calculate bounding box at each frame for him
    glTranslatef(positionn.x,-0.42f,positionn.z);
    glScalef(0.7f,0.7f,0.7f);
    glRotatef(angle,0,1,0);
    drawMo();
    DefineCollisionBoxes(pmodel1,"body"); // actual function call
    drawBox(box_mo); //draw bounding box
    glPopMatrix();

    //test if the character collides with any of the walls - not working
    for(int i=0;i<static_boxes;i++){
        if(CollisionTest(box_mo,static_box[i]) == true){
            printf("collision");
        }
    }


    //swap buffers
    glutSwapBuffers();
}

Answer 1

I will try to give an outline on how to solve the collision problem. For simplicity I will make the following assumptions:

1. We have a coordinate system the maze exists within.
2. Both the camera and the model are transformed into this coordinate system.
3. The only transformation performed on the walls in order to get them to that coordinate system is pure translation without any rotations or scaling.
4. The character will be translated,rotated and scaled.
5. You don't want to check if you will collide but if you collided.
6. You have or you will write or acquire a vector and matrix library

If we use these assumptions we can represent each wall using a rectangle in 3d. And since we assumed the maze is neither rotated nor scaled we can do it once and store it in an array or a B-tree or what ever. (Note that selecting the right data structure to store your world for calculations can greatly increase performance)

The character moves around the the maze and we assumed that it can be both rotated and scaled. The easiest way to decide if the character has collided with anything is to calculate the bounding sphere of the object. Once you have you can for the sake of the collision detection store just two points. The center point of the sphere and any arbitrary point on the sphere.

Once the character is taken to the correct position in the maze you apply the exact same transformation to the two mentioned points. You either do this using your matrix library or you can query the MODELVIEW matrix after transforming the character. You can do this by calling 'glGetFloatv` like this:

GLfloat model[16]; 
glGetFloatv(GL_MODELVIEW_MATRIX, model); 

Once you have transformed the two points you can find the distance between them - this will be the distance an object has to be away from the transformed center point to avoid collision.

Now the last thing to do is go over the relevant planes and check point to plane distance using the transformed center point and the calculated distance. You then need to make sure that the projected center unto the plane falls within the rectange.

And here is an outline of the program (No real code here just comments and function abstractions)

void drawCharacter(Matrix4f const & charMatrix);
void drawMaze(Matrix4f const & mazeMatrix);
//Will return MAX_FLT to indicate out of rectangle condition
float distanceToRectangle(Vector3f const & point, Rectangle3df const & plane);
vector<Rectangle3df> wallPlanes;
Vector3f centerOfCharSphere;
Vector3f pointOnCharSphere;
//Initialization
/*
1. Go Over maze create planes for all walls
2. Calculate character sphere and extract two points: The center of the sphere and a point on the sphere
*/

//Render
/*
Calculate the charMatrix - The matrix that takes the character from object CRS to maze CRS
Calculate the translation matrix for the maze (mazeMatrix) - the matrix that translates the maze into place
*/

Vector3f transformedSphereCenter = charMatrix.transform(centerOfCharSphere);
Vector3f transformedPointOnSphere = charMatrix.transform(pointOnCharSphere);
Vector3f R = transformedPointOnSphere - transformedSphereCenter;
float safeDistance = R.length();
for(vector<Plane3f>::const_iterator it = wallPlanes.begin(); it != wallPlanes.end(); it++)
{
    if(distanceToRectangle(transformedSphereCenter, *it) <= safeDistance)
       printf("collided\n");
}

/*
Setup projection matrix
Setup the modelview matrix for the camera
*/
drawMaze(mazeMatrix);
drawCharacter(charMatrix);

I hope this puts you on the right track