space partitioning algorithm speed

Question

I am developing a 3D Game Engine as a project. I would like to use space partitioning algorithms for each triangle/polygon in my scene to efficiently detect collisions. I just want to know (before I start programming the specifics) how fast is a typical space partitioning algorithm in modern computer games? I have dynamical objects so I am thinking that I might have to repartition my scene every frame. Is that possible and still achieve a reasonable frame rate? It would be very much appreciated if the answer could include data (e.g. the FPS, number of polygons, etc.). If that is too much trouble, just tell me if it is plausible to repartition every frame.

Any help would be appreciated.

Answer 1

I would first suggest reading the chapter on Broad-Phase Collision Detection with CUDA. It goes into comparison of different broad phase collision algorithms. Your performance depends on a few key variables. The first variable is whether or not your algorithm is implemented using GPU acceleration. The previously cited article contains some benchmarks on framerate vs. number of objects. At the very least it should give you a good idea of what is achievable.

If you don’t plan on GPU acceleration, sweep and prune is one of the easiest to implement. I don’t know the exact figures, but it performs well when there are few objects and your objects don’t vary too much between frames. In this situation, you have O(n) performance. This is a good one to start with as a baseline, because it is trivial to implement.

If you are really getting serious, I recommend the book Real-Time Collision Detection. I used this one when doing research on collision detection methods. It was a great resource.