快速2D照明算法？

Question

我們有一個帶半透明牆壁和幾個光源的矩形區域。我們只考慮頂視圖，所以它是一個2D問題。我們需要找到該區域每個點的近似光照（信號強度）。

我們需要使算法真的很快。蠻力法對我們的目的來說太慢了。你可以假設所有的牆壁衰減相同的數量，即使恆定的衰減量也是可以接受的。

面積最多爲1000x1000，光源不會超過100個。光源的範圍可以約爲。 50-100個單位（他們不是無限的）。更快但近似的算法是受歡迎的。

在此先感謝！

我試過的基本上是強力方法：比較每個採樣點與每個牆壁和光源以確定其光度。顯然，它是O（n^3），速度慢得令人難以接受。

到時候我並不是指任何特定的限制：但是在100ms或更快的時間內完成整個圖像會很好。請記住，我不要求速度的準確性。

Answer 1

只是在黑暗中刺：你看過（GPU加速）光子映射？

Answer 2

您可以通過線性丟失質量（圖像獲得半直徑並重新採樣回相同大小），以二次方式減少類似算法的運行時間（例如跳過每第2個x和y）。

使用位圖存儲亮度，並在較小尺寸的位圖（除以接近因子）上渲染所有點線atc（但也將所有點除以接近係數），然後使用高斯模糊並重新採樣回所需的尺寸。然後從像素中提取亮度。

我在YouTube上上傳了一段視頻，顯示我做了一個測試的運行，如果這可以工作的話。這似乎omething類似於您需要（與在單個線程「幾乎實時」這樣做）：

Link to Video

當然，這裏的牆壁是用透明特性線，光不會擴散，你會期望但線性，但「逼近」應該可以用你的算法，或者如果速度足夠，你可以適應這個。謹防代碼寫得非常糟糕，因爲我只是在試驗。

這裏光度是標準化的，您可能會將對數尺度的光度嵌入像素中，因此您可以適應更大的範圍，以保留原始值。

是你可以用它的東西： 這裏是項目：

Link to project

如果您優化並擰它，大概100毫秒與100個燈直徑300一1000×1000的圖像，並像20層長度200，可以達到5的近似值。