Quadtree for 2D collision detection

Question

I'm trying to use a quadtree for 2D collision detection, but I'm a little stumped on how to implement it. First of all, I'd have a quadtree which contains four subtrees (one representing each quadrant), as well as a collection of objects which don't fit into a single subtree.

When checking an object for collisions in the tree, I would do something like this (thanks to QuadTree for 2D collision detection):

1. Check the object for collisions with any objects in the current node.
2. For any subtree whose space overlaps the object, recurse.

To find all collisions within a quadtree tree:

1. Check each object in the current node against each other object in the current node.
2. Check each object in the current node against each subtree.

To insert into a quadtree:

1. If the object fits into multiple subtrees, then add it to the current node, and return.
2. Otherwise, recurse into whichever subtree contains it.

To update a quadtree:

1. Recurse into each subtree.
2. If any element in the current node no longer fits completely in the current tree, move it to the parent.
3. If any element in the current node fits into a subtree, insert it into the subtree.

Is this alright? Can it be improved?

Xuthus

Implement it the way you describe it, I've done it this way and the way Dave O. has done it and this is easier to code and it's faster. Managing more lists to keep track of all the leaves your on adds avoidable overhead. Here's the source (in Java) to one of my versions: Steerio – Dunghill

Answer 1

Your quadtree structure isn't optimal. You're right to store 4 subtrees per node, but actual objects should only be stored inside the leaves, not inner nodes. Therefore the collection holding the actual objects needs to be moved to the leaves.

Let's have a look at the implementation of the operations:

1. Insert an object into the quadtree:
   Check if the object intersects the current node. If so, recurse. If you've reached the leaf level, insert the object into the collection.
2. Delete an object from the quadtree:
   Execute the exact same steps as if inserting the object, but when you've reached the leaf level delete it from the collection.
3. Test if an object intersects any object inside the quadtree:
   Execute the exact same steps as if inserting the object, but when you've reached the leaf level check for collision with all the objects in the collection.
4. Test for all collisions between all objects inside the quadtree:
   For every object in the quadtree execute the single object collision test.
5. Update the quadtree:
   Delete all objects from the quadtree whose position has been modified and insert them again.

This has several advantages:

• By only storing objects in the leaves it is very easy to handle operations on the quadtree (fewer special cases)
• The quadtree can have leaves with different depth, thus allowing you to adapt the density of the quadtree depending on the spatial region it covers. This adaption can happen at runtime, thus keeping the object/node ratio optimal.

Only disatvantage:

• Objects can belong to several collections inside the quadtree. You're going to need an extra linear collection outside the quadtree to enumerate every object without duplicates.

Pumpkinseed

It's that extra disadvantage I'm worried about. Won't that lead to the addition of extra code (like the linear collection outside the quadtree) to make sure that A only collides with B once, even though B might be in multiple subtrees? – Xuthus

@RobotGymnast Collision is not a problem since you only return true/false and if an object belongs to multiple sets it's still identical across them. Enumeration is. You can't use the quadtree to go through all your objects, because you'd visit some of them multiple times. – Pumpkinseed

This may be naïve, but what about adding a touched() type function to the objects? That way during traversal when an object as been inspected you can set a touched flag and thus ignore it if it comes back up? I know it may not be a perfectly clean or even elegant method but it seems simple enough and I've used it to great effect with my quadtree implementations. – Phenocryst

Another disadvantage I just discovered is that if you have four large objects, say, covering the entire tree, it'll subdivide until you hit the depth limit. Add a fifth one, and without some convoluted edge case handling, it'll crash. – Goldfish

Yet another is that calculating a bounding rect, for many objects (lines, circles, rectangles, even polygons) is much, much cheaper and trivial than calculating intersections. – Goldfish

Answer 2

Quad trees are not always the best data structure for collision detection. The overhead of a quadtree can potentially be unbounded (if you don't limit the depth of the tree), and in the worst case don't give any speed up at all. Instead, you might want to consider using a sparse grid, which gives better performance than a quadtree only without the extra overhead of traversing multiple tree levels.

There are also other completely different approaches which might be even better. For example, you could try implementing Zomorodian and Edelsbrunner's algorithm, as I did in the following module:

• https://github.com/mikolalysenko/box-intersect

Here are also some articles which I wrote that discuss these issues in more detail:

• http://0fps.net/2015/01/07/collision-detection-part-1/
• http://0fps.net/2015/01/18/collision-detection-part-2/
• http://0fps.net/2015/01/23/collision-detection-part-3-benchmarks/

In particular, if you look at the benchmarks in the last section you will see that of all the libraries surveyed, quadtrees tended to perform quite poorly compared to other collision detection methods like R-Trees, grids or segment trees.

Fail

these blog posts are excellent. some of the best information on this topic i have found – Leung

Answer 3

I am not sure how cpu effective it is yet, but it seems to be working fine on my core duo in eclipse, still runs at over 2400 fps lol..

basically, I added one list to collidable objects to store references to quadtree node objects that I have associated the object with (via inserting into the quadtree). I also added a list to each quadtree node, that stores references to any objects deemed within the bounds of that node. So each node will only have one occurrence of each object. each node also stores a reference to its parent node, for navigation to nearby nodes if I want to check any of them after the inital node for further collision accuracy.

it's very easy to get references to all other objects in one cell:

list temp_checklist = object.cells[cell_index].objects
//('objects' being some sort of array or list of object references as described above)

hope that helps someone ;)

Guest