Tuesday, March 8, 2016
BVH builds
In the new mini-book I cover BVHs. In the book I always went for simple conceptual code figuring people can speed things up later. I have what must be close to a minimum BVH build, but it just gets us the log(N). It picks a random axis, splits in the middle of the list:
I could have split geometrically and done a O(N) sweep and the code might have been as small, but I wanted to set people up for a top-down surface-area heuristic (SAH) build. As discussed by Aila, Karras, and Laine in 2013 (great paper--- download it here) we don't fully understand why lazy SAH builds work so well. But let's just be grateful. So what IS the most compact top down build? I am going to write one to be supplemental for the book and just sweeping on those qsorts above is what appears best to me, but I invite pointers to good practice.
instead of a full sort, I've used std::nth_element, std::partition -- which can be slightly faster but also conveys what the splitting axis is doing.
ReplyDeletei can't find the reference but a performance trick is to sort along the x,y,z axis once and re-use the results during top-down traversal.
Orthogonal to nth_element/partition/qsort, you could pass a lambda that captures the axis, removing the need for if/else if/else.
ReplyDeleteYou don't seem to be storing the axis in the BVH, so you might consider randomizing which box assigned to left or right (or, equivalently, randomly sorting primitives in ascending/descending order). That way you won't get pathologically bad results when casting a ray with a direction in the wrong octant.
I was not aware of those std:: features. Good call!
ReplyDeleteWhy do you take random axis instead of longest one?
ReplyDeleteThe longest axis isn't necessarily the best one for splitting object lists, because it does not necessarily produce more compact children. Imagine triangulating a long axis-aligned cylinder and then creating a BVH.
ReplyDeleteLongest axis is often good, but the adversarial cases are nasty as friedlinguini points out. But the real reason I did that was just a minimally simple version.
ReplyDelete