Collision detection
Jiří Chmelík, Marek Trtík
PA199
2
 Broad phase
 Sweep and prune algorithm
 Narrow phase
 Gilbert-Johnson-Keerthi (GJK) algorithm
 Caching collisions
 Computing collision time
Outline
3
Broad phase
4
 The goal is to quickly find pairs of potentially colliding rigid bodies.
 Used algorithm defines meaning of “potentially colliding”. Examples:
 When AABBs of the bodies are colliding.
 When both bodies are in the same area of space.
 We can use space partitioning data structures we already know:
 Octree, k-D tree, BSP
 Rigid bodies change their positions and orientations during simulation.
=> The data structure must be periodically updated.
 Utilize time coherence of frames (positions of bodies do not change
much between adjacent frames) to get an efficient update algorithm.
Broad phase
5
x
y
A
C
𝑥 𝐴 𝑥 𝐴
𝑦 𝐴
𝑦 𝐴
𝑥 𝐶 𝑥 𝐶
B
𝑥 𝐵
𝑥 𝐵
D
𝑥 𝐷
𝑥 𝐷
𝑦 𝐷
𝑦 𝐷
𝑦 𝐵
𝑦 𝐵
𝑦 𝐶
𝑦 𝐶
𝐿 𝑥 = [ 𝑥 𝐴, 𝑥 𝐶, 𝑥 𝐴, 𝑥 𝐵, 𝑥 𝐶, 𝑥 𝐵, 𝑥 𝐷, 𝑥 𝐷 ]
𝐿 𝑦 = [ 𝑦 𝐶, 𝑦 𝐴, 𝑦 𝐶
, 𝑦 𝐷, 𝑦 𝐵, 𝑦 𝐴
, 𝑦 𝐵
, 𝑦 𝐷
]
Use InsertSort
Sweep and prune algorithm
𝑊𝑥 = { }
𝑊𝑦 = { }
𝑊 = 𝑊𝑥 ∩ 𝑊𝑦 = { }
A, 𝐶 , {𝐵, 𝐶}
A, 𝐶 , {𝐵, 𝐷}{A, 𝐷},{A, 𝐵},
{A, 𝐶}
6
 The presented version is easy to understand and implement.
 But it wastes time by recomputing 𝑊 from scratch each time step.
 In practice, we use an improved version:
 We start with the arrays 𝐿 𝛼, 𝛼 ∈ {𝑥, 𝑦, 𝑧}, and 𝑊 from the previous frame.
 We incrementally update each 𝐿 𝛼 and 𝑊 for each relocated object 𝐴.
foreach axis 𝛼 ∈ {𝑥, 𝑦, 𝑧} do:
Update 𝛼 𝐴 in 𝐿 𝛼 by the new lower bound of 𝐴 along the axis 𝛼.
while ∃𝛼 𝑋
𝑌
right before 𝛼 𝐴 in 𝐿 𝛼 s.t. 𝛼 𝑋
𝑌
> 𝛼 𝐴 do:
Swap 𝛼 𝐴 with 𝛼 𝑋
𝑌
in 𝐿 𝛼.
if 𝑋 is None then Insert {𝐴, 𝑌} to 𝑊.
Sweep and prune algorithm
Moving 𝛼 𝐴
“to the left”
7
Update 𝛼 𝐴 in 𝐿 𝛼 by the new upper bound of 𝐴 along the axis 𝛼.
while ∃𝛼 𝑋
𝑌
right after 𝛼 𝐴 in 𝐿 𝛼 s.t. 𝛼 𝐴 > 𝛼 𝑋
𝑌
do:
Swap 𝛼 𝐴 with 𝛼 𝑋
𝑌
in 𝐿 𝛼.
if 𝑌 is None then Insert {𝐴, 𝑋} to 𝑊.
while ∃𝛼 𝑋
𝑌
right after 𝛼 𝐴 in 𝐿 𝛼 s.t. 𝛼 𝐴 > 𝛼 𝑋
𝑌
do:
Swap 𝛼 𝐴 with 𝛼 𝑋
𝑌
in 𝐿 𝛼.
if 𝑋 is None then Erase {𝐴, 𝑌} from 𝑊.
while ∃𝛼 𝑋
𝑌
right before 𝛼 𝐴 in 𝐿 𝛼 s.t. 𝛼 𝑋
𝑌
> 𝛼 𝐴 do:
Swap 𝛼 𝐴
with 𝛼 𝑋
𝑌
in 𝐿 𝛼.
if 𝑌 is None then Erase {𝐴, 𝑋} from 𝑊.
Sweep and prune algorithm
Moving 𝛼 𝐴
“to the right”
Moving 𝛼 𝐴
“to the right”
Moving 𝛼 𝐴
“to the left”
8
 Possible memory representation of the lists 𝐿 𝛼, 𝛼 ∈ {𝑥, 𝑦, 𝑧}:
