algorithm - 降低光线转换算法的 O(n²) 时间复杂度

Question

我已经编写了一个基于标准算法的光线转换算法。交点是使用 Möller-Trumbore 算法计算的(与更简单的算法相比，该算法将执行时间减少了约 350%)。

总体执行以下步骤:

1. 对于每个三角形，从光源向三角形射出一条光线
2. 检查是否有其他三角形与射线相交。获取与射线源(即光源)距离最短的那个。
3. 用最小距离照亮那个(三角形设置 shaded = false)

我不需要不同的阴影变化；三角形只需要保存信息，无论它们是否被着色( bool 值)。

问题是对于第 2 步，我需要对场景中的所有三角形进行相交检查。换句话说，时间复杂度是 O(n²)。然而，我已经读到有可能有一个时间复杂度为 O(log n) 的光线转换算法。

我有一些减少执行时间的想法。例如，我可以从计算中排除所有与光源的距离大于光线射向的三角形，这可能会减少 50% 的执行时间。但是复杂度仍然是 O(n²)，并且在处理大量日期时不会有太大帮助。

例如，在具有 100.000 的场景上使用光线追踪算法仍然是可能的，但需要大约 10 分钟，并且当场景包含更多三角形时，该数量将呈指数增长。

有没有办法在不从根本上改变算法工作方式的情况下将时间复杂度降低到较低的复杂度级别？

编辑:我已经实现了 @meowgoesthedog 建议的边界体积层次结构 (BVH) 版本。三角盒相交实现起来有点棘手，但除此之外，它背后的理论很容易理解。

我试过不同数量的分区和子分区，结果差异很大，但在大多数情况下，光线转换的性能要好得多。没有通用的最佳配置，因此为不同的对象/场景尝试不同的数字是有意义的。在我的例子中，4/2(将房间分成 4*4*4 个边界框，每个边界框包含 2*2*2 个子框，即 64 个框，每个框有 8 个内部框)、5/2 和 6/2 通常表现良好，尽管对于某些对象，非分层分区效果最好(例如 10/0)。

所需的射线-三角形相交测试的数量最多可减少 97%(可能更多)，但更高级别的分区会使边界框/AABB 的创建成本相当高。如果配置良好，程序的执行速度比没有边界体积的解决方案快 4 倍。在具有大量三角形(超过 10000 个)的场景中可以更好地看到更好的性能。

但是，我的实现仍然相对幼稚，而且我确信还有很大的改进空间。如果我得到好的结果，我会继续修补并更新这篇文章!

Answer 1

这取决于您所说的“从根本上改变”它的工作方式是什么意思。如果您的意思是不改变其行为，即它的输出结果和准确性，那么可以。

这样做的方法是使用空间层次结构数据结构；这将以指数的方式减少搜索空间，为您提供对数时间复杂度。三种最常用的此类结构是:1. Octrees，2. Boundary-Volume Hierarchies (BVH)，以及 3. KD-trees>.

八叉树很容易构造，但内存效率或性能不如其他八叉树。 KD 树很难很好地构建，但内存效率更高，并提供最快的交叉时间。 BVH 介于两者之间。

对于 KD 树，this是一个很好的起点； this document在光线追踪社区中广为人知，非常适合进一步研究。

(另一种结构是著名的二进制空间分区 (BSP)。这提供了比上述所有三种更好的性能。但是，构建最佳 BSP 树对于一次性光线追踪渲染来说成本太高。)

为了让您了解即使是简单的实现也能带来的潜在 yield ，我在自己的光线追踪项目中使用了 KD 树。在 1920x1080 分辨率下，使用 100K 三角形模型、简单的 Lambertian 着色和每像素 100 个样本，渲染仅需 7 秒。我尝试了朴素的 O(n) 算法，每个像素只有 1 个样本，分辨率为 320x240，耗时 10 分钟。