Rigid Body Collision Resolution

This page tackles the problem of how to resolve the collision of two rigid bodies. My first encounter with this question was while designing a computer game in 2004. For over three years, I did not come across a satisfactory treatment neither in books, nor in the Internet. During my semester in Kiruna, I finally had the opportunity to thoroughly investigate the problem myself.

We derive a mathematical solution to the problem step by step. To perform simulations and to visualize the objects in motion, we utilize a computer program, which is available for download. The implementation uses double precision, and simple Euler integration to solve the differential equations of rotation.

Rigid Body Collision Resolution (C++) *	ribocore.zip	230 kB
Download this article	rigid_body_collis...	320 kB

* The program checks the math, and produces the animations on this website.

Towards a mathematical solution

This section suggests forces and torques that - when applied to the bodies during collision - will preserve total linear momentum as well as total angular momentum. In this model, we allow the bodies to intrude each other. However, the forces and torques applied during collision make the bodies separate again.

In the illustrations, the ellipsoids visualize the inertia tensors of the bodies. The ellipsoids are not identical to the exterior of the body.

The rigid bodies are enumerated by . Each body has

Recall the assumptions stated above. The center of total mass is at position 0, i.e.

and the total linear momentum (impulse) is the null vector:

We treat the collection of bodies as a closed system. Within this system, the total linear momentum, and the total angular momentum are perserved, i.e. constant vectors, at all times.

The total linear momentum is the sum of the linear momentums of each body

The total angular momentum is the sum of the angular momentums of each body with respect to the center of total mass

Since in our world, the total momentums are constant, the derivative with respect to time is the null vector. I.e. we demand

In the above derivation, we assume that all quantities depend on time, except mass and the inertia tensors. The introduced variables represent the following:

while is the angular velocity in matrix form

We are interested in forces and torques applied to the bodies during the period of contact.

We specialize the formulas on two rigid bodies, i.e. we assume . We introduce a few more symbols that characterize the contact between the two bodies:

If bodies are intruding each other, then let be proportional to the distance of intrusion. If the bodies are not in contact, we set . We suggest to apply the following forces and torques

We show that under these conditions both, the total linear momentum and the total angular momentum are preserved. Conservation of total linear momentum follows because

The total angular momentum does not change because

There is no time for procrastination.

In the introduction, we have stated the ultimate goal of this project: Given the linear and angular velocities just prior to the contact, we would like to have a formula that computes the linear and angular velocities just after the contact. This section suggests a solution to this problem. The solution is consistent with the definitions and derivations carried out earlier.

In the illustrations, the ellipsoids visualize the inertia tensors of the bodies. The ellipsoids are not identical to the exterior of the body.

First, we introduce a few more symbols

We suggest: The linear and angular velocities just prior to the contact relate to the linear and angular velocities just after the contact in the following way

We show that under these conditions both, the total linear momentum and the total angular momentum are preserved. Conservation of total linear momentum follows because

The total angular momentum after collision is

From that, we subtract the total angular momentum before collision

and yield a difference of

At this point,

is the only remaining unknown. As we will show next,

is uniquely determined under the assumption that the two bodies collide elastically.

In an elastic collision, the total energy before the collision equals the total energy after the collision, i.e.

Previously, we have suggested the relations

where

Now, determining so that the total energy is preserved reduces to solve a quadratic polynomial. Evidently, is one solution to conserve total energy, which corresponds to "no collision". However, we are interested in

Note, the numerator of the fraction is the scalar product between the velocity of contact and the surface normal , where

Basically, we are done at this point. The latter value of

generates the three animations you see above. We conclude with some remarks:

To produce a final demonstration, we use the collision detection library RAPID. The white spheres indicate the location of last contact.

Software and further reading

An open source physics engine that I have checked out myself, in the Newton Game Dynamics by Julio Jerez and Alain Suero. The software comes with a demo that explores the broad spectrum of applications. I find the results to be efficient, stable, and realistic. Moreover, the authors C++ style is just perfect.

The Open Dynamics Engine (ODE) originally by Russell Smith seems to be a popular C++ library for developers in gaming, but also in robotics. The library is suitable for simulating articulated rigid body structures. However, ODE emphasizes speed and stability over physical accuracy.

Computer graphics researchers from Stanford University came up with a successful strategy to animate and collide innumerable rigid bodies. The paper Nonconvex Rigid Bodies with Stacking describes how to achieve breathtaking results. An open source implementation of their method is written by Danny Chapman. To resolve a multi-contact multi-body collision, the authors propose to simulate the scenario a number of times: The sequence of pairwise collisions are resolved with different ordering and the outcomes are averaged.