Gamasutra: The Art & Business of Making Gamesspacer
Simple Intersection Tests For Games
View All     RSS
September 17, 2014
arrowPress Releases
September 17, 2014
PR Newswire
View All





If you enjoy reading this site, you might also want to check out these UBM Tech sites:


 
Simple Intersection Tests For Games
by miguel gomez []

October 18, 1999 Article Start Page 1 of 7 Next
 

Whether it's your car crossing the finish line at 180 miles per hour, or a bullet tearing through the chest of your best friend, all games make use of collision detection for object interaction. This article describes some simple intersection tests for the most useful shapes: spheres and boxes.

Sweep Tests for Moving Objects

A common approach to collision detection is to simply test for whether two objects are overlapping at the end of each frame. The problem with this method is that quickly moving objects can pass through each other without detection. To avoid this problem, their trajectories can be subdivided and the objects checked for overlap at each point; however, this gets expensive if either object experienced a large displacement. On the other hand, a sweep test can efficiently determine a lower and upper bound for the time of overlap, which can then be used as more optimal starting points for the subdivision algorithm.

A Sphere-Plane Sweep Test

Figure 1 shows an example of a quickly moving sphere passing through a plane. It can be seen that C0 is on the positive side of the plane and C1 is on its negative side.

Kuras
Figure 1. A sphere passes through a plane.

 

In general, if a sphere penetrated a plane at some point during the frame, then d0>r and d1<r, where r is the radius of the sphere and d0 and d1 are the signed distances from the plane to C0 and C1, respectively. The signed distance from a point C to a plane can be calculated with the formula

More efficiently, we can store the plane in the form {n, D}, where

The distance d is then calculated

The trajectory from C0 to C1 can be parameterized with a variable u, which may be thought of as normalized time, since its value is 0 at C0 and 1 at C1. The normalized time at which the sphere first intersects the plane is given by

The center of the sphere at this time can then be interpolated with an affine combination of C0 and C1

This formula interpolates Ci correctly as long as d0 is not equal to d1 (which is the case if displacement has occurred), even when r = 0 (the case of a line segment). If desired, the parameter u can also be used to linearly interpolate the orientation of an object at this point.

In this example, it was assumed that the sphere approached the plane from the positive side and that the sphere was not already penetrating the plane at C0.. In the case that there could have been penetration on the previous frame, the condition |d0|<=r should also be checked. Listing 1 gives an implementation of this sphere-plane sweep test.

Listing 1. A sphere-plane sweep test.

#include "vector.h"

class PLANE

{

 

public:

VECTOR N;
//unit normal

SCALAR D;
//distance from the plane to the origin from a
//normal and a point

PLANE( const VECTOR& p0, const VECTOR& n ): N(n), D(-N.dot(p0))
{}
//from 3 points

PLANE( const VECTOR& p0, const VECTOR& p1,
const VECTOR& p2 ): N((p1-p0).cross(p2-p0).unit()),
D(-N.dot(p0))
{}
//signed distance from the plane topoint 'p' along
//the unit normal

const SCALAR distanceToPoint( const VECTOR& p ) const
{

 

 

return N.dot(p) + D;

}

};

const bool SpherePlaneSweep
(
const SCALAR r, //sphere radius
const VECTOR& C0, //previous position of sphere
const VECTOR& C1, //current position of sphere
const PLANE& plane, //the plane
VECTOR& Ci, //position of sphere when it first touched the plane
SCALAR& u //normalized time of collision

)

{

const SCALAR d0 = plane.distanceToPoint( C0 );
const SCALAR d1 = plane.distanceToPoint( C1 );

//check if it was touching on previous frame
if( fabs(d0) <= r )

{

 

Ci = C0;
u = 0;
return true;

}

//check if the sphere penetrated during this frame
if( d0>r && d1<r )
{

 

u = (d0-r)/(d0-d1); //normalized time
Ci = (1-u)*C0 + u*C1; //point of first contact
return true;

}

return false;

}

For the definition of the VECTOR class, please see [3].


Article Start Page 1 of 7 Next

Related Jobs

Crystal Dynamics
Crystal Dynamics — Redwood City, California, United States
[09.16.14]

Senior Environment Artist
DoubleDown Interactive
DoubleDown Interactive — Seattle, Washington, United States
[09.16.14]

Principal Game Designer
DoubleDown Interactive
DoubleDown Interactive — Seattle, Washington, United States
[09.16.14]

Senior Product Manager
Mobilityware
Mobilityware — Irvine, California, United States
[09.16.14]

Senior UI Artist






Comments


Dave Moss
profile image
The scaler u0 and u1 represent the time the objects will collide...

Petter Oberg
profile image
Shouldn't SphereSphereSweep() return true only if 0 <= u0 <= 1, since else the collision does not occur within this frame?


none
 
Comment: