CS 4: Lecture 19
Monday, April 3, 2006
COLLISIONS
==========
Suppose you want to model a game of pool. How do you simulate pool balls
colliding off each other, or the bumpers?
One way is to model everything as a spring. In fact, all solid objects behave
something like springs, even if they're as rigid as pool balls. When pool
balls collide with each other, they compress slightly at the point of contact,
although the compression is too small to see with the eye.
Recall that a spring is described by Hooke's law, F(t) =  k d(t), where F(t)
is the force exerted by the spring, k is the spring constant, and d(t) is the
displacement of the spring from its preferred position.
With collisions, this rule changes slightly, because colliding pool balls push
each other apart, but they never pull each other together. For collisions,
d(t) is the _interpenetration_distance_; that is, how much the balls would
overlap each other if they remained perfectly round (rather than compressed at
the collision point). So we have
/
  k d(t) , d(t) >= 0
F(t) = < (1)
 0 , d(t) <= 0.
\
Let's consider collisions between a ball and an edge of the pool table first.
We can describe the bumpers of the table with the lines x = 0, x = x_0,
y = 0, and y = y_0. If a ball has x and ycoordinates of x(t) and y(t),
respectively, then its interpenetration distance into the left bumper is
d(t) = x(t), and its interpenetration distance into the right bumper is
d(t) = x(t)  x_0.
But what is the _direction_ of the force? The force two objects exert on each
other is always normal to the plane of contact. In this case, the bumper _is_
the plane of contact. So the left bumper, for instance, applies a force
pointing directly to the right (along the xaxis). This is true regardless of
the direction the ball is moving.
/ velocity
/
 _ /
 / \+
/ \
+> F(t)
\ /
 \_/

The ball bounces off the bumper so fast, you don't see the bumper compressing.
In other words, the spring constant k is quite large. When k is large, the
spring is said to be very _stiff_. It should come as no surprise that when
you're modeling stiff springs, you have to take very small timesteps. If you
don't, the ball and the bumper will interpenetrate too deeply, and the answer
will be quite inaccurate.
Now, consider two balls B_1 and B_2 colliding. Let p_1 and p_2 be the vector
positions of their centers, and let r_1 and r_2 be their radii, respectively.
The balls interpenetrate if the distance between their centers is less than
r_1 + r_2. The interpenetration distance d(t) is described by
d(t) = p_1(t)  p_2(t)  (r_1 + r_2).
We can plug this value of d(t) into Equation (1) to get the force the balls
apply to each otherbut that only tells us the magnitude of the force, not the
direction. By Newton's Third Law, the balls push each other with equal and
opposite forces. Again, the forces are normal to the tangent plane at the
collision point. Since the balls are spherical, we can draw a line connecting
the centers of the balls, and know that the forces are directed along the line.
_ /
B_1 / \ /
/ \ _
 p_1 / \ < \
\ / \ \ \
\_/ p_2  \ >
/ \ /
/ \_/ B_2 F_12 F_21
/
To express the forces as vectors, let's find a _unit_vector_ that points from
the center of B_2 to the center of B_1.
p_1(t)  p_2(t) p_1  p_2
u(t) =  =  .
p_1(t)  p_2(t) sqrt((p_x1  p_x2)^2 + (p_y1  p_y2)^2)
Then, the force exerted on B_1 by B_2 is
F_12(t) =  F(t) u(t), [remember that F(t) is negative]
and the force exerted on B_2 by B_1 is
F_21(t) = F(t) u(t).
Now that we have expressions for the forces on the balls, we can integrate
their velocities and motions through time using Euler's method or Heun's method
as usual (consult the Lecture 9 notes for details).
Conservation of Energy and Momentum

There's another way to model collisions, based on conservation laws. The idea
is that whenever a collision occurs, we immediately compute the _final_
velocities of the balls after the collision is completely finished. We assume
that the materials are idealized elastic materials, which means that they do
not lose any energy to friction or heat. This is not a truly accurate
modelafter all, real pool balls don't keep bouncing around the table all day
long after you hit them once. But for short periods of time, it's a pretty
good approximation.
Suppose a pool ball hits the left bumper with velocity v = (v_x, v_y). After
the collision, its velocity is w = (w_x, w_y).
The left bumper exerts a force on the ball that is normal to the bumperin
other words, directed along the xaxis. So the ball's yvelocity does not
change, and w_y = v_y.
The ball has a kinetic energy of E = m v^2 / 2, where m is its mass. The
bumper's kinetic energy can be measured the same way, but the bumper has
velocity zero both before and after the collision, so its contribution to the
energy is zero.
The law of conservation of energy says that the ball and bumper have the same
total energy after the collision they had before the collision, so
1 2 1 2
 m w =  m v .
