Quadtrees + Collision Detection

Typicall in quad-trees your nodes contain EITHER child nodes OR object lists. I believe a node containing child nodes is a 'branch' and a node containing objects is a 'leaf'.

And you don't just check the object list for the node your Object A is in, because as I think you were hinting at, objects can straddle multiple nodes.

When I want to know how many objects are potential collision candidates I'll start with the bounding sphere for that object. I pass that into the root node of my quad tree. Each quadtree node has its own sphere (remember sphere-sphere checks are very cheap to do) and I move down the list with some simple logic. If a quad-tree sphere was entirely inside the object's sphere (ie, large object w/small quadtree nodes) then ALL the children of that node are potential candidates (you could choose to optimize out further checks down the tree, but I tend not to).

If the node's sphere just intersects the object's sphere, or the object's sphere is inside the node's sphere (assuming you make that kind of distinction) then further testing is necessary. At that point I'll do a sphere-box check (still pretty cheap if you're using AABB) since the sphere checks produce more positives than needed, especially when your tree nodes are more rectangular than square.

Same rules apply on that level, if it intersects then all the children are analyzed, and that is where the recursion comes in. Hope I explained that well.

Does it fit into the current node (start at the root)

You may be missing part of how quadtrees work. Every point should fit in the root node.

ItsDoh, I think your description of a quadtree is a bit off. There are quadtree implementations that contain object lists in nodes besides the leaves. In fact I'm having trouble thinking of any case where it would make sense to store object lists only in leaf nodes (edit: this makes sense when the quadtree is being used to store points). Using bounding spheres is entirely optional and not necessarily faster because it will cause false negatives for intersection tests and possibly false positives for containment tests depending on the shapes of the objects.

The reason why quadtrees can speed up collision tests is that for N objects there are N*(N-1)/2 pairs to check for collisions. In most situations the objects will be scattered over the game world and will therefore be in entirely different parts of the quadtree. Instead of checking every pair for intersections you only need to check the pairs that are in intersecting nodes in the tree.

For a small number of objects it isn't worth it because it is much faster to check all N*(N-1)/2 pairs. For a large number of objects scattered over the landscape using a quadtree or other spacial partitioning scheme is indispensible. If you have 1000 objects then that's nearly half a million pairs to check for collisions. Spatial partitioning schemes can reduce that number greatly. Even if there are 999 enemies to check for collisions with one player, it can still be faster to use the quadtree than to perform 999 checks.

There's a version of quadtrees called "loose quadtrees" where objects of a certain size are always placed in the same level of the tree regardless of their position. This can be useful for dynamic objects since you can avoid having to determine what level the object should be placed on and it eliminates "hot spots" like the center of the quadtree. (edit: is there actually a difference between "loose quadtrees" and hierarchal grids? the more I think about it, the more I think they're the same thing)

[Edited by - Vorpy on January 28, 2007 7:03:06 PM]

Quote:

Original post by Vorpy (edit: is there actually a difference between "loose quadtrees" and hierarchal grids? the more I think about it, the more I think they're the same thing)

They're different in as much as one is a tree and the other is a number of grids. A tree has a root and a hierarchical grid does not. Trees are frequently pointer-based whereas grids are not. However, if you linearize the loose octree/quadtree and chop off the root (only retaining the last k levels) then you basically end up with something that's a hierarchical grid. It is reasonable to pose the question: at which point during this "optimization" does the loose octree/quadtree turn into a hierarchical grid and cease to be a loose octree/quadtree? I think the only sensible answer is the counter-question: how long is a piece of string?

Vorpy, I'm aware you can maintain lists at each level, but going back to the original problem he seemed to be thinking there was no reason to check beyond the root node, or he didn't realize the root node encompassed the entire region, I'm not sure which.

And I thought I'd explained that bounding spheres were only as first-stage intersection test, you should of course then continue with more accurate to the geometry tests if the sphere-sphere checks come out true.