"Collision detection tutorial" - читать интересную книгу автора (Christopoulos Dimitrios)

Sphere – Sphere collision

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(TVectoramp; point, doubleamp; TimePoint, double Time2, intamp; BallNr1, intamp; 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 lt; NrOfBalls - 1; i++) {

  for (int j = i+1; j lt; NrOfBalls; j++) {

   RelativeV = ArrayVel[i] - ArrayVel[j]; // Find distance

   rays = TRay(OldPos[i], TVector::unit(RelativeV));

   MyTime = 0.0;

   if ( (rays.dist(ArrayPos[j])) gt; 40) continue;       //If distance between centers bigger than 2*radius

                                                                             //an intersection occurred

   while (MyTime lt; Time2) //Loop to find the exact intersection point

   {

    MyTime += Add;

    posi = OldPos[i] + RelativeV * MyTime;

    if (posi.dist(OldPos[j]) lt;= 40) {

     point = posi;

     if (Timedummy gt; (MyTime - Add)) Timedummy = MyTime - Add;

     BallNr1 = i;

     BallNr2 = j;

     break;

    }

   }

  }

 }

 if (Timedummy != 10000) {

  TimePoint = Timedummy;

  return 1;

 }

 return 0;

}