Improvements to BVH

[jaxry]

The heart of any high-performance ray tracer lies in the acceleration structure for ray intersections. The construction and traversal of this acceleration structure has the biggest impact on performance and is the most important thing to optimize.

Currently, we using a SAH-based BVH as described in pbrt. We are traversing this BVH on the GPU naively based off ideas in pbrt. Both the construction and traversal of this BVH don't consider GPU architecture (memory bandwidth, ray coherence, etc), and GPU-specific designs contribute to around a 100% or 200% speedup in rendering time.

This tickets serves as a reference to recent papers, and will be updated on a regular basis. There are advantages and disadvantages to every design, and it remains an open question about which design is best suited for use in WebGL (versus CUDA or other GPU APIs).

• 2017 - Gayot et al. - GPU Ray Tracing using Irregular Grids
• 2017 - Ylitie et al. - Efficient Incoherent Ray Traversal on GPUs Through Compressed Wide BVHs
• 2018 - Gu et al. - Fast and Dynamic Construction of Bounding Volume Hierarchies based on Loose Octrees
• 2019 - Lin et al. - Dual-Split Trees

Does anyone have experience or input with recent developments towards gpu-tailored acceleration structures that might work well with the renderer?

[Usnul]

Heya, I thought you might be interested. I have 2 implementations of BVH in my engine https://github.com/Usnul/meep. The engine in MIT licensed, one BVH implementation is compact and another one is dynamic. Build times are pretty fast for both. The dynamic BVH implementation has refitting, so you can move things around, rotate, scale etc. My code is based on a bunch of slightly older papers. If you're interested - I could pull it out into a separate module so both projects can benefit from it.

[jaxry]

@Usnul, your work sounds interesting. A dynamic BVH is a really neat idea since it's a start for dynamic scenes, and that sounds like a road we'd like to explore eventually. At this point we're trying to optimize BVH traversal as much as possible for static scenes, so that's what I'd like to explore first.

Where in that engine is the BVH code located? Does this compact BVH implementation traverse particularly fast on the GPU? Is it based off any papers or is there somewhere I can learn more about it, aside from the code itself?

[Usnul]

hey @jaxry , the representation is based on an intel paper, i don't recall it off the top of my head, i kept poor notes at the time. The idea is probably the same as what you're doing, you basically allocate space for a perfectly balanced tree, and then just fill in the space, every node has a pre-determined location. It's "compact" in the sense that it's binary, but it can be quite wasteful if the BVH is poorly balanced. It's fast to build and is fast to traverse though. My implementation is CPU-side, so it uses uint8, and the like for compactness, on the GPU you have to be a bit more tricky due to GLSL type constraints and available data transfer formats (textures, i guess?).

The code for all BVH stuff is located here: https://github.com/Usnul/meep/tree/master/src/model/core/bvh2

The binary format BVH is here: https://github.com/Usnul/meep/blob/master/src/model/core/bvh2/binary/IndexedBinaryBVH.js

Just had another look, turns out I have two implementations of binary format for BVH, one is compact and the other one is fast. So if you're interested in the compact one, it's here: https://github.com/Usnul/meep/blob/master/src/model/core/bvh2/binary/BinaryBVH.js

Nothing revolutionary here, the code is pretty short too. It's been a number of years since I wrote that code, so it may take me a little time to recall details, but I'm here for any questions!