<p>@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):
<a href="https://i.sstatic.net/1kZZB.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/1kZZB.png" alt="Figure 3: Overview of raytracing building blocks" /></a>
<strong>Figure 3:</strong> Overview of raytracing building blocks</p>
<p><a href="https://i.sstatic.net/CJj8g.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/CJj8g.png" alt="Figure 4: Acceleration Structure" /></a></p>
<p><strong>Figure 4:</strong> Overview of raytracing building blocks</p>
<p><a href="https://developer.nvidia.com/rtx/raytracing/dxr/DX12-Raytracing-tutorial-Part-1" rel="nofollow noreferrer">https://developer.nvidia.com/rtx/raytracing/dxr/DX12-Raytracing-tutorial-Part-1</a> - please refer for more informations. Image 3 and 4 are copied from chapter 7 and 8.</p>
<p>You may also find some interesting bits in Microsoft DXR documentation - <a href="https://microsoft.github.io/DirectX-Specs/d3d/Raytracing.html" rel="nofollow noreferrer">https://microsoft.github.io/DirectX-Specs/d3d/Raytracing.html</a> 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.</p>
<p>Due to some disadvantages of using BVH e.g.lack of front-to-back traversal, some methods were implemented to deal with that:</p>
<blockquote>
<p>[...]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.</p>
</blockquote>
<p>From <a href="http://www.realtimerendering.com/raytracinggems/unofficial_RayTracingGems_v1.7.pdf#page=147" rel="nofollow noreferrer">http://www.realtimerendering.com/raytracinggems/unofficial_RayTracingGems_v1.7.pdf#page=147</a> - Chapter 9 <em>Multi-Hit Ray Tracing in DXR</em> by Christiaan Gribble and SURVICE Engineering</p>
<p>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.</p>
<hr />
<p>@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.</p>
<hr />
<p>@Nash Gold
<a href="https://rads.stackoverflow.com/amzn/click/com/B007COYODQ" rel="nofollow noreferrer" rel="nofollow noreferrer">https://www.amazon.com/Real-Time-Rendering-Tomas-Akenine-Mo%C2%A8ller-ebook/dp/B007COYODQ/</a> (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.</p>
<p>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.</p>

CC BY-SA 4.0
2020-08-13T18:32:37.553Z
@NashGold If RT gems caught your attention, you may also want to read PBRT - http://www.pbr-book.org/3ed-2018/contents.html - it is much more focused on theoretical aspects of raytracing/path-tracing - sampling, theory of signals, camera models, color theory and so on.
DirectX_Programmer
CC BY-SA 4.0
2020-08-13T19:40:58.717Z
@DirectX_Programmer, not really. I'm doing a simple voxel engine for a pixelart game. PBR would be an overkill. But thanks anyway.
Nash Gold
CC BY-SA 4.0
2020-08-13T09:40:31.820Z
2020-08-13T09:40:31.820Z
DirectX_Programmer
<p>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?</p>

<raytracing><bounding-volume-hierarchy>
Is BVH faster than the octree/kd-tree for raytracing the objects on a GPU?
Nash Gold
# Is BVH faster than the octree/kd-tree for raytracing the objects on a GPU?

(Asked by: username_0 on 2020-08-10)

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?

**Tags:** raytracing, bounding-volume-hierarchy


---

## 1 answers

### Answer by username_1 on 2020-08-13. Score: 4

@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](https://i.sstatic.net/1kZZB.png)](https://i.sstatic.net/1kZZB.png)
**Figure 3:** Overview of raytracing building blocks

[![Figure 4: Acceleration Structure](https://i.sstatic.net/CJj8g.png)](https://i.sstatic.net/CJj8g.png)

**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.

---

@username_0
[https://www.amazon.com/Real-Time-Rendering-Tomas-Akenine-Mo%C2%A8ller-ebook/dp/B007COYODQ/](https://rads.stackoverflow.com/amzn/click/com/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.

> **Comments:**
> **username_1**: @username_0 If RT gems caught your attention, you may also want to read PBRT - http://www.pbr-book.org/3ed-2018/contents.html - it is much more focused on theoretical aspects of raytracing/path-tracing - sampling, theory of signals, camera models, color theory and so on.  
> **username_0**: @username_1, not really. I'm doing a simple voxel engine for a pixelart game. PBR would be an overkill. But thanks anyway.  

---

