How can I create a bounding volume hierarchy for constantly moving objects?

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

I'd like to add some practical perspective to this.

Let me preface that I'm operating on limited information here:

• I don't know how many objects you are dealing with.
• I don't know what exactly your acceleration structure is used for. Frustum culling? Ray tracing? Collision detection between objects in the BVH?

Going forward I'm going to assume you are talking about frustum culling a few thousand objects.

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 argue that if you have to visit every object every frame in order to calculate a BVH, culling them directly and without a BVH is actually faster. This of course depends on your frustum culling implementation. The bounding volumes of all objects should be stored contiguously in memory. This results in more efficient CPU cache utilization and allows for further optimization using SIMD instructions. DICE has a whole presentation on this subject: Culling the Battlefield: Data Oriented Design in Practice
The presentation also mentions speeding culling up even more, using a simple grid.

Since I assume most 3D/simulation/game code bases already have some kind of BVH class and I don't know how critical it is for you to get the BEST culling performance, I'd like to present some arguments for sticking with a BVH:

Depending on what method you use, constructing a BVH can be fast and simple.

My current implementation of a binary BVH (each node can only have zero or two children and each leaf node only stores one item) that is designed for quick construction takes around 0.18ms for 1137 objects on a single thread of an i7-5960X @ 3.89GHz. I'm sure it can be faster. Construction is performed without reallocating memory in the process (this doubled the construction performance).

While SAH might generate the best BVH, it takes a long time. SAH is good for things you can precompute, like collision meshes. At runtime you can then put the collision meshes into a BVH that is more suited for real-time construction.

A fast and simple BVH construction approach (the one I'm using currently) is to sort all objects on an axis (for example the parent AABB's longest axis) and split the collection in the middle.

To speed things up even more, calculate the node AABBs AFTER constructing the tree, by combining the two child node AABBs of a parent node. This avoids iterating through all objects (another 2x speedup). This however is only possible if your splitting criterion doesn't rely on the parent's AABB.