15,112,662 members
Articles / Multimedia / OpenGL
Article
Posted 5 Nov 2014

45K views
21 bookmarked

# Dynamic Bounding Volume Hiearchy in C#

Rate me:
An overview and C# implementation of 3d space partitioning using a BVH (bounding volume hierarchy), with dynamic updates via refitting and tree-rotations.

### 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 object type it holds. In order to handle any object type without introducing a type or interface dependence, it does this by means of an adaptor interface, `SSBVHNodeAdaptor<GO>`. The source code contains an example adaptor implementation for SimpleScene scene manager objects. This Node adaptor is used to ask for the position and bounding-sphere radius of an object, as well as maintain the mapping from a node-object to a BVH-leaf. If desired, this mapping can be handled by directly adding a pointer from your objects to `ssBVHNode<GO>`, or as in the example, you may use an external mapping such as a hash table.

C#
```public interface SSBVHNodeAdaptor<GO> {
ssBVH<GO> BVH { get; }
void setBVH(ssBVH<GO> bvh);

Vector3 objectpos(GO obj);   // read the object position of a GO object

void mapObjectToBVHLeaf(GO obj, ssBVHNode<GO> leaf);   // map a GO to a BVH leaf
void unmapObject(GO obj);                              // unmap a GO from it's BVH leaf

void checkMap(GO obj);                                 // assert that there is leaf mapping
ssBVHNode<GO> getLeaf(GO obj);                         // retrieve the leaf mapping
}
```

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`.

C#
```if (addObjectInBulk) {
// full BVH build
} else {
// incremental BVH build...
worldBVH = new ssBVH<SSObject>(new SSObjectBVHNodeAdaptor(), new List<SSObject>());
}```

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.

C#
```void OnUpdateFrame(FrameEventArgs e) {
float fElapsedTimeMS = (float)(e.Time * 1000.0);

// update 3d objects..

mainScene.Update(fElapsedTimeMS);

// restructure the BVH.. only once per frame
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.

C#
```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.

C#
```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 ) {
}
```

### 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.

## Share

 United States
David Jeske is an Entrepreneur and Computer Programmer, currently living in San Francisco, California.

He earned his B.S. Computer Engineering at University of Illnois at Champaign/Urbana (UIUC), and has worked at several Silicon Valley companies, including Google, Yahoo, eGroups.com, 3dfx, and Akklaim Entertainment. He has managed and architected extremely high-traffic websites, including Yahoo Groups and orkut.com, and has experience in a broad spectrum of technology areas including scalability, databases, drivers, system software, and 3d graphics.

 First Prev Next
 Can it handle rotations? nightrider133-Jun-16 0:51 nightrider13 3-Jun-16 0:51
 Re: Can it handle rotations? David Jeske15-Apr-17 8:06 David Jeske 15-Apr-17 8:06
 The optimization process will restructure the BVH so it never has to be rebuilt. That said, if you substantially change most of the nodes in the BVH, it may take less time to rebuild from scratch than to optimize it. What are you doing with the BVH? How to handle rotating objects depends on what you are doing with the BVH. One way to use a BVH is to have a coarse BVH at the scene level, which only contains object bounding boxes or spheres. Any time an object bounding box moves or changes, the BVH needs to be optimized and refit, but not fully rebuilt. Often a BVH is built for a local object mesh. This BVH exists in the object local coordinate space, so it is immune to object rotations in the world space. Object animation, however, requires moving polygons and re-optimizing the BVH. Ray queries which contact an object bounding box in the scene level BVH can be transformed into object local space and continued in the mesh BVH for precise mesh collisions.
 Great article! Possible bug... HomerJohnston24-Nov-14 20:00 HomerJohnston 24-Nov-14 20:00
 Re: Great article! Possible bug... David Jeske25-Nov-14 9:55 David Jeske 25-Nov-14 9:55
 Re: Great article! Possible bug... HomerJohnston25-Nov-14 18:49 HomerJohnston 25-Nov-14 18:49
 Re: Great article! Possible bug... David Jeske26-Nov-14 10:03 David Jeske 26-Nov-14 10:03
 Re: Great article! Possible bug... HomerJohnston4-Dec-14 20:10 HomerJohnston 4-Dec-14 20:10
 Last Visit: 31-Dec-99 19:00     Last Update: 27-Nov-21 5:22 Refresh 1