I'd like to be able to render a large population of small independently moving objects in real time. They may move in a swarm-like manner, but their relative positions will not be coherent - their position may change arbitrarily within a swarm and swarms may break up and reform at any point.

What approach to building a bounding volume hierarchy would best suit this situation? Is there a way to maintain a hierarchy which is sub-optimal but good enough, that only requires a partial update each frame? Or is there a way of building a hierarchy from scratch each frame that is fast enough for smooth animation?

The number of objects will be too large to render without a hierarchy, but for the same reason I expect building the hierarchy to be time consuming.

I'd like to be able to render a large population of small independently moving objects in real time. They may move in a swarm-like manner, but their relative positions will not be coherent - their position may change arbitrarily within a swarm and swarms may break up and reform at any point.

What approach to building a bounding volume hierarchy would best suit this situation? Is there a way to maintain a hierarchy which is sub-optimal but good enough, that only requires a partial update each frame? Or is there a way of building a hierarchy from scratch each frame that is fast enough for smooth animation?

The number of objects will be too large to render without a hierarchy, but for the same reason I expect building the hierarchy to be time consuming.

Following the comment from John Calsbeek, if my focus on bounding volume hierarchies is misguided, and there is a better space partitioning approach for this situation, please answer accordingly. I'm looking for something that can deal with what I describe, including anything I haven't thought of.