Game Development Reference

In-Depth Information

r

t
clip

t = 1

v

p

A − B

s

t = 0

Figure 5.5.
A new lower bound
t
clip
is found by clipping the ray
r
using the supporting

plane at
p
=
s
A−B
(
−
v
)
.

however, in our case, we perform the advancement inside GJK. We do regular

GJK iterations and use the supporting planes that are generated in each iteration

as clipping planes. Each time we find a new lower bound
t
clip
, time is advanced

to this value. In terms of configuration space, we say that the origin is “shifted”

to
t
clip
r
. Of course, conceptually the origin does not move along the ray. Instead,

the CSO moves in the opposite direction.

Let
s
=
t
r
be the current lower bound for the hit spot. Then the current CSO

is
A−B−
s
. In search of the point of the CSO closest to the origin, GJK generates

a supporting plane with normal

−
v
and support point
p
=
s
A−B
(
−
v
). We can

identify the intersection point of the plane and the ray as

t
clip
=
v

·

p

v

·

r

and find the following:

1. If
v
·
r
>
0,then
t
clip
is a lower bound for
t
hit
,andif
v
·
p
>t
v
·
r
,then

t
clip
>t
, which means that we found a better lower bound. See Figure 5.5

for an illustration of this case.

2. If
v

·

r
<
0,then
t
clip
is an upper bound for
t
hit
,andif
v

·

p
>t
v

·

r
,then

t
clip
<t
, which means we have evidence that the ray misses.

p
>
0, then the ray

misses as well, since it is completely contained in the positive half-space of

the supporting plane.

·

·

3. If
v

r
=0, then the ray is not clipped at all, and if
v

Again, we see that for all three cases, if
v

r
, then the ray can either be

clipped or rejected. As long as this condition is not valid, we continue performing

regular GJK iterations. Note that we need to search for the closest point of the

·

p
>t
v

·