c++ - Coarse Collision Detection in highly dynamic environment

I'm currently working a 3D space game with A LOT of dynamic objects that are all moving (there is pretty much no static environment). I have the collision detection and resolution working just fine, but I am now trying to optimize the collision detection (which is currently O(N²) -- linear search). I thought about multiple options, a bounding volume hierarchy, a Binary Spatial Partitioning tree, an Octree or a Grid. I however need some help with deciding what's best for my situation. A grid seems unfeasible simply due to the space requirements and cache coherence problems.

Since everything is so dynamic however, it seems to be that trees aren't ideal either, since they would have to be completely rebuilt every frame. I must admit I never implemented a physics engine that required spatial partitioning, do I indeed need to rebuild the tree every frame (assuming that everything is constantly moving) or can I update the trees after integrating?

Advice is much appreciated - to give some more background: You're flying a space ship in an asteroid field, and there are lots and lots of asteroids and some enemy ships, all of which shoot bullets.

EDIT: I came across the "Sweep an Prune" algorithm, which seems like the right thing for my purposes. It appears like the right mixture of fast building of the data structures involved and detailed enough partitioning. This is the best resource I can find.

If anyone has any suggestions whether or not I'm going in the right direction, please let me know.

Answer

I unfortunatelly now don't have time to read about that SAP algorithm, but what I have read few months ago (but I don't know, if it's suitable for your problem, it's much more suitable for points - not objects):

You can use some special case of kd-Tree - for example octree - which uses half partitioning in each axis (in article I have read, they were using quarter partitioning - each axis is split to 4 peaces). You use dynamic version of it.

First you build your structure at the beginning. This means, you split space into kd-Tree. Leaf of tree should have some limited number of objects (for our example let's take 64). Each node knows of course how many objects is in it.

When you update positions of objects, you transfer them also in structures nodes. After that, you update whole structure according to these rules:

1) When inner node has less then limited number of points (sum of its leafs is less then 64), then you merge leafs and inner node becomes leaf.

2) When some leaf has more then 64 objects, you split this node.

If you want, I can try to find that article - when I will have some time.