Are collision detection always O(n^2)?

Question

Are physics engine able to decrease that complexity, for example by grouping objects who are near each other and check for collisions inside this group instead of against all objects ? (for example, far objects can be removed from a group by looking at its velocity and distance from other objects).

If not, does that make collision trivial for spheres (in 3d) or disk (in 2d) ? Should I make a double loop, or create an array of pairs instead ?

EDIT: For physics engine like bullet and box2d, is collision detection still O(N^2) ?

Answer 1

Spatial division is always O(N^2) in worst case and that is what complexity in informatics is about.

However there are algorithms that work in linear time O(N). All of them are based on some kind of sweep line.

Basically you need to have your objects sorted by one coordinate. Let's say X. If you perform the sort every time before collision detection, the complexity will be O(N*logN). The trick is to sort only when you are adding objects to the scene and later when something in the scene changes. Sorting after movement is not trivial. See the linked paper below for an algorithm that takes into movement and still works in linear time.

Then you sweep from left to right. Each time your sweep line crosses beginning of an object, you put it inside a temporary list. Every time your sweep line exits the object, you take it out from the list. You consider collisions only inside this temporary list.

The naive sweep line is O(N^2) in worst case as well (you make all objects span the whole map from left to right), but you can make it O(N) by making it smarter (see link below). A really good algorithm will be quite complex.

This is simple diagram how the sweep line works:

The line sweeps from left to right. Objects are sorted by X coordinate.

• Case one: First two objects are checked. Nothing else matters.
• Case two: First object was checked and is gone from the list. Two and three are checked.
• Case three: Even if that object IS colliding, we don't check.
• Case four: Because we check in this case!

Algorithms like this have complexity O(C*N) = O(N).

Source: Two years of computational geometry courses.

In collision detection this is typically called Sweep and Prune, but sweep line family of algortithms is useful in many other fields.

Further recommended reading that I believe is out of scope of this question, but nevertheless interesting: Efficient Large-Scale Sweep and Prune Methods with AABB Insertion and Removal - This paper presents an enhanced Sweep and Prune algorithm that uses axis-aligned bounding boxes (AABB) with sorting that takes into account movement. Algorigthm presented in the paper works in linear time.

---

Now note that this is the best algorithm in theory. It doesn't mean that it is used. In practice, O(N^2) algorithm with spatial division will have better performance speed wise in typical case (close to O(N)) and some extra requirement for memory. This is because the constant C in O(C*N) can be very high! Since we usually have enough memory and typical cases have objects spread evenly in space - such algorithm will perform BETTER. But O(N) is the answer to the original question.

Answer 2

No. Collision detection is not always O(N^2).

For instance, say we have a 100x100 space with objects with size 10x10. We could divide this space in cells of 10x10 with a grid.

Each object can be in up to 4 grid cells (it could fit right in a block or be "between" cells). We could keep a list of objects in each cell.

We only need to check for collisions in those cells. If there is a maximum number of objects per grid cell (say, there are never more than 4 objects in the same block), then collision detection for each object is O(1) and collision detection for all objects is O(N).

This is not the only way to avoid O(N^2) complexity. There are other methods, more adequate for other use-cases - often using tree-based data structures.

The algorithm I described is one type of Space partitioning, but there are other space partitioning algorithms. See Types of space partitioning data structures for some more algorithms that avoid the O(N^2) temporal complexity.

Both Box2D and Bullet support mechanisms to reduce the number of checked pairs.

From the manual, section 4.15:

Collision processing in a physics step can be divided into narrow-phase and broad-phase. In the narrow-phase we compute contact points between pairs of shapes. Imagine we have N shapes. Using brute force, we would need to perform the narrow-phase for N*N/2 pairs.

The b2BroadPhase class reduces this load by using a dynamic tree for pair management. This greatly reduces the number of narrow-phase calls.

Normally you do not interact with the broad-phase directly. Instead, Box2D creates and manages a broad-phase internally. Also, b2BroadPhase is designed with Box2D’s simulation loop in mind, so it is likely not suited for other use cases.

From the Bullet Wiki:

There are various kinds of broadphase algorithms that improve upon the naive O(n^2) algorithm that just returns the complete list of pairs. These optimised broadphases sometimes introduce even more non-colliding pairs but this is offset by their generally improved execution time. They have different performance characteristics and none outperform the others in all situations.

Dynamic AABB Tree

This is implemented by the btDbvtBroadphase in Bullet.

As the name suggests, this is a dynamic AABB tree. One useful feature of this broadphase is that the structure adapts dynamically to the dimensions of the world and its contents. It is very well optimized and a very good general purpose broadphase. It handles dynamic worlds where many objects are in motion, and object addition and removal is faster than SAP.

Sweep and Prune (SAP)

In Bullet, this is the AxisSweep range of classes. This is also a good general purpose broadphase, with a limitation that it requires a fixed world size, known in advance. This broadphase has the best performance for typical dynamics worlds, where most objects have little or no motion. Both btAxisSweep3 and bt32AxisSweep3 quantize the begin and end points for each axis as integers instead of floating point numbers, to improve performance.

The following link is a general introduction to broadphase and also a description of the Sweep and Prune algorithm (although it calls it "Sort and Sweep"):

http://www.ziggyware.com/readarticle.php?article_id=128

Also, take a look at the wikipedia page:

http://en.wikipedia.org/wiki/Sweep_and_prune

Answer 3

O(N^2) refers to the fact that if you have N objects, figuring out what is colliding with what is, worst case, N^2 collision computations. Say you have 3 objects. To find "who is hitting who", you have to find:

o1 hitting o2?  o1 hitting o3?
o2 hitting o1?  o2 hitting o3?
o3 hitting o1?  o3 hitting o2?

That's 6 checks for collisions, or N*(N-1) checks. In asymptotic analysis we'd expand the polynomial and approximate as O(N^2). If you had 100 objects, then that'd be 100*99, which is close enough to 100*100.

So if you partition space using an octree for example, the average number of comparisons between bodies is reduced. If it is possible for all the objects to gather into a very small area (say if you're doing some kind of particle flow simulation, where particles can gather in the same area) then the O(N^2) may still occur at points in the simulation (at which points you'll see slowdown).

So, the whole point of O(N^2) there is because of the nature of each body checking every other body in the scene. That's just the nature of the computation. A lot of things can help to make this cheaper though. Even a scene graph (say detecting between objects in the same room only) will reduce the number of collision computations to be done significantly, but it will still be O(M^2) (where M is the number of objects in the room to be collision detected against). Spherical bounding volumes make the initial check very fast (if( distance( myCenter, hisCenter ) > (myRadius+hisRadius) ) then MISS), so even if collision detection is O(N^2), the bounding sphere computations are likely to happen very fast.