在GPU上进行光线追踪时，BVH是否比八叉树/ kd树更快？

#1 楼

首先，重要的是要观察到，为射线追踪建立加速结构的方法基本上有两种不同的“类”：1）空间细分方法（例如BSP，kD-Tree，Octree等）；和2）对象细分方法（例如BVH）。虽然空间细分方法是通过将平面递归地细分为平面，而不要遵循嵌入到该空间中的几何体，而对象细分方法是通过递归地将几何体细分为越来越小的部分，并用通常紧密的体积包裹每个部分。可以在PBRT v3在线书中找到更多有关空间和对象细分的基础知识。
每种方法（空间或对象细分）都有其优缺点。对于空间细分方法，由于子空间不重叠，因此我们通常可以更轻松地以从前到后或从后到前的顺序遍历结构。当光线穿过这样的结构时，只要它碰到表面，我们就可以停止穿过。这通常会导致更快的遍历方案。几个软件渲染器利用了空间细分方案提供的遍历效率。另一方面，空间细分方案的实现可能更加复杂（通常必须调整一些epsilon），并且可能导致树的深度增加。此外，他们也不喜欢非常动态的几何图形。如果编码为空间细分的加速结构的几何形状发生变化，则通常必须从头开始重建加速结构。
对象细分方法具有完全不同的特性。由于对象被体积细分，并且这些体积可能重叠，因此遍历通常较慢。例如，一旦射线发现与曲面的相交，我们就不能停止遍历BVH。由于体积重叠，因此我们可能需要在退出遍历之前检查与附近图元的潜在交集。另一方面，实现BVH可能更容易，因为我们不必用平面拆分对象部分。同样，BVH通常会生成较浅的结构（最终可能会补偿较慢的遍历）。但是，BVH最有趣的方面之一是它们对动态几何友好。如果几何形状发生变化（但实际上变化不大），我们可以简单地在本地调整相应边界体积的大小和位置（即重新调整）。这些调整可能会导致需要调整父体积，该过程可能最终导致可能到达BVH根节点的连锁反应。总而言之，假设我们拥有一个合理平衡的BVH，这些操作将为〜O（log n），这确实非常快捷。
以上段落描述了BVH的传统特征。当前，有关该主题的研究很多，并且随着时间的流逝，它的一些不足之处已经大大减少。值得一提的是，例如，仍然在2007年，Wald，Boulos和Shirley设计了一种非常高效的基于BVH的加速结构，用于GPU上的交互式光线跟踪，可与诸如kD-Trees的空间细分方案相媲美。这项工作很有影响力。
实际上，有多种原因使BVH成为GPU进行交互式光线跟踪的首选加速数据结构。根据Wodniok和Goesele的说法，在GPU光线跟踪的背景下，使BVH成为流行的加速结构的主要因素是其“内存占用空间（...）有效的空白空间剪切，快速构建和简单的更新过程”。 （...）而（...）提供与kD-Trees类似的（...）性能”。关于快速BVH重建，看一下Lauterbach等人的LBVH可能很有趣。 Pantaleoni和Luebke的HLBVH以及Karras和Aila的HLBVH能够迭代地重建BVH。重叠影响遍历过程的效率，因为当光线碰到重叠时，必须针对两个子节点对其进行测试。 SBVH，由Stich等撰写。等是一种混合结构，它同时使用空间和对象细分，从而减少了重叠。根据该论文，缺点是SBVH不再处理动态场景，并且可能使内存消耗增加30％。 SBVH的构建过程也不如常规BVH快。
当前的NVidia RTX GPU支持传统的BVH，SBVH和Karras / Aila加速结构。正如@DirectX_Programmer所指出的那样，在以下他的回答中，RTX驱动程序实际上将这些结构组合成由两个级别组成的更灵活的安排。
此回答仍然充满了应接受的强有力的陈述。小心。实际上，有一些技术可以探索空间细分结构的本地更新。旨在在找到交点后立即停止BVH遍历的技术；等等。我仍在编辑此答案，并在时间允许的情况下添加适当的参考。
我认为，此答案提供了广阔的前景。

#2 楼

@Christian Pagot
我认为值得一提的是，DXR正在使用底层加速结构（BLAS）和顶层加速结构（TLAS）：

图3：光线追踪构建基块

图4：光线追踪构建基块概述
https://developer.nvidia.com/rtx/raytracing/dxr/DX12-Raytracing-tutorial-Part-1-请参阅更多信息。图片3和4是从第7章和第8章复制而来的。
您还可以在Microsoft DXR文档中找到一些有趣的地方-https://microsoft.github.io/DirectX-Specs/d3d/Raytracing.html我真的希望我可以找到有关重建TLAS / BLAS的更多信息。如果我没有记错的话，有两种方法-如果结构仅稍有不同，则可以进行部分重建。当结构与实际几何形状相差太大时，您必须进行完全重建。抱歉，我没有消息来源说明O的复杂性。
由于使用BVH的一些缺点，例如缺少前后遍历，因此实现了一些方法来处理该问题：

[...]但是，基于对象分区的结构（例如BVH）中的有序遍历不是那么容易实现的。尽管基于遍历优先级队列（而不是遍历堆栈）的实现可以实现BVH的从前到后遍历[7]，但大多数公共可用的，广泛使用的生产射线跟踪API并未提供有序的BVH遍历变体。 />
从http://www.realtimerendering.com/raytracinggems/unofficial_RayTracingGems_v1.7.pdf#page=147-Christiaan Gribble和SURVICE Engineering撰写的第9章DXR中的多点射线追踪
我通常推荐这本书，即使我只读了1/3。它包含许多有关光线跟踪的最新文章。

@lightxbulb
我希望我能够通过消息来源支持克里斯蒂安·帕戈特（Pagot）的部分陈述。我对在DXR中重建BHV的复杂性感到非常失望。也许有人会对此链接。

@Nash Gold
https://www.amazon.com/Real-Time-Rendering-Tomas-Akenine-Mo%C2%A8ller- ebook / dp / B007COYODQ /（我没有读过第四版）-您可以在第17章中找到碰撞检测算法。在第14章中可以找到加速算法。在整本书中，也有很多关于交集算法甚至用法的讨论。三角形风扇，条带，网格和优点，所有优点和缺点。
我一开始喜欢这本书。但是，如果您是经验丰富的图形程序员，则可以通过其他来源了解其大部分内容。因此，我只会参考提到的章节。