Алгоритм быстрого 2D-освещения?

У нас есть прямоугольная область с полупрозрачными стенами и несколькими источниками света. Мы рассматриваем только вид сверху, так что это двумерная проблема. Нам нужно найти приблизительное освещение (силу сигнала) в каждой точке области.

Нам нужно сделать алгоритм действительно быстрым. Метод грубой силы был слишком медленным для наших целей. Вы можете предположить, что все стены ослабляют на одинаковую величину, даже постоянная величина ослабления допустима.

Площадь будет не более 1000x1000, и не будет более 100 источников света. Источники света могут иметь диапазон прибл. 50-100 единиц (они не бесконечны). Приветствуются более быстрые, но приблизительные алгоритмы.

Заранее спасибо!

То, что я пробовал, было методом грубой силы: сравнение каждой точки выборки с каждой стеной и источником света для определения ее яркости. Очевидно, что это O (n ^ 3) и неприемлемо медленно.

Под временем я не имел в виду какого-либо конкретного ограничения: но было бы неплохо сделать все изображение в пределах 100 мс или быстрее. Помните, мне нужна не столько точность, сколько скорость.