Dimitrios Christopoulos - Collision detection tutorial

N is the Normal at the collision point

The new vector R is calculated as follows:

R= 2 * (-I dot N) * N + I

The restriction is that the I and N vectors have to be unit vectors. The velocity vector as used in our examples represents speed and direction. Therefore it can not be plugged into the equation in the place of I, without any transformation. The speed has to be extracted. The speed for such a velocity vector is extracted finding the magnitude of the vector. Once the magnitude is found, the vector can be transformed to a unit vector and plugged into the equation giving the reflection vector R. R shows us now the direction, of the reflected ray, but in order to be used as a velocity vector it must also incorporate the speed. Therefore it gets, multiplied with the magnitude of the original ray, thus resulting in the correct velocity vector.

In the example this procedure is applied to compute the collision response if a ball hits a plane or a cylinder. But it works also for arbitrary surfaces, it does not matter what the shape of the surface is. As long as a collision point and a Normal can be found the collision response method is always the same. The code which does these operations is

rt2=ArrayVel[BallNr].mag(); //find magnitude of velocity

ArrayVel[BallNr].unit(); //normalize it

//compute reflection

ArrayVel[BallNr] = TVector::unit( (normal * (2 * normal.dot(-ArrayVel[BallNr]))) + ArrayVel[BallNr] );

ArrayVel[BallNr] = ArrayVel[BallNr] * rt2; //muliply with magnitude to obtain final velocity vector

Determining the collision response, if two balls hit each other is much more difficult. Complex equations of particle dynamics have to be solved and therefore I will just post the final solution without any proof. Just trust me on this one :) During the collision of 2 balls we have a situation as it is depicted in Figure 4.

Figure 4

U1 and U2 are the velocity vectors of the two spheres at the time of impact. There is an axis (X_Axis) vector which joins the 2 centers of the spheres, and U1x, U2x are the projected vectors of the velocity vectors U1,U2 onto the axis (X_Axis) vector.

U1y and U2y are the projected vectors of the velocity vectors U1,U2 onto the axis which is perpendicular to the X_Axis. To find these vectors a few simple dot products are needed. M1, M2 is the mass of the two spheres respectively. V1,V2 are the new velocities after the impact, and V1x, V1y, V2x, V2y are the projections of the velocity vectors onto the X_Axis.

In more detail:

a) Find X_Axis

X_Axis = (center2 – center1);

Unify X_Axis, X_Axis.unit();

b) Find Projections

U1x = X_Axis * (X_Axis dot U1)

U1y = U1 – U1x

U2x = -X_Axis * (-X_Axis dot U2)

U2y = U2 – U2x

c) Find new velocities

V1x = ((U1x * M1) + (U2x * M2) - (U1x - U2x) * M2) / (M1 + M2)

V2x= ((U1x * M1) + (U2x * M2) - (U2x - U1x) * M1) / (M1 + M2)

In our application we set the M1=M2=1, so the equations get even simpler.

d) Find the final velocities.

V1y = U1y

V2y = U2y

V1 = V1x+V1y

V2 = V2x+V2y

The derivation of that equations has a lot of work, but once they are in a form like the above they can be used quite easily. The code which does the actual collision response is

TVector pb1, pb2, xaxis, U1x, U1y, U2x, U2y, V1x, V1y, V2x, V2y;

double a,b;

pb1 = OldPos[BallColNr1 ] + ArrayVel[BallColNr1] * BallTime; //find pisiotion of ball1

pb2 = OldPos[BallColNr2] + ArrayVel[BallColNr2] * BallTime; //find position of ball2

xaxis = (pb2 - pb1).unit(); // find xaxis

a = xaxis.dot(ArrayVel[BallColNr1]); // find projection

U1x = xaxis * a; // find projected vectors

U1y = ArrayVel[BallColNr1] - U1x;

xaxis = (pb1 - pb2).unit(); // do the same as above

b = xaxis.dot(ArrayVel[BallColNr2]); // to find projection

U2x = xaxis * b; // vectors for the other ball

U2y = ArrayVel[BallColNr2] - U2x;

V1x = (U1x + U2x - (U1x - U2x)) * 0.5; // now find new velocities

V2x = (U1x + U2x - (U2x - U1x)) * 0.5;

V1y = U1y;

V2y = U2y;

for (j=0; j < NrOfBalls; j++) // update all ball positions

ArrayPos[j] = OldPos[j] + ArrayVel[j] * BallTime;

ArrayVel[BallColNr1] = V1x + V1y; // set new velocity vectors

ArrayVel[BallColNr2] = V2x + V2y; // to the colliding balls

To simulate realistic movement with collisions, determining the the collision point and computing the response is not enough. Movement based upon physical laws has also to be simulated.

The most widely used method for doing this is using Euler equations. As indicated all the computations are going to be performed using time steps. This means that the whole simulation is advanced in certain time steps during which all the movement, collision and response tests are performed. As an example we can advanced a simulation 2 sec. on each frame. Based on Euler equations, the velocity and position at each new time step is computed as follows:

Velocity_New = Velovity_Old + Acceleration * TimeStep

Position_New = Position_Old + Velocity_New * TimeStep

Now the objects are moved and tested angainst collision using this new velocity. The Acceleration for each object is determined by accumulating the forces which are acted upon it and divide by its mass according to this equation.

Force = mass * acceleration

A lot of physics formulas :)

But in our case the only force the objects get is the gravity, which can be represented right away as a vector indicating acceleration. In our case something negative in the Y direction like (0,-0.5,0). This means that at the beginning of each time step, we calculate the new velocity of each sphere and move them testing for collisions. If a collision occurs during a time step (say after 0.5 sec with a time step equal to 1 sec.) we advance the object to this position, compute the reflection (new velocity vector) and move the object for the remaining time (which is 0.5 in our example) testing again for collisions during this time. This procedure gets repeated until the time step is completed.

When multiple moving objects are present, each moving object is tested with the static geometry for intersections and the nearest intersection is recorded. Then the intersection test is performed for collisions among moving objects, where each object is tested with everyone else. The returned intersection is compared with the intersection returned by the static objects and the closest one is take. The whole simulation is updated to that point, (i.e. if the closest intersection would be after 0.5 sec. we would move all the objects for 0.5 seconds), the reflection vector is calculated for the colliding object and the loop is run again for the remaining time.

Every time a collision takes place an explosion is triggered at the collision point. A nice way to model explosions is to alpha blend two polygons which are perpendicular to each other and have as the center the point of interest (here intersection point). The polygons are scaled and disappear over time. The disappearing is done by changing the alpha values of the vertices from 1 to 0, over time. Because a lot of alpha blended polygons can cause problems and overlap each other (as it is stated in the Red Book in the chapter about transparency and blending) because of the Z buffer, we borrow a technique used in particle rendering. To be correct we had to sort the polygons from back to front according to their eye point distance, but disabling the Depth buffer writes (not reads) does also the trick (this is also documented in the red book). Notice that we limit our number of explosions to maximum 20 per frame, if additional explosions occur and the buffer is full, the explosion is discarded. The source which updates and renders the explosions is