___________ ____________ ___________ ____________ 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 |
|___________|____________|___________|____________|
Collision Detection: QuadTree performance.
Author
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:
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, ...).
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, ...).
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]
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]
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
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
