Podręcznik Grafika komputerowa i wizualizacja

12.9 Rosyjska ruletka

Światło dociera do obserwatora po nieskończonej liczbie odbić pośrednich. Stosując całkowanie stochastyczne w realizacji śledzenia promienni wykorzystuje się skończoną liczbę promieni, skończona liczbę poziomów rekurencji, czy skończoną długość ścieżki promienia w śledzeniu ścieżek. Wybór liczby tego typu elementów jest zadaniem trudnym. Problemem jest podjęcie decyzji kiedy przerwać operacje rekurencyjne albo jakiej długości powinna być ścieżka promienia. Zawsze można przecież przeprowadzić jeszcze jedną iterację, pytanie tylko, czy uzyskane dzięki temu efekty warte będą nakładu włożonej dodatkowo pracy. Najczęściej stosowanym mechanizmem pozwalającym podjąć decyzję o odpowiednim przerwaniu obliczeń jest tzw. rosyjska ruletka.

Niech dane będzie wyrażenie X którego wartość jest wyznaczana w sposób rekurencyjny. Aby podjąć decyzję czy przerwać obliczenia wystarczyłoby sprawdzić, czy X mieści się w pewnym przedziale tzn. jeśli X<TX. Jednak takie podejście powoduje, że jeśli to postępowanie będzie wielokrotnie powtarzane (np. dla wielu pikseli) to określenie wartości granicznej przedziału wpływałoby w sposób systematyczny na uzyskiwane wartości. Zastosowanie rosyjskiej ruletki pozwala uniknąć tego problemu.

ALGORYTM  Rosyjskiej Ruletki

if  X<TX  then
begin

s = RAND[0,1] 
if  s < P  then   przerwij obliczenia
else  X = X/(1-P)

end

przy czym RAND[0,1]  generuje wartość losową o równomiernym rozkładzie z przedziału [0,1]. P jest przyjętym prawdopodobieństwem przerwania obliczeń. Zwiększając wartość P można zdecydować o szybszym przerwaniu obliczeń ale należy się liczyć z tym że wartość X będzie odbiegała od oczekiwanej. Zmniejszenie wartości P powoduje zwiększenie prawdopodobieństwa osiągnięcia dokładniejszej wartości X , zmniejsza wariancję. Ale konsekwencją zmniejszenia wartości P jest również wydłużenie czasu obliczeń.

Takie podejście nie zmienia wartości oczekiwanej,  . 

Rosyjska ruletka jest nieobciążoną metodą zakończenia obliczeń statystycznych na pewnym poziomie rekurencji. Taki mechanizm może być w analogiczny sposób stosowany w wyznaczaniu wartości całki czy określaniu długości ścieżki w śledzeniu ścieżek.

 Zastosowanie mechanizmu rosyjskiej ruletki w grafice komputerowej zostało zaproponowane przez J.Arvo i D.Kirka w 1990 roku [16]. Więcej na ten temat można również znaleźć w podręcznikach [2,6].