For the collision detection we are going to use algorithms which are mostly used in ray tracing.
Lets first define a ray.
A ray using vector representation is represented using a vector which denotes the start and a vector (usually normalized) which is the direction in which the ray goes. Essentially a ray starts from the start point and travels in the direction of the direction vector. So our ray equation is.
PointOnRay = Raystart + t*Raydirection
t is a float which takes values from [0, infinity).
With 0 we get the start point and substituting other values we get the corresponding points along the ray.
PointOnRay, Raystart, Raydirection, are 3D Vectors with values (x,y,z). Now we can use this ray representation and calculate the intersections with plane or cylinders.
A plane is represented using its Vector representation as
Xn dot X = d
Xn, X are vectors and d is a floating point value.
Xn is its normal
X is a point on its surface
d is a float representing the distance of the plane along the normal, from the center of the coordinate system.
Essentially a plane represents a half space. So all that we need to define a plane is a 3D point and a normal from that point which is perpendicular to that plane. These two vectors form a plane, ie. if we take for the 3D point the vector (0,0,0) and for the normal (0,1,0) we essentially define a plane across x,z axes. Therefore defining a point and a normal is enough to compute the Vector representation of a plane.
Using the vector equation of the plane the normal is substituted as Xn and the 3D point from which the normal originates is substituted as X. The only value that is missing is d which can easily be computed using a dot product (from the vector equation).
(Note: This Vector representation is equivalent to the widely known parametric form of the plane Ax + By + Cz + D=0 just take the three x,y,z values of the normal as A,B,C and set D=-d).
The two equations we have until know are
PointOnRay = Raystart + t * Raydirection
Xn dot X = d
If a ray intersects the plane at some point then there must be some point on the ray which satisfies the plane equation as follows
Xn dot PointOnRay = d
or
(Xn dot Raystart) + t* (Xn dot Raydirection) = d
solving for t
t = (d – Xn dot Raystart) / (Xn dot Raydirection)
or by replacing d
t= (Xn dot PointOnRay – Xn dot Raystart) / (Xn dot Raydirection)
or by summing it up
t= (Xn dot (PointOnRay – Raystart)) / (Xn dot Raydirection)
t represents the distance from the start until the intersection point along the direction of the ray. Therefore substituting t into the ray equation we can get the collision point. There are a few special cases though.
If Xn dot Raydirection = 0 then these two vectors are perpendicular (ray runs parallel to plane) and there will be no collision. If t is negative the collision takes place behind the starting point of the ray along the opposite direction and again there is no intersection. In the code now the function
int TestIntersionPlane(const Plane& plane,const TVector& position,const TVector& direction, double& lamda, TVector& pNormal) {
double DotProduct = direction.dot(plane._Normal); //Dot product between plane normal and ray direction
double l2;
//Determine if ray paralle to plane
if ((DotProduct < ZERO) && (DotProduct > -ZERO)) return 0;
l2=(plane._Normal.dot(plane._Position-position)) / DotProduct; //Find distance to collision point
if (l2 < -ZERO) //Test if collision behind start
return 0;
pNormal = plane._Normal;
lamda=l2;
return 1;
}
It calculates and returns the intersection. Returns 1 if there is an intersection otherwise 0. The parameters are the plane, the start and direction of the vector, a double (lamda) where the collision distance is stored if there was any, and the returned normal at the collision point.
Computing the intersection between an infinite cylinder and a ray is much more complicated that is why I won't explain it here. There are way too many math involved too be useful and my goal is primarily to give you tools how to do it without getting into much detail (this is not a geometry class). If anyone is interested in the theory behind the intersection code, please look at the
Graphic Gems II Book (pp 35, intersection of a with a cylinder). A cylinder is represented as a ray, using a start and direction (here it represents the axis) vector and a radius (radius around the axis of the cylinder). The relevant function is
int TestIntersionCylinder(const Cylinder& cylinder, const TVector& position, const TVector& direction, double& lamda, TVector& pNormal, TVector& newposition)
Returns 1 if an intersection was found and 0 otherwise.
The parameters are the cylinder structure (look at the code explanation further down), the start, direction vectors of the ray. The values returned through the parameters are the distance, the normal at the intersection point and the intersection point itself.
A sphere is represented using its center and its radius. Determining if two spheres collide is easy. Just by finding the distance between the two centers (dist method of the TVector class) we can determine if they intersect, if the distance is less than the sum of their two radius.
The problem lies in determining if 2 MOVING spheres collide. Bellow is an example where 2 sphere move during a time step from on point to another. Their paths cross in-between but this is not enough to prove that an intersection occurred (they could pass at a different time) nor can be the collision point be determined.
Figure 1
The previous intersection methods were solving the equations of the objects to determine the intersection. When using complex shapes or when these equations are not available or can not be solved, a different method has to be used. The start points, endpoints, time step, velocity (direction of the sphere + speed) of the sphere and a method of how to compute intersections of static spheres is already known. To compute the intersection, the time step has to be sliced up into smaller pieces. Then we move each time the spheres according to that sliced time step using its velocity, and check for collisions. If at any point collision is found (which means the spheres have already penetrated each other) then we take the previous position as the intersection point (we could start interpolating between these points to find the exact intersection position, but that is mostly not required).
The smaller the time steps, the more slices we use the more accurate is the method. As an example lets say the time step is 1 and our slices are 3, then we would check the two balls for collision at time 0 , 0.33, 0.66, 1. Easy !!!! The code which performs this is
/*************************************************************************************/
/*************************************************************************************/
/*** Find if any of the current balls ****/
/*** intersect with each other in the current timestep ****/
/***Returns the index of the 2 intersecting balls, the point and time of intersection */
/*************************************************************************************/
/*************************************************************************************/
int FindBallCol(TVector& point, double& TimePoint, double Time2, int& BallNr1, int& BallNr2) {
TVector RelativeV;
TRay rays;
double MyTime=0.0, Add=Time2/150.0, Timedummy=10000, Timedummy2=-1;
TVector posi;
//Test all balls against each other in 150 small steps
for (int i=0; i < NrOfBalls - 1; i++) {
for (int j = i+1; j < NrOfBalls; j++) {
RelativeV = ArrayVel[i] - ArrayVel[j]; // Find distance
rays = TRay(OldPos[i], TVector::unit(RelativeV));
MyTime = 0.0;
if ( (rays.dist(ArrayPos[j])) > 40) continue; //If distance between centers bigger than 2*radius
//an intersection occurred
while (MyTime < Time2) //Loop to find the exact intersection point
{
MyTime += Add;
posi = OldPos[i] + RelativeV * MyTime;
if (posi.dist(OldPos[j]) <= 40) {
point = posi;
if (Timedummy > (MyTime - Add)) Timedummy = MyTime - Add;
BallNr1 = i;
BallNr2 = j;
break;
}
}
}
}
if (Timedummy != 10000) {
TimePoint = Timedummy;
return 1;
}
return 0;
}
So now that we can determine the intersection point between a ray and a plane/cylinder we have to use it somehow to determine the collision between a sphere and one of these primitives. What we can do so far is determine the exact collision point between a particle and a plane/cylinder. The start position of the ray is the position of the particle and the direction of the ray its velocity (speed and direction). To make it usable for spheres is quite easy. Look at Figure 2a to see how this can be accomplished.
Figure 2a Figure 2b
Each sphere has a radius, take the center of the sphere as the particle and offset the surface along the normal of each plane/cylinder of interest. In Figure 2a these new primitives are represented with doted lines. Your actual primitives of interest are the ones represented with continuous lines but the collision testing is done with the offset primitives (represented with doted lines). In essence we perform the intersection test with an little offset plane and a larger in radius cylinder. Using this little trick the ball does not penetrate the surface if an intersection is determined with its center. Otherwise we get a situation as in Figure 2b, where be sphere penetrates the surface. This happens because we determine the intersection between its center and the primitives, which means we did not modify our original code!
Having determined where the collision takes place we have to determine if the intersection takes place in our current time step. Timestep is the time we move our sphere from its current point according to its velocity. Because we are testing with infinite rays there is always the possibility that the collision point is after the new position of the sphere. To determine this we move the sphere, calculate its new position and find the distance between the start and end point. From our collision detection procedure we get also the distance from the start point to its collision point. If this distance is less than the distance between start and end point then there is a collision. To calculate the exact time we solve this simple equation. Represent the distance between start – end point with Dst, the distance between start – collision point Dsc, and the time step as T. The time where the collision takes place (Tc) is:
Tc= Dsc * T / Dst
All this is performed of course if an intersection is determined. The returned time is a fraction of the whole time step, so if the time step was 1 sec, and we found an intersection exactly in the middle of the distance then the calculated collision time would be 0.5 sec. this can be interpreted like "0.5 sec after the start there is an intersection". Now the intersection point can be calculated by just multiplying Tc with the current velocity and adding it to the start point.
Collision point= Start + Velocity * Tc
This is the collision point on the offset primitive, to find the collision point on the real primitive we add to that point the reverse of the normal at that point (which is also returned by the intersection routines) by the radius of the sphere. Note that the cylinder intersection routine returns the intersection point if there is one so it does not need to be calculated.