5

我们有一个带有半透明墙壁和几个光源的矩形区域。我们只考虑俯视图,所以这是一个 2D 问题。我们需要找到该区域每个点的近似照明(信号强度)。

我们需要让算法变得非常快。蛮力方法对于我们的目的来说太慢了。您可以假设所有墙壁都衰减相同的量,即使是恒定的衰减量也是可以接受的。

该区域最多为 1000x1000,并且不会有超过 100 个光源。光源的范围可以约为。50-100 个单位(它们不是无限的)。欢迎使用更快但近似的算法。

提前致谢!

我尝试的基本上是蛮力方法:将每个样本点与每个墙壁和光源进行比较以确定其光度。显然,它是 O(n^3) 并且慢得令人无法接受。

时间我并不是指任何特定的限制:但最好在 100 毫秒或更快的时间内完成整个图像。请记住,我对准确性的要求不如速度。

4

2 回答 2

3

只是在黑暗中刺伤:您是否研究过(GPU 加速的)光子映射?

于 2011-05-06T08:59:27.860 回答
0

您可以通过线性损失质量(图像获得一半直径并重新采样回相同大小)来二次减少类似算法的运行时间(例如,跳过每第二个 x 和 y)。

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

我在 youtube 上上传了一段视频,显示了我编写代码以尝试是否可行的测试运行。它似乎与您需要的类似(在单个线程上“几乎实时”进行):

链接到视频

当然,这里的墙壁是具有透明属性的线条,光线不会像您期望的那样漫射,而是线性漫射,但是您的算法应该可以使用“近似值”,或者如果速度足够,您可以调整这个值。并且要注意代码写得很糟糕,因为我只是在做实验。

这里亮度是标准化的,您可能会以对数比例将亮度嵌入到像素中,这样您就可以适应更大的范围,以保留原始值。

你可以用它来做点什么吗:这是项目:

链接到项目

如果您对其进行优化和线程化,对于具有 100 个直径为 300 的灯和 20 个长度为 200 的墙(近似为 5)的 1000x1000 图像可能需要 100 毫秒。

于 2011-05-06T18:18:56.870 回答