2 replies to this topic

[BeanDog]

I have a fairly large number of objects--thousands, perhaps tens of thousands--which are laid out on the 2D plane. I have an axis-aligned bounding box for each of these objects, and these bounding boxes vary in size dramatically. I do know that all of these objects are within a certain area--the boundaries of their world. I'd like to figure out which of these objects appears within a given viewport as quickly as possible.

I looked around a bit at quadtrees, but I'm not totally clear on how (or if) they might be applicable to objects that are not simply points. Can someone point me in the right direction?

[Calexus]

A quadtree would probably fit your needs perfectly. It is easy and straightforward to implement and performs well for "normal" scenes. When working with none point size objects you simply use there bounding volumes, aabb in your case, and insert them either in the last nod containing the entire bounding volume (be it internal or leaf node) or in all the leaf nodes the bounding volume intersects. You could also use a combination of both but that is probably not very useful.

If you don't want to use a quad tree there are other alternatives like the good old grid structure, the bsp-tree, bounding volume hierarchies or spatial hashing. Or you could probably just iterate all the objects ant test them all if you have lets say less then 20k objects but then I would use bounding spheres instead as the are much cheaper to test. Actually it's usually a good idea to always test spheres first, even if you have an aabb you test the bounding sphere of the aabb before you test the aabb itself.

[BeanDog]

Ooooh, that was the basic conceptual idea I'd missed. I'd assumed that all objects had to be stored in the leaves of a quadtree. Thanks!