我编写了一个基于标准算法的光线转换算法。交点是使用 Möller-Trumbore 算法计算的(与更简单的算法相比，执行时间减少了约 350%)。
总体执行以下步骤:
- 对于每个三角形，从光源向三角形发射一条光线
- 检查是否还有其他三角形与射线相交。找到与光线原点(即光源)距离最小的一个。
- 照亮距离最小的那个(三角形的阴影设置为 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 个)的场景中，更好的性能更加明显。
但是，我的实现仍然相对幼稚，我确信还有很多改进的空间。如果取得好的结果，我将继续修补并更新这篇文章!
最佳答案
这取决于您所说的“从根本上改变它的工作方式”是什么意思。如果您的意思是不改变其行为，即输出结果和准确性，那么是的。
这样做的方法是使用空间层次结构数据结构；这将以指数方式减少搜索空间，从而获得对数时间复杂度。最常用的三种结构是:1.八叉树、2.边界体积层次结构 (BVH) 和 3.KD 树>.
八叉树非常容易构造，但内存效率或性能不如其他八叉树。 KD 树很难很好地构建，但内存效率更高，并且可以提供最快的交叉时间。 BVH 是......介于两者之间。
对于 KD 树，this是一个很好的起点； this document在光线追踪界很有名气，对于进一步研究非常有好处。
(另一种结构是著名的二元空间分区(BSP)。这比上述三种结构具有更好的性能。但是，对于一次性光线跟踪渲染来说，构造最佳 BSP 树的成本太高。)
为了让您了解简单实现的潜在 yield ，我在自己的光线追踪项目中使用了 KD 树。在 1920x1080 的分辨率下，使用 100K 三角形模型、简单的朗伯着色和每像素 100 个样本，渲染仅需 7 秒。我尝试了朴素的 O(n) 算法，每个像素只有 1 个样本，分辨率为 320x240，花了 10 分钟。
关于algorithm - 降低光线转换算法的 O(n²) 时间复杂度，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/45896293/