Eccentric Developments

Building Bounding Volume Hierarchies With Octrees

In the previous article I explained how the Bounding Volume Hierarchies (BVH) work and why they help speeding up ray-object intersections in a scene. At the end of the whole implementation, the path tracer I have been implementing, improved its speed significantly, but there was a catch...

The BVH building algorithm was, to put is simply, naïve; it divided the scene in halves recursively but disregarded any partition balancing.

This is not ideal, because it doesn't make any effort in order to reduce overlapping between the bounding boxes (BBs). Overlapping is undesirable as it will increase the amount of intersection tests that will have to be calculated.

A good BVH reduces the overlapping of BBs as much as possible, but building them is more complicated. There are multiple ways to build BVHs that approach the optimal structure, using sorting, surface heuristics and the one that I like to use which relies on octrees.

Now I know what you are thinking, "what is an octree?" An octree is a subdivision of 3D space in eight sectors, basically, a cube, composed of eight smaller cubes.

The octree is used to divide and group in sections the triangles in the scene, not dissimilar to being sorted using a bucket sort algorithm, and then use the octree nodes to determine the best space subdivision.

The high-level description of this way to build the BVH is as follows:

  1. Calculate the overall BB of the triangles in scope.
  2. If there are four or less triangles, create a leaf and assign the triangles to it, stop the algorithm. Otherwise, continue.
  3. Take the midpoint of the BB and clasify the triangles into each of the eight sections of the octree.
  4. Count the number of triangles in the following six categories: -x/+x, -y/+y, -z/+z.
  5. Calculate the difference between each -/+ categories, i.e. -x/+x = P, -y/+y = Q, -z/+z = R.
  6. Find the smaller number of the differences. As such as if for instance Q is the smaller of the three, it means that the y axis split offers the best balance for the space subdivision.
  7. Create a node for the current overall BB where the left and right children correspond to the -/+ parts of the selected axis.
  8. Populate the left and right children by grouping the triangles assigned to each and recusively calling Step 1.

For the path tracer, after this change is implemented, there is no other update that needs to be done to use this improved BVH. Also, this is not a performance critical part of the renderization process, so we can take some liberties on the algorithm implemented and don't worry too much about the performance.

The updated code is below

Results

The following numbers were taken using Safari 17.6, in a M1 MBA running macOS Sonoma (14.6.1) on Low Power Mode:

Method Result
Naïve 1520 ms
Octree 1388 ms
Performance increase: 8.6%

The octree method for building the BVH, offers around 8% better performance against the naïve method. This doesn't look like much, but you have to keep in mind that the scene used so far offers the best case scenario for the naïve method; the objects are grouped around the middle of the scene and they where added to the scene array in a controlled way, in other words, if you pick two contiguoues (from the scene array) triangles, for example: 255 and 256, the odds of they being right next to each other in the scene space, is very high.

Having said that, getting any performance increase is great. And if the scene is esparce, it will offer even better gains. There are other methods to build this, that I might explore in the future.

Closing

Now I am in a bit of a bind, the JavaScript implemtation I've been developing in this series is based in Light (it needs a good README), which is another path tracer I've been working on and off for a long time. The problem is that writting this path tracer in JavaScript is not as fun as I expected, there are some very interesting aspects to it, for example WASM+SIMD is great, but the JavaScript language itself doesn't lend itself to speed optimizations without lots of effort and (very) ugly code.

For this reason, next articles on path tracing will be based on Light, that way I can focus on a single project and spend more time working with WASM. If things do not work as expected I'll go back to the JavaScript path tracer.

Enrique CR - 2024-09-15