Fast 2D illumination algorithm?

Question

We have a rectangular area with translucent walls and a few light sources.We are considering only the top view,so it is a 2D problem. We need to find the approximate lighting (signal strength)at each point of the area.

We need to make the algorithm really fast. The brute force method was just too slow for our purposes. You can assume that all walls attenuate by same amount, even constant amount of attenuation is acceptable.

The area would be at most 1000x1000, and there would not be more than 100 light sources. The light sources can have a range of approx. 50-100 units (they are not infinite). Faster but approximate algorithms are welcome.

Thanks in advance!

What I tried was basically brute force method: comparing each sample point with each wall and light source to determine its luminosity. Obviously, it is O(n^3) and unacceptably slow.

By time I did not mean any specific limit: but it would be nice to do the whole image within 100ms or faster. Remember, I do not require accuracy as much as speed.

Answer 1

Just a stab in the dark: have you looked into (GPU-accelerated) photon mapping?