Is Russian Roulette really the answer?

Question

I have seen that in some implementations of Path Tracing, an approach called Russian Roulette is used to cull some of the paths and share their contribution among the other paths.

I understand that rather than following a path until it drops below a certain threshold value of contribution, and then abandoning it, a different threshold is used and paths whose contribution is below that threshold are only terminated with some small probability. The other paths have their contribution increased by an amount corresponding to sharing the lost energy from the terminated path. It isn't clear to me whether this is to correct a bias introduced by the technique, or whether the whole technique is itself necessary to avoid bias.

• Does Russian Roulette give an unbiased result?
• Is Russian Roulette necessary for an unbiased result?

That is, would using a tiny threshold and just terminating a path the moment it drops below that threshold give a more biased or less biased result?

Given an arbitrarily large number of samples, would both approaches converge on an unbiased resulting image?

I'm looking to understand the underlying reason for using the Russian Roulette approach. Is there a significant difference in speed or quality?

---

I understand that the energy is redistributed among other rays in order to preserve total energy. However, could this redistribution not still be done if the ray were terminated on dropping below a fixed threshold, rather than having a randomly determined life span after reaching that threshold?

Conversely, if the energy that would be lost by terminating a ray without redistributing its energy is eventually lost anyway (as the rays to which it is redistributed are also eventually terminated), how does this improve the situation?

Answer 1

In order to understand Russian Roulette, let's look at a very basic backward path tracer:

void RenderPixel(uint x, uint y, UniformSampler *sampler) {
    Ray ray = m_scene->Camera.CalculateRayFromPixel(x, y, sampler);

    float3 color(0.0f);
    float3 throughput(1.0f);

    // Bounce the ray around the scene
    for (uint bounces = 0; bounces < 10; ++bounces) {
        m_scene->Intersect(ray);

        // The ray missed. Return the background color
        if (ray.geomID == RTC_INVALID_GEOMETRY_ID) {
            color += throughput * float3(0.846f, 0.933f, 0.949f);
            break;
        }

        // We hit an object

        // Fetch the material
        Material *material = m_scene->GetMaterial(ray.geomID);
        // The object might be emissive. If so, it will have a corresponding light
        // Otherwise, GetLight will return nullptr
        Light *light = m_scene->GetLight(ray.geomID);

        // If we hit a light, add the emmisive light
        if (light != nullptr) {
            color += throughput * light->Le();
        }

        float3 normal = normalize(ray.Ng);
        float3 wo = normalize(-ray.dir);
        float3 surfacePos = ray.org + ray.dir * ray.tfar;

        // Get the new ray direction
        // Choose the direction based on the material
        float3 wi = material->Sample(wo, normal, sampler);
        float pdf = material->Pdf(wi, normal);

        // Accumulate the brdf attenuation
        throughput = throughput * material->Eval(wi, wo, normal) / pdf;


        // Shoot a new ray

        // Set the origin at the intersection point
        ray.org = surfacePos;

        // Reset the other ray properties
        ray.dir = wi;
        ray.tnear = 0.001f;
        ray.tfar = embree::inf;
        ray.geomID = RTC_INVALID_GEOMETRY_ID;
        ray.primID = RTC_INVALID_GEOMETRY_ID;
        ray.instID = RTC_INVALID_GEOMETRY_ID;
        ray.mask = 0xFFFFFFFF;
        ray.time = 0.0f;
    }

    m_scene->Camera.FrameBuffer.SplatPixel(x, y, color);
}

IE. we bounce around the scene, accumulating color and light attenuation as we go. In order to be completely mathematically unbiased, bounces should go to infinity. But this is unrealistic, and as you noted, not visually necessary; for most scenes, after a certain number of bounces, say 10, the amount of contribution to the final color is very very minimal.

So in order to save computing resources, many path tracers have a hard limit to the number of bounces. This adds bias.

That said, it's hard to choose what that hard limit should be. Some scenes look great after 2 bounces; others (say with transmission or SSS) may take up to 10 or 20.

If we choose too low, the image will be visibly biased. But if we choose too high, we're wasting computation energy and time.

One way to solve this, as you noted, is to terminate the path after we reach some threshold of attenuation. This also adds bias.

Clamping after a threshold, will work, but again, how do we choose the threshold? If we choose too large, the image will be visibly biased, too small, and we're wasting resources.

Russian Roulette attempts to solve these problems in an unbiased way. First, here is the code:

