Archived

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

generating BSPs in real time for collision detection

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

Lets say, we have a lot of moving spheres in a 3d space, and we want to check if they collide each other. If I do a raw loop checking every sphere with all the other spheres, the speeds decresases exponentially when the number of spheres increase. I''ve read that there are ways to partition the space in real time so you can have most of the spheres separated by planes, so to before checking a sphere, we traverse the generated BSP tree from were the sphere is... But I haven''t found any detailed info, or faqs that explain this... so, for large environments with a huge amount of elements (spheres), how can I speed up the checks? (BSPs, octrees?) help?

Share this post


Link to post
Share on other sites
BSP trees would be bad. there are other, faster ways. John Ratcliff proposed a dynamic sphere tree (buggy though) approach, available in Graphics Gems 2 (you have to buy the quite expensive book though). There are kd-trees, octrees, voxels, but a simple and relatively efficient algo is to sort objects along several axes (2 axes, x and z, or 3 axes (x, y, z), or just one), trasverse the list on each axes and build up pairs of potentially colliding objects by checking if the objects span on each axis overlap. Then merge the lists, and it should give you a list of pairs of objects to test.

you can also use a static data structure, like a static bsp, and store objects that belong to bsp leaves, and test objects occupying the same leaves.

Share this post


Link to post
Share on other sites
if all the spheres fall within one convex hall.. meaning an end leaf... then you will def run into the problem described above. If, however, your spheres where runing between rooms, then testing collisions relative to each sphere would be bsp quick. +)

You could do something like a dynamic collision speed thing. =P
ie.
Say you have 50 spheres in a room. So your looping through all the spheres. You could have a performance timer that watches frame rates related to collision and if things begin to fall below an acceptable rate, you could take a splitter plane and drop it in the middle of the room ( or in a more stratigic place ) and tie it to the bsp essentially making two rooms with an invisible wall. this could continue to furthur subdivide the room. As frame rates increase, you can remove more of the ''walls''.

The other approach is to figure out how physics engines handle a great number of objects without much flicker in frame rate. tokamak?

Hope this helps,
Andy

Share this post


Link to post
Share on other sites


the environment I was planning to create is basically an asteroids field with lots and lots of spheres moving arround, I can render quite a lof of asteroids, but when I enable collisions the fps drops a lot. Since the collision detection algorythm is pretty simple, I figure that I''m losing most of the CPU cycles in the sphere-sphere test interation loop

At first, I was thinking in building a BSP on the fly... it''s not that hard, just take the first two spheres and set the first plane at half distance between them, then check the rest of the spheres and place them on their side of the plane, and repeat with every leaf... but I bumped in some hard to solve inconsistencies (when spheres are cut by a plane)

Oliii: the axes sorting looks pretty interesting and easy to do, I might go this way, thanks




Share this post


Link to post
Share on other sites
I''m having exactly the same problem as you do. I''m thinking of implementing a proximity list. The only problem is updating this list. That would give a framerate drop i suspect but i still have to test this out.

Share this post


Link to post
Share on other sites