Sign in to follow this  
leiavoia

Sweep&Prune Variant (please critique)

Recommended Posts

leiavoia    960
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

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