struct Link {
Link *next, *prev;
float coord;
char lohi : 1;
};
using AABB = Link[2][3];
Sweep and prune algorithm
𝐴𝐴𝐵𝐵
next
𝑥 𝐴 in 𝐿 𝑥
𝑦 𝐴 in 𝐿 𝑦
𝑧 𝐴 in 𝐿 𝑧
𝑥 𝐴 in 𝐿 𝑥
𝑦 𝐴 in 𝐿 𝑦
𝑧 𝐴 in 𝐿 𝑧
prev
Link[0][*]
Link[1][*]
Points to some
“red” link in the
previous AABB.
Represents
either 𝛼 𝐴 or 𝛼 𝐴
.
If lohi == 0, then
“coord” is 𝛼 𝐴
and 𝛼 𝐴 otherwise.
9
 If “p” is a pointer to a “Link” of the list 𝐿 𝛼, 𝛼 ∈ {0,1,2} (i.e., {𝑥, 𝑦, 𝑧}), then
we can convert it to a pointer to AABB using the pointer arithmetic:
(AABB*)(p – (𝛼 + 3 * (int)p.lohi) * sizeof(Link))
 Represent the set 𝑊 as a dictionary of pairs of object IDs.
 Sort the pair s.t. the lower ID comes first and the other the second.
 Initialize the data structure to contain a single auxiliary AABB s.t:
 Values in the links are: 𝑥 𝐴 = 𝑦 𝐴 = 𝑧 𝐴 = −∞ and 𝑥 𝐴
= 𝑦 𝐴
= 𝑧 𝐴
= +∞.
 All 2*3 links are properly interconnected in the lists 𝐿 𝑥, 𝐿 𝑦, 𝐿 𝑧.
 This auxiliary AABB avoids the “nullptr” check in the algorithm (loops).
Sweep and prune algorithm
10
 Performance of the algorithm is sensitive to alignment of objects
along coordinate axes:
 A relocation of an object leads to a lot of swaps thought the “cluster”
in the array.
Sweep and prune algorithm
x
y
A C B D
“Cluster” of bounds
𝑦∗ and 𝑦∗
in 𝐿 𝑦 due to
alignment of objects
along the x axis.
11
Narrow phase
12
 The goal is for each pair of potentially colliding shapes to:
 Decide whether the shapes really collide or not.
 Compute a finite model of the (infinite) set of
all collision points.
 Example: Find finite and minimal number of points
in ℋ whose convex hull contains ℋ.
 Requirement: The effect of collision forces computed at points of the
model must be equal to collision forces computed at all points in ℋ.
Narrow phase
Stack of two boxes
(top view)
ℋ
𝐴
𝐵
𝐷
𝐶
13
 Decides whether two convex shapes have empty intersection or not.
Convex shapes Concave shapes
 We can approximate a concave shape by a set of convex shapes.
 For the empty intersection we can obtain a pair of the closest points.
 We must first build a terminology:
 Minkowski sum and difference
 Simplex
 Support function
