Jump to content
  • Advertisement
Sign in to follow this  
BeanDog

Cull sparse 2D objects by bounding box

This topic is 2550 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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
Advertisement
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
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
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!