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?

EDIT: Removed details of post due to misunderstanding/misreading of the original post! Apologies!

Regards,
Sharky


---
< Sharky's Coding Corner >
< Coder @ Strangelite >
---

[edited by - Sharky on November 7, 2003 4:33:13 AM]

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

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

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.