Алговики - Вклад [ru]

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

2017-10-24T20:05:25Z

Kst179:

Metropolis light transport<ref>Veach E., Guibas L. J. Metropolis light transport //Proceedings of the 24th annual conference on Computer graphics and interactive techniques. – ACM Press/Addison-Wesley Publishing Co., 1997. – С. 65-76.</ref> — это алгоритм, применяющий один из вариантов метода Монте Карло — метод Метрополиса-Гастинга<ref>Hastings W. K. Monte Carlo sampling methods using Markov chains and their applications //Biometrika. – 1970. – Т. 57. – №. 1. – С. 97-109.</ref>, Монте Карло на Марковских цепях ('''Metropolis-Hastings, Markov chain Monte Carlo, MCMC'''), для генерации изображений при помощи физического описания трехмерных сцен. Алгоритм используется в компьютерной графике, решает задачу глобального освещения (точное моделирование световых эффектов). Отличается от классических методов, таких как Bidirectional path tracing скоростью работы и точностью моделирования (возвращает несмещенное значение).

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

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

Основной объект с которыми работает трассировщик лучей это ''пути'' от источников света до камеры. Путь это ломанная, каждое звено которой имитирует направление движения фотона, ломанная начинается в источнике света, изменяет направление при попадании на какую либо поверхность, а последнее звено должно заканчиваться в камере. Обозначим путь как <math>\overline{x} = x_1, x_2, \dots, x_k</math>, где <math>k>1, x_i</math> — координата на поверхности некоторого объекта от которого отражается луч). Для каждого пути введем некоторую функцию <math>f(\overline{x})</math>, обозначающую яркость, с которой этот луч освещает пиксель матрицы камеры.

[[Файл:Ray.jpg|справа|350пкс|Пример трассировки лучей]]

Обычные методы трассировки лучей генерируют очень много путей и потом аггрегируют значение яркости по каждому пикселю. Это может быть очень долго, из за того что много компьютерного времени уходит на генерацию лучей с малой яркостью последующий вклад которых в результатирующее изображение мал (пример — две комнаты, разделенные слегка приоткрытой дверью в одной находится источник света, в другой — камера, тогда большинство независимо сгенерированных путей будет проходить сквозь стену, а значит иметь нулевую яркость).

