oreilly.comSafari Books Online.Conferences.


Five Steps to Adding Physics-Based Realism to Your Games
Pages: 1, 2

Step 3: Collision Detection and Response

It is important to make the distinction between collision detection and collision response. Collision detection is a computational geometry problem involving the determination of whether and where two or more objects have collided. Collision response is a physics problem involving the motion of two or more objects after they have collided.

Related Reading

Physics for Game DevelopersPhysics for Game Developers
By David M. Bourg
Table of Contents
Sample Chapter
Full Description

Collision detection is a crucial aspect of any real-time simulation where objects are not supposed to be able to pass through each other. Your collision-response algorithms rely on the results of your collision-detection algorithms in order to accurately determine the appropriate response to any collision. Therefore, you should take care in making sure your collision-detection schemes are accurate and reliable. That said, collision detection is no easy task. I personally find it much more difficult to implement robustly than it is to implement the physics aspects of rigid body simulations. For game applications, as I'm sure you are aware, speed is also a major issue, and accurate collision detection can be slow. Generally, you'll want to use a two-phase approach to collision detection. First, you can use a bounding sphere or box check to test whether there are possible collisions between objects. If this check indicates possible collisions, then you'll want to do a more detailed check on the candidate objects to see if they are indeed intersecting.

There are many approaches you can take for this detailed collision check. The thing you have to keep in mind is the trade-off between accuracy and performance. Kevin Kaiser addresses triangle-to-triangle level collision detection in detail in Chapter 4.5 of Game Programming Gems. Nick Bobic also treats polygonal collision detection in his Gamasutra article Advanced Collision Detection Techniques. Brian Mertich has also written several useful papers on collision detection for real-time simulations.

