Is BVH faster than the octree/kd-tree for raytracing the objects on a GPU?

Question

Apparently most people use BVHs in their raytracers. The ray-AABB intersection code is very fast and and the BVHs also compresses empty space efficiently, working even with infinitely large objects, while octrees (a more uniform subtype of BVH) apparently have a problems with compressing large open worlds - no way you can insert into a finite grid that huge mountain in the distance, without making the grid cells overly large. So what are the best practices?

Answer 1

First, it is important to observe that there are basically two different "classes" of methods for building accelerations structures for ray tracing: 1) space subdivision methods (e.g. BSP, kD-Tree, Octree, etc.); and 2) object subdivision methods (e.g. BVH). While space subdivison methods work by recursively subdividing the space with planes, without sticking to the geometry embedded into that space, object subdivison methods work by subdividing the geometry recursively into smaller and smaller parts, wrapping each part with a, usually tight, volume. More on the basics of space and object subdivision that can be found in the PBRT v3 online book.

Each method (space or object sudivision) has its own pros and cons. In the case of space subdivision methods, since the subspaces do not overlap, we can usually traverse the structure in front-to-back, or back-to-front, order more easily. When a ray is traversing such structure, as soon as it hits a surface, we can stop the traversal. This usually leads to faster traversal schemes. Several software renderers take advantage of the traversal efficiency given by the space subdivision schemes. On the other hand, space subdivision schemes may be more intricate to implement (usually you have to tweak some epsilons) and may lead to deeper trees. Also, they do not like very much dynamic geometry. If the geometry encoded into a space subdivision acceleration structure changes, we usually have to rebuild the acceleration structure from scratch.

Object subdivision methods have quite different characteristics. Since the object is subdivided with volumes, and these volumes may overlap, the traversal is traditionally slower. We cannot, for instance, stop traversing a BVH as soon as a ray finds an intersection with a surface. Since the volumes overlap, we may need to check for potential intersections with nearby primitives before quitting the traversal. On the other hand, it may be easier to implement a BVH because we do not have to split the object parts with planes. Also, BVHs usually generate shallower structures (which may eventually compensate the slower traversal). However, one of the most interesting aspects of the BVHs is that they are dynamic geometry-friendly. If geometry changes (but not much, actually), we can simply locally adjust the size and position of the corresponding bounding volume (i.e. refitting). These adjustments may cause the need to adjust the parent volumes, a procedure that may culminate in a chain reaction that may reach the root node of the BVH. All in all, assuming that we have a reasonably balanced BVH, these operations will be ~O(log n), which is really fast and cool.

The above paragraph describes the traditional characteristics of the BVHs. There is currently lots of research going on on the topic, and several of its ineficiencies have been significantly reduced over time. It should be noted, for instance, that still in 2007, Wald, Boulos and Shirley have designed a very efficient BVH-based acceleration structure, for interactive ray tracing on GPUs, that rivals with space subdivision schemes such as kD-Trees. This work was very influential.

Actually there are several reasons that make the BVHs the preferred acceleration data structure for interactive ray tracing o GPUs. According to Wodniok and Goesele, the main factors that have turned the BVH into a popular acceleration structure in the context of GPU ray tracing are its "memory footprint (...) efficient empty space cut-off, fast construction, and simple update procedure (...) while (...) offering similar (...) performance as kD-Trees". Regarding fast BVH reconstruction, it may be interesting to take a look at the LBVH, by Lauterbach et. al., the HLBVH, by Pantaleoni and Luebke, and the one by Karras and Aila, that are capable to rebuild BVHs iteractively. Overlapping impacts the traversal procedure efficiency because, when a ray hit the overlap, it has to be tested against the two child nodes. SBVHs, by Stich et. al. is a hybrid structure that employs both spatial and object subdivisions such that overlap is reduced. The cons, according to the paper, are the fact that SBVH does not handle dynamic scenes anymore, and that it may increase memory consumption up to 30%. The SBVH building procedure, also, is not as fast as for the regular BVHs.

The current NVidia RTX GPUs support the traditional BVH, the SBVH and Karras/Aila acceleration structure. As pointed out and detailed by @DirectX_Programmer, in his answer below, these structures are actually combined, by the RTX drivers, into a more flexible arrangement composed by two levels.

Answer 2

@Christian Pagot I think it is worth mentioning, that DXR is using Bottom Level Acceleration Structures (BLAS) as well as Top Level Acceleration Structures (TLAS): Figure 3: Overview of raytracing building blocks

Figure 4: Overview of raytracing building blocks

https://developer.nvidia.com/rtx/raytracing/dxr/DX12-Raytracing-tutorial-Part-1 - please refer for more informations. Image 3 and 4 are copied from chapter 7 and 8.

You may also find some interesting bits in Microsoft DXR documentation - https://microsoft.github.io/DirectX-Specs/d3d/Raytracing.html I really hoped that I could find some more about rebuilding TLAS/BLAS. If I remember correctly there are two ways - if structures differ only slightly, you can do partial rebuild. When you get to the point, where structures differ too much from actual geometry, you have to do full rebuild. I don't have a source stating big O complexity, I am sorry.

Due to some disadvantages of using BVH e.g.lack of front-to-back traversal, some methods were implemented to deal with that:

[...]However, ordered traversal in a structure based on object partitioning, such as a BVH, is not achieved so easily. While an implementation based on a traversal priority queue (rather than a traversal stack) enables front-to-back traversal of a BVH [7], most publicly available, widely used production ray tracing APIs do not provide ordered BVH traversal variants.

From http://www.realtimerendering.com/raytracinggems/unofficial_RayTracingGems_v1.7.pdf#page=147 - Chapter 9 Multi-Hit Ray Tracing in DXR by Christiaan Gribble and SURVICE Engineering

I generally recommend this book, even though I've just read 1/3 of it. It contains a lot of state of the art articles about raytracing.

---

@lightxbulb I hope that I've managed to support part of Christian's Pagot statements with sources. I'm really disappointed that I couldn't find complexity of rebuilding BHV in DXR. Maybe somebody will have a link to that.

---

@Nash Gold https://www.amazon.com/Real-Time-Rendering-Tomas-Akenine-Mo%C2%A8ller-ebook/dp/B007COYODQ/ (I haven't read 4th edition) - you can find Collision Detection algorithms in chapter 17. Acceleration Algorithms in chapter 14. Also throughout the book, there is a lot of talking about intersection algorithms and even about usage of triangle fans, strips, meshes and pros, cons of all of them.

I enjoyed this book at the beginning. But if you're seasoned graphics programmer, you know most of its content through other sources. Therefore I would only refer to mentioned chapters.