In this article I'm going to show how to simulate gravity (aka terrain collisions).

One can classify terrain collisions in indoor and outdoor.

Most of the time indoor is easier because most of your surfaces will be flat. All you'd have to do is find the nearest floor (if your scene is a building with multiple floors and stairs make sure you pick the nearest one under your character), get the maximum Y coordinate (assuming height spans on the Y axis - it could very well be Z or even X) and set your character's Y's position (Camera's position actually) to that value plus the height of the character. By now getting the min and max coordinates of objects should be familiar to you (you may read the previous tutorial about Bounding Box)

The hard part is when your surface is not horizontal: you could have hills for example. The most common way to model terrain is to create a plane in 3D Studio Max (doing it by code would be harder but not impossible - in Delta Force they generate the terrain by code) play a bit by moving points (check smooth selection and see how it works because it will help a lot) or applying a randomize modifier. After that import the terrain plane in your program like it was any other object. Next it's time to process the triangles in the object and extract the information we need.

In this case getting the Y value is a bit harder because getting min coordinates and maximum coordinates is not good enough....that unless you want going up the hill to feel like climbing stairs. If you want a smooth movement like in games you must calculate the intersection with the triangle right under the character and use that Y coordinate.

First thing is to find which triangle is the one under the character! There are many ways to do that: some are more cpu intensive and some use up more memory but leave the cpu alone thus giving a higher frame rate. It's a cpu memory compromise. One thing is certain: make your terrain use as few triangles as possible (use the optimize modifier in 3D Studio Max to eliminate unnecessary triangles).

One way to do it is to calculate a projection for each triangle and approximate it with a rectangle (the same way you created the bounding box in the previous tutorial, just that we are not interested in the Y coordinate this time) and then see if your point (character position) is over it. You can test this just like you tested if a point is in a bounding box, just don't the test Y coordinate this time:

bool IsOver(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 ;

}

You are going to notice that I used the same structure BoundingBox. The name may be inappropriate since you aren't actualy calculating a box....you are calculating a rectangle! Yet defining a rectangle and a box still requires the 2 points: 2 opposite corners (which happen to be the min and max value on each axis x,y,z.

Also you may notice this function isn't very accurate. It might not see such a good idea to aproximate a triangle with a rectangle but it saves the cpu a lot of time and usually this won't give undesirable effects. If you have a better a idea change it with your function.

So lets define a new structure to use a more appropriate name and add some extra information in it. It's not enough to know that we are on a certain triangle approximated by a given rectangle but we want to at least have a reference to the actual data that defines the triangle to calculate the exact intersection.

struct Vector3
{

float x;
float y;
float z;

};
struct TriangleAprox
{

Vector3 max;
Vector3 min;
int tr_index; // index of triangle

};

I've added an index to point to the real triangle data but you could even store the triangle instead or simply what we need from it: the equation of the plan determined by the 3 vertexes of the triangle. Having this equation we can easily calculate the intersection point where the feet of the game character stand. I've chosen to spear some memory and just keep and index.

A little math reminder: the equation of a plan is completely determined by 3 points (x1,y1,z1), (x2,y2,z2), (x3,y3,z3) and is

Ax + By + Cz + D = 0,

where (A,B,C) is the plane normal (GLM calculates normals) and can be manualy calculated if you know the 3 points with the formula:

float A = y1 *(z2 - z3) + y2 *(z3 - z1) + y3 *(z1 - z2);
float B = z1 *(x2 - x3) + z2 *(x3 - x1) + z3 *(x1 - x2);
float C = x1 *(y2 - y3) + x2 *(y3 - y1) + x3 *(y1 - y2);
float D = -(x1 *(y2* z3 - y3* z2) + x2 *(y3* z1 - y1* z3) + x3 *(y1 *z2 - y2 *z1));

We already know the X and Y components of the player's position (px and pz) but we don't know the elevation (py). We do know about it that it's straight over the intersection of that line with the triangle and it's only higher with the actual height of you game character. We the equation of the plan (Ax+By+Cz+D=0 where we have calculated A,B,C and D), we know the equation on the 3D line is:

, where px and pz are known values and t is the parameter that varies the point up and down the line.

Our YY (the value of Y in the intersection) is actually t. All we need to do is insert the x,y,z from the line equation into the plane equation and calculate t (YY):

YY = t = - (D+A*px+C*pz)/B;

Now that you have the intersection point (px,YY,pz) you also know the coordinates of the camera (px,py,pz) = (px,YY+height_of_the_character,pz).

Example coding

The code I'm going to show uses the model structure from GLM. Take a look at the Working with 3D models section for a presentation of the GLM library...library that you can get from here or from the example folder of the GLUT official source distribution.

You can find out more about how GLM holds the structure of your model from here

// The approximations for the terrain

TriangleAprox *terrainb[100000];
int terrainindex=0;

void initbox(TriangleAprox *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;

}

// 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).
// Somewhere in the code you want to say:
// The terrain I did in 3D Studio Max is called "Terrain". Find it and add it to collision testing!

void DefineTerrain(GLMmodel *model, char *NameOfTerrainObj)
{

// GLM provides us with a function to search for an object (=group) with a given name
GLMgroup *plan = glmFindGroup(model,NameOfTerrainObj);
// for each triangle of the terrain make an aproximation
for(int i = 0; i < plan->numtriangles; i++)
{

TriangleAprox*box = (TriangleAprox*)malloc(sizeof(TriangleAprox));
initbox(box);
for (int j=0;j<3;j++)
{

// Remember I told you plan->triangles[i] is actualy an index that points to the real triangle data
// stored the model->triangles[] array.
// That model->triangles[] array has a structure called vindices that tells us the index of the vertex in the vertex list
// So .vindices[0] is the index of the first vertex, .vindices[2] the second and .vindices[3] the third
// This line of code retrives the index of the vertex beloging to the given triangle
GLuint index = model->triangles[plan->triangles[i]].vindices[j];
// with this index we now go and retrive the actual (x,y,z) coordinates of the vertex from the model->vertices[] array
// This array is as follows: x1,y1,z1,x2,y2,z2,x3,y3,z3,x4,y4,z4,....
// So if you wanted the coordinates for the 5th vertex in the list you would take the 3 floats starting with
// the position 4*3 (it's 4 not 5 because the count starts with 0)
GLfloat x = model->vertices[index*3 + 0];
GLfloat y = model->vertices[index*3 + 1];
GLfloat z = model->vertices[index*3 + 2];

if (box->min.x>x) box->min.x = x;
if (box->min.y>y) box->min.y = y;
if (box->min.z>z) box->min.z = z;

if (box->max.x<x) box->max.x = x;
if (box->max.y<y) box->max.y = y;
if (box->max.z<z) box->max.z = z;

}

box->tr_index = plan->triangles[i];
terrainb[terrainindex++]=box;

}

}

// Find the terrain box that is right under the player
TriangleAprox *FindTerrainBox(float x, float y, float z)
{

for (int i=0;i<terrainindex;i++)

if (IsUnder(terrainb[i],x,y,z))

return terrainb[i];

return 0;

}

// This function will return y coordinate for the given x and y

float CalculateTerrainCollisions(GLMmodel *model,float px, float py, float pz)
{

int y=-300;

TriangleAprox *b = FindTerrainBox(px,y,pz);

if (!b) return -100000; // broken map? no triangle under the character???

int index = model->triangles[b->tr_index].vindices[0];

float x1 = model->vertices[index*3+0];
float y1 = model->vertices[index*3+1];
float z1 = model->vertices[index*3+2];

index = model->triangles[b->tr_index].vindices[1];
float x2 = model->vertices[index*3+0];
float y2 = model->vertices[index*3+1];
float z2 = model->vertices[index*3+2];

index = model->triangles[b->tr_index].vindices[2];
float x3 = model->vertices[index*3+0];
float y3 = model->vertices[index*3+1];
float z3 = model->vertices[index*3+2];

// calculate plane equation: Ax+By+Cz+D=0
float A = y1 *(z2 - z3) + y2 *(z3 - z1) + y3 *(z1 - z2);
float B = z1 *(x2 - x3) + z2 *(x3 - x1) + z3 *(x1 - x2);
float C = x1 *(y2 - y3) + x2 *(y3 - y1) + x3 *(y1 - y2);
float D = -(x1 *(y2* z3 - y3* z2) + x2 *(y3* z1 - y1* z3) + x3 *(y1 *z2 - y2 *z1));

if (B==0) B=0.1;

// do the intersection with the plane

return height_of_character - (D+A*px+C*pz)/B;
break;

}