快速的2D照明算法？

Question

我们有一个带半透明墙壁和几个光源的矩形区域。我们只考虑俯视图，因此这是一个二维问题。我们需要找到每个点的近似照明（信号强度）。

我们需要让算法真正快速。暴力方法对我们的目的来说太慢了。您可以假设所有墙壁都具有相同的衰减值，即恒定的衰减值是可接受的。

该区域最大为1000x1000，在该区域内不会超过100个光源。光源的范围可以大约为50-100单位（它们不是无限的）。欢迎更快但近似的算法。

提前感谢！

我尝试的基本上是暴力方法：将每个采样点与每堵墙壁和每个光源进行比较，以确定其亮度。显然，这是O（n ^ 3），速度不可接受。

关于时间，我没有任何具体限制：但是在100毫秒或更快的时间内完成整个图像会很好。请记住，我需要的不是精度，而是速度。

- Sourav Chakraborty

---

你需要单个点的速度和2D图像中所有点的速度是多少？速度指时间，例如毫秒... - Marino Šimić

Answer 1

只是瞎猜一下：你有没有考虑过（GPU加速的）光子映射？

- nielsbot

Answer 2

你可以通过二次减少运行时间类似的算法（例如跳过每个第二个x和y），但是会线性地失去质量（图像直径减半并重新采样到相同大小）。

使用位图存储亮度，并在较低大小的位图上渲染（除以近似因子）所有点线等（但也将所有点除以近似因子），然后使用高斯模糊并重新采样回所需大小。然后从像素中提取亮度。

我上传了一个视频到YouTube，展示了我尝试的代码测试的运行情况。它似乎与您需要的内容类似（在单个线程上“几乎实时”完成）：

视频链接

当然，在这里，墙壁是具有透明属性的线条，光线不会像您预期的那样扩散，而是线性的，但是“近似值”应该可用于您的算法，或者如果速度足够快，则可以调整此算法。请注意，代码编写得非常糟糕，因为我只是在进行实验。

在这里，亮度被归一化，您可能会选择将亮度嵌入对数比例尺中的像素中，以便您可以适应更大的范围，以保留原始值。

如果您需要使用它做些什么：

这是项目链接：

项目链接

如果您进行优化和线程处理，可能可以在大约5的近似值下，以100ms的速度处理1000x1000像素、100个直径为300的灯光和20个长度为200的墙壁。

- Marino Šimić