В '''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-го пикселя пропорциональна количеству приходящих в этот пиксель лучей а от их вида никак не зависит (но для этого необходимо чтобы пути строго соответствовали своему распределению).

== Математическое описание алгоритма ==
Для семплирования путей из, вообще говоря, неизвестного нам распределения <math>p(\overline{x})</math> используется метод '''MCMC'''. Построим следующую марковскую цепь: введем некоторую вероятность <math>K(\overline{y}|\overline{x})</math> перехода <math>\overline{x} \rightarrow \overline{y}</math>. Выберем произвольный путь <math>\overline{x_0}</math> и случайным блужданием будем переходить от <math>\overline{x_{i-1}}</math> к <math>\overline{x_i}</math>. Пусть <math>\overline{x_0}</math> распределено с некоторой плотностью вероятности <math>p_0(\overline{x})</math>, тогда <math>x_i</math> будет распределено как <math>p_i(\overline{x}) = \int_{\Omega} K(\overline{x}|\overline{y})p_{i-1}(\overline{y})d\overline{y}</math>. При некоторых условиях на <math>K(\overline{x}|\overline{y}), ~\underset{i\rightarrow\infty}{lim}p_i(\overline{x}) = p(\overline{x})</math>, откуда следует что при правильном выборе <math>K(\overline{x}|\overline{y})</math>, и большом количестве переходов, независимо от выбора <math>\overline{x_0}</math>, все <math>\overline{x_i}</math> будут распределены согласно вероятности <math>p(\overline{x})</math>.

Пусть мы находимся в состоянии (пути) <math>\overline{x}</math>, сделаем над путем некоторую мутацию (небольшое изменение) и получим некоторый другой путь <math>\overline{y}</math>. На пространстве всевозможных мутаций над <math>\overline{x}</math> введем вероятность <math>T(\overline{y}| \overline{x})</math> того что при мутации <math>\overline{x}</math> получится <math>\overline{y}</math>. Далее мы можем принять эту мутацию или отклонить с некоторой вероятностью <math>a(\overline{y}|\overline{x})</math>. Если мутация принимается, то совершается переход по марковской цепи <math>\overline{x} \rightarrow \overline{y}</math>, иначе <math>\overline{x}\rightarrow\overline{x}</math>, т.е. мы остаемся в том же состоянии. Таким образом мы сконструировали <math>K(\overline{y}|\overline{x}) = a(\overline{y}|\overline{x})T(\overline{y}|\overline{x})</math>, при <math>\overline{x} \neq \overline{y}, K(\overline{x}|\overline{x}) = \int_{\Omega}(1-a(\overline{y}|\overline{x}))T(\overline{y}|\overline{x})d\overline{y}</math>, где <math>T(\overline{y}|\overline{x})</math> определяется тем, как именно мы производим мутации над путями, будет обсуждено чуть позже, а <math>a(\overline{y}|\overline{x})</math> выбирается таким, чтобы цепь сходилась к стационарному состоянию, и скорость сходимости была как можно выше. Согласно ''принципу детального равновесия'' Марковская цепь сходится к стационарному распределению <math>p(\overline{x})</math> при <math>p(\overline{x})K(\overline{y}|\overline{x}) = p(\overline{y})K(\overline{x}|\overline{y})</math>, или, что тоже самое:
<math>\frac{1}{b}f(\overline{x})a(\overline{y}|\overline{x})T(\overline{y}|\overline{x}) = \frac{1}{b}f(\overline{y})a(\overline{y}|\overline{x})T(\overline{x}|\overline{y})</math>.

Откуда получаем <math>\frac{a(\overline{y}|\overline{x})}{a(\overline{x}|\overline{y})} = \frac{f(\overline{y})T(\overline{x}|\overline{y})}{f(\overline{x})T(\overline{y}|\overline{x})}</math>. Так как скорость сходимости необходима как можно большая, то выберем <math> a(\overline{y}|\overline{x})</math> и <math> a(\overline{x}|\overline{y})</math> максимально возможным: <math>a(\overline{y}|\overline{x}) = min\left\{ 1, \frac{f(\overline{y})T(\overline{x}|\overline{y})}{f(\overline{x})T(\overline{y}|\overline{x})} \right\} </math>.

Теперь определим функцию <math>f(\overline{x})</math>. Функция <math>f(\overline{x})</math> складывается из нескольких промежуточных значений, каждое из которых отображает какая часть освещенности падает при прохождении звена пути/отражения луча от поверхности. Рассмотрим одно звено пути <math>x' \rightarrow x''</math>. Пусть x' находится на поверхности объекта излучающего свет. Тогда определим <math>L_e(x'\rightarrow x'')</math> как освещенность точки <math>x''</math> при излучении света из точки <math>x'</math>. Для точечного источника <math>L_e(x'\rightarrow x'') = \frac{I}{||x' - x''||^2}</math>, где I — интенсивность источника, для излучающей поверхности с нормалью <math>\overline{n}</math> в точке <math>x'</math>, <math>L_e(x' \rightarrow x'') = I\frac{|<\overline{n}, x''-x'>|}{||x'-x''||^3}</math> и т.д. для каждого типа источника функция будет разной.

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

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

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

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

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

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

= Литература =

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

2017-10-24T14:22:56Z

Kst179: /* Математическое описание алгоритма */

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

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

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

Основной объект с которыми работает трассировщик лучей это ''пути'' от источников света до камеры. Путь это ломанная, каждое звено которой имитирует направление движения фотона, ломанная начинается в источнике света, изменяет направление при попадании на какую либо поверхность, а последнее звено должно заканчиваться в камере. Обозначим путь как <math>\overline{x} = x_1, x_2, \dots, x_k</math>, где <math>k>1, x_i</math> — координата на поверхности некоторого объекта от которого отражается луч). Для каждого пути введем некоторую функцию <math>f(\overline{x})</math>, обозначающую яркость, с которой этот луч освещает пиксель матрицы камеры.

[[Файл:Ray.jpg|справа|350пкс|Пример трассировки лучей]]

Обычные методы трассировки лучей генерируют очень много путей и потом аггрегируют значение яркости по каждому пикселю. Это может быть очень долго, из за того что много компьютерного времени уходит на генерацию лучей с малой яркостью последующий вклад которых в результатирующее изображение мал (пример — две комнаты, разделенные слегка приоткрытой дверью в одной находится источник света, в другой — камера, тогда большинство независимо сгенерированных путей будет проходить сквозь стену, а значит иметь нулевую яркость).

В '''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-го пикселя пропорциональна количеству приходящих в этот пиксель лучей а от их вида никак не зависит (но для этого необходимо чтобы пути строго соответствовали своему распределению).

== Математическое описание алгоритма ==
Для семплирования путей из, вообще говоря, неизвестного нам распределения <math>p(\overline{x})</math> используется метод '''MCMC'''. Построим следующую марковскую цепь: введем некоторую вероятность <math>K(\overline{y}|\overline{x})</math> перехода <math>\overline{x} \rightarrow \overline{y}</math>. Выберем произвольный путь <math>\overline{x_0}</math> и случайным блужданием будем переходить от <math>\overline{x_{i-1}}</math> к <math>\overline{x_i}</math>. Пусть <math>\overline{x_0}</math> распределено с некоторой плотностью вероятности <math>p_0(\overline{x})</math>, тогда <math>x_i</math> будет распределено как <math>p_i(\overline{x}) = \int_{\Omega} K(\overline{x}|\overline{y})p_{i-1}(\overline{y})d\overline{y}</math>. При некоторых условиях на <math>K(\overline{x}|\overline{y}), ~\underset{i\rightarrow\infty}{lim}p_i(\overline{x}) = p(\overline{x})</math>, откуда следует что при правильном выборе <math>K(\overline{x}|\overline{y})</math>, и большом количестве переходов, независимо от выбора <math>\overline{x_0}</math>, все <math>\overline{x_i}</math> будут распределены согласно вероятности <math>p(\overline{x})</math>.

