Sign in to follow this  
wild_pointer

Detecting collisions between large numbers of static objects

Recommended Posts

wild_pointer    291
Not sure if this belongs here or in game programming, sorry. I'm working on a toy terrain engine that's made up of thousands of cubes just like Minecraft. I put some basic collision detection in but it's really slow as I'm naively testing against hundreds of thousands of objects. I can implement a broadphase and I will have to eventually but I think a better first step would be to take advantage of the fact that nearly everything is static and further that I can very quickly index my cubes by position.

My idea is to only add and remove the static cubes from the physics simulation depending on if any dynamic objects are nearby (the player,. mostly). This way I'm not testing against them and I'm also not paying to keep all those objects in memory. This wouldn't be hard to do so I'm mainly asking because I'm sure not the first person to deal with this kind of problem and I want to know if this is the "right" way. Is there some reference implementation anyone knows of I could borrow from? I looked around a little and couldn't find any physics engines that seemed to do this but I'm not sure if that's because my approach is stupid or maybe my situation is relatively unique (though I imagine anyone doing collision with arbitrary terrain would run into the same thing).

Thanks!

Share this post


Link to post
Share on other sites
SimonForsman    7642
[quote name='wild_pointer' timestamp='1305496502' post='4811221']
Not sure if this belongs here or in game programming, sorry. I'm working on a toy terrain engine that's made up of thousands of cubes just like Minecraft. I put some basic collision detection in but it's really slow as I'm naively testing against hundreds of thousands of objects. I can implement a broadphase and I will have to eventually but I think a better first step would be to take advantage of the fact that nearly everything is static and further that I can very quickly index my cubes by position.

My idea is to only add and remove the static cubes from the physics simulation depending on if any dynamic objects are nearby (the player,. mostly). This way I'm not testing against them and I'm also not paying to keep all those objects in memory. This wouldn't be hard to do so I'm mainly asking because I'm sure not the first person to deal with this kind of problem and I want to know if this is the "right" way. Is there some reference implementation anyone knows of I could borrow from? I looked around a little and couldn't find any physics engines that seemed to do this but I'm not sure if that's because my approach is stupid or maybe my situation is relatively unique (though I imagine anyone doing collision with arbitrary terrain would run into the same thing).

Thanks!
[/quote]

you should be able to deactivate any obstructed cubes, if a cube is removed all cubes it touched should become "active", if a cube is added you can check if any of the cubes it touches is completely covered (a cube would be completely covered if there are cubes on all sides of it) , This would basically mean that the majority of the cubes in your world won't be a part of your physics simulation.

Its also a good idea to use sphere to sphere or AABB collision tests as an early test due to their low costs.

If you can access your cubes based on their position (If you store them in a 3D array or similar structure it should be trivial to do so) then its also very easy to limit any test to cubes in a specific area.

Share this post


Link to post
Share on other sites
wild_pointer    291
[quote name='SimonForsman' timestamp='1305497695' post='4811232']
you should be able to deactivate any obstructed cubes, if a cube is removed all cubes it touched should become "active", if a cube is added you can check if any of the cubes it touches is completely covered (a cube would be completely covered if there are cubes on all sides of it) , This would basically mean that the majority of the cubes in your world won't be a part of your physics simulation.

Its also a good idea to use sphere to sphere or AABB collision tests as an early test due to their low costs.

If you can access your cubes based on their position (If you store them in a 3D array or similar structure it should be trivial to do so) then its also very easy to limit any test to cubes in a specific area.
[/quote]


I already only add visible blocks to the physics system. My question is more about only keeping the static objects nearby to dynamic ones in the simulation and if this is a usual way of dealing with lots of terrain (And if so how is there some generic way that my collision system could handle this for me? Otherwise I'd handle adding and removing objects in the game code).

Share this post


Link to post
Share on other sites
Waterlimon    4398
If you have objects like in minecraft (only take up a few cubic meters of space) you could simply take the few cubes it might touch. If you have small item-like objects, you just need to get the cubes touching the grid point the item is in.


If you have larger objects you could divide the world in chunks and use only the chunks it might be in, though i think the most efficient way might be to use some kind of a tree, wich shouldnt be hard on a voxel based map...

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this