Whatever collision-detection scheme you use, there are certain pieces of information that it must provide to you in order for you to simulate physically accurate collision responses. Your collision-detection routine must tell you:

  • The point of contact on each body. For example, the location of the contact point relative to the center of gravity of each body involved in the collision.
  • The collision normal vector (and the tangential vector if you're modeling friction in your collisions).
  • The relative velocities of each body at the point or points of contact.

If you're writing a 3-D game complete with detailed polygon models for high-quality rendering, you might be tempted to use those same models in your collision-detection checks for your physics simulation. However, you may not want to do this since it will take more CPU time to do the collision check and may be unnecessary in terms of physical realism. Don't confuse the requirements for visual realism with physical realism. You may find that you need highly detailed polygon models for quality renderings, but your collision model for that object may only need a fraction of the number of polygons. Granted, this approach means you'll have to keep track of two models for each object in your simulation, but the payoff in terms of performance may be well worth it.

Related Reading

Physics for Game DevelopersPhysics for Game Developers
By David M. Bourg
Table of Contents
Sample Chapter
Full Description

It is important to make the distinction between collision detection and collision response.

My treatment of rigid body collision response in my book is based on classical Newtonian impact principles. Bodies that are colliding are treated as rigid regardless of their construction and material. Rigid bodies discussed here do not change shape even upon impact. This, of course, is an idealization. You know from your everyday experience that when objects collide they dent, bend, compress, or crumple. For example, when a baseball strikes a bat, it may compress as much as three quarters of an inch during the millisecond of impact. Notwithstanding this reality, you can rely on the well-established impulse method to approximate rigid body collisions. In this method, an impulsive force is applied to each colliding object at the point or points of impact. This force is calculated such that it changes the velocity of each object instantly, not allowing them to penetrate one another. The method is semi-empirical in that it uses so-called coefficients of restitution to simulate the hardness or softness of various objects. For example, different coefficients of restitution can be used to simulate a rubber ball bouncing off of a hard surface, or a lump of clay that sticks to a surface after a collision.

This classical approach is widely used in engineering machine design, analysis, and simulations. However, for rigid body simulations there is another class of methods known as penalty methods at your disposal. In penalty methods, the force at impact is represented by a temporary spring that gets compressed between the objects at the point of impact. This spring compresses over a very short time and applies equal and opposite forces to the colliding bodies to simulate collision response. Proponents of this method say it has the advantage of ease of implementation. However, one of the difficulties encountered in its implementation is numerical instability. David Baraff reviews several aspects of penalty methods (as well as other methods) in his paper Nonpenetrating Rigid Body Simulation.

Step 4: Numerical Integration

The next aspect of implementing your physics simulator deals with actually solving the equations of motion. The equations of motion can be classified as ordinary differential equations. In some simple cases you can solve these differential equations analytically. However, this won't be the case for general rigid body simulations. Force and moment calculations for your system can get pretty complicated and may even rely on tabulated empirical data, which will prevent you from writing simple mathematical functions that can be easily integrated. This means you have to use numerical-integration techniques to approximately integrate the equations of motion. I say approximately because solutions based on numerical integration won't be exact and will have a certain amount of error depending on the chosen method. I discuss several integration methods, along with sample code, in Chapter 11 of my book.

By far, the easiest integration method to implement is Euler's method. In this method you first calculate the forces and moments on each object in order to determine acceleration. Recalling the equation for Newton's second law, you can obtain acceleration by dividing the resultant force acting on an object by the object's mass (for angular acceleration you need to divide torques by inertias). Once you have acceleration you can obtain the change in velocity by simply multiplying the acceleration by a small change in time called a time step. The object's new velocity is simply its old velocity plus the change in velocity for the current time step. To obtain the object's new position, you first multiply its velocity by the time step to obtain a change in displacement (position) and then add this change to the object's last position. To minimize numerical errors you must step through your simulation at very small time steps with this method.

A major drawback of Euler's method is instability. If your time steps are too large, then your solution may diverge from the exact solution, and your simulation may blow up.

A major drawback of Euler's method is instability. If your time steps are too large, then your solution may diverge from the exact solution, and your simulation may blow up. For example, I was recently implementing a simulation of water flowing over a dam using a method called Smoothed Particle Hydrodynamics. Initially, I was using Euler's method just so I could get the simulation up and running quickly, with the idea of implementing a better method later. While running the simulation for the first time, the water started flowing over the dam in a fairly realistic manner. However, after a few steps all the particles representing the water took to the air and flew out of my computational domain like meteors. Obviously this is wrong, and is a good example of a solution becoming numerically unstable. To solve the problem I was forced to implement an alternative method sooner than I had anticipated.

One such method is known as the Improved Euler method. For ill-conditioned problems, this method is far more stable than Euler's method. However, it requires two force calculations for each object in the simulation. Thus, improved accuracy and stability come at a price in terms of CPU time. Other methods, including the Runge-Kutta and Leap-frog methods, also improve accuracy and stability but again at the cost of CPU time, and in some cases increased memory requirements. Sometimes you can offset the increased CPU burden with these improved methods since they allow you to take larger time steps while still maintaining accuracy. The bottom line is that, here again, you're faced with trading off ease of implementation and speed with accuracy and more importantly, stability.

Step 5: Tuning

The final and arguably the most time-consuming aspect of implementing your physics simulator is tuning (also known as parameter tuning). Many times I've gone through the steps outlined above only to run my simulation to watch it fail. Either the simulation blew up or the behavior of the objects I was trying to simulate was less than accurate.

When writing any simulation you'll find that there are many empirical coefficients and parameters that you have to estimate, for example, collision tolerances, coefficients of restitution, mass properties, and drag coefficients, among others. In many cases your initial estimates for such parameters may be off, resulting in instability or unrealistic behavior. This means that you'll have to tune such parameters until you get the results you want. By tuning I mean the trial-and-error process of changing certain parameters to see what effect they have on your simulation until you get it to work right. In some cases it may mean implementing new algorithms, as I had to do with the integration scheme in my water simulation, for example.

There are a couple of things you can do to make this job easier on yourself. First, research the physics behind what it is you are simulating. Try to obtain an understanding of how the system you are simulating actually behaves in the real world. Find out what factors are important: for example, what forces govern the system's behavior, and try to find some real-world empirical data for things such as drag coefficients, coefficients of restitution, friction coefficients, and so on. This will help take some of the guesswork out of setting initial values for such parameters, and help to identify unrealistic behavior.

Second, don't bury (or spread out) all this data in your source code. Set up a bunch of defines for such data in one file so you can quickly find and change the data as you go through the tuning process. Something you might consider is implementing a mechanism that allows you to change specific data on the fly so you can tune certain aspects of the simulation in real time. I've found this helpful in specific simulations where, for example, I wanted to see the effects of changing viscous drag as the simulation ran. I found it difficult to observe subtle changes in behavior if I had to stop one simulation, change some data, and then rerun the simulation again; especially if the behavior I wanted to observe didn't occur at the start of the simulation but only after many hundreds of time steps.

David M. Bourg performs computer simulations and develops analysis tools that measure such things as hovercraft performance and the effect of waves on the motion of ships and boats.

O'Reilly & Associates will soon release (November 2001) Physics for Game Developers.

Return to the Linux DevCenter.

Linux Online Certification

Linux/Unix System Administration Certificate Series
Linux/Unix System Administration Certificate Series — This course series targets both beginning and intermediate Linux/Unix users who want to acquire advanced system administration skills, and to back those skills up with a Certificate from the University of Illinois Office of Continuing Education.

Enroll today!

Linux Resources
  • Linux Online
  • The Linux FAQ
  • Linux Kernel Archives
  • Kernel Traffic

  • Sponsored by: