Podręcznik Grafika komputerowa i wizualizacja

Metropolis Light Transport (MLT) jest jedną z najciekawszych metod rozwiązania problemu oświetlenia globalnego. MLT pojawiło się grafice komputerowej w 1997 roku w artykule E.Veach i L.Guibas [11]. Autorzy zaadaptowali metodę próbkowania zaproponowaną wcześniej przez Metropolis (i innych) [12] do efektywnego próbkowania w statystycznym rozwiązywaniu problemów fizycznych. Podstawową zaletą stosowania MLT w śledzeniu promieni jest możliwość adaptacyjnego próbkowania ścieżek promieni światła i niezależnego rozpatrywania lokalnych „porcji” światła, w oparciu o bardzo prosty mechanizm. Najczęściej stosowanym mechanizmem wyboru próbek jest uzależnienie go, po prostu od wartości funkcji opisującej lokalne zmiany luminancji. Dzięki temu łatwiejsze stało się analizowanie przypadków, gdzie właśnie lokalne zmiany są najsilniejsze jak np. zjawiska kaustyczne. Metoda MLT zrewolucjonizowała rozwiązanie problemu oświetlenia globalnego, dając możliwość efektywniejszego (a tym samym szybszego) uzyskania zadowalających obrazów (rys.12.10). Metoda MLT była wielokrotnie uzupełniana i doskonalona. M.Pauly (i inni) w artykule [13] zaproponowali zastosowanie metody do scen zawierających mgłę i dym. Wiele prac dotyczy próby poprawy zbieżności i właściwości statystycznych MLT [14, 15]. Praktyczne uwagi dotyczące współczesnych zastosowań MLT można znaleźć także w [6].

Rys.12.10. a) Obraz wygenerowany z wykorzystaniem dwukierunkowego śledzenia ścieżek
i nadpróbkowania 40 próbek na piksel. b) Obraz wygenerowany z zastosowaniem MLT,
250 mutacji na piksel.   Czas realizacji w obu przypadkach taki sam.
Prezentowane rysunki są fragmentami rysunków pochodzących z pracy [11].
Fair use – dozwolony użytek w celach edukacyjnych.

Niech dana będzie funkcja f(x) nieujemna w rozpatrywanym przedziale. Jeśli chcemy spróbkować funkcję f(x) algorytmem Metropolis, to algorytm ten uzależnia generowanie próbek od wartości funkcji f(x). Takie podejście jest bardzo wygodne, nie wymaga odwracania funkcji, odpowiednich normalizacji czy wyznaczania całki. Wystarczy tylko wartość funkcji. Jest to szczególnie wygodne w sytuacjach gdy inne metody próbkowania stwarzają problemy.

Proces generowania próbek jest rozpoczynany od wygenerowania startowej, losowej próbki x₀. Każda następna jest generowana na podstawie próbki poprzedniej za pomocą funkcji mutacji x_i+1=M(x_i). Funkcja ta zmienia wartość próbki, w najprostszym przypadku może to być generowanie nowej wartości losowej, niezależnie od próbki poprzedniej. Do generowania próbek wykorzystywane są jeszcze dwie funkcje. Pierwszą jest funkcja przejścia P(x_i,x_i+1) określająca prawdopodobieństwo przejścia ze stanu x_i do x_i+1 z wykorzystaniem mutacji M(x). Drugą jest funkcja akceptacji    określająca prawdopodobieństwo akceptacji zrealizowanej mutacji. Jeśli punkcja przejścia jest symetryczna tzn. P(x_i,x_i+1) = P(x_i+1,x_i)  to  .  Generowanie próbek opisuje Algorytm Metropolis.

ALGORYTM  Metropolis

x₀=RAND() , i=0
powtarzaj następujący zestaw operacji  aż i osiągnie wartość N
begin

wyznacz nową próbkę  x_i+1=M(x_i)
określ poziom akceptacji a = A(x_i, x_i+1)
jeśli (RAND()<a) to i=i+1 oraz zapamiętaj x_i

end

Algorytm generuje N próbek zgodnie z rozkładem określanym pośrednio przez funkcję akceptacji. Nieujemną funkcją f(x) wykorzystywaną w MLT jest funkcja luminancji ścieżki. Oznacza to, że przy najprostszej mutacji (nowa wartość losowa) próbki są generowane w taki sposób, że promienie są kierowane w obszary lokalnie jaśniejsze. Takie podejście pozwala wydobyć szczegóły w jasnych miejscach obrazów. W ten sposób, niejako, faworyzowane są te ścieżki, które prowadzą do źródeł światła, a pomijane te, które nie wnoszą lokalnych zmian lub są po prostu ciemne. Takie podejście jest w dużym stopniu zgodne z naszą percepcją – w zróżnicowanym tonalnie obrazie łatwiej zauważyć szczegóły, czy zmiany barwy, w jasnych obszarach niż w obszarach ciemnych

Warto także zwrócić uwagę na wady próbkowania Metropolis w śledzeniu promieni. Jest to próbkowanie zależne od stanu (rozkładu barw) pikseli obrazu. Nie jest metodą uniwersalną, która przyspieszy zawsze obliczenia. Jeśli scena jest równomiernie oświetlona lub decydujące w oświetleniu jest bezpośrednie źródło światła, to tradycyjne śledzenie ścieżek da szybciej lepsze rozwiązanie. MLT sprawdzi się jednak zawsze tam gdzie występują widoczne lokalne zmiany oświetlenia i przeważa oświetlenie pośrednie (po wielokrotnych odbiciach).