Пусть мы находимся в состоянии (пути) <math>\overline{x}</math>, сделаем над путем некоторую мутацию (небольшое изменение) и получим некоторый другой путь <math>\overline{y}</math>. На пространстве всевозможных мутаций над <math>\overline{x}</math> введем вероятность <math>T(\overline{y}| \overline{x})</math> того что при мутации <math>\overline{x}</math> получится <math>\overline{y}</math>. Далее мы можем принять эту мутацию или отклонить с некоторой вероятностью <math>a(\overline{y}|\overline{x})</math>. Если мутация принимается, то совершается переход по марковской цепи <math>\overline{x} \rightarrow \overline{y}</math>, иначе <math>\overline{x}\rightarrow\overline{x}</math>, т.е. мы остаемся в том же состоянии. Таким образом мы сконструировали <math>K(\overline{y}|\overline{x}) = a(\overline{y}|\overline{x})T(\overline{y}|\overline{x})</math>, при <math>\overline{x} \neq \overline{y}, K(\overline{x}|\overline{x}) = \int_{\Omega}(1-a(\overline{y}|\overline{x}))T(\overline{y}|\overline{x})d\overline{y}</math>, где <math>T(\overline{y}|\overline{x})</math> определяется тем, как именно мы производим мутации над путями, будет обсуждено чуть позже, а <math>a(\overline{y}|\overline{x})</math> выбирается таким, чтобы цепь сходилась к стационарному состоянию, и скорость сходимости была как можно выше. Согласно ''принципу детального равновесия'' Марковская цепь сходится к стационарному распределению <math>p(\overline{x})</math> при <math>p(\overline{x})K(\overline{y}|\overline{x}) = p(\overline{y})K(\overline{x}|\overline{y})</math>, или, что тоже самое:
<math>\frac{1}{b}f(\overline{x})a(\overline{y}|\overline{x})T(\overline{y}|\overline{x}) = \frac{1}{b}f(\overline{y})a(\overline{y}|\overline{x})T(\overline{x}|\overline{y})</math>.

Откуда получаем <math>\frac{a(\overline{y}|\overline{x})}{a(\overline{x}|\overline{y})} = \frac{f(\overline{y})T(\overline{x}|\overline{y})}{f(\overline{x})T(\overline{y}|\overline{x})}</math>. Так как скорость сходимости необходима как можно большая, то выберем <math> a(\overline{y}|\overline{x})</math> и <math> a(\overline{x}|\overline{y})</math> максимально возможным: <math>a(\overline{y}|\overline{x}) = min\left\{ 1, \frac{f(\overline{y})T(\overline{x}|\overline{y})}{f(\overline{x})T(\overline{y}|\overline{x})} \right\} </math>.

Теперь определим функцию <math>f(\overline{x})</math>. Функция <math>f(\overline{x})</math> складывается из нескольких промежуточных значений, каждое из которых отображает какая часть освещенности падает при прохождении звена пути/отражения луча от поверхности. Рассмотрим одно звено пути <math>x' \rightarrow x''</math>. Пусть x' находится на поверхности объекта излучающего свет. Тогда определим <math>L_e(x'\rightarrow x'')</math> как освещенность точки <math>x''</math> при излучении света из точки <math>x'</math>. Для точечного источника <math>L_e(x'\rightarrow x'') = \frac{I}{||x' - x''||^2}</math>, где I — интенсивность источника, для излучающей поверхности с нормалью <math>\overline{n}</math> в точке <math>x'</math>, <math>L_e(x' \rightarrow x'') = I\frac{|<\overline{n}, x''-x'>|}{||x'-x''||^3}</math> и т.д. для каждого типа источника функция будет разной.

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

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

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

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

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

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

= Литература =

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

2017-10-23T20:34:11Z

Kst179: /* Математическое описание алгоритма */

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

2017-10-23T18:10:10Z

Kst179: /* Математическое описание алгоритма */

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

2017-10-23T16:33:15Z

Kst179: /* Общее описание алгоритма */

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

2017-10-23T15:57:29Z

Kst179: /* += Общее описание алгоритма = */

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

2017-10-23T15:57:02Z

Kst179: /* Общее описание алгоритма */

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

2017-10-23T12:11:20Z

Kst179:

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

2017-10-21T10:37:18Z

Kst179: Новая страница: «= Свойства и структура алгоритма = == Общее описание алгоритма == == Математическое описан…»

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

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

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

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

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

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

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

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

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

= Литература =