Jump to content

  • Log In with Google      Sign In   
  • Create Account


How to do broadphase efficiently


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
1 reply to this topic

#1 lucky6969b   Members   -  Reputation: 535

Like
0Likes
Like

Posted 08 January 2012 - 08:28 AM

For a 500-object world, what is the most efficient way to do broadphase for collision detection?
Do I have to loop thru each of them, and separate them into regions. It will suffer from performance degrade due to a large number of active objects involved. How do you guys deal with this?
Thanks
Jack

Sponsor:

#2 wodinoneeye   Members   -  Reputation: 666

Like
3Likes
Like

Posted 08 January 2012 - 09:49 PM

For a 500-object world, what is the most efficient way to do broadphase for collision detection?
Do I have to loop thru each of them, and separate them into regions. It will suffer from performance degrade due to a large number of active objects involved. How do you guys deal with this?
Thanks
Jack




Some optimization can be made if there are basic assumptions that are in effect.

Octtrees and BSPs can be costly when most objects constantly move and you have to rebuild the tree data so much.

If you can find that there are limitations, simpler solutions can be made (ie- regular catesian grid type membership arrays to spatially divide your objects).

If your bounding boxes are small and your map large you can have an array 2D grid sized to just over the diameter of your largest bounding box.
(The grid size also should be at least as large as the largest move increment per time quantum.)
Objects have markers put in the array cells (linked list) they currently are centered in and move the markers if their location causes them to be in another cell (simple coordinate threshold test).
This revising of the position data is quite cheap (and with a fairly fine grained grid the link lists are not too long so linear traversals can be done against the sets for removal, inserts are at the linklist head)
Collision checking for any object will be against the list of objects in their current cell and any of its adjacent (8) cells (since the object may overlap into adjacent cells). Because of the cell sizing the test need only be made within the adjacent cells.
Every time an object moves you do a lazy evaluation check if the objects intersects with any objects within the cells (lazy evaluation is a simpler less costly test that is used to cull obvious non-collisions and any likely collision test are made with much more costly exact tests - bounding box or worst individual bounding boxes of sub-objects) A simple culling test would be to test the box (dx dy, dz) distance of centerpoints being less than twice the max bounding box radius (not even a suqare root is needed).

If you have to also test linear segments of fast projectiles, the same grid data can be used (use bresenham to find all the grid points the segment travels thru and expand that set to include the adjacents).


If your world is 3D, a 2D grid is still usable to break the collision test sets into very small groupings.
--------------------------------------------Ratings are Opinion, not Fact




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS