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

Custom Search