Sign in to follow this  
BeanDog

Cull sparse 2D objects by bounding box

Recommended Posts

BeanDog    1065
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?

Share this post


Link to post
Share on other sites
Calexus    245
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.

Share this post


Link to post
Share on other sites
BeanDog    1065
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!

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this