Gamasutra is part of the Informa Tech Division of Informa PLC

This site is operated by a business or businesses owned by Informa PLC and all copyright resides with them. Informa PLC's registered office is 5 Howick Place, London SW1P 1WG. Registered in England and Wales. Number 8860726.


Gamasutra: The Art & Business of Making Gamesspacer
Simple Intersection Tests For Games
View All     RSS
May 21, 2019
arrowPress Releases
May 21, 2019
Games Press
View All     RSS








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 Previous Page 2 of 7 Next
 

A Sphere-Sphere Sweep Test

Figure 2 shows two spheres that collided between frames. If these spheres experienced acceleration during the frame, their trajectories will be second or higher order curves; however, usually their paths can be accurately approximated as linear segments according to the equations

 

Since both spheres traveled for the same amount of time, u is the same for both trajectories. The square of the distance between the lines is

and to calculate when they first make contact, we must solve for u such that

This leads to the quadratic equation

The vector vba can be thought of as the displacement of B observed by A. This equation is quadratic in u, so there may be no solution (the spheres never collided), one solution (they just glanced each other), or two solutions (in which case the lesser solution is when they began to overlap and the greater is when they became disjoint again). Again, it is a good idea to check for overlap at the beginning of the frame, since this will handle the case of two stationary spheres. Listing 2 shows an implementation of the sphere-sphere sweep test.

Listing 2. The sphere-sphere sweep test.

#include "vector.h"

template< class T >

inline void SWAP( T& a, T& b )
//swap the values of a and b

{

 

const T temp = a;
a = b;
b = temp;

}

// Return true if r1 and r2 are real
inline bool QuadraticFormula
(
const SCALAR a,
const SCALAR b,
const SCALAR c,
SCALAR& r1, //first
SCALAR& r2 //and second roots
)

{

 

 

const SCALAR q = b*b - 4*a*c;
if( q >= 0 )

{

 

 

const SCALAR sq = sqrt(q);
const SCALAR d = 1 / (2*a);
r1 = ( -b + sq ) * d;
r2 = ( -b - sq ) * d;
return true;//real roots

}

else

{

 

 

return false;//complex roots

}

}

const bool SphereSphereSweep
(
const SCALAR ra, //radius of sphere A
const VECTOR& A0, //previous position of sphere A
const VECTOR& A1, //current position of sphere A
const SCALAR rb, //radius of sphere B
const VECTOR& B0, //previous position of sphere B
const VECTOR& B1, //current position of sphere B
SCALAR& u0, //normalized time of first collision
SCALAR& u1 //normalized time of second collision

)

{

 

const VECTOR va = A1 - A0;
//vector from A0 to A1

const VECTOR vb = B1 - B0;
//vector from B0 to B1

const VECTOR AB = B0 - A0;
//vector from A0 to B0

const VECTOR vab = vb - va;
//relative velocity (in normalized time)

const SCALAR rab = ra + rb;

const SCALAR a = vab.dot(vab);
//u*u coefficient

const SCALAR b = 2*vab.dot(AB);
//u coefficient

const SCALAR c = AB.dot(AB) - rab*rab;
//constant term

//check if they're currently overlapping
if( AB.dot(AB) <= rab*rab )

{

 

 

u0 = 0;
u1 = 0;
return true;

}

//check if they hit each other
// during the frame
if( QuadraticFormula( a, b, c, u0, u1 ) )
{

 

 

if( u0 > u1 )
SWAP( u0, u1 );
return true;

}

return false;

}


Article Start Previous Page 2 of 7 Next

Related Jobs

Insomniac Games
Insomniac Games — Burbank, California, United States
[05.21.19]

User Experience Researcher
Qualcomm
Qualcomm — San Diego, California, United States
[05.21.19]

PBR Environment Game Artist
Infinity Ward / Activision
Infinity Ward / Activision — Woodland Hills, California, United States
[05.21.19]

UI Engineer (Temporary)
FoxNext Games
FoxNext Games — San Jose , California, United States
[05.20.19]

Senior Character Artist





Loading Comments

loader image