Game Development Reference

In-Depth Information

earliest time the objects come in contact is given by the smallest
t
for which

t
r

∈

A

−

B
.

We need to perform a ray cast on the CSO to find the
t
at the first hit. We will

denote this instance of time by
t
hit
. The corresponding point
t
hit
r
is called the

hit spot
. If the origin is not contained in
A

−

B
, meaning
t
hit
>
0, then the hit

spot must be a point on the boundary of
A

−

B
. In that case, there exists a proper

normal at the hit spot.

A nonzero vector
n
and a point
p
on the boundary of the CSO define a sup-

porting plane if

n

·

p
=max

{

n

·

x
:
x

∈

A

−

B

}

.

A supporting plane exists for all points on the boundary as long as the CSO is con-

vex. Clearly, any nonzero vector
n
is a normal of a supporting plane at
s
A−B
(
n
).

Let us make a few observations. For a supporting plane with normal
n
and

point
p
on the boundary of
A

−

B
, we know that all points
x
for which
n

·

x
>
n

·

p

are not contained in
A

B
.Now,let
x
=
t
r
be a point on the ray. We find that

the section of the ray corresponding to

−

t
n

·

r
>
n

·

p

is not contained in
A

−

B
, and thus cannot contain the hit spot. More specifically,

for

t
clip
=
n

·

p

r
,

n

·

we know the following:

1. If
n

·

r
<
0,then
t
clip
is a lower bound for
t
hit
. Moreover, if
n

·

p
<
0,then

t
clip
is positive and indeed the ray is clipped.

2. If
n

p
<
0,then

t
clip
is negative and the ray can be rejected since it will never hit the CSO.

·

r
>
0,then
t
clip
is an upper bound for
t
hit
.Now,if
n

·

3. If
n

p
<
0,

then the ray can be rejected as well, since it completely lies in the positive

half-space of the supporting plane.

·

r
=0, then the ray is not clipped at all. Furthermore, if
n

·

Note that in all three cases the ray is either clipped by or completely contained in

the positive half-space of the supporting plane if
n

p
<
0.

Our strategy for computing
t
hit
is to iteratively clip sections of the ray that

are guaranteed not to intersect the CSO until we arrive at the hit spot. This ap-

proach is generally known as
conservative advancement
[Mirtich and Canny 95];

·