Is BVH faster than the octree/kd-tree for raytracing the objects on a GPU? 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?
First, it is important to observe that there are basically two different &quot;classes&quot; 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 &quot;memory footprint (...) efficient empty space cut-off, fast construction, and simple update procedure (...) while (...) offering similar (...) performance as kD-Trees&quot;. 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.