Game Development Reference

In-Depth Information

translated CSO, so we must add
p

s
, rather than
p
, to the current simplex. Each

time a better lower bound is found, the current simplex is flushed and GJK is

restarted using the last-found support point as the initial simplex. An alternative

to flushing the simplex would be to translate it along with the CSO. However, this

approach is not advised since simplices generated from the translated simplex

may be close to being affinely dependent, causing all sorts of numerical issues.

−

Algorithm 2
GJK-based continuous collision test. For positive results, this algorithm

terminates with
t
being the time of impact,
s
the hit spot, and
n
the normal at
s
.

t

←

0;

←

s

0
;

n
←
0
;

v
←

arbitrary point in
A − B
;

W ←∅
;

while

2
>ε
2
do

v

begin

p

←

s
A−B
(

−

v
);

if
v

·

p
>t
v

·

r
then

begin

if
v

r
>
0
then

begin

t
=
v
·
p

v
·
r

·

;

if
t>
1
then return false
;

s

←

t
r
;

W

←∅

;

n

←−

v

end

else return false
;

end
;

Y

←

W

∪{

p

−

s

}

;

←

point closest to the origin of conv(
Y
);

v

W

←

smallest
X

⊆

Y
such that
v

∈

conv(
X
)

end
;

return true

The algorithm terminates when either
s
is close enough to
A

−

B
or we find

evidence that the ray does not intersect
A

B
. Since the ray has a finite length,

we can also return a miss as soon as the lower bound
t
becomes greater than one.

The distance of
s
to
A

−

−

B
is approximated by

v

, so an obvious termination

2

ε
2
,where
ε
is the set tolerance for the absolute error of

condition is

v

≤