Previous Section  < Day Day Up >  Next Section

Applications in Collision Detection

The preceding section alluded to using circles and spheres for bounding geometry in your game. Certainly you can use other shapes, but the circle and sphere are simple shapes to work with numerically, and the test for collisions between circles and spheres is much faster than any other test. This test might lack precision, but because it's so fast, this test is perfect as the first line of defense. Let's look more closely at how to use these equations to mathematically determine whether two objects have collided.

Let's start with the two-dimensional circle, and then we'll expand the same process to 3D. Quite often, when you have an odd-shaped object such as a car, it's difficult to perform precise collision detection on the shape. One very common solution is to place it inside a bounding circle and just perform the collision detection on the circle instead. As you saw in a previous example, the car can be placed in a bounding circle defined by (x–h)2 + (y–k)2 = r2, as shown in Figure 2.12.

Figure 2.12. A general bounding circle on a car.

graphics/02fig12.gif

Now you can investigate the collision detection of two cars placed in bounding circles. Both circles are defined by a center and a radius, as shown in Figure 2.13.

Figure 2.13. Two bounding circles barely touching.

graphics/02fig13.gif

Notice that in Figure 2.13 the two circles are just barely touching. When this is the case, you can see that the distance (D) between the two centers must equal the sum of the two radii (r1+r2). This means that if the two circles are overlapping (that is, colliding), the distance between the centers must be less than the sum of the two radii (r1+r2), as shown in Figure 2.14.

Figure 2.14. Two bounding circles overlapping.

graphics/02fig14.gif

This observation results in a simple less-than-or-equal-to check. Earlier in this chapter we reviewed the distance formula, so that can be used to calculate the distance between the two centers. Then you just have to compare that distance to the sum of the two radii (r1+r2).

Circle-Circle Collision Detection

Given two circles graphics/02inl02.gif and graphics/02inl03.gif, if graphics/02inl04.gif a collision occurs.


NOTE

The circles do not have to be the same size for this method to work. They can have different-length radii based on the size of the objects inside.


Keep in mind that in video games objects move frame by frame, so this function must be set up inside a loop so that it's rechecked each frame. Also remember that as you move objects frame by frame, the motion is not smooth. The objects kind of jump a short distance each frame. This means that two objects might not touch at all in one frame and then overlap in the next frame; they might skip over the instant where they were just barely touching. That is why it's necessary to do a less-than-or-equal-to check rather than just an equal check.

Example 2.12: Circle-Circle Collision

Suppose you are coding the collision detection for a 2D racing game, and you decide to use bounding circles. In the current frame, one car's bounding circle is defined by the equation (x–50)2 + (y–20)2 = 900, and the other car's bounding circle is defined by the equation (x+10)2 + (y–10)2 = 400. Have they collided yet?

Solution

  1. To perform this collision detection, you first must determine the center and the radius for each bounding circle. The first circle has center (50,20) and a radius of 30, and the second circle has center (–10,10) and a radius of 20.

  2. Calculate the distance (D) between the two centers:

    graphics/02equ15.gif


  3. Finally, you need to check to see if D (r1+r2). In this case, (r1+r2) = 30+20 = 50, so D is not (r1+r2), which means that there is no collision.

As soon as you start coding this, you'll find that the square-root function is very expensive, meaning that it takes a lot of processing power. There is a quick and easy way to eliminate the square root and speed up this collision check. If you square both sides of the inequality, the same less-than-or-equal-to relationship is true. You can see in Example 2.12 that if 60.83 is not less than 50, (60.83)2 is still not less than (50)2. This faster method (Optimized Circle-Circle Collision Detection) is as follows.

Optimized Circle-Circle Collision Detection

Given two circles graphics/02inl05.gif and graphics/02inl06.gif, if (h2–h1)2 + (k2–k1)2 (r1+r2)2, there is a collision.


By now you can probably guess just how to extend this process to 3D. Rather than using bounding circles, you can use bounding spheres in 3D. Again, an equation for the bounding sphere can be determined by the model's center and the radius to its farthest vertex. After that, it's just a frame-by-frame check to see if the spheres have overlapped. We'll stick with the faster version from here on out.

Optimized Sphere-Sphere Collision Detection

Given two spheres graphics/02inl07.gif and graphics/02inl08.gif, if (h2–h1)2 + (k2–k1)2 + (l2–l1)2 (r1+r2)2, there is a collision.

