Tuesday, March 12, 2019

Making your BVH faster

I am no expert in making BVHs fast so just use this blog post as a starting point.   But there are some things you can try if you want to speed things up.   All of them involve tradeoffs so test them rather than assume they are faster!  

1. Store the inverse ray direction with the ray.   The most popular ray-bounding box hit test assumes this (used in both the intel and nvidia ray tracers as far as I know):

Note that if ray direction were passed in you would have 6 divides rather than 6 adds.

2.  Do an early out in your ray traversal.   This is a trick used in many BVHs but not the one I have in the ray tracing minibook series.   Martin Lambers suggested this version to me which is not only faster, it is cleaner code.

3. Build using the surface area heuristic (SAH).   This is a greedy algorithm that minimizes the sum of the areas of the bounding boxes in the level being built.    I based mine on the pseudocode in this old paper I did with Ingo Wald and Solomon Boulos.    I used simple arrays for the sets and the quicksort from wikipedia for the sort.