Download
Introduction
In this article we will quickly review 3d space partitioning, offering explanation as to why the Bounding Volume Hierarchy has become increasingly popular in 3d space partitioning applications, such as 3d games and ray-tracing. Then we present a reusable, public domain licensed BVH implementation in C# which uses incremental tree refitting and rotations to quickly handle incremental updates, as described in [1. kopta].
In our example, the BVH is what allows the CPU to quickly determine which of the 40,000 asterois in the scene is clicked on by the user. When the mouse is clicked, a ray is cast into the scene from the camera, and instead of testing our ray against every one of the asteroids, we traverse the BVH enclosing volumes, performing only log2(N) comparisons to determine which asteroids could be clicked on, and only test those asteroids. In this case log2(40,000), or about 15 comparisons.
What is Space Partitioning?
Most 3d software, whether a 3d game, 3d modeler, or some other form of 3d tool, at some point or another will benefit from a space partitioning system. For the unitiated, space-partitioning is the term we use to talk about organizing objects that occupy volume. This is different from sorting-structures, which can only order objects which have no volume.
For example, it is easy to sort the numbers 1, 4, and 7 into ascending order. However, how would you sort the ranges 1-10, 1-5, 2-3, and 3-7?
Because ranges occupy volume, there is no simple 'ascending' order of them which is universally useful.
Space partitioning is a set of algorithms which organize volumes which can overlap each other in some or all dimensions. Rather than 'ordering' them, such as is done with sorting, space-partitioning divide and oragnize volumes of space. This enables quickly traversing the divided space to answer geometric queries. In the case of 3d space partitioning, this usually means quickly returning the 3d objects which touch a line, triangle, or sphere.
Dividing Space
One of the pivotal differences in space partitioning schemes, is how they divide space.
Many 3d space partitioning algorithms, such as octrees, kd-trees, and BSP-trees, slice 3d space with a flat 3d plane. The splitting plane creates two subvolumes, and objects are sorted into the subvolume they touch. This is efficient to search, but presents a challenge when objects overlap the split boundary.
Exclusive split-planes. In a precomputed BSP-tree, expensive pre-calculations are done to determine efficient splitting planes, and when triangles cross the plane, they are cut into smaller triangles at the boundary. Obviously, this makes moving geometry after the planes are calculated fairly expensive.
Non-exclusive split-planes. In dynamic applications of octrees or kd-trees, objects may be placed into all subvolumes they touch. This requires extra work when moving objects, and extra tests when traversing the space, to handle duplicate object occurances.
The BVH tackles this issue differently, because it does not use splitting planes. Instead a volume is subdivided by defining two potentially overlapping subvolumes. These volumes can be defined with any geometry, including spheres, elipsoids, bounding boxes, or axis-aligned bounding boxes. To make the splits efficient, contained objects are divided to two sets by minimizing the surface-area of the sub-volumes which contain the two sets, estimated by a surface-area-heuristic (SAH).
When used in a binary-fashion, as we do in our implementation, there are exactly two sub-volumes of each volume. Because the subvolumes are arbitrary enclosing volumes, traversing the BVH means checking both sub-volumes of any matching volume. However, this increased cost brings increased flexibilty. The sub-volumes may be very far apart, more efficiently dividing space, or they may overlap.
The ability for sub-volumes to overlap is the main reason the BVH can very efficiently handle dynamic updates. When objects only move a short distance, the only adjustment required is a very quick adjustment of the bounds of their enclosing volume(s). Even if those volumes overlap, the BVH will still function correctly, although at slightly reduced efficiency.
When changes introduce significant overlap, the BVH tree may need to be restructured -- meaning objects may need to be moved to a different place in the tree in order to make the volumes more efficient. Imagine our BVH tree of asteroids, and then imagine a single object moving through the asteroid field -- what we want, is for the moving object to "hop" through the volumes as it moves through space, rather than merely expanding it's initial volume to fill the entire space.
Our implementation performs this restructuring by using tree-rotations, similar to binary-tree-rotations. However, instead of using rotations to balance the tree, they are used to move objects between volumes to reduce the overall SAH cost, sometimes by unbalancing the tree. The method we use is described by Kopta, et. al. [1].
Instantiating the BVH
ssBVH<GO> is paramaterized by the "Game Object" type it holds (GO=Game Object). In order to handle any object type without introducing a type or interface dependence to your game objects, it requires adaptor interface, SSBVHNodeAdaptor<GO>. The source code contains an example adaptor implementation for SimpleScene scene manager objects. The Node adaptor is required to do a few things (a) ask for the object center of an object, (b) ask for the bounding-sphere radius of an object, and (c) maintain a mapping between a GameObject and the ssBVH leaf an object is currently in. If desired, the mapping from a GameObject to an ssBVHNode<GO> leaf can be implemented a pointer from a GameObject to the ssBVHNode<GO> containingLeaf, or you may use an external mapping such as a hash table that maps your game objects to the containingLeaf.
public interface SSBVHNodeAdaptor<GO> {
ssBVH<GO> BVH { get; }
void setBVH(ssBVH<GO> bvh);
Vector3 objectpos(GO obj);
float radius(GO obj);
void mapObjectToBVHLeaf(GO obj, ssBVHNode<GO> leaf);
void unmapObject(GO obj);
void checkMap(GO obj);
ssBVHNode<GO> getLeaf(GO obj);
}
Once an adaptor has been implemented for your object type, ssBVH may be instantiated. You may either provide a list of objects to add in bulk (which is faster), or you may add them one at a time. You also need to hook your scene to call ssBVH<GO>.addObject(GO obj) and ssBVH<GO>.removeObject(GO obj) when objects are added or removed from the scene. Here is an example of how the BVH is instantiated with SimpleScene SSObject.
if (addObjectInBulk) {
worldBVH = new ssBVH<SSObject>(new SSObjectBVHNodeAdaptor(),mainScene.Objects);
} else {
worldBVH = new ssBVH<SSObject>(new SSObjectBVHNodeAdaptor(), new List<SSObject>());
mainScene.objects.ForEach( o => worldBVH.addObject(o) );
}
Handling Dynamic Updates
If you wish the BVH to handle dynamic updates, then each time your object moves, you call the change notify function on it's bvh leaf : ssBVHNode<GO>.refit_ObjectChanged(ssBVHNodeAdaptor<GO> adaptor, GO obj), this quickly and conservatively expands the BVH to handle the node-update, at the cost of efficiency. An additional function is provided ssBVH<GO>.optimize(), which attempts to perform tree-rotations to optimize the BVH, in the case where objects have moved far enough to create inefficient volume overlaps. While optimze() is very fast, it is more efficient to make many changes and then perform a single optimize, than it is to optimize after every object update. For example, in a game-loop, you would call optimize() only once per frame. Below is a sample of a game-like update loop, including the BVH optimize.
void OnUpdateFrame(FrameEventArgs e) {
float fElapsedTimeMS = (float)(e.Time * 1000.0);
mainScene.Update(fElapsedTimeMS);
worldBVH.optimize();
}
Performing BVH accelerated queries
Now that the BVH is built, and optimized for any updates, it can accelerate queries into the 3d volume. For example, to find objects potentially hit by a ray, ssBVH<GO>.traverse(SSRay) returns a list of ssBVHNode<GO> intersecting the ray, which in turn contain objects which can be considered for intersection. When there are a large number of objects, this is much more efficient than testing all objects in a scene. For example, in one test with 80k objects, traverseRay typically hit only 100 BVH nodes, resulting in 800-times fewer hit-tests.
List<ssBVHNode<GO>> hits = gameMode.worldBVH.traverse(ray);
Other overloads of ssBVH<GO>.traverse() provide intersection with an Axis Aligned Bounding Box (AABB), as well as a functional traverse where any match-test delegate function may be provided.
Other useful tools
Example code is also provided with SimpleScene that renders out BVH nodes, optionally highlighting a set of them. For example, this code projects a ray, then highlights every BVH node touched by the ray, using the supplied SSBVHRender class.
var hits = gameMode.worldBVH.traverseRay(ray);
gameMode.worldBVH_visual.highlightNodes.Clear();
Console.WriteLine("click hit {0} BVH nodes", hits.Count);
foreach ( var hit in hits ) {
gameMode.worldBVH_visual.highlightNodes.Add(hit);
}
Notes and Future Work
ssBVH handles more than one GO object per leaf (LEAF_OBJ_MAX), however, dynamic updates only work efficiently if the BVH has only one node per leaf. Future work will include code to split and merge leaf nodes, to allow tree-restructuring to work effectively when each leaf node holds multiple objects.
References