The following simple function can be used to detect whether or not two spheres have collided. In this example, we will be using the sphere struct which we defined earlier, and which has been repeated here for ease. Notice that in calculating the distance between the centers of the spheres, we are not using square root but rather comparing the value against the sum of the radii squared. This is a slight but effective optimization that can dramatically improve your frame rate if there are a large number of sphere-to-sphere collision checks that are required every frame.


struct sphere

{

    float center[3];

    float radius;

};

// purpose: to detect a collision between 2 spheres

// input:   S1- our first sphere, passed by reference

//          S2- our second sphere, passed by reference

// output: true if there is a collision, else false

bool ColBetweenSpheres(sphere &S1, sphere &S2)

{

    return (pow(S2.center[0] – S1.center[0], 2) +

          pow(S2.center[1] – S1.center[1], 2) +

          pow(S2.center[2] – S1.center[2], 2)) <

          pow(S1.radius + S2.radius, 2));

}

Take note of the fact there is no complicated if-else statement in the function. Should the comparison of the two values resolve to true, then there has been a collision and that very answer can be returned. Should the comparison resolve to false, there has been no collision, and that answer can also be returned.


Example 2.13: Sphere-Sphere Collision

Suppose you are coding the collision detection for a 3D racing game, and you decide to use bounding spheres. In the current frame, one car's bounding sphere is defined by the equation (x–30)2 + (y–20)2 + (z+10)2 = 1600, and the other car's bounding sphere is defined by the equation x2 + (y–40)2 + (z+50)2 = 2500. Have they collided yet?

Solution

  1. To perform this collision detection, you first must determine the center and the radius for each bounding sphere. The first sphere has center (30,20,–10) and a radius of 40, and the second sphere has center (0,40,–50) and a radius of 50.

  2. Calculate the distance (D) between the two centers:

    graphics/02equ16.gif


  3. Finally, you need to check to see if D (r1+r2). In this case, (r1+r2) = 40+50 = 90, so D (r1+r2), which means that yes, there is a collision.

Bounding circles and spheres are a simple approach to collision detection. They're a relatively fast method, but they're not always the most accurate. Look back at Figure 2.11, where we first used a bounding circle on the car. Notice all the empty space within the circle? That space is dangerous, because it could cause false collisions. This phenomenon is illustrated in Figure 2.15.

Figure 2.15. False collisions.

graphics/02fig15.gif

One way to avoid false collisions is to use a different shape that fits your model more closely. Just make sure that you can define the shape with an equation of some sort so that you can perform a numeric check. Another way is to set up a hierarchy of circles. Start by checking for a collision between the two original bounding circles. If the check you performed earlier returns no collision, there's no problem. However, if it returns a collision, it might be a false alarm, so at that point you could perform a closer check. In other words, set up a conditional that states that if no collision occurs, keep going. If there is a collision, do a closer check. In this closer check, you can use several smaller bounding circles that fit the object more closely. This gives you better accuracy, but it takes extra processing time if there's a possibility of a collision. If the two larger circles aren't overlapping, there's no sense in taking the time to check all the smaller circles. Figure 2.16 shows how you might use smaller circles to get a tighter fit on the car.

Figure 2.16. A circle hierarchy on a car.

graphics/02fig16.gif

NOTE

Whether you follow up the initial check with smaller circles or any other more precise check, the one large bounding circle or sphere is always a fast approach for the first test.


The preceding chapter looked at intersecting lines, and this chapter examined intersecting circles and spheres. Collision detection is a significant part of any game engine, because it manages the interaction of all the individual objects in your game world. There will always be new ways of approaching collision detection that are faster or more accurate, but this discussion gives you a foundation for investigating alternative methods.

Self-Assessment

1.

Suppose you are coding the collision detection for a 2D baseball game, and you decide to use bounding circles. In the current frame, one player's bounding circle is defined by the equation (x–70)2 + (y–20)2 = 1600, and the baseball's bounding circle is defined by the equation (x–50)2 + (y–60)2 = 256. Have they collided yet?

2.

Suppose you are coding the collision detection for a 3D football game, and you decide to use bounding spheres. In the current frame, one player's bounding sphere is defined by the equation (x–50)2 + y2 + (z+20)2 = 1600, and the football's bounding sphere is defined by the equation (x–60)2 + (y–70)2 + (z+50)2 = 400. Have they collided yet?

3.

What might be an extra step you could take to avoid false collisions when working with bounding spheres?


    Previous Section  < Day Day Up >  Next Section