Collision detection
Jiří Chmelík, Marek Trtík
PA199

‹#›
uBroad phase
uSweep and prune algorithm
u
uNarrow phase
uGilbert-Johnson-Keerthi (GJK) algorithm
u
uCaching collisions
u
uComputing collision time
Outline

‹#›
u
Broad phase

‹#›
uThe goal is to quickly find pairs of potentially colliding rigid bodies.
uUsed algorithm defines meaning of “potentially colliding”. Examples:
uWhen AABBs of the bodies are colliding.
uWhen both bodies are in the same area of space.
uWe can use space partitioning data structures we already know:
uOctree, k-D tree, BSP
uRigid bodies change their positions and orientations during simulation.
u => The data structure must be periodically updated.
uUtilize time coherence of frames (positions of bodies do not change much between adjacent frames)
to get an efficient update algorithm.
Broad phase

‹#›
x
y
A
C
B
D
Use InsertSort
Sweep and prune algorithm

‹#›
Sweep and prune algorithm


‹#›
Sweep and prune algorithm


‹#›
Sweep and prune algorithm
next
prev
Link[0][*]
Link[1][*]
Points to some “red” link in the previous AABB.

‹#›
Sweep and prune algorithm


‹#›
uPerformance of the algorithm is sensitive to alignment of objects along coordinate axes:
u
u
u
u
u
u
uA relocation of an object leads to a lot of swaps thought the “cluster” in the array.
u
Sweep and prune algorithm
x
y
A
C
B
D

‹#›
u
Narrow phase

‹#›
Narrow phase
Stack of two boxes (top view)

‹#›
uDecides whether two convex shapes have empty intersection or not.
u
u
u
u
u Convex shapes            Concave shapes
u
uWe can approximate a concave shape by a set of convex shapes.
uFor the empty intersection we can obtain a pair of the closest points.
u
uWe must first build a terminology:
uMinkowski sum and difference
uSimplex
uSupport function
Gilbert-Johnson-Keerthi (GJK) algorithm

‹#›
GJK: Minkowski sum


‹#›
GJK: Minkowski difference


‹#›
GJK: Minkowski difference


‹#›
uA simplex is a convex hull of an affinely independent points.
u
u
u
u
u point             line                  triangle                  tetrahedron
u
uGJK searches for a simplex s.t. origin lies inside or prove that no such simplex exists.
u
uNote: In 2D case we only need point, line and triangle.
GJK: Simplex

‹#›
GJK: Support function


‹#›
GJK: Support function
Body space
World space
Rotation matrix
Translation
vector

‹#›
GJK: Support function


‹#›
GJK: Support function


‹#›
GJK: Support function examples


‹#›
GJK: Support function examples


‹#›
GJK: Support function


‹#›
GJK: The algorithm – intuition (2D case)


‹#›
GJK: The algorithm – intuition (2D case)


‹#›
GJK: The algorithm – intuition (2D case)


‹#›
GJK: The algorithm
Point, line, triangle, or tetrahedron.
Can be computed quickly for shapes

‹#›
u
Caching collisions

‹#›
Caching collisions


‹#›
uThere are several possibilities:
uDistance between collision points in world space:
u
u
u
u
uDistance between collision points in body space:
u
Caching collisions
Imprecise.
Precise in space of the box
Imprecise in space of ground

‹#›
Caching collisions


‹#›
Caching collisions
Recommended approach

‹#›
Caching collisions


‹#›
u
Computing collision time

‹#›
Tunnelling and penetration
Penetration
Tunnelling

‹#›
Dealing with tunnelling and penetration
We move all bodies in each internal time step.

‹#›
Computing collision time
(2)
Start position
(3)
(1)

‹#›
u[1] Erin Catto; Iterative Dynamics with Temporal Coherence; Crystal Dynamics, Menlo Park,
California, 2005
u[2] E. G. Gilbert, D. W. Johnson and S. S. Keerthi; A fast procedure for computing the distance
between complex objects in three-dimensional space; Journal on Robotics and Automation, vol. 4, no.
2, pp. 193-203, April 1988
u [3] G. Bergen; A Fast and Robust GJK Implementation for Collision Detection of Convex Objects;
Eindhoven University of Technology. 1999
u [4] G.v.d. Bergen; Collision detection in interactive 3D environments; ISBN: 1-55860-801-X,
Elsevier, 2004.
References

‹#›
uWe usually compute all collision points of the model at once.
uBut it is also possible to compute all required collision points of the model incrementally – in
several time steps.
uExample: Compute collisions between two rectangles (2D case).
uSuppose we can compute a pair of the closest points of the rectangles.
Narrow phase
Model the collision by the closest points
Keep the collision from the previous step
  (points are still
   close enough)
Add the other collision from new closest points.
Collision force is applied.