Collision Handling Methods

This page discusses the pro's and con's of various methods of handling collisions in rigid body physics simulations.

The simulations discussed here use simplified rules to determine the result of a collision. A more exact simulation would model the deformation of the colliding bodies on a very small time scale (over the span of a microsecond). But that would require much more complex software and data, and would not run interactively in real-time.

The bottom line: there isn't a perfect solution. The book Physics-Based Animation by Erleben, Sporring, Henriksen, and Dohlmann discusses several approaches to handling collisions. In comparing two of the methods considered below, they write (on page 153):

We cannot really talk about one method being more correct or better than the other because it is possible to set up physical configurations of colliding rigid bodies where one of the methods computes the wanted motion and the other does not and vice versa.

Single Collisions

I present some theory about rigid body collisions at Physics of Collision for Rigid Bodies in 2 Dimensions. That presentation concerns a single collision between two bodies at one collision point. The key idea is that we can find a collision impulse which reverses the collision such that the final velocity, vf, after the collision is some multiple of the initial velocity, vi.

   vf = −e vi (1)

The velocity here is the speed at which the gap distance between the objects is changing (not the speed of the objects themselves). So this is collision velocity: how fast the objects are colliding (negative velocity) or separating (positive velocity). The elasticity e is a constant between 0 and 1 that indicates how "bouncy" the collision is, where e = 1 means perfectly elastic and e = 0 means completely inelastic. For e = 1 the velocity after the collision is the opposite of the velocity before the collision.

That all works well for single collisions. However, multiple collisions are more complicated.

Multiple Collisions

For multiple collisions, there are vast numbers of possible configurations of bodies and points of resting contact and collision between them. However, the most typical case is a set of bodies in resting contact with each other, with another body crashes into one member of the group; the impact of the collision spreads through the group causing bodies to scatter in various directions. Think of the initial "break" in a game of pool, where one ball collides into a large group of balls that are at rest and in resting contact with each other.

PICTURE OF POOL BREAK HERE?

Simultaneous Collision Handling

One method of handling multiple collisions is called the simultaneous collisions method. In this scheme, we predict the result at every point of collision or resting contact by using equation (1). We then find the appropriate collision impulse at each point of collision of contact such that the end result matches what we predicted.

Consider a situation where there are two hockey pucks at rest and in contact with each other; and then a third puck comes from the left and strikes one of the pucks. (Imagine we are looking down onto an air hockey table).

Unable to run the simulation!
You need to get Java software
or see instructions for enabling Java.

Click the Reset button to see the collision again.

