Sign in to follow this  

Sweep&Prune Variant (please critique)

This topic is 4824 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

SCENARIO: I have a bidirectional 2D world full of objects composed of polygons for collision detection. The actual collision detection part is working well, but is based on a quadtree which i suspect is causing slowdown with large numbers of objects. I need a framework for spatial partitioning that is: - Fast - Has Large numbers of objects (~1000 or less) - Capable of handling any size object. A true quadtree is an expandable/collapsable structure that saves memory over a grid approach, but is not so quick. I am not concerned about memory usage (most PCs have more than they need anyway). POTENTIAL SOLUTION: Organize all objects simultaniously into 4 lists appropriately sorted: Xmins Xmaxes Ymins Ymaxes And "cross bookkeep" to keep the location of objects in those four lists within the object itself for quick access. When i want to know what other objects an object collides with i make a list composed of these criteria: 1) all objects sorted in the "Xmins" list that have an xmax value less than the object's xmin 2) all objects sorted in the "Xmaxes" list that have an xmin value greater than the object's xmax. 3) all objects sorted in the "Ymins" list that have an ymax value less than the object's ymin 4) all objects sorted in the "Ymaxes" list that have an ymin value greater than the object's ymax. For each criteria, i'm basically just travlling up or down the particular list from my current object's location until i hit a value that's outside the objects bounding box, stop, then check the other criteria. When an object moves, it simply bubbles up or down the list (and usually not very far either). This might be simpler than doing a lot of "am i in this node?" bounding box checking like i'm doing now. That's it in a nutshell. I'm not even sure if i'm thinking this out right, so if you can critique or suggest an alternative, i'd appreciate the advice. Thanks.

Share this post


Link to post
Share on other sites

This topic is 4824 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.

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