Thursday, March 10, 2016

A simple SAH BVH build

Here is a cut at a BVH build that cuts along the longest axis using the surface-area-heuristic (SAH).   The SAH minimizes:

SUM_left_right number_of_children_in_subtree*surface_area_of_bounding_box_of_subtree

This has been shown by many people to work shockingly well.

Here's my build code and it works ok.   I still have to sort because I need to sweep along an axis.   Is it worth it to tree each of three axes instead of longest?   Maybe.... bundles of long objects would be the adversarial case for the code below.


friedlinguini said...

"Worth it" isn't really answerable without more information, since you're comparing the up-front cost of creation against an arbitrary number of ray intersections. You might also consider simply rotating among the three axes.

By the way, you have some memory leaks there. Ideally you'd probably want to reuse the buffers globally (or at least per-thread), but std::vectors would be convenient if you're not worried about heap allocation overhead.

Peter Shirley said...

Good call on the memory leak. By worth it I really just mean worth investing developer (i.e., my) time in. Rotating would certainly make it more robust for adversarial cases like bundles of sticks.