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.

  • 1
    $\begingroup$ Are you intentionally restricting the question to bounding volume hierarchies, or are you open to other forms of spatial partitioning? $\endgroup$ – John Calsbeek Aug 9 '15 at 23:19
  • 1
    $\begingroup$ @JohnCalsbeek I've edited to clarify - thanks for pointing out my inadvertent restriction. $\endgroup$ – trichoplax Aug 9 '15 at 23:32

Consider using spatial hashing, especially if your objects are similarly sized.

Basically, divide your world into uniformly-sized grid cells (2D and 3D are both valid possibilities depending on the amount of vertical motion). Each update, assign your object to each bin that it overlaps—if the cells are decently sized relative to the objects, most objects should end up in a single bin.

Each bin is inserted into a hash table, with the key being the coordinates of the bin. (You can also think of it as a hash table with multiple values for the same key, and inserting an object once for every cell that it overlaps.)

There's no hierarchy to rebuild in this scheme, which makes it well suited for dynamic scenes. You can still test the cell's dimensions against the frustum or against occluders at a coarse level and discard many objects at once. Also, it's easier to manage this structure incrementally—you can keep the hash table the same from frame to frame and only move objects from one bin to another when they cross the boundary of a cell.


You could try to simply make the bounding volumes a bit larger than necessary so that the objects don't cross their boundaries on every move but then again, you would have to rebuild the structure now-and-then anyway.

Or, there is Bounding interval hierarchy which tries to address precisely this scenario.

Or, the paper by Ingo Wald, Solomon Boulos and Peter Shirley titled Ray Tracing Deformable Scenes Using Dynamic Bounding Volume Hierarchies might be of interest.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.