space partitioning algorithm speed
===

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.