Basic Primitive Tests - Real-Time Collision Detection - page 223

touches the plane. The condition for Q to be on the plane is ( n · Q ) = d . Solving for

C )) ( n

t gives t 1, the AABB touches the plane at

time t , with point of contact Q . Unlike the moving-sphere-against-plane test, for an
AABB there will not necessarily be a unique point of contact, as the contact region
might be an edge or a face of the AABB. Due to the format used for the AABB in the
preceding presentation, the test for an OBB is identical, except for the computation of
r , which now involves the axes corresponding to the orientation of the OBB instead
of the world axes.

= ( r + d − ( n · · v ). If 0 ≤ t ≤

5.5.5 Intersecting Moving Sphere Against Sphere

Let two spheres S 0 and S 1 be given with radii r 0 and r 1 , respectively. Their cor-
responding movements are given by the two movement vectors v 0 and v 1 . The
parameterized movement of the sphere centers can therefore be described by the
expressions P 0 ( t ) = C 0 + t v 0 and P 1 ( t ) = C 1 + t v 1 over the time interval 0 ≤ t ≤ 1.

The vector d between the sphere centers at time t is given by

d ( t ) = ( C 0 + t v 0 ) − ( C 1 + t v 1 ) = ( C 0 − C 1 ) + t ( v 0 − v 1 ).

Assuming the spheres do not initially touch, they first come in contact when the length
of d equals the sum of their radii: ( d ( t )

d ( t )) 1/2

r 1 . To avoid the square root
expression, both sides of the equivalence can be squared, giving d ( t )

· = r 0 +

r 1 ) 2 .

· d ( t ) = ( r 0 +

To solve for t , let s = C 0 − C 1 , v = v 0 − v 1 , and r = r 0 + r 1 , then:

r 1 ) 2

· = + ⇔

d ( t ) d ( t ) ( r 0 (original expression)

r 2

( s + t v ) · ( s + t v ) = ⇔ (substituting d ( t ) = s + t v )

v ) t 2 r 2

· + · + · = ⇔

( s s ) 2( v s ) t ( v (expanding dot product)

v ) t 2 r 2 )

( v · + 2( v · s ) t + ( s · s − = 0 (canonic form for quadratic equation)

This is a quadratic equation in t . Writing the quadratic in the form at 2 + 2 bt + c = 0,

r 2 gives the solutions for t as

with a = v · v , b = v · s , and c = s · s −

√ b 2

= −

b ± − ac

t .

a

b 2

The discriminant d = − ac determines how many real-valued roots the quadratic

<

has. If d 0, it has no real-valued roots, meaning the spheres will not intersect. If

= >

d 0, there is one real root and the spheres become tangential at time t .If d 0,