   Partitioning for Collision/Culling
  Hello Friends,I am trying to decide which algorithm I should use for partitioning the game world. My game is 3D and has dynamic objects. I was thinking about maybe an Octree would be good, but come to think of it, it has to calculate EVERY frame because of the dynamic objects. So, my question is this. What would be the best space partitioning for a 3D game for collision and culling that has dynamic objects?Thanks in advanced.   
  You are right. Traditional spatial partition scemes are not very useful for dynamic entities.For collision detection take a look at Sweep And Prune (SAP).For culling I dont know. On my current project we just cull all the dynamic enteties witout any spatial subdivision. We do not have a lot of dynamic stuff.[Edited by - ApLars on June 6, 2010 2:15:11 PM];  Thanks, I will looking into SAP.Also, my game is going to be a big open world type of game, with a lot of dynamic objects, so I need a way to partition the game world to know which node I am in and only check that node and neighbor nodes for collision and culling.There has to be a way for dynamic objects.   ;  Partitioning is obviously a very important part of your physics engine. It's just an additional abstraction model, like Axis Aligned Bounding Box. Even when you deal with dynamic entities, it is always better to group objects by collision possibility. For instance, lets say you have 100 objects in the scene. If you checked every single pair, then you would have 100(100-1)/2, which is 4950 checks per frame. If you break them into groups of 10 on average, you would have 10*10*9/2 which is 450 checks. This basically means that you just saved yourself 4500 collision checks per frame which this space partitioning algorithm. Now, even if ALL of those objects are dynamic and you have to recheck all of them every frame, you would have yourself 100 more checks which are most likely to be less expensive than the checks for collision detection (depends on the algorithm though, but you will most often find an increase).As for the actual partitioning algorithms, it depends on your game and the setting in the game. I really like Octrees myself, because they are very easy to implement and they scale well with the scene, but they do not often accurately represent the actual scenery. For example, if you had 2 rooms that are separate, but that are where most of the action is happening, and they happen to be in the same collision group, you would have alot of useless checks between them. In that case you could implement volume partitioning to encapsulate those rooms in their own boxes, thus rendering the scenery much more effective. I would personally just leave a place for a partitioning algorithm in your physics engine and then implement it once the performance boost is needed and once it is clear what the game is like.For collision algorithms Sweep and Prune is the way to go, just remember to use layers of abstraction, like AABBs or spheres, for complex and compound objects to make fake collisions less expensive.   ;  Thanks for your input so far.I would really like Octrees, but have to figure out an efficient way to use them for dynamic objects. Or, do I only use it for the static objects in the game? i.e. the game world. But what would I do for the dynamic objects then. Meaning the player, AI players, etc... I would really like to use one spatial partitioning system, but if it comes down to two of them so be it.Thanks again.   