Collision detection and response in
the assignment
Marek Trtík
PA199
2
 Position of the ball: 𝐩 = 𝐩 𝑥, 𝐩 𝑦, 𝑟
⊤
,
where 𝑟 is the radius of the sphere.
 If 𝐩 − 𝑟 > 𝑟𝑔 then GAME OVER.
 If 𝐩 + 𝑟 ≥ 𝑟𝑝 − 𝑤 𝑝 ∧ 𝐩 − 𝑟 ≤ 𝑟𝑝 + 𝑤 𝑝
then “broad phase with paddles”.
 If 𝐩 + 𝑟 ≥ 𝑟𝑏 − 𝑤 𝑏 ∧ 𝐩 − 𝑟 ≤ 𝑟𝑏 + 𝑤 𝑏
then “broad phase with bricks”.
 Otherwise, no collision.
Collision detection: Broad phase
𝑟𝑏
𝑟𝑝
𝑟𝑔
𝑂
𝜃 𝑝𝜃
𝐩
𝑤 𝑝
𝑤 𝑏
𝜑 𝑝
3
Collision detection: Broad phase
𝑟𝑏
𝑟𝑝
𝑟𝑔
𝑂
𝜃 𝑝𝜃
𝐩
𝑤 𝑝
𝑤 𝑏
𝜑 𝑝
# Colliding with Paddles (brick wall case is similar)
def broad_phase(positions,𝑤 𝑝,𝜑 𝑝):
𝑟𝑝, 𝜃 𝑝= positions[0]
for 𝑟𝑝
′, 𝜃 𝑝
′ in positions[1:]:
if min_difference(𝜃, 𝜃 𝑝
′ )
< min_ difference(𝜃, 𝜃 𝑝):
𝑟𝑝, 𝜃 𝑝= 𝑟𝑝
′, 𝜃 𝑝
′
if min_difference(𝜃, 𝜃 𝑝) ≤ 𝜑 𝑝:
return narrow_phase_case_1(𝐩, 𝑟𝑝)
else
return narrow_phase_case_2(𝐩,𝑟,𝜃,𝑟𝑝,𝜃 𝑝,𝑤 𝑝,𝜑 𝑝)
4
 Case 1: “min_difference(𝜃, 𝜃 𝑝) ≤ 𝜑 𝑝”.
def narrow_phase_case_1(𝐩, 𝑟𝑝):
𝐧 = 𝐩 / |𝐩|
return -𝐧 if |𝐩| < 𝑟𝑝 else 𝐧
Collision detection: Narrow phase
𝑂
𝜃
x
y 𝐩
𝜃 𝑝
𝜑 𝑝
−
𝐩
|𝐩|
= 𝐧
𝐩
𝐩
|𝐩|
= 𝐧
𝑟𝑝
5
 Case 2: “min_difference(𝜃, 𝜃 𝑝) > 𝜑 𝑝”.
def narrow_phase_case_2(𝐩,𝑟,𝜃,𝑟𝑝,𝜃 𝑝,𝑤 𝑝,𝜑 𝑝):
sign = 1 if on_left(𝜃, 𝜃 𝑝 + 𝜑 𝑝) else -1
𝑨 = to_cartesian(𝑟𝑝-𝑤 𝑝, 𝜃 𝑝 + sign*𝜑 𝑝)
𝑩 = to_cartesian(𝑟𝑝+𝑤 𝑝, 𝜃 𝑝 + sign*𝜑 𝑝)
ෝ𝒒 = closest_point_on_line(𝑨𝑩, 𝐩)
return 𝐩 − ෝ𝒒 / |𝐩 − ෝ𝒒| if 𝐩 − ෝ𝒒 ∈ (0, ۧ𝑟 else None
Collision detection: Narrow phase
𝑟𝑝
𝑂
𝜃
x
y
𝜃 𝑝
𝜑 𝑝
𝐩
𝐩 − ෝ𝒒
𝐩 − ෝ𝒒
= 𝐧
ෝ𝒒
𝑩
𝑤 𝑝
𝑨
6
𝐧
𝐯 𝑝
 Ball’s velocity: 𝐯 = 𝑣 𝑥, 0, 𝑣𝑧
⊤, 𝐯 = 𝑣0,
where 𝑣0 is the fixed speed.
 We have the unit collision normal
𝐧 = 𝑛 𝑥, 𝑛 𝑦, 0 , 𝐧 = 1
from the collision detection.
 Velocity of a paddle is 𝐯 𝑝.
Collision response
𝐯
𝐩
7
Collision response
𝐯 𝑝
𝐯
𝐧
We can model
the situation as
𝐯
𝐩
𝐧
𝐯 𝑝
Compute the
relative velocity
8
Collision response
−𝐯 𝑝
𝐯
𝐧
Δ𝐯
𝐧
Δ𝐯
Δ𝐯𝑡
Δ𝐯 𝑛
Decompose Δ𝐯
IMPORTANT
Continue only if
Δ𝐯 ⋅ 𝐧 < 0
Δ𝐯 𝑛 = 𝐧 ⋅ Δ𝐯 𝐧
Δ𝐯𝑡 = Δ𝐯 − Δ𝐯 𝑛
9
Δ𝐯𝑡
′ “Bounce of the paddle” velocity change:
Δ𝐯 𝑛
′ = −2Δ𝐯 𝑛
 “Match paddle’s velocity” velocity change:
Δ𝐯𝑡
′
= −𝜇 𝑝 min Δ𝐯 𝑛 , Δ𝐯𝑡
Δ𝐯𝑡
|Δ𝐯𝑡|
, if Δ𝐯𝑡 > 0,
where 0 ≤ 𝜇 𝑝 ≤ 1 is a “friction” coefficient.
 So, the collision response velocity is:
𝐯𝑟𝑒𝑠 = 𝐯 + Δ𝐯 𝑛
′
+ Δ𝐯𝑡
′
 The final velocity is then:
𝐯 ≔ 𝑣0
𝐯 𝑟𝑒𝑠
𝐯 𝑟𝑒𝑠
, NOTE: 𝐯𝑟𝑒𝑠 > 0.
Collision response
Δ𝐯 𝑛
′𝐯𝑟𝑒𝑠
Δ𝐯𝑡
Δ𝐯 𝑛
𝐯
10
 Polar coordinates:
 Always normalize the angles to the range ‫ۦ‬0, 2𝜋) before comparison.
 Consider using normalization directly in:
 Conversion from the Cartesian to polar coordinates.
 Operators for addition and subtraction of angles.
 Alternatively, in comparison operators.
 Otherwise, assert angles are normalized before comparisons.
 When implementing angle comparison algorithm, keep in mind the case
of passing the polar axis (in CW or CCW direction).
Implementation notes
11
 Recommendations:
 Build tests and test scenes for collision detection and response
algorithms.
=> Do not build the complete scene of the game (all paddles all wall
bricks).
=> Test function “closest_point_on_line” is different situations
(configurations of line’s points and the reference point).
=> Test all phases of the collision detection in separate test scenes.
=> Test collison response in separate test scenes (for different velocities
of the ball and the paddle).
Implementation notes