Trees in Collision Detection

From GPWiki

Trees in Collision Detection

The problem of collision detection is often sped up by quickly rejecting collisions that aren't possible. For example, before doing an expensive test, a simple bounding box test can be done, hopefully leading to the expensive test being avoided. Trees can be used to avoid testing for collisions between objects that are in different places in the world and aren't big enough to reach each other.

Naive Approach

When doing collision detection, the naive algorithm is as follows:

for each item A in world
 for each item B in world
  if (A != B)
   check for collisions between A and B

This approach has O(n²) complexity, so doesn't scale well when many objects are present.

An Improvement

A simple approach to speed it up is to split the world into a few sections. In this example, we will consider a 2D world split into 2 sections - east and west. The technique will generalise to any number of dimensions or sections however.

Now the algorithm is slightly more complicated, but still basically the same as above:

for each item A in world.east
 for each item B in world.east
  if (A != B)
   check for collisions between A and B

for each item A in world.west
 for each item B in world.west
  if (A != B)
   check for collisions between A and B

But, how do we know which objects are is world.east and which are in world.west? The easiest way to do this is to make the objects responsible for ensuring they are mentioned in the correct list. So, whenever an object moves, code similar to the following is used:

Move toX, toY
 // Dereference
 for each world section W
  for each mention M of me in W
   remove M

 // Move
 me.X = toX
 me.Y = toY

 // Rereference
 for each world section W
  if (my bounding box intersects W)
   add me to W

This above algorithm can be tweaked to be a bit faster by making sure that only the world sections which are being changed get changed. Also note that an object can be in more than one section - if an object has one side in the 'east' section and another in the 'west' section, it will be counted as being in both.

The algorithm above gives a factor of improvement (it should be a bit under twice as fast as the original approach when using 2 sections - the extra overheads and the choice of sections can cause variation in speed - if all the objects are in the 'east' section, then the algorithm will be slower than the original approach.

The Tree Generalisation

If you don't understand the previous approach, then go back and read it again (and fix it up) - this builds on top of the section method.

What if, instead of having 2 sections, we have an unlimited number of sections? Instead of a section just containing objects, we can allow a section to contain either a few more sections (all of which are contained completely by this 'parent' section) or objects (just like the original sections).

This is probably best described by a picture, but I don't know how to put them in :), so I'll describe the picture and you can draw it in your mind/edit the page to make it good.

Draw a square - this is the whole world, all objects must be inside this square.
 You can draw some objects in the square if you want - make sure they aren't 
 points - they should have a width and height.

Now, pick an object that doesn't have a line through it yet
With the smallest square containing that object, draw 2 lines creating 4 squares of equal size.
Repeat until all objects have a line through them

The above picture is an example tree, with each section containing either 4 more sections or a list of objects in the section.

Now, checking for collisions can be done just on the items in a single section - but now, a section can be really small where there are actually object boundaries and big where nothing is. Traversing the tree (looking for the lists of items) can be done with any standard tree traversal algorithm such as pre-order traversal or post-order traversal.

Maintaining the tree when an object moves is slightly trickier though. The simplified algorithm is as follows:

Move toX, toY
 // Dereference
 for each world section W
  for each mention M of me in W
   remove M
  if (boundaries in W don't touch any objects)
   collapse W (concatenating the object lists in each subsection into one)

 // Move
 me.X = toX
 me.Y = toY

 // Rereference
 for each world section W
  if (my bounding box intersects W)
   add me to W
   while (I have no lines through me)
    subdivide W (creating 4 new object lists each containing the objects from W which are in the sub-sections)
    set W to be the new sub-section that contains me (if multiple exist then this loop will terminate)

Again, this can be sped up (in this case, sped up a lot) by ensuring that excessive adding and removal doesn't happen. However, generally you will find that the performance is now closer to O(nlog(n) - so you can add lots of objects to the world without much slowdown at all.

Notes

The above implementation is a fairly pure one, in the real world, you probably don't want to be subdividing as much as what happens above - this can be done by setting a more restrictive constraint on when to subdivide. The easyest way to do this is to just set a minimum size for each section and not to expand a section if the new sections would be smaller than that.

The pseudo-code glosses over a lot of implementation issues, however the operations which are glossed over are things which can be done quickly - even if the code is non-trivial.

References

Wikipedia on collision detection