Computer Graphics

Hierarchical Bounding Volume Tree with High-performance Concurrency

At DigiPen I have made several computer graphics projects for various classes. My latest project is a high-performance hierarchical bounding volume tree, for culling. I went beyond the specifications and made a concurrent implementation, along with a high-complexity scene to test it.

The following is a video with spoken audio explaining the project:

The scene is partitioned into axis-aligned bounding-boxes, each containing more objects. This process continues recursively until there are no objects to categorize. Tree construction is generally considered slow, so moving objects are updated in the tree individually. However, this update method becomes too slow for a scene where most or all of the objects are moving, which I demonstrated by adding a kinetic mode to the scene, which moves every object continuously. As a result, I decided to optimize the construction algorithm significantly, by-passing the original problem.

My primary interest was in making the construction concurrent, because the method lent it self naturally to independent tasks (this type of problem is called embarrassingly parallel). After partitioning each data set into two parts, each part is recursively constructed in parallel. Because tree node count increases exponentially with depth, it's not practical to continue this concurrency beyond a certain depth, or CPU cores become overloaded with work. Related, parallel construction with too few elements results in wasted work because the CPU core spends more time preparing to execute concurrently than it does simply executing.

Both of these parameters were adjusted via automatic profiling. The program can be run in profiling mode, which tweaks the settings across a range of values, then calculates which combination resulted in the highest performance. (The process takes around 20 minutes overall.)

Further improvements could be made by using the existing tree structure as a heuristic. Currently, the tree is constructed as if it were new each frame, but assuming objects only move slightly the construction algorithm can approximate a best solution.

Overall, the concurrent method increased performance by about 60%.

Shader Programming with GLSL

I am also comfortable with programming custom shaders for object materials. The following is a silent video showcasing the following in series: standard texture and normal mapping with reflection and refraction mapping, and shadow mapping.