Gilbert-Johnson-Keerthi (GJK) algorithm
14
 Minkowski sum: 𝒜 + ℬ = 𝒂 + 𝒃; 𝒂 ∈ 𝒜 ∧ 𝒃 ∈ ℬ .
 How to draw Minkowski sum?
 Choose some points ෝ𝒂 ∈ 𝒜 ∧ ෡𝒃 ∈ ℬ.
 Then, ∀𝒂 ∈ 𝒜 ∃𝒂′ s.t. 𝒂 = ෝ𝒂 + 𝒂′.
 Therefore, for each 𝒂 ∈ 𝒜 ∧ 𝒃 ∈ ℬ
𝒂 + 𝒃 = ෝ𝒂 + ෡𝒃 + 𝒂′ + 𝒃′
 So, we draw 𝒜 + ℬ around ෝ𝒂 + ෡𝒃:
 Draw ℬ around ෝ𝒂 + ෡𝒃.
 Draw 𝒜 around ℬ’s perimeter.
 𝒜 + ℬ is the convex hull.
GJK: Minkowski sum
𝑂
𝒜
ℬ
෡𝒃
ෝ𝒂
ෝ𝒂
𝒜 + ℬ
𝒂
𝒂′
15
 Minkowski difference: 𝒜 − ℬ = 𝒜 + −ℬ ,
where −ℬ = −𝒃; 𝒃 ∈ ℬ
 Lemma: The shortest distance between
𝒜 and ℬ is equal to the distance of
𝒜 − ℬ to the origin.
Proof: It is a length of the shortest ෝ𝒂 − ෡𝒃,
s.t. ෝ𝒂 ∈ 𝒜 ∧ ෡𝒃 ∈ ℬ. But ෝ𝒂 − ෡𝒃 ∈ 𝒜 − ℬ.
 Consequence: Shapes 𝒜 and ℬ collide
if and only if 𝒜 − ℬ contains the origin.
GJK: Minkowski difference
ℬ
𝒜
−ℬ
𝒜 − ℬ
𝒜
𝒜 − ℬ
𝒜
𝒜 − ℬ
𝑂
16
 Lemma: If shapes 𝒜 and ℬ are convex, then 𝒜 − ℬ is also convex.
Proof: For each 𝒖, 𝒗 ∈ 𝒜 − ℬ there exist 𝒂 𝑢, 𝒂 𝑣 ∈ 𝒜 and 𝒃 𝑢, 𝒃 𝑣 ∈ ℬ s.t.
𝒖 = 𝒂 𝑢 − 𝒃 𝑢 and 𝒗 = 𝒂 𝑣 − 𝒃 𝑣. Then, for 𝑡 ∈ 0,1 , we get
𝒖 + 𝑡 𝒗 − 𝒖 = 𝒂 𝑢 − 𝒃 𝑢 + 𝑡 𝒂 𝑣 − 𝒃 𝑣 − 𝒂 𝑢 − 𝒃 𝑢 =
𝒂 𝑢 − 𝒃 𝑢 + 𝑡𝒂 𝑣 − 𝑡𝒃 𝑣 − 𝑡𝒂 𝑢 + 𝑡𝒃 𝑢 =
𝒂 𝑢 + 𝑡 𝒂 𝑣 − 𝒂 𝑢 − 𝒃 𝑢 + 𝑡 𝒃 𝑣 − 𝒃 𝑢 .
𝒜 and ℬ are convex => 𝒂 𝑢 + 𝑡 𝒂 𝑣 − 𝒂 𝑢 ∈ 𝒜, 𝒃 𝑢 + 𝑡 𝒃 𝑣 − 𝒃 𝑢 ∈ ℬ =>
𝒂 𝑢 + 𝑡 𝒂 𝑣 − 𝒂 𝑢 − 𝒃 𝑢 + 𝑡 𝒃 𝑣 − 𝒃 𝑢 ∈ 𝒜 − ℬ => 𝒜 − ℬ is convex.
 Consequence: If the origin lies in the convex hull of points 𝒂1, … , 𝒂 𝑛 ∈
