Archived

This topic is now archived and is closed to further replies.

owl

Collision Detection: QuadTree performance.

Recommended Posts

Hello. I have my collision detection and response algorithms working and I''m now trying to implement a quadtree system to reduce the number of checks when having lots of colliders. What I did looks like this:

 ___________ ____________ ___________ ____________  A (world)
|           |            |           |            |
|           |            |       [o3]|            |
|     F     |     G      |     J     |      K     |
|___________B____________|___________C____________|
|           |            |           |            |
|           |            |           |            |
|     H     |     I      |     L     |      M     |
|___________|____________|___________|____________|
|           |            |           |            |
|           |            |           |            |
|     N     |     O  [o2]|[o1] P     |      Q     |
|___________D____________|___________E____________|
|           |            |           |            |
|           |          / |           |            |
|     R     |     S  [c] |     T     |      U     |
|___________|____________|___________|____________|

 
So, for instance, I have my 2D world divided in nodes and sub-nodes (A{B[F,G,...],C...}), and a collider [c] (currently in node S) going in a direction "/" that will (at some point in time) overlap with the subnodes D[O], E[T,P], C[L, J] in that order. This is already nice because instead of checking for collision against all the objects in all nodes I only check the ones that are in those specific nodes that will at some point overlap/collide with the moving object [c]. Now, what I would like to have is the hability to discriminate the nodes that [c] will never reach because some obstacle in a closer node will prevent [c] touch them. ([o3] at C[J] for example) So I said: If an obstacle is found in the closest node, then I stop looking for collisions in the remaining "potential-overlaping" nodes, and voila. But this doesn''t work. There are some cases when I have the closest obstacle in a node that isn''t the closest node, so the aproach above fails. How would I go to limit the number of nodes I check when using a quadtree for space partitioning? Any clue? Thanks.

Share this post


Link to post
Share on other sites
There are some cases when I have the closest obstacle in a node that isn''t the closest node, so the aproach above fails.

how can that be? surely, you must take the bounding rectangle of the object, and add a reference of the object in every leaf nodes it covers. else, if you just pass the position of the object to the AABB tree, it''s gonna fail. you just have to be careful not to test an object more than once, which can be easily done (a global test counter you increment, and when you test an object, you store the current test counter value in the object, store tested objects in a bucket, ...).

Share this post


Link to post
Share on other sites
If you just want to find the nearest obstacle, you can perform a Nearest Neighbour Search using your quad tree, which is fairly efficient. If, however, you're just looking for a way to prune nodes from the list of nodes to check, then I'm afraid you're going to have to at least check them in sequence, starting with the first node that the trajectory intersects. At any time the trajectory is blocked by an object, you can stop checking. If the trajectory is not stopped by an object in a given node, then you need to check the next node along.

One optimisation you might consider if you have multiple dynamic objects that can collide is to add timings to entry points for nodes along their respective trajectories. Then, you need only check for collisions in nodes that have at least two objects (at least one object must be dynamic) and ONLY if the time windows of occupancy within that node overlap.

Cheers,

Timkin

[edited by - Timkin on March 28, 2004 7:55:40 PM]

Share this post


Link to post
Share on other sites
For the object that you are testing collision for check the 8 nodes around it for other objects. Build a list of those objects and these are the ones you test for collision with

Share this post


Link to post
Share on other sites