Russian roulette questions

[Bo]

Hi

I am not understanding Russian roulette when applied to Monte Carlo
integration.

Integral( f(p,o,w) * L( p, w) * cos(theta) * dw )

estimated by

1/N * Sum( f(p,o,Wi) * L(p,Wi) * cos(theta) / pdf( Wi ) )

Where each Wi is sampled or importance sampled in the integrating
domain.

For each evaluation with a particular Wi, we generate a canonical
uniform random variable Ei and check its value against a Q.

Only If Ei>Q, evaluate the expression and add to sum:
f(p,o,Wi) * L(p,Wi) * cos(theta) / pdf(Wi) / (1-Q)

I am not understanding how Q is determined, especially the part about
when f, L are small.

For example, since the brdf function f is usually between 0 and 1, and
I estimate that 20% of the times f is negligible, can I set Q to be
0.2?

But what if the expression is not evaluated because a Ei<Q, but f
happens to take a large value? Is that the source of the increased
variance discussed in the book?

Another confusion is:
1) are we somehow able to skipping calculating ALL terms of the sum
with negligible value?
2) Or are we skipping a percentage equal to Q from all the terms with
negligible value?
3) Or are we skipping a percentage equal to Q from all terms,
negligible or not?

Is Q constant for all Wi? It doesn't seem constant when path tracing
is discussed on page 745.

I can understand that in other applications such as shooting 1000
photons to a material with 20% absorption rate, I can use Russian
roulette to randomly remove 200 photons while not reducing energy
level for the other 800. But with Monte Carlo it is less intuitive.

Thanks

Bo

[Matt Pharr]

Interestingly enough, the termination probability (Q below) can be set
any way you want to, using any information you like (and the result
will be unbiased as long as you do the reweighting correctly with the
1/(1-Q) term as below.

So for direct lighting, a typical use would be to evaluate f() and L()
but not compute visibility (shadow ray). If f * L is small, then pick
a high Q value (terminate most of the time). If f*L is big, set Q to
zero if you want to, etc..

Or, if L() is expensive to evaluate, you can just decide based on the
f() value. Or you can set Q regardless of those values; anything is
correct mathematically.

The difficult part is improving efficiency (image variance per time
spent on computation). For example, it'd be silly to set Q = 0.5 all
of the time--although the result would still be correct in the limit,
for half the rays (probabilistically), you'd go through all the work
of tracing the eye ray, evaluating the BRDF, doing texturing, etc,
just to throw it all away (and weight the rays that weren't terminated
with a factor of 2x (1/(1-.5)). You can see there that you'd
definitely be less efficient compared to no Russian roulette at all.

Regarding the questions below, I think the following answers them all
(but send a followup note if you have more questions). The usual
Russian roulette algorithm is basically:

sum = 0
for i = 1 to N samples
a = evaluate the inexpensive terms of the estimate (f, f*L without
visibility, ...)
Q = g(a); // g() is any function of a. Or it can be constant, or
can return RandomFloat() if you don't care about efficiency :-)
if (RandomFloat() < Q)
// ignore this term of the sum, do nothing
else
sum += (1/N) * (evaluate the entire estimate, for real) / (1-Q);

I hope this helps.

Thanks,
-matt