void RenderPixel(uint x, uint y, UniformSampler *sampler) {
    Ray ray = m_scene->Camera.CalculateRayFromPixel(x, y, sampler);

    float3 color(0.0f);
    float3 throughput(1.0f);

    // Bounce the ray around the scene
    for (uint bounces = 0; bounces < 10; ++bounces) {
        m_scene->Intersect(ray);

        // The ray missed. Return the background color
        if (ray.geomID == RTC_INVALID_GEOMETRY_ID) {
            color += throughput * float3(0.846f, 0.933f, 0.949f);
            break;
        }

        // We hit an object

        // Fetch the material
        Material *material = m_scene->GetMaterial(ray.geomID);
        // The object might be emissive. If so, it will have a corresponding light
        // Otherwise, GetLight will return nullptr
        Light *light = m_scene->GetLight(ray.geomID);

        // If we hit a light, add the emmisive light
        if (light != nullptr) {
            color += throughput * light->Le();
        }

        float3 normal = normalize(ray.Ng);
        float3 wo = normalize(-ray.dir);
        float3 surfacePos = ray.org + ray.dir * ray.tfar;

        // Get the new ray direction
        // Choose the direction based on the material
        float3 wi = material->Sample(wo, normal, sampler);
        float pdf = material->Pdf(wi, normal);

        // Accumulate the brdf attenuation
        throughput = throughput * material->Eval(wi, wo, normal) / pdf;


        // Russian Roulette
        // Randomly terminate a path with a probability inversely equal to the throughput
        float p = std::max(throughput.x, std::max(throughput.y, throughput.z));
        if (sampler->NextFloat() > p) {
            break;
        }

        // Add the energy we 'lose' by randomly terminating paths
        throughput *= 1 / p;


        // Shoot a new ray

        // Set the origin at the intersection point
        ray.org = surfacePos;

        // Reset the other ray properties
        ray.dir = wi;
        ray.tnear = 0.001f;
        ray.tfar = embree::inf;
        ray.geomID = RTC_INVALID_GEOMETRY_ID;
        ray.primID = RTC_INVALID_GEOMETRY_ID;
        ray.instID = RTC_INVALID_GEOMETRY_ID;
        ray.mask = 0xFFFFFFFF;
        ray.time = 0.0f;
    }

    m_scene->Camera.FrameBuffer.SplatPixel(x, y, color);
}

Russian Roulette randomly terminates a path with a probability inversely equal to the throughput. So paths with low throughput that won't contribute much to the scene are more likely to be terminated.

If we stop there, we're still biased. We 'lose' the energy of the path we randomly terminate. To make it unbiased, we boost the energy of the non-terminated paths by their probability to be terminated. This, along with being random, makes Russian Roulette unbiased.

To answer your last questions:

1. Does Russian Roulette give an unbiased result?
   • Yes
2. Is Russian Roulette necessary for an unbiased result?
   • Depends on what you mean by unbiased. If you mean mathematically, then yes. However, if you mean visually, then no. You just have to choose you max path depth and cutoff threshold very very carefully. This can be very tedious since it can change from scene to scene.
3. Can you use a fixed probability (cut-off), and then redistribute the 'lost' energy. Is this unbiased?
   • If you use a fixed probability, you are adding bias. By redistributing the 'lost' energy, you reduce the bias, but it is still mathematically biased. To be completely unbiased, it must be random.
4. If the energy that would be lost by terminating a ray without redistributing its energy is eventually lost anyway (as the rays to which it is redistributed are also eventually terminated), how does this improve the situation?
   • Russian Roulette only stops the bouncing. It doesn't remove the sample completely. Also, the 'lost' energy is accounted for in the bounces up to the termination. So the only way for the the energy to be 'eventually lost anyway' would be to have a completely black room.

In the end, Russian Roulette is a very simple algorithm that uses a very small amount of extra computational resources. In exchange, it can save a large amount of computational resources. Therefore, I can't really see a reason not to use it.

Answer 2

The Russian roulette technique itself is a way of terminating paths without introducing systemic bias. The principle is fairly straightforward: if at a particular vertex you have a 10% chance of arbitrarily replacing the energy with 0, and if you do that an infinite number of times, you will see 10% less energy. The energy boost just compensates for that. If you did not compensate for the energy lost due to path termination, then Russian roulette would be biased, but the whole technique is a useful method of avoiding bias.

If I was an adversary looking to prove that the "terminate paths whose contribution is less than some small fixed value" technique is biased, I would construct a scene with lights so dim that the contributing paths are always less than that value. Perhaps I'm simulating a low-light camera.

But of course you could always expose the fixed value as a tweakable parameter to the user, so they can drop it even further if their scene happens to be low-light. So let's disregard that example for a minute.

What happens if I consider an object that is illuminated by a lot of very low-energy paths that are collected by a parabolic reflector? Low energy paths don't necessarily bounce around indiscriminately in a manner that you can completely neglect. Similarly reasoning applies for, e.g., cutting off paths after a fixed number of bounces: you can construct a scene with a path that bounces off a series of 20 mirrors before hitting an object.

Another way of looking at it: if you set the contribution of a path to 0 after it falls below some fixed epsilon, how do you correct for that energy loss? You aren't simply reducing the total energy by some fraction. You don't know anything about how much energy you are neglecting, because you are cutting off at some contribution threshold before you know the other factor: the incident energy.

Answer 3

Just to expand on some of the other answers, the proof that Russian Roulette does not give a biassed result is very simple.

Suppose that you have some random variable $F$ which is the sum of several terms:

$$F = F_1 + \cdots + F_N$$

Replace each term with:

$$F'_i = \left\{ \begin{array}{ll} \frac{1}{p_i} F_i & \hbox{with probability } p_i \\ 0 & \hbox{otherwise} \end{array} \right.$$

Then:

$$E[F'_i] = p_i \times \frac{1}{p_i}E[F_i] + (1-p_i) \times 0 = E[F_i]$$

Note that it doesn't matter what probabilities you pick for $p_i$. The expected value of the terms, and hence the expected value of $F$, is the same.