# Ray-tracing with Bounding Volume Hierarchies

When naively raytracing (with triangle primitives), for n rays and m triangles there are mn intersection tests, as every ray must check for intersection with every triangle in the scene (ignoring triangle culling).

I will be making a binary tree as these are by far the most common, but there’s nothing stopping you from making a tree of higher degree.

A non-ideal case of a sphere hierarchy, and a *really* non-ideal case.

##### Constructing the BVH

I’ll be starting with a 3D model imported from a ‘.obj’ file, a triangle mesh represented as an array of triangles. In my implementation I only use vertex information, no normals or UVs, as they’re unrelated to the BVH, and implementing them is it’s own task.

As we’re making a binary BVH, at every level we split the group of triangles into two groups. This splitting should be done so that each group is as spatially distinct as possible from the other. My quick and dirty solution is to calculate the variance in position of all the triangles in each dimension, relative to the centre of the BV of the group. In the process I also calculate the means position of the triangles. Then I find the dimension with the greatest variance as split along that axis, using the previously found mean position to get the mean along the splitting axis, defining the axis aligned plane that splits the triangles into two groups.

Welford’s method for computing variance.

This approach is far from ideal, and has many cases with pretty awful BV choices for the subgroups. But it works, and improvement on it is left as an exercise for the reader :).

Once we have our two subgroups, we calculate the mean position of each subgroup, and find the minimum radius of each sphere that completely covers each subgroup, by iterating over each vertex in the subgroup and calculating the distance to the mean position. Once done, we have two new BVs for our subgroups, and we can recurse downwards again!

A major choice during the BVH construction is when to stop recursing down. We might naively keep going until we get a subgroup with a single element that can’t be split any further, but this only adds a rather unnecessary check when we should just be intersection testing against the triangle. With such small groups of triangles the benefits of a BVH can be quickly outweighed by it’s overhead.

This is a similar way of thinking to the way that the most efficient sorting algorithms are implemented, with quicksort at a high level for it’s asymptotic O(nlogn) running time, then when the sizes of the arrays to be sorted are reduced to a low enough number switching to insertion sort. Even though insertion sort has an O(n^2) running time, it can be quicker than quicksort on these small array slices due to quicksort’s overhead.

The approach I used was to just pick a minimum number of triangles that each group could have, and if a subgroup had that or below (due to splitting a group of size just above the minimum) then it wouldn’t recursively split and would instead store the triangles in it’s group.

##### Rendering with the BVH

As stated before, we test for intersection with the BV, and if that is true then we recursively test for intersection with it’s children.

The in-depth implementation of the BVH, along with a lot of extras, can be found here, along with a code repo here.

Thanks for reading, and I hope it’s been helpful! :)