Game Engine Architecture

614 12. Collision and Rigid Body Dynamics

12.3.5.1. Point versus Sphere

We can determine whether a point p lies within a sphere by simply forming

the separation vector s between the point and the sphere’s center c and then

checking its length. If it is greater than the radius of the sphere r, then the

point lies outside the sphere; otherwise, it lies inside:

;

if r, then is inside.

=−

≤

scp

sp

12.3.5.2. Sphere versus Sphere

Determining if two spheres intersect is almost as simple as testing a point

against a sphere. Again, we form a vector s connecting the center points of the

two spheres. We take its length, and compare it with the sum of the radii of the

two spheres. If the length of the separating vector is less than or equal to the

sum of the radii, the spheres intersect; otherwise, they do not:

12

12

;

if (rr), then spheres intersect.

=−

≤+

sc c

s

(12.1)

To avoid the square root operation inherent in calculating the length of vec-

tor s, we can simply square the entire equation. So Equation (12.1) becomes

12

2

(^2122)

;

;

if (rr) , then spheres intersect.

=−

=⋅

≤+

sc c

s ss

s

12.3.5.3. The Separating Axis Theorem

Most collision detection systems make heavy use of a theorem known as

the separating axis theorem (htt p://en.wikipedia.org/wiki/Separating_axis_

theorem). It states that if an axis can be found along which the projection of

two convex shapes do not overlap, then we can be certain that the two shapes

do not intersect at all. If such an axis does not exist and the shapes are convex,

then we know for certain that they do intersect. (If the shapes are concave, then

they may not be interpenetrating despite the lack of a separating axis. This is

one reason why we tend to favor convex shapes in collision detection.)

This theorem is easiest to visualize in two dimensions. Intuitively, it says

that if a line can be found, such that object A is entirely on one side of the line

and object B is entirely on the other side, then objects A and B do not overlap.

Such a line is called a separating line, and it is always perpendicular to the sepa-

rating axis. So once we’ve found a separating line, it’s a lot easier to convince

ourselves that the theory is in fact correct by looking at the projections of our

shapes onto the axis that is perpendicular to the separating line.