Участник:Kst179/Metropolis light transport

Материал из Алговики
Перейти к навигации Перейти к поиску

Metropolis light transport — это алгоритм, применяющий один из вариантов метода Монте Карло — метод Метрополиса-Гастинга, Монте Карло на Марковских цепях (Metropolis-Hastings, Markov chain Monte Carlo, MCMC), для генерации изображений при помощи физического описания трехмерных сцен. Алгоритм используется в компьютерной графике, решает задачу глобального освещения (точное моделирование световых эффектов). Отличается от классических методов, таких как Bidirectional path tracing скоростью работы и точностью моделирования (возвращает несмещенное значение).


1 Свойства и структура алгоритма

2 += Общее описание алгоритма =

Основной объект с которыми работает трассировщик лучей это пути от источников света до камеры. Путь это ломанная, каждое звено которой имитирует направление движения фотона, ломанная начинается в источнике света, изменяет направление при попадании на какую либо поверхность, а последнее звено должно заканчиваться в камере. Обозначим путь как [math]\overline{x} = x_1, x_2, \dots, x_k[/math], где [math]k\gt 1, x_i[/math] — координата на поверхности некоторого объекта от которого отражается луч). Для каждого пути введем некоторую функцию [math]f(\overline{x})[/math], обозначающую яркость, с которой этот луч освещает пиксель матрицы камеры. Обычные методы трассировки лучей генерируют очень много путей и потом аггрегируют значение яркости по каждому пикселю. Это может быть очень долго, из за того что много компьютерного времени уходит на генерацию лучей с малой яркостью последующий вклад которых в результатирующее изображение мал (пример — две комнаты, разделенные слегка приоткрытой дверью в одной находится источник света, в другой — камера, тогда большинство независимо сгенерированных путей будет проходить сквозь стену, а значит иметь нулевую яркость). В MLT путь считается случайной величиной, с плотностью вероятности [math]p(\overline{x}) = \frac{1}{b}f(\overline{x}), b=const[/math], а генерация путей происходит согласно этому распределению. Тогда получается что более весомых путей мы генерируем больше, а пути проходящие через стены или на которых теряется слишком много яркости мы практически не рассматриваем. Также если генерировать пути согласно вышеописанному распределению то выражение для подсчета окончательного изображения [math]m_j = \int _{\Omega} w_j(\overline{x})f(\overline{x})d\overline{x}[/math], (где [math]m_j[/math] — значение [math]j[/math]-го пикселя, [math]\Omega[/math] — пространство всевозможных путей, [math]w_j(\overline{x})[/math] — индикатор того, что [math]\overline{x}[/math] попадает в [math]j[/math]-й пиксель) можно заменить на следующую несмещенную оценку:

[math]m_j = \int _{\Omega} w_j(\overline{x})f(\overline{x})d\overline{x} = \int _{\Omega} w_j(\overline{x})\frac{f(\overline{x})}{p(\overline{x})} p(\overline{x})d\overline{x} = \mathbb{E} w_j(\overline{x})\frac{f(\overline{x})}{p(\overline{x})} \approx \frac{1}{N} \sum _{i=0} ^{N} w_j(\overline{x_i})\frac{f(\overline{x_i})}{p(\overline{x_i})} = \frac{b}{N} \sum _{i=0} ^{N} w_j(\overline{x_i})[/math].

То есть после семплирования путей [math]\overline{x_1}, \overline{x_2}, \dots, \overline{x_N}[/math] получаем что яркость j-го пикселя пропорциональна количеству приходящих в этот пиксель лучей а от их вида никак не зависит (но для этого необходимо чтобы пути строго соответствовали своему распределению).

2.1 Математическое описание алгоритма

2.2 Вычислительное ядро алгоритма

2.3 Макроструктура алгоритма

2.4 Схема реализации последовательного алгоритма

2.5 Последовательная сложность алгоритма

2.6 Информационный граф

3 Программная реализация алгоритма

4 Литература