(If you don't see the simulation try instructions for enabling Java.)

We assume these hockey pucks are exactly lined up, elasticity is 1, and the pucks have the same mass. There are two points of collision, the collision on the left has a vi = −2, the right collision has vi = 0. By using equation (1) we get for the left collision vf = 2 and for the right collision vf = 0. So we see the left puck bounce away to the left, and the pair of pucks move to the right remaining together.

This is the wrong behavior! If you play billiards, you probably know that what should happen: the left and middle pucks should remain stationary, and the right-most puck should move away. Another example of the correct behavior is seen in the toy called a Newton's Cradle (LINK TO SIMULATION). It is a set of steel balls suspended from strings, such that they are resting against each other; when you pick up one of the balls at the end and let it hit the group, that ball stops and the ball at the other end flies away.

codebase="." width=640 height=440>
Unable to run the simulation!
You need to get Java software
or see instructions for enabling Java.

Consider just two hockey pucks, one stationary, and the other moving from the left. Suppose they have the same mass, are perfectly elastic (e = 1), and the motion is aligned so they hit squarely. After they collide, the left puck should be stationary, and the right puck should move away. Because this is a single collision, equation (1) gives the correct result, with vf = −vi, and this is what we see in the Hockey Puck simulation. In the case of three hockey pucks, the same thing should happen: the velocity should transfer from the left puck to the right puck, with the impact transferred thru the middle puck.

codebase="." width=640 height=440>
Unable to run the simulation!
You need to get Java software
or see instructions for enabling Java.

Click the Reset button to see the collision again.

Another way to see this: What if the two stationary pucks are not quite touching, but there is a small gap between them? Then, what happens is the "one hits one" collision happening twice, separated by a small gap of time and space. The Hockey Puck simulation below demonstrates this. Since you can make this gap as small as you want, it seems unreasonable that the behavior suddenly changes dramatically when the pucks are touching instead of separated by a tiny gap.

Unable to run the simulation!
You need to get Java software
or see instructions for enabling Java.

Sequential Collision Handling

sequence of collisions
sequence of collisions

An alternate method is called sequential collision handling (also known by the term propagating impulses). With the sequential method, we imagine that each of the multiple collisions happens one at a time in sequence; we resolve each collision as a single collision, and then based on the resulting velocities there are subsequent collisions to resolve. All this happens instantaneously. It's rather like pretending that there are tiny gaps between the objects, and that they rebound against each other after the initial collision occurs.

Consider the "one hits two" scenario, where one puck hits two motionless pucks that are in contact. With the simultaneous method, we used equation (1) to decide in advance what the final velocities would be at the two collision points (this was described above). The sequential method goes thru a process of "collision resolving" where objects collide and rebound against each other, possibly many times, until there are no more collisions. This process of collision resolving takes no time, the idea being that because the objects are all in contact there is no distance for them to travel to bump into one another.

With the sequential collision handling method, when elasticity e = 1, the "one hits two" scenario goes like this: assume the left puck approaches the two stationary pucks with vi = −2

The result is that the left and middle pucks are stationary, and vf = 2 for the second collision. The simulation below runs this scenario with the sequential collision method; it shows that the sequential method correctly handles this case, in contrast to the simultaneous method.

Unable to run the simulation!
You need to get Java software
or see instructions for enabling Java.

Click the Reset button to see the collision again.

Curious fact: With elasticity e = 1. we had only 2 collisions in the sequence. But with lower elasticity, such as e = 0.8, you wind up with with an infinite series of smaller and smaller collisions as the middle puck collides back and forth between the left and right pucks. (POSSIBLY SHOW SOME DEBUG OUTPUT FOR THIS???).

Problems with sequential collisions.

The most obvious "problem" with sequential collisions is when we have a square block instead of a round ball, and the two corners of the block hit an edge at the same moment. Here is a simulation of this; first with sequential collision handling and then with simultaneous collision handling. Which do you think is more realistic?

Unable to run the simulation!
You need to get Java software
or see instructions for enabling Java.

Click the Reset button to see the collision again.

Above is with sequential collision handling. Below is the same situation with simultaneous collision handling.

Unable to run the simulation!
You need to get Java software
or see instructions for enabling Java.

Click the Reset button to see the collision again.

Is this really a problem with sequential collision handling? It would be very rare to have a collision happen in this mathematically precise way where both corners are colliding at the same speed. And note that with a tiny change in the angle of the block, the simultaneous collision handling produces pretty much the same result as the sequential handling. The simulation below uses simultaneous collision handling, but the "offset" parameter lets us change the starting angle of the block by a slight amount.

Unable to run the simulation!
You need to get Java software
or see instructions for enabling Java.

Click the Reset button to see the collision again.

Earlier in discussing the "one hits two" scenario, we used the principle that "slight variations shouldn't radically change the solution". If we apply that principle here, then the sequential collision handler actually looks like the better of the two.

Below is a situation where an object collides into two other objects at the same time. Again it's the case that the sequential method gives a non-symmetric result, where the two collisions get different impulses because one is resolved before the other. If you choose "simultaneous" from the collision handling menu, you will see that the simultaneous solver gives a nice symmetric result. However if you put in a tiny offset, like 0.01, which changes the angle of the rectangular block slightly, then the result is similar to what the sequential method produces.

Unable to run the simulation!
You need to get Java software
or see instructions for enabling Java.

Click the Reset button to see the collision again.

A Hybrid Method: between sequential and simultaneous.

sequence of collisions
sequence of collisions

Here is a hybrid combination of the two approaches. It is like the sequential method in resolving a sequence of individual collisions. But for each individual collision, it considers all the active collisions on that body. So we get a nice result for the "one hits two" case with square blocks (see the simulation below).

The first collision is solved simultaneously for both collisions at the corners between the left and middle blocks, so it gets a nice symmetric result: after the first collision the left block is stationary, and the middle block is moving to the right and starting to collide with the right block (see the picture at left). Next, the second collision is solved simultaneously for both corner collisions between the middle and right block, with the result that the middle block is stationary and the right block is moving.

Try selecting the other collision methods from the menu to see the difference; you should find that only the hybrid method gives the "correct" results.

Unable to run the simulation!
You need to get Java software
or see instructions for enabling Java.

Click the Reset button to see the collision again.

The hybrid method decides which collisions to consider in each step as it resolves collisions sequentially. The criteria is something like this: Take the collision with the biggest velocity, which is between body A and body B; then add in any other significant collisions involving bodies A or B. Significant means any collision with at least 10% of the velocity of the primary collision. So resting contacts are ignored.

One can imagine using an alternate hybrid method which would take only collisions between body A and body B; that would still give the "right" results for the colliding square blocks (and also for the unequal velocity collisions considered below). But it would fail to give the nice symmetric result in the "one hits two separate" scenario shown below. (Try selecting the various collision methods on the menu below to compare results).

Unable to run the simulation!
You need to get Java software
or see instructions for enabling Java.

Click the Reset button to see the collision again.

TO DO: Perhaps offer another hybrid collision method that only considers collisions between body A and B???

Problems with the hybrid method.

The hybrid model doesn't correctly handle cases where there are multiple collisions with unequal velocities, because it is based on using simultaneous collision handling for each individual "collision event". Below is an example where there are 2 simultaneous collisions, but at different velocities. What should happen is that the left and right pucks swap velocities, and the middle puck remains stationary.

Unable to run the simulation!
You need to get Java software
or see instructions for enabling Java.

Click the Reset button to see the collision again.

The sequential method gives the correct result for this case:

Unable to run the simulation!
You need to get Java software
or see instructions for enabling Java.

Click the Reset button to see the collision again.

The correct result should be the same as if there were no middle puck; the impact forces should transfer through the middle puck (because the masses are all equal and elasticity is 1). Here is the situation with just 2 pucks, and any of the solvers gives the same result because only a single collision is involved.

Unable to run the simulation!
You need to get Java software
or see instructions for enabling Java.

Click the Reset button to see the collision again.

Note that a variation of the hybrid method (discussed above) would solve this situation correctly, but wouldn't solve other situations that this hybrid method does solve. So there doesn't appear to be some magical method that will solve all situations correctly.

Spring Based Collisions

A different method of handling collisions involves placing tiny but very stiff springs at each collision point between objects. The simultaneous, sequential and hybrid methods considered above all instantaneously resolve the collision with a set of impulses. In contrast, with spring based collision handling, the simulation continues to run during the collision. Because the springs involved are very stiff, the time steps taken during the collision must be very small.

The spring method gives the correct result for the "one hits one" situation, as seen in the simulation below. (This simulation is not a general rigid body simulation, but does show the results of using springs in simple linear collisions.)

Unable to run the simulation!
You need to get Java software
or see instructions for enabling Java.

Click the Reset button to see the collision again.

But for the "one hits two" situation, the spring method gives an incorrect result. The left and middle block are moving after the collision, instead of remaining motionless as they should.

Unable to run the simulation!
You need to get Java software
or see instructions for enabling Java.

Click the Reset button to see the collision again.

Conclusion: Handling multiple collisions is hard!

Among the collision handling methods considered here, none give the "correct" results in every situation. Although it could be argued that our expectation of getting perfectly symmetric results for multiple collisions is not realistic. If you accept that, then perhaps the sequential collision handler is the best method.

A more physically accurate method of collision handling would involve sophisticated modeling of the properties of the objects: how they deform and rebound. Using such a model with an advanced simulation technique like Finite Element Analysis can give very accurate results, and these kinds of techniques are used in science and industry.

But for the simple rigid body simulations considered here, which we want to run quickly, interactively, in real time, we must accept that our simple model will not always handle every complicated situation we throw at it.

Algorithm running time is another consideration for deciding which collision handling method to use; that is, how much computer processing time is needed to handle the collision? In this regards, the simultaneous method shines, because it predicts the results of each collision using equation (1) and does a single calculation to find the impacts needed to give that result. The sequential method (and hybrid method) does several calculations, possibly dozens, for a collision; so it takes more time. The spring-collision method needs very fine-scale times steps during the collision because the springs involved are so stiff; this takes more time to compute.

There is one more important consideration with the sequential collision handler: because of all the rebounding that occurs as objects bounce back and forth, it is possible to get situations that never resolve. Where the sequence of collisions continues on forever, which causes the software to get stuck in an infinite loop. A test can be added in the software to quit the collision handling process if too many collisions have occurred; but of course, then the result will not be "correct".

If anyone reading this says "hogwash! I have a method that works perfectly in all situations!" please let me know. Thanks!

Table of pro's and con's of each method.

simultaneous hybrid sequential springs
speed fast, only one calculation more time to resolve sequence of collisions more time to resolve sequence of collisions much slower because fine-scale time steps during collisions
reliability very reliable possibility of infinite collision sequence possibility of infinite collision sequence possibility that springs might not resolve collision state
correctness in general prediction of results is usually wrong order of collision resolving affects results order of collision resolving affects results dynamics of springs don't match real collisions very well
correctness for Newton's Cradle or "one hits two" pucks incorrect correct even with multiple collision points (blocks) correct if single points of collision incorrect
correctness for symmetric collisions like "one hits two separate" correct correct incorrect correct
correctness for asymmetric collisions like "two hits one asymmetric" incorrect incorrect correct incorrect

About joints: In the 2D physics engine used here, joints are handled differently from normal collisions and contacts between rigid bodies. A joint is a permanent connection between two bodies, or between a body and the (infinite mass) background. For example, in constructing a pendulum there are two joints made at the pivot point; one acts horizontally and the other acts vertically. (MORE ABOUT JOINTS ELSEWHERE ON THE 2D PHYSICS ENGINE PAGE??) In regards to collisions, joints are always handled simultaneously with other collisions, even in the sequential handling method or hybrid method.

Collision Lab

There are many more configurations of experiments that are possible. Please try them on your own to see which collision method gives better results. Try different elasticity also because that makes a difference especially for the sequential method.

Valid HTML 4.01!