2 2
Therefore,
2 2 2 2
w + w = v + v ,
x y x y
but remember that w_y = v_y, so
2 2
w = v .
x x
This equation has two solutions: w_x = v_x, or w_x = v_x. The reason it has
two solutions is because the law of conservation of energy, by itself, doesn't
know when the ball has hit the bumper and when it hasn't. But it's clear to us
that the solution w_x = v_x applies before the ball hits the bumper, and the
solution w_x = v_x applies after the ball hits the bumper. So we can
implement the collision as a logical rule.
When a ball hits a bumper whose normal is parallel to the xaxis, the ball's
xvelocity is reversed (changed from v_x to v_x).
Next, let's look at two balls colliding. To keep it simple for now, suppose
that the balls' centers both have the same ycoordinate, so the tangent plane
is parallel to the yaxis, and the mutual pushing forces are directed along the
xaxis.
m_1 _  _ m_2 _  _ + w_2
/ \  / \ w_1 <\ / \  / \/
/ \/ \ X \/ /\
 >  +     / 
X /\ \/ \ /\ /
v_1 / \_/  \_/\ \_/  \_/
 \ v_2 
Let m_1 and m_2 be the masses of the balls; let v_1 and v_2 be their initial
velocities before the collision; and let w_1 and w_2 be their velocities after
the collision.
The forces the balls apply to each other are parallel to the xaxis, so the
balls' yvelocities do not change.
w = v ; w = v . (2)
y1 y1 y2 y2
But we still have two more unknownsw_x1 and w_x2so we'll need two equations
to solve for them. In addition to using conservation of energy, we'll also use
the law of conservation of momentum, which says that the balls have the same
total momentum before and after the collision.
m v + m v = m w + m w .
1 1 2 2 1 1 2 2
This vector equation is actually two equationsone for each coordinate axis.
We only need the equation for the xcoordinates. Rearranging terms, we have
m (v  w ) = m (w  v ) . (3)
1 x1 x1 2 x2 x2
By conservation of energy, the balls have the same total energy before and
after the collision.
2 2 2 2
m v + m v = m w + m w .
1 1 2 2 1 1 2 2
Expanding by components and rearranging terms gives
2 2 2 2 2 2 2 2
m (v + v  w  w ) = m (w + w  v  v ) .
1 x1 y1 x1 y1 2 x2 y2 x2 y2
But by (2) the yterms cancel, giving
2 2 2 2
m (v  w ) = m (w  v ).
1 x1 x1 2 x2 x2
We can divide this by (3), giving
v + w = w + v .
x1 x1 x2 x2
Now, we can substitute w_x2 = v_x1 + w_x1  v_x2 back into (3) and solve for
w_x1, giving
m_1 v_x1 + m_2 (2 v_x2  v_x1)
w_x1 =  . (4)
m_1 + m_2
We can solve for w_x2 by substituting w_x1 back into (3), giving
m_1 (2 v_x1  v_x2) + m_2 v_x2
w_x2 =  . (5)
m_1 + m_2
Now, we can model balls colliding by simply plugging their initial velocities
into equations (4) and (5). Pool balls usually all have the same mass; when
they do, the equations can be simplified.
If m_1 = m_2, then w_x1 = v_x2 and w_x2 = v_x1.
We can implement this collision as a logical rule.
When two balls of equal mass collide so that the normal to their tangent
plane is parallel to the xaxis, the balls exchange their xvelocities.
Warning: in a simulation you need to be careful not to apply the rule again
postcollision, once the balls are already moving apart! It's easy to mess
this up if the balls interpenetrate too far.
What if the tangent plane _isn't_ parallel to any axis? Then we do the
following.
 Compute the unit vector u (discussed above). We'll do our calculations
along the "uaxis".
 Compute the projections of the velocities onto the uaxis, namely
v_u1 = v_1 . u and v_u2 = v_2 . u (here, the "." is a dot product, aka
inner product; the dot should be centered, but I can't draw that in ASCII).
 Figure out the postcollision uvelocities of the balls, w_u1 and w_u2,
using the formulae above.
 Replace the old uvelocities with the new ones:
w_1 = v_1 + (w_u1  v_u1) u, and w_2 = v_2 + (w_u2  v_u2) u.