#algorithm #2d #lighting
#алгоритм #2d #Освещение
Вопрос:
У нас есть прямоугольное помещение с полупрозрачными стенами и несколькими источниками света.Мы рассматриваем только вид сверху, так что это 2D-проблема. Нам нужно найти приблизительное освещение (уровень сигнала) в каждой точке области.
Нам нужно сделать алгоритм действительно быстрым. Метод грубой силы был просто слишком медленным для наших целей. Вы можете предположить, что все стены ослабляют на одинаковую величину, даже постоянная величина ослабления приемлема.
Площадь была бы не более 1000х1000, и там было бы не более 100 источников света. Диапазон источников света может составлять приблизительно 50-100 единиц (они не бесконечны). Более быстрые, но приблизительные алгоритмы приветствуются.
Заранее спасибо!
То, что я пробовал, было в основном методом грубой силы: сравнение каждой точки выборки с каждой стеной и источником света для определения ее яркости. Очевидно, что это O (n ^ 3) и неприемлемо медленно.
Под временем я не имел в виду какое-либо конкретное ограничение: но было бы неплохо сделать все изображение в течение 100 мс или быстрее. Помните, мне требуется не столько точность, сколько скорость.
Комментарии:
1. какая скорость для одной точки вам нужна и какая скорость для всех точек на 2d-изображении? скорость означает время, например, миллисекунды…
Ответ №1:
Просто попытка в темноте: вы изучали отображение фотонов (с ускорением GPU)?
Ответ №2:
Вы можете уменьшить время выполнения аналогичного алгоритма квадратично (например, пропустить каждые 2 x и y), линейно теряя качество (изображение приобретает половину диаметра и пересчитывает обратно до того же размера).
Используйте растровое изображение для сохранения яркости и визуализируйте на растровом изображении меньшего размера (разделите на коэффициент аппроксимации) все ваши точки на линии atc (но также разделите все точки на коэффициент аппроксимации), затем используйте размытие по Гауссу и выполните повторную выборку до желаемого размера. Затем извлеките яркость из пикселей.
Я загрузил видео на YouTube, показывающее запуск теста, который я написал, чтобы проверить, может ли это сработать. Кажется, что-то похожее на то, что вам требуется (выполнение этого в режиме «почти реального времени» в одном потоке):
Конечно, здесь стены представляют собой линии со свойствами прозрачности, и свет рассеивается не так, как вы ожидали, а линейно, но «приближение» должно использоваться вашим алгоритмом, или вы можете адаптировать этот, если скорости достаточно. И будьте осторожны, код написан очень плохо, потому что я просто экспериментировал.
Здесь яркость нормализована, вы, вероятно, предпочли бы встраивать яркость в логарифмическом масштабе в пиксели, чтобы можно было установить больший диапазон для сохранения исходных значений.
Можно ли его для чего-то использовать: Вот проект:
Если вы оптимизируете и расширяете его, возможно, 100 мс для изображения размером 1000×1000 со 100 источниками света диаметром 300 и примерно 20 стенами длиной 200, с максимумом 5 достижимо.