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 y-coordinates 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 x-axis). 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 other--but 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 model--after 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 bumper--in other words, directed along the x-axis. So the ball's y-velocity 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 x-axis, the ball's x-velocity 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 y-coordinate, so the tangent plane is parallel to the y-axis, and the mutual pushing forces are directed along the x-axis. 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 x-axis, so the balls' y-velocities do not change. w = v ; w = v . (2) y1 y1 y2 y2 But we still have two more unknowns--w_x1 and w_x2--so 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 equations--one for each coordinate axis. We only need the equation for the x-coordinates. 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 y-terms 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 x-axis, the balls exchange their x-velocities. Warning: in a simulation you need to be careful not to apply the rule again post-collision, 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 "u-axis". - Compute the projections of the velocities onto the u-axis, 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 post-collision u-velocities of the balls, w_u1 and w_u2, using the formulae above. - Replace the old u-velocities with the new ones: w_1 = v_1 + (w_u1 - v_u1) u, and w_2 = v_2 + (w_u2 - v_u2) u.