降低光线投射算法的 O(n²) 时间复杂度
Reducing the O(n²) Time Complexity of a Ray Casting algorithm
我写了一个基于标准算法的光线投射算法。交点是使用 Möller-Trumbore 算法计算的（与更简单的算法相比，该算法将执行时间减少了约 350%）。
总体执行以下步骤：
- 对于每个三角形，从光源射出一条光线到三角形
- 检查是否有其他三角形与射线相交。获取与光线原点（即光源）距离最短的那个。
- 照亮距离最短的那个（设置三角形的 shaded = false）
我不需要不同的阴影变化；三角形只需要保存信息，如果它们完全没有阴影（布尔值）。
问题是对于第 2 步，我需要对场景中的所有三角形进行相交检查。换句话说，时间复杂度是 O(n²)。然而，我已经读到有可能有一个时间复杂度为 O(log n) 的光线投射算法。
我有一些减少执行时间的想法。例如，我可以从计算中排除所有与光源的距离大于光线射向的三角形，这可能会减少 50% 的执行时间。但是复杂度仍然是 O(n²) 并且在处理大量日期时它不会有太大帮助。
例如，在具有 100.000 个的场景上使用光线追踪算法仍然是可能的，但需要大约 10 分钟，并且当场景包含更多三角形时，该数量将呈指数增长。
有没有办法在不从根本上改变算法工作方式的情况下将时间复杂度降低到较低的复杂度class？
编辑： 我已经实施了 @meowgoesthedog 建议的边界体积层次结构 (BVH) 版本。三角盒相交实现起来有点棘手，但除此之外它背后的理论很容易理解。
我试过不同数量的分区和子分区，结果差异很大，但在大多数情况下，光线投射的性能要好得多。没有通用的最佳配置，因此为不同的 objects/scenes 尝试不同的数字是有意义的。在我的例子中，4/2（将房间分成 4*4*4 个边界框，每个边界框包含 2*2*2 个子框，即 64 个框，每个框有 8 个内部框）、5/2 和 6/2 通常表现良好，尽管对于某些对象，非分层分区效果最好（例如 10/0）。
所需的光线-三角形相交测试的数量最多可减少 97%（可能更多），但更高级别的分区会使边界框/AABB 的创建成本相当高。如果配置良好，程序的执行速度比没有边界体积的解决方案快 4 倍。在具有大量三角形（超过 10000 个）的场景中可以更好地看到更好的性能。
但是，我的实现仍然相对幼稚，我相信还有很大的改进空间。如果我得到好的结果，我会继续修补和更新这个 post！
这取决于你所说的 "fundamentally changing the way" 是什么意思。如果你的意思是不改变它的行为，即它的输出结果和准确性，那么是的。
这样做的方法是使用 spatial-hierarchy 数据结构；这将减少搜索space 指数，给你一个对数时间复杂度。三种最常用的此类结构是：1. Octrees、2. Boundary-Volume Hierarchies (BVH) 和 3. KD树.
八叉树很容易构造，但内存效率或性能不如其他八叉树。 KD 树很难很好地构建，但内存效率更高，并提供最快的交叉时间。 BVH 是...介于两者之间。
对于 KD 树，this is a good starting point; this document 在光线追踪社区中广为人知，非常适合进一步研究。
(另一种结构是著名的 Binary-Space 分区 (BSP)。这提供了比上述所有三个更好的性能。但是，构建最佳 BSP 树对于一次性光线追踪渲染来说成本太高。 )
为了让您了解即使是简单的实现也能带来潜在收益，我在自己的光线追踪项目中使用了 KD 树。在 1920x1080 分辨率下，使用 100K 三角形模型、简单的 Lambertian 着色和每像素 100 个样本，渲染仅需 7 秒。我尝试了朴素的 O(n) 算法，每个像素只有 1 个样本，分辨率为 320x240，花了 10 分钟。
我写了一个基于标准算法的光线投射算法。交点是使用 Möller-Trumbore 算法计算的（与更简单的算法相比，该算法将执行时间减少了约 350%）。
总体执行以下步骤：
- 对于每个三角形，从光源射出一条光线到三角形
- 检查是否有其他三角形与射线相交。获取与光线原点（即光源）距离最短的那个。
- 照亮距离最短的那个（设置三角形的 shaded = false）
我不需要不同的阴影变化；三角形只需要保存信息，如果它们完全没有阴影（布尔值）。
问题是对于第 2 步，我需要对场景中的所有三角形进行相交检查。换句话说，时间复杂度是 O(n²)。然而，我已经读到有可能有一个时间复杂度为 O(log n) 的光线投射算法。
我有一些减少执行时间的想法。例如，我可以从计算中排除所有与光源的距离大于光线射向的三角形，这可能会减少 50% 的执行时间。但是复杂度仍然是 O(n²) 并且在处理大量日期时它不会有太大帮助。
例如，在具有 100.000 个的场景上使用光线追踪算法仍然是可能的，但需要大约 10 分钟，并且当场景包含更多三角形时，该数量将呈指数增长。
有没有办法在不从根本上改变算法工作方式的情况下将时间复杂度降低到较低的复杂度class？
编辑： 我已经实施了 @meowgoesthedog 建议的边界体积层次结构 (BVH) 版本。三角盒相交实现起来有点棘手，但除此之外它背后的理论很容易理解。
我试过不同数量的分区和子分区，结果差异很大，但在大多数情况下，光线投射的性能要好得多。没有通用的最佳配置，因此为不同的 objects/scenes 尝试不同的数字是有意义的。在我的例子中，4/2（将房间分成 4*4*4 个边界框，每个边界框包含 2*2*2 个子框，即 64 个框，每个框有 8 个内部框）、5/2 和 6/2 通常表现良好，尽管对于某些对象，非分层分区效果最好（例如 10/0）。
所需的光线-三角形相交测试的数量最多可减少 97%（可能更多），但更高级别的分区会使边界框/AABB 的创建成本相当高。如果配置良好，程序的执行速度比没有边界体积的解决方案快 4 倍。在具有大量三角形（超过 10000 个）的场景中可以更好地看到更好的性能。
但是，我的实现仍然相对幼稚，我相信还有很大的改进空间。如果我得到好的结果，我会继续修补和更新这个 post！
这取决于你所说的 "fundamentally changing the way" 是什么意思。如果你的意思是不改变它的行为，即它的输出结果和准确性，那么是的。
这样做的方法是使用 spatial-hierarchy 数据结构；这将减少搜索space 指数，给你一个对数时间复杂度。三种最常用的此类结构是：1. Octrees、2. Boundary-Volume Hierarchies (BVH) 和 3. KD树.
八叉树很容易构造，但内存效率或性能不如其他八叉树。 KD 树很难很好地构建，但内存效率更高，并提供最快的交叉时间。 BVH 是...介于两者之间。
对于 KD 树，this is a good starting point; this document 在光线追踪社区中广为人知，非常适合进一步研究。
(另一种结构是著名的 Binary-Space 分区 (BSP)。这提供了比上述所有三个更好的性能。但是，构建最佳 BSP 树对于一次性光线追踪渲染来说成本太高。 )
为了让您了解即使是简单的实现也能带来潜在收益，我在自己的光线追踪项目中使用了 KD 树。在 1920x1080 分辨率下，使用 100K 三角形模型、简单的 Lambertian 着色和每像素 100 个样本，渲染仅需 7 秒。我尝试了朴素的 O(n) 算法，每个像素只有 1 个样本，分辨率为 320x240，花了 10 分钟。