QuadTree: store only points, or regions?

Question

I am developing a quadtree to keep track of moving objects for collision detection. Each object has a bounding shape, let's say they are all circles. (It's a 2D top-down game)

I am unsure whether to store only the position of each object, or the whole bounding shape.

If working with points, insertion and subdivision is easy, because objects will never span multiple nodes. On the other hand, a proximity query for an object may miss collisions, because it won't take the objects' dimensions into account. How to calculate the query region when you only have points?

If working with regions, how to handle an object that spans multiple nodes? Should it be inserted in the nearest parent node that completely contains it, even if this exceeds the node's capacity?

Thanks.

Answer 1

If storing extended objects (regions) in a quadtree, the object should be referenced from all the leaf nodes it touches. I wouldn't try to find the least common ancestor and store it there, because then e.g. a small object that happens to cross a high-level boundary will end up in a very high node, and must be tested against everything else in that large, high-level node when you do collision queries and suchlike.

However, you also have to be careful because large objects could end up being referenced from many nodes, making them expensive to update when they move around, and causing them to be re-checked many times for collisions etc. Depending on your use case it might be worth using some kind of heuristic to store large objects at a higher level in the tree, but this would complicate the algorithms, so I probably woudn't bother unless you establish that it's really a performance problem in your particular case.

Similarly, to query a region, the query should look at all the leaf nodes the queried region touches.

These basically use the same algorithm, which is to start with a region and push it down through the tree to find the leaf nodes it touches. It's a depth-first traversal, but at each node you can prune any children that don't touch the region. You'll need to maintain a stack to keep track of where you are in the traversal.

Answer 2

You must store it in the smallest node that completely contains it- even if this exceeds capacity (use a resizable container).

Answer 3

I would add this as a comment in response to @Nathan Reed's answer, except it's too big to be a comment, and is perhaps in any case worthy of being a separate answer.

We were doing precisely what was proposed in his answer, and in fact have comment in the source linking to this page. For the most part, it has worked extremely well, except that once every two or three months, we've been losing a server at random that has gone non-responsive due to massive duration of search queries.

The root cause of the problem came to my attention while doing a performance check to try and figure what was causing this. It's likely only a concern if you permit overlapping objects. In our game we do, and in a worst case scenario it occasionally lead to a performance killing depth spike.

We had one edge case where about 100 objects, all with with bounding disks, were clustered in very close proximity. That lead to the problem of a very deep spike in the tree, because we got to the point where objects were larger than the area covered by the quadtree nodes, so each new object was showing up in multiple nodes, leading to massive subdivision of the tree, thus snowballing the problem out of control.

The takeaway from this is that if you allow object regions to overlap, keep a close eye on things if you get tight clusters of objects, to ensure your tree doesn't get too deep.

The solution I'm currently investigating is to store objects as points, and then when doing a search, increase the bounds of the search rectangle by the maximum radius stored in the tree. That should work for us, because the tree is a first pass search, we then do a true circle based range check, along with a few other criteria checks, so the extra false alerts will get filtered out.

Your actual mileage may vary.