Руска рулетка

В Монте Карло интегрирането, руската рулетка е една относително сложна (за разбиране) техника, която се обяснява най-добре чрез пример.

Представете си, че сте ръководител на китайския национален отбор по информатика - това са ~2000 китайчета, които се борят за правото си да бъдат пратени на международната олимпиада (за момент игнорирайте нереализма на ситуацията - все пак, само 2000 китайчета!). Както и да е, след множество вътрешни контролни, всеки ученик има рейтинг, който отразява неговите умения и е реално число между 0 и 1 (0 = много слаб състезател; 1 = един от най-добрите състезатели).
За нещастие, обаче, при преразпределението на бюджета, вашите финанси са значително поорязани и затова се налага да разпуснете част от децата. Един по-практичен метод би бил да ги сортирате по рейтинг и да оставите само тези с най-голям рейтинг. Но сортирането не винаги е възможно (а в Монте Карло интегрирането - никога). Затова ще приложим друга схема. Ако даден ученик има рейтинг x (x e [0..1]), то, с вероятност 1-x ще пратим ученика вкъщи (еквивалентно: с вероятност x той ще остане). Така, добрите ученици почти сигурно ще останат, докато слабите, в голямата си част, ще бъдат разпуснати.

Окей, сега си представете, че сме имали 50 китайчета с рейтинг 0.2. Математическото очакване е, че след "чистката" ще останат само 10 от тях. Въпросът, който ни задават, е

"Ако бяхте пратили 50-те китайчета, колко медала щяха да завоюват от международната олимпиада?".

Ние пращаме само 10, но зад всяко от изпратените стоят още 4 другарчета, които "не са имали късмета". Нека тези 10 завоюват Y медала. Бихме очаквали 50-те да завоюват 5 пъти повече медали. Иначе казано: Y * (1/x), където x е 0.2.

Макар и не толкова интуитивно, същата идея може да се приложи и върху цялата група от 2000 китайчета първоначално. Нека ни бяха питали: "Тези 2000 колко медала щяха да вземат, ако ги бяхме пратили всичките" (не се безпокойте, медали има достатъчно). За произволно китайче с рейтинг x, оцеляло от чистката, може да приемем, че е представител на групата от около 1/х китайчета с подобен на него рейтинг, като останалите от групата са разпуснати. Затова, неговият принос от олимпиадата умножаваме с 1/x, за да отчетем предполагаемия принос от цялата група. Иначе казано, ако номерираме всички оцелели от чистката китайчета с числата от 1 до N, X_i показва рейтинга на i-тото китайче, и Y_i показва броя завоювани медали от него (0 или 1), то очаквания брой медали от 2000-те китайчета е SUM_{{i = 1..N}}(Y_i / X_i)

Как се прилага руската рулетка в контекста на алгоритъма Path tracing? Тук, вместо китайчета, имаме пътища (още недостроени), а техния рейтинг е изразен от pathMultiplier. По-точно, rating = pathMultiplier.intensity(). При rating >= 1, прилагаме си досегашния алгоритъм без модификации. Ако rating < 1, то трябва да изберем дали да "убием" пътя или не, на случаен принцип. Вероятността пътят да бъде убит трябва да е (1 - rating) (това е руската рулетка). Под "убийство" разбираме следното - прекратавяме строежа на пътя и връщаме черно. Ако пътят оцелее от руската рулетка, то по-нататъшния принос от този път (т.е. това, което pathtrace() връща чрез return) трябва да умножим с 1 / rating.

Добавете един bool с име roulette към GlobalSettings. Ако е включен, прилагайте техниката на руската рулетка в pathtrace(). Увеличете maxTraceDepth на 8 и направете измервания при включена и изключена рулетка. При включена, алгоритъмът трябва да работи много по-бързо (двойно или тройно), но да връща по-шумен резултат при същия брой пътища на пиксел (с повече "горещи пиксели", идващи от силно безперспективни пътища, които руската рулетка все пак е избрала да продължи). При правилна реализация, резултатната картинка при включена/изключена рулетка не трябва да е осезаемо по-ярка или по-тъмна.
Като допълнително подобрение, с цел подтискане на шума: направете руската рулетка да не се прилага, ако текущата дълбочина е под 4. Това все още трябва да увеличава скоростта на рендериране поне двойно.