Optimizing Real-time Physics:
Avoiding the O(n²) Worst-Case Collision Detection Scenario
(Friday, June 28, 2002)

(ARTICLE IN PROGRESS)

Introduction

If you've played with one of those physics SDK demos where you can smash a whole lot of objects into each other, you've likely brought to its knees by making too many objects collide. This slowdown is caused by several factors which I'll explain and give solutions for:

1. Worst case: n(n-1)/2 collisions.
2. Callbacks are sloooooooooooooooooooow!!!
3. SDKs don't degrade gracefully

1. Worst-Case Party Handshakes

Remember the elementary combinatorics problem "if each person at a party shakes hands with everyone else, how many handshakes are possible"? Well, this is the same as the worst case for collision detection. The maximum number of collisions (or handshakes) between n objects is n(n-1)/2, which is on the order of n². Figure 1 illustrates the maximal interactions between five objects, which indeed add up to 5(4)/2=10.

Figure 1: Maximal interactions between five objects

This is bad, but how bad? To get some idea, we'll study the simplest system: a world made of spheres ¹. We test for collision by comparing distances to the sum of the radii. The test itself can be reduced to a constant number of operations involving only a few multiplications and additions. But in the worst case, we have to do O(n²) tests, which doesn't scale gracefully to large numbers of spheres. Put simply, we're screwed if our environment allows the maximal number of collisions to occur.

In practice, our worlds are populated so that the worst case doesn't occur. I'd like to emphasize that if an environment is constructed in which every object collides with every other object, there's no way around the O(n²) computational complexity. So whatever we do, we must avoid this at all costs.

2. Slow Callbacks

Assume for now we've lifted the O(n²) worst-case curse and got our engine scaling to tens of thousands of rigid bodies. Most physics SDKs have done exactly this and thus scale to very complex scenes; however, there's the problem of user-supplied collision-handling callbacks.

3. Graceful Degradation

This is one way around the worst-case scenario and is just good form anyhow. The physics engine should provide a setting that does "panic mode" low-accuracy simplified collision detection. The idea is that it's better for the physics simulation to look terrible than for it to run at single-digit framerates. But we need to make sure the simulation is plausible (i.e., players can't fall through the ground, etc.).

What we want then is conservative collision detection. We do this by over-approximating collisions through the use of simpler geometries that bound the rigid bodies. The advantage is that we don't incur the expense of the narrow-phase. The disadvantage is that false positives are a guaranteed side-effect. This can result in unrealistic "explosions" in scenes that behave correctly before the narrow-phase is deactivated². But then, which is more jarring—single-digit framerates or unrealistic physics?

Some ways to degrade collision detection & response gracefully:

• Don't do narrow-phase: Only test for collisions between bounding volumes. Can still bog down scenes which don't lend themselves to sweep-and-prune.

Now that we've explored conservative collision detection, we'll look at an alternative. ... (reference to Mirtich's scheduling algorithm in "Efficient Algorithms for Two-Phase Collision Detection") ... ... use this scheduling algorithm to do collision tests less frequently for complex objects and more frequently for simple objects ... ... discuss tradeoffs ...

References

1. John Dingliana Carol O'Sullivan. Graceful Degradation of Collision Handling in Physically Based Animation.
   
2. rec.games.programmer thread (Brandon Van Every, May 9, 1998): Brandon Van Every outlines the problems inherent in the O(n²) collision detection/handling process.
   1. Excessive memory caching, due to generation of memory state for intermediate results... O(n²) storage space is too damn much and doesn't scale!
   2. Sequentiality: ???
   3. (3) *CALLBACKS*: kills cache locality, introduces function-call speed grind.
3. Russell Smith. Open Dynamics Engine v0.035 Pre-release User Guide. Open source physics SDK... Contains guidelines for writing a well-behaved, fast simulation.
4. Thalmann. Collision Detection. Really great in-depth explanation of divide-and-conquer schemes.
5. Pablo Jiménez. Orientation-based Pruning for Collision Detection. A novel approach which reduces complexity by considering the relative orientations and velocities of rigid bodies.

Footnotes

1. It isn't likely that any arrangement of spheres will reach n(n-1)/2 collisions, but bear with me here.
2. One way around this is to utilize the feature of your Physics SDK to take low-energy, stationary objects out of the simulation. So at least these stationary objects don't "explode" for no good reason when the narrow-phase is bypassed.

See Also:
Sphere Collision Test Without a Square Root
Sweep-and-Prune