Game Development Reference

In-Depth Information

proportional to the maximum squared length of a vector in
Y
. So, a robust imple-

mentation would use as termination condition

2

2
:
y
∈

v

≤

ε
tol
max

{
y

Y

}

,

where
ε
tol
is an order of magnitude larger than the machine epsilon of the used

floating-point format. Choosing a tolerance
ε
tol
that is too small may result in

infinite looping, since then the rounding noise in the computation of

2
can

v

become greater than
ε
tol
times the maximum squared length of a vector
y

Y
.

The convergence speed depends on the used shape types. We have found

the worst convergence for quadric shapes such as spheres and cylinders. For a

quadric, the average number of iterations is roughly proportional to

∈

log(
ε
tol
).

For instance, an
ε
tol
of 10
−
6
results in eight iterations on average for random rays

with a high hit probability. Polytopes usually take fewer iterations.

For collision detection, the performance of GJK can be boosted by allowing

an early out as soon as
v
becomes a separating axis [van den Bergen 99]. Frame

coherence can be exploited by caching this axis and using it as the initial
v
in the

next frame. A similar scheme can be used for the GJK ray cast. In case of a miss,

v
is a separating axis of the ray and the object CSO. If the configuration of objects

does not change a lot over time, then this separating axis is likely to be a sepa-

rating axis in the next frame as well. By initializing
v
with a previously returned

separating axis, the number of iterations per frame can be reduced considerably.

Note that since this
v
may no longer be contained in
A

−

B
, it is necessary to skip

the termination test for the first iteration. Overall, a continuous GJK collision test

that exploits earlier separating axes is only slightly more expensive than the static

version.

−

5.7 Contacts

A contact between two objects is defined by a contact point and an orientation

of the contact plane. The plane separates the two objects at the contact point.

In physics-based simulations, contact constraints should keep the objects from

further interpenetrating at the contact point. Usually, a force or impulse along the

contact normal is applied in order to take care of this. The objects are, of course,

free to move away from each other, so normal forces or impulses act in only one

direction. Furthermore, objects in contact usually experience friction. Friction

acts laterally, i.e., along the contact plane.

The collision handler should return a contact point and normal for each collid-

ing pair of convex objects. The continuous collision test described in Section 5.6

returns these contact data for the first time of contact. The problem is that if the