𝒜 − ℬ, then convex shapes 𝒜 and ℬ have non-empty intersection.
GJK: Minkowski difference
17
 A simplex is a convex hull of an affinely independent points.
point line triangle tetrahedron
 GJK searches for a simplex s.t. origin lies inside or prove that no such
simplex exists.
 Note: In 2D case we only need point, line and triangle.
GJK: Simplex
18
 Given a shape 𝒜 and a non-zero
vector 𝒅, a support function
𝑆 𝒜 returns a point 𝑆 𝒜 𝒅 ∈ 𝒜 s.t.
𝑆 𝒜 𝒅 ⋅ 𝒅 = max 𝒙 ⋅ 𝒅; 𝒙 ∈ 𝒜 .
GJK: Support function
𝒅𝒅1
𝒅2
𝒜
𝑆 𝒜(𝒅1)
𝑆 𝒜(𝒅)
𝑆 𝒜(𝒅2)
19
 A shape 𝒜 can be defined in a local system – body/model space.
 Therefore, this must be reflected in the computation of 𝑆 𝒜 𝒅 .
GJK: Support function
𝑥′
𝑦′
𝑧′
Body space
𝑥
𝑦
𝑧
World space
𝒑′
𝑅
Rotation matrix
𝒙
Translation
vector
𝒑
𝒑 = 𝑅𝒑′
+ 𝒙
𝒑′ = 𝑅⊤ 𝒑 − 𝒙
20
 When a convex shape 𝒜 is defined in body space (𝑅, 𝒙), then we
denote 𝑅𝒜 + 𝒙 the corresponding convex shape in the world space.
 More precisely: 𝑅𝒜 + 𝒙 = {𝑅𝒑′ + 𝒙 ; 𝒑′ ∈ 𝒜}.
 Lemma: 𝑆 𝑅𝒜+𝒙 𝒅 = 𝑅𝑆 𝒜 𝑅⊤ 𝒅 + 𝒙, for each world-space vector 𝒅 ≠ 𝟎.
Proof: First, we show that ∀𝒑′ ∈ 𝒜 the following equality (*) holds true
𝑅𝒑′ + 𝒙 ⋅ 𝒅 = 𝑅𝒑′ ⋅ 𝒅 + 𝒙 ⋅ 𝒅
= 𝒅⊤
𝑅𝒑′
+ 𝒙 ⋅ 𝒅
= 𝒅⊤ 𝑅 𝒑′ + 𝒙 ⋅ 𝒅
= 𝑅⊤
𝒅 ⊤
𝒑′
+ 𝒙 ⋅ 𝒅
= 𝒑′ ⋅ 𝑅⊤ 𝒅 + 𝒙 ⋅ 𝒅.
GJK: Support function
21
Now, 𝑆 𝑅𝒜+𝒙 𝒅 ⋅ 𝒅 = max 𝒑 ⋅ 𝒅; 𝒑 ∈ 𝑅𝒜 + 𝒙
= max 𝑅𝒑′ + 𝒙 ⋅ 𝒅; 𝒑′ ∈ 𝒜
= max 𝒑′ ⋅ 𝑅⊤ 𝒅 + 𝒙 ⋅ 𝒅; 𝒑′ ∈ 𝒜 according to (*)
= max 𝒑′ ⋅ 𝑅⊤ 𝒅 ; 𝒑′ ∈ 𝒜 + 𝒙 ⋅ 𝒅
= 𝑆 𝒜 𝑅⊤ 𝒅 ⋅ 𝑅⊤ 𝒅 + 𝒙 ⋅ 𝒅
= 𝑅𝑆 𝒜 𝑅⊤ 𝒅 + 𝒙 ⋅ 𝒅 according to (*)
Therefore, 𝑆 𝑅𝒜+𝒙 𝒅 = 𝑅𝑆 𝒜 𝑅⊤ 𝒅 + 𝑥.
GJK: Support function
22
 𝒜 is a sphere at the origin with the radius 𝑟:
𝑆 𝒜 𝒅 = 𝑟
𝒅
𝒅
 𝒜 is an axis aligned bounding box (AABB) at the origin with sizes
2𝑠 𝑥, 2𝑠 𝑦, 2𝑠𝑧 along corresponding coordinate axes:
𝑆 𝒜 𝒅 = sgn 𝒅 𝑥 𝑠 𝑥, sgn 𝒅 𝑦 𝑠 𝑦, sgn 𝒅 𝑧 𝑠𝑧
⊤
where sgn 𝑎 = ቊ
−1 if 𝑎 < 0
1 otherwise
GJK: Support function examples
23
 𝒜 is a cylinder at the origin with the central axis aligned with the z
coordinate axis, with the radius 𝑟 and with the top and bottom base
at z-coordinate ℎ and −ℎ, respectively:
𝑆 𝒜 𝒅 = ൞
𝑟
𝜎
𝒅 𝑥,
𝑟
𝜎
𝒅 𝑦, sgn 𝒅 𝑧 ℎ
⊤
if 𝜎 > 0
0,0, sgn 𝒅 𝑧 ℎ ⊤ otherwise
where 𝜎 = 𝒅 𝑥
2
+ 𝒅 𝑦
2
, and sgn(𝑎) was defined earlier.
 𝒜 is any convex polytope (e.g., point, line, triangle, convex polygon,
tetrahedron, box, …) with vertices V = {𝒗1, … , 𝒗 𝑛}:
𝑆 𝒜 𝒅 = 𝒗 𝑘 s. t. 𝒗 𝑘 ⋅ 𝒅 = max{𝒗𝑖 ⋅ 𝒅 ; 𝒗𝑖 ∈ V}
GJK: Support function examples
24
 Lemma: 𝑆 𝒜−ℬ 𝒅 = 𝑆 𝒜 𝒅 − 𝑆ℬ −𝒅 .
Proof: 𝑆 𝒜−ℬ 𝒅 ⋅ 𝒅 = max 𝒂 − 𝒃 ⋅ 𝒅; 𝒂 ∈ 𝒜 ∧ 𝒃 ∈ ℬ
= max 𝒂 ⋅ 𝒅; 𝒂 ∈ 𝒜 − min 𝒃 ⋅ 𝒅; 𝒃 ∈ ℬ
= 𝑆 𝒜 𝒅 ⋅ 𝒅 + max 𝒃 ⋅ −𝒅 ; 𝒃 ∈ ℬ
= 𝑆 𝒜 𝒅 ⋅ 𝒅 + 𝑆ℬ −𝒅 ⋅ −𝒅
= (𝑆 𝒜 𝒅 − 𝑆ℬ −𝒅 ) ⋅ 𝒅.
 We therefore do not have to construct 𝒜 − ℬ and 𝑆 𝒜−ℬ. We work with
the given shapes 𝒜 and ℬ and their support functions.
GJK: Support function
25
GJK: The algorithm – intuition (2D case)
𝑆 ={ }
ℬ
𝒜
𝒜 − ℬ
𝑂
𝒅1
𝐬0,
𝐬1
𝐬2𝐬1,
𝐬2
𝐬0 𝐬1
𝐬0
𝐬1
𝐬2
𝒔0
𝒅2
𝐬2=
𝐬1 = 𝑆 𝒜−ℬ 𝒅1 = 𝑆 𝒜 𝒅1 − 𝑆ℬ −𝒅1 = 𝐬 𝟏 − 𝐬 𝟏
𝐬 𝟎, 𝐬 𝟎 – closest points from the
previous round (or random)
𝐬2 = 𝑆 𝒜−ℬ 𝒅2 = 𝑆 𝒜 𝒅2 − 𝑆ℬ −𝒅2 = 𝐬 𝟐 − 𝐬 𝟐
𝐬0 = 𝐬 𝟎 − 𝐬 𝟎
𝒅3
𝐬3=
𝐬3=
𝐬3=
𝐬1 ⋅ 𝒅1 ≥ 0 => continue
𝐬3 = 𝑆 𝒜−ℬ 𝒅3 = 𝑆 𝒜 𝒅3 − 𝑆ℬ −𝒅3 = 𝐬 𝟑 − 𝐬 𝟑
𝐬2 ⋅ 𝒅2 ≥ 0 => continue
𝐬3 ⋅ 𝒅3 < 0 => NO INTERSECTION!
26
 Since 𝒜 and ℬ have empty intersection, we can compute a pair of closest
points:
 First, we find the closest point 𝑋 of the simplex 𝑆 = {𝐬1, 𝐬2} to the origin. That is
𝑋 = 𝐬1 + 𝑡 𝐬2 − 𝐬1 for some 𝑡 ∈ 0,1 s.t. 𝑋 − 𝑂 2
= 𝐬1 + 𝑡 𝐬2 − 𝐬1
2
is minimal.
So, solve the equation:
𝑑
𝑑𝑡
𝐬1 + 𝑡 𝐬2 − 𝐬1
2
= 0
𝑑
𝑑𝑡
𝐬1 ⋅ 𝐬1 + 𝑡2𝐬1 ⋅ 𝐬2 − 𝐬1 + 𝑡2
𝐬2 − 𝐬1
2
= 0
2𝐬1 ⋅ 𝐬2 − 𝐬1 + 2𝑡 𝐬2 − 𝐬1
2
= 0
𝑡 = −
𝐬1 ⋅ 𝐬2 − 𝐬1
𝐬2 − 𝐬1
2
GJK: The algorithm – intuition (2D case)
Also clip 𝑡 to 0,1 .
27
 Then, find the corresponding points in the shapes 𝒜 and ℬ.
𝐬1 + 𝑡 𝐬2 − 𝐬1 = 𝐬 𝟏 − 𝐬 𝟏 + 𝑡( 𝐬 𝟐 − 𝐬 𝟐 − (𝐬 𝟏 − 𝐬 𝟏))
= 𝐬 𝟏 + 𝑡(𝐬 𝟐 − 𝐬 𝟏) − 𝐬 𝟏 + 𝑡 𝐬 𝟐 − 𝐬 𝟏
GJK: The algorithm – intuition (2D case)
∈ 𝒜 ∈ ℬ
28
Choose some 𝒑 ∈ 𝒜 − ℬ. // Usually, 𝒑 comes from the previous frame.
𝑆 = ∅ // We start with the empty simplex.
𝒔 = 𝑆 𝒜−ℬ −𝒑 // NOTE: Our direction vector 𝒅 to the origin is just −𝒑.
while 𝒑 2 − 𝒑 ⋅ 𝒔 > 𝜖2 do: // Proving termination condition: see [4].
// 𝒑 is still far from the closest point of 𝒜 − ℬ to the origin.
𝒑 = closest_to_origin convex_hull(𝑆 ∪ {𝒔})
𝑆 = smallest 𝑋 ⊆ 𝑆 ∪ 𝒔 s.t. 𝒑 ∈ convex_hull(𝑋) // Reduce the simplex.
𝒔 = 𝑆 𝒜−ℬ −𝒑
return 𝒂 ∈ 𝒜, 𝒃 ∈ ℬ s.t. 𝒑 = 𝒂 − 𝒃. // |𝒑| is the closest distance.
GJK: The algorithm
Point, line, triangle,
or tetrahedron.
Can be computed quickly for shapes
29
Caching collisions
30
 Efficiency of the PGS algorithm for a constraint system depends on
the initial value 𝝀0.
 It is likely that 𝜆 computed for a collision constraint at current frame
would be “almost valid” for the next frame (if the collision persists).
 Therefore, caching 𝜆 values for collision (and other types of)
constraints amongst frames can bring considerable speed boost.
 How to match collisions computed in different frames?
Caching collisions
31
 There are several possibilities:
 Distance between collision points in world space:
 Distance between collision points in body space:
Caching collisions
𝑡𝑡 + Δ𝑡
𝑎𝑏 𝑐𝑑
Correct mapping:
𝑎 → 𝑐, 𝑏 → 𝑑
Word distance mapping:
𝑏 → 𝑐 (wrong), 𝑎 → ? , ? → 𝑑
Imprecise.
Precise in
space of
the box
𝑡𝑡 + Δ𝑡
𝑎𝑏 𝑐𝑑
𝑡𝑡 + Δ𝑡
𝑎𝑏 𝑐𝑑
Imprecise
in space
of ground
32
 Identify collisions by geometrical properties of collision shapes:
enum GTYPE { VERTEX, EDGE, FACE };
struct CollisionID {
int body_index_1; // The index of ℛ 𝑖: 𝑖
GTYPE feature_type_1; // The type of colliding geometry in ℛ 𝑖
int feature_index_1; // Index of the colliding geometry in ℛ 𝑖
int body_index_2; // The index of ℛ𝑗: 𝑗
GTYPE feature_type_2; // The type of colliding geometry in ℛ 𝑖
int feature_index_2; // Index of the colliding geometry in ℛ 𝑖
};
Define also comparison and hashing of CollisionID instances.
Caching collisions
33
 The cache should be a map from CollisionID instance to values 𝜆:
using collision_cache = std::unordered_map<CollisionID,float>;
 And how to use the cache?
Caching collisions
𝑡𝑡 + Δ𝑡
𝑎𝑏 𝑐𝑑
We get precise mapping:
id 𝑎 = id 𝑐 ⇒ 𝑎 → 𝑐
id 𝑏 = id 𝑑 ⇒ 𝑏 → 𝑑
Recommended
approach
34
 Before solving the constraint system initialize 𝝀0 s.t.
 For each computed collision 𝑐 and the corresponding element 𝝀𝑖
0
:
 Build the CollisionID instance 𝑖𝑑 from 𝑐.
 If 𝑖𝑑 is present in the cache, then set 𝝀𝑖
0
to the value 𝜆 in the cache.
 Otherwise, set 𝝀𝑖
0
to 0.
 Once new solution 𝝀 is computed updated the cache as follows:
 Clear the cache.
 For each collision 𝑐 and the corresponding computed value 𝜆:
 Build the CollisionID instance 𝑖𝑑 from 𝑐.
 Insert the mapping 𝑖𝑑 → 𝜆 to the cache.
Caching collisions
35
Computing collision time
36
Tunnelling and penetration
PenetrationTunnelling
37
 The simplest approach is to subdivide the game time step Δ𝑡 of into
several small internal time steps.
 For broad phase:
 Approximate collision shapes of bodies
by “moving spheres”:
 Use the adaptive time step:
 For each pair of potentially colliding shapes compute the nearest
collision time.
 Move the bodies only to the minimum of all nearest collision times.
Dealing with tunnelling and penetration
We move all bodies in
each internal time step.Δ𝑡𝒗
38
 Binary search for Ƹ𝑡 ∈ 𝑡, 𝑡 + ∆t
 There are 4D collision algorithms – they consider translations and
rotations of tested objects.
Computing collision time
𝜀
𝑡 + ∆t/2
(2)
𝑡
Start position
𝑡 +
3
4
∆𝑡
(3)
Ƹ𝑡
Ƹ𝜀
(1)
𝑡 + ∆t
39
[1] Erin Catto; Iterative Dynamics with Temporal Coherence; Crystal
Dynamics, Menlo Park, California, 2005
[2] E. G. Gilbert, D. W. Johnson and S. S. Keerthi; A fast procedure for
computing the distance between complex objects in threedimensional
space; Journal on Robotics and Automation, vol. 4, no. 2,
pp. 193-203, April 1988
[3] G. Bergen; A Fast and Robust GJK Implementation for Collision
Detection of Convex Objects; Eindhoven University of Technology. 1999
[4] G.v.d. Bergen; Collision detection in interactive 3D environments;
ISBN: 1-55860-801-X, Elsevier, 2004.
References