Quadtrees - Adding and Finding data.

Quote:

1 - Where do you store the objects? Do you store the object in the node that it fits entirely in? Or do you store it in EVERY node that it fits in? For example: Do I always add the object to the root, then see what other nodes it's touching, and add it there?

In my quadtrees, I always store each object in the smallest quadtree node that completely contains it. To ensure that objects are inserted into ideal nodes, I use 'loose' quadtree nodes.

Quote:

2 - What's an effective method of finding other objects? Let's say my HomingMissile object is looking for objects near it to smash into. What's a good way of getting all the objects around it? My guess is you define a box with the size you want to look in - then ask the quadtree for a list of objects from nodes that are touching that box.

That would probably work. Also consider that each object you insert into the tree should probably have its own bounding box, so that the potential collision list becomes even smaller after you traverse the quadtree. Of course, taking velocity into account, you may have to use a swept volume, like a lozenge, instead of a box.

Quote:

If you're right in the middle, then you're going to get a list of objects from every single node - I suppose that's one of the worst case scenario's however.

That would only occur if your quadtree had only one subdivision. Consider the following pseudo code:


Note that you invariably have to add collision objects contained in the root node, but as you keep traversing the tree, you avoid large chunks contained by children. Also, even though you may often add objects owned by large nodes, the number of objects in these nodes is likely to be small.

I wanted to find an article on loose quadtrees to link to, but, oddly enough*, I was unable to find one. So I guess my mention of loose quadtrees warrants further explanation.

In a loose quadtree or octree, when an object being inserted falls outside the bounds of a node, but the distance between the far extent of the object and the far extent of the node is less than some pre-defined value Epsilon, the node's boundaries are extended to encompass the object, and the object is inserted.

Here is a picture to help explain:


After many objects have been inserted into a loose quadtree, the nodes are likely to overlap, but that's okay - as long as the value of Epsilon is reasonable (less than or equal to half the node's width), the tree should still function ideally.

* - I've read about them in at least three different books

Quote:

Original post by extralongpants In a loose quadtree or octree, when an object being inserted falls outside the bounds of a node, but the distance between the far extent of the object and the far extent of the node is less than some pre-defined value Epsilon, the node's boundaries are extended to encompass the object, and the object is inserted.

That's not what's generally meant by a loose quadtree or octree. That is, the node boundaries do not change as objects are inserted into a loose tree, the boundaries remain static. The term "loose" comes from the node boundaries having been "relaxed" so as to overlap neighboring nodes; but that's done statically, at the construction of the tree.

Compare Thatcher Ulrich's description of loose octrees/quadtrees here: http://www.tulrich.com/geekstuff/partitioning.html

Loose octrees/quadtrees are (or can be made to be very) similar to hierarchical grids/field-trees.

I went back and looked through some of my old books, and it seems that you are right. I happened upon Thatcher Ulrich's article in Game Programming Gems, for instance, and it does indeed use the loose quadtree method that he describes in the article you pointed me to.

I can't remember where I read about the idea of adjustment upon insertion. I know the term 'loose' comes from the overlap; the adjustment upon insertion idea is to keep the nodes only as loose as they have to be. And I should say that in the method I described, your Epsilon is measured to the original width of the node, not the current width. So in essence, you're testing for containment by the fully extended node, but are only adjusting the boundaries of the node to minimally contain the object.

Regardless, keeping the node boundaries static would probably be the best choice in this case, as objects are going to be inserted and removed during run-time.

[EDIT] - And now that I think about it, in the scheme I describe, you'd have to adjust parent volumes too, if you wanted child nodes completely contained (and I'm certain you would). So that's even more reason to use static boundaries. Sorry for the confusion, GroZZleR.


[Edited by - extralongpants on January 23, 2007 9:22:56 AM]