The Next Week: We can use std::nth_element instead of std::sort for more efficient BVH Construction

[DeltaPavonis]

In Section 3: Bounding Volume Hierarchies of "Ray Tracing: The Next Week", the given approach for splitting BVH volumes is as follows (emphasis mine):

I’ll choose the middle ground, and at each node split the list along one axis. I’ll go for simplicity:

1. randomly choose an axis
2. sort the primitives (using std::sort)
3. put half in each subtree

and the general code is

std::sort(objects.begin() + start, objects.begin() + end, comparator);

auto mid = start + object_span/2;
left = make_shared<bvh_node>(objects, start, mid);
right = make_shared<bvh_node>(objects, mid, end);

However, if the goal is just to split objects[start..end) into a smaller and larger half, we can use the more-efficient standard library algorithm std::nth_element, which runs in linear time on average, rather than the linearithmic time complexity of std::sort. The modified code would be

auto mid = start + object_span/2;
std::nth_element(objects.begin() + start, objects.begin() + mid, objects.begin() + end);

left = make_shared<bvh_node>(objects, start, mid);
right = make_shared<bvh_node>(objects, mid, end);

Conceptually, what std::nth_element(objects.begin() + start, objects.begin() + mid, objects.begin() + end); does is it rearranges elements in the range from objects.begin() + start to objects.begin() + end (excluding the end, as usual) to ensure that objects.begin() + mid will end up with the value that it would have had if we just sorted the range, and that all elements occurring before objects.begin() + mid are not greater than it. This is exactly what we want.

Admittedly, any actual performance gain from this is probably very small, unless an immense amount of objects are being rendered (I've tested it on my machine with no noticeable differences). However, I think it's a good use of the C++ standard algorithms library, and it doesn't spend time doing what doesn't need to be done.

[hollasch]

Very nice proposal, by the way. I'd never heard of this function (algorithm) — it seems tailor fit for our purposes.