Congratulations…
If you are still with me you have survived successfully the theory section ;)
Before having fun playing around with the demo, some further explanations about the source code are necessary.
The main flow and steps of the simulation are as follows (in pseudo code).
While (Timestep != 0) {
For each ball {
compute nearest collision with planes;
compute nearest collision with cylinders;
Save and replace if it the nearest intersection in time computed until now;
}
Check for collision among moving balls;
Save and replace if it the nearest intersection in time computed until now;
If (Collision occurred) {
Move All Balls for time equal to collision time;
(We already have computed the point, normal and collision time.)
Compute Response;
Timestep -= CollisonTime;
} else Move All Balls for time equal to Timestep
}
The actual code which implements the above pseudo code is much harder to read but essentially is an exact implementation of the pseudo code above.
// While time step not over
while (RestTime > ZERO) {
lamda = 10000; //initialize to very large value
// For all the balls find closest intersection between balls and planes/cylinders
for (int i = 0; i < NrOfBalls; i++) {
// compute new position and distance
OldPos[i] = ArrayPos[i];
TVector::unit(ArrayVel[i],uveloc);
ArrayPos[i] = ArrayPos[i] + ArrayVel[i] * RestTime;
rt2 = OldPos[i].dist(ArrayPos[i]);
// Test if collision occured between ball and all 5 planes
if (TestIntersionPlane(pl1, OldPos[i], uveloc, rt, norm)) {
// Find intersection time
rt4 = rt * RestTime / rt2;
// if smaller than the one already stored replace and in timestep
if (rt4 <= lamda) {
// if intersection time in current time step
if (rt4 <= RestTime + ZERO) if (! ((rt <= ZERO) && (uveloc.dot(norm) > ZERO)) ) {
normal = norm;
point=OldPos[i] + uveloc * rt;
lamda = rt4;
BallNr = i;
}
}
}
if (TestIntersionPlane(pl2, OldPos[i], uveloc, rt, norm)) {
//…The same as above omitted for space reasons
}
if (TestIntersionPlane(pl3, OldPos[i], uveloc, rt, norm)) {
//…The same as above omitted for space reasons
}
if (TestIntersionPlane(pl4, OldPos[i], uveloc, rt, norm)) {
//…The same as above omitted for space reasons
}
if (TestIntersionPlane(pl5, OldPos[i], uveloc, rt, norm)) {
//…The same as above omitted for space reasons
}
// Now test intersection with the 3 cylinders
if (TestIntersionCylinder(cyl1, OldPos[i], uveloc, rt, norm, Nc)) {
rt4 = rt * RestTime / rt2;
if (rt4 <= lamda) {
if (rt4 <= RestTime + ZERO) if (! ((rt <= ZERO) && (uveloc.dot(norm) > ZERO)) ) {
normal = norm;
point = Nc;
lamda = rt4;
BallNr = i;
}
}
}
if (TestIntersionCylinder(cyl2, OldPos[i], uveloc, rt, norm, Nc)) {
//…The same as above omitted for space reasons
}
if (TestIntersionCylinder(cyl3, OldPos[i], uveloc, rt, norm, Nc)) {
//…The same as above ommited for space reasons
}
}
// After all balls were tested with planes/cylinders test for collision
// between them and replace if collision time smaller
if (FindBallCol(Pos2, BallTime, RestTime, BallColNr1, BallColNr2)) {
if (sounds) PlaySound("Explode.wav", NULL, SND_FILENAME|SND_ASYNC);
if ( (lamda == 10000) || (lamda > BallTime) ) {
RestTime = RestTime - BallTime;
TVector pb1, pb2, xaxis, U1x, U1y, U2x, U2y, V1x, V1y, V2x, V2y;
double a,b;
...
code omitted for space reasons
the code is described in the Physically Based Modeling section under sphere to sphere collision
...
// Update explosion array and insert explosion
for (j = 0; j < 20; j++) {
if (ExplosionArray[j]._Alpha <= 0) {
ExplosionArray[j]._Alpha = 1;
ExplosionArray[j]._Position = ArrayPos[BallColNr1];
ExplosionArray[j]._Scale = 1;
break;
}
}
continue;
}
}
// End of tests
// If collision occured move simulation for the correct timestep
// and compute response for the colliding ball
if (lamda !=10000) {
RestTime -= lamda;
for (j = 0; j < NrOfBalls; j++) ArrayPos[j] = OldPos[j] + ArrayVel[j] * lamda;
rt2 = ArrayVel[BallNr].mag();
ArrayVel[BallNr].unit();
ArrayVel[BallNr] = TVector::unit( (normal * (2 * normal.dot(-ArrayVel[BallNr]))) + ArrayVel[BallNr] );
ArrayVel[BallNr] = ArrayVel[BallNr] * rt2;
// Update explosion array and insert explosion
for (j = 0; j < 20; j++) {
if (ExplosionArray[j]._Alpha <= 0) {
ExplosionArray[j]._Alpha = 1;
ExplosionArray[j]._Position = point;
ExplosionArray[j]._Scale = 1;
break;
}
}
} else RestTime=0;
} //end of while loop
The main global variables of importance are:
| Represent the direction and position of the camera. The camera is moved using the LookAt function. As you will probably notice, if not in hook mode (which I will explain later), the whole scene rotates around, the degree of ratation is handles with camera_rotation. | TVector dir; TVector pos(0,-50,1000); float camera_rotation=0; |
| Represent the acceleration applied to the moving balls. Acts as gravity in the application. | TVector accel(0,-0.05,0); |
| Arrays which hold the New and old ball positions and the velocity vector of each ball. The number of balls is hard coded to 10. | TVector ArrayVel[10]; TVector ArrayPos[10]; TVector OldPos[10]; int NrOfBalls=3; |
| The time step we use. | double Time=0.6; |
| If 1 the camera view changes and a (the ball with index 0 in the array) ball is followed. For making the camera following the ball we used its position and velocity vector to position the camera exactly behind the ball and make it look along the velocity vector of the ball. | int hook_toball1=0; |
| Self explanatory structures for holding data about explosions, planes and cylinders. | struct Plane struct Cylinder struct Explosion |
| The explosions are stored in a array, of fixed length. | Explosion ExplosionArray[20]; |
The main functions of interest are:
| Perform Intersection tests with primitives | int TestIntersionPlane(…); int TestIntersionCylinder(…); |
| Loads Textures from bmp files | void LoadGLTextures(); |
| Has the rendering code. Just renders every time the balls, walls, columns and explosions | void DrawGLScene(); |
| Performs the main simulation logic | void idle(); |
| Sets Up OpenGL state | void InitGL(); |
| Find if any balls collide again each other in current time step | int FindBallCol(…); |
For more information look at the source code. I tried to comment it as good as possible. Once the collision detection and response logic is understood, the source should become very clear. For any more info don't hesitate to contact me.
As was stated at the beginning the subject of collision detection is a very difficult and versatile subject to be covered only by one tutorial. Although we have come a long way, learned a lot of new stuff and can now create some nifty and impressive things as the demo shows, there is still a long way in front of you. Now that you have the basics all the other sources on Collision Detection and Physically Based Modeling out there should become easier to understand. With this I send you on your way and wish you happy collisions!!!