<h1>Forking defeats Russian Roulette</h1>

<p>A key difference between path tracing and ray tracing is that unlike ray tracing, which can have a branching tree of rays splitting at each intersection, path tracing follows a single path with no recursive branching. </p>

<p>Russian Roulette requires that only one recursive function call be made each time through the function. However, the code currently branches at each function call, so each call triggers several more calls. This prevents the roulette process from killing the recursion. New recursive function calls are being introduced faster than they can be killed off. The problem is similar to a <a href="https://en.wikipedia.org/wiki/Fork_bomb" rel="noreferrer">fork bomb</a>, growing exponentially, so that the killing cannot keep up.</p>

<p>The clue that led me to look for this problem was that you said that it works fine when the number of Monte Carlo samples is set to 1. In this case the function is only called once each time, so the recursion can only maintain the same number of rays, not introduce new ones. So there is no forking and when the recursion is killed that is the end of it.</p>

<p>If you want more than one Monte Carlo sample per pixel, you will need to move that loop out of the recursive function so that the number of samples does not grow.</p>

<h1>Pseudocode examples</h1>

<h3>Approach 1</h3>

<pre><code>function RECURSIVE_FUNCTION()
{
    RECURSIVE_FUNCTION()
}
</code></pre>

<p><em>This sends 1 ray that bounces around the scene but does not fork.</em></p>

<hr>

<h3>Approach 2</h3>

<pre><code>function RECURSIVE_FUNCTION()
{
    for(var i = 0; i &lt; 10; ++i)
    {
        RECURSIVE_FUNCTION()
    }
}
</code></pre>

<p><em>This sends 10 rays that each spawn 10 new rays, giving 100 rays, then 1000, then 10000...</em></p>

<hr>

<p>If you want 10 samples per pixel, use the function from approach 1, and call it 10 times. Currently the code uses approach 2, which causes far more than 10 samples per pixel, exploding to arbitrarily large numbers of rays until the stack overflows.</p>

<p><em>Note that I've simplified the recursive calls in the pseudocode for the sake of explanation, but the same problem presents itself in the real code:</em> <code>traceRay</code> <em>calls</em> <code>indirectLighting</code> <em>once, then</em> <code>indirectLighting</code> <em>calls</em> <code>traceRay</code> <em>multiple times depending on</em> <code>MC_SAMPLES</code><em>, then each of those calls to</em> <code>traceRay</code> <em>calls</em> <code>indirectLighting</code> <em>again. Each time through this cycle there are</em> <code>MC_SAMPLES</code> <em>times as many calls as the previous time, and Russian Roulette cannot cull enough of these calls to prevent runaway growth.</em></p>

CC BY-SA 3.0
2017-05-05T18:02:42.320Z
I am wondering where it would be better to put the code for Russian Roulette: in traceRay or in the indirectLighting function?
vendrick
CC BY-SA 3.0
2017-05-05T19:33:58.363Z
That sounds like a potential new question...
trichoplax is on Codidact now
CC BY-SA 3.0
2017-04-30T11:09:43.513Z
2017-04-30T21:35:32.853Z
2017-04-30T21:35:32.853Z
trichoplax is on Codidact now
<p>I am trying to write my own path tracer in JavaScript, but I have a problem with the implementation of russian roulette. First, let me describe how my path tracer works.</p>

<p>I have a function called <em>traceRay</em> where I am looking for ray-objects intersections and doing some shading. Shading is divided into direct and indirect illumination. I have a separate function that does Importance Sampling only and it is being called inside <em>traceRay</em>. This function gets Monte Carlo samples count and max recursion depth as parameters, generates sample rays and calls <em>traceRay</em> again (if max recursion depth is not exceeded).</p>

<pre><code>RayTracer.indirectLighting = function(scene, camera, intersectionPoint, normal, options)
{
  var prob = 0.5;
  var oneOverProb = 1/prob;
  if(Math.random() &lt; prob) return new Vector(0,0,0);

  var diffuse = new Vector(0, 0, 0);
  var specular = new Vector(0, 0, 0);

  if(options.MC_SAMPLES &gt; 0)// &amp;&amp; options.MC_DEPTH &gt; 0)
  {
    var basis = createCoordinationSystem(normal);
    var sampleVector, sampleTransformed, mcRay;
    for(var i = 0; i &lt; options.MC_SAMPLES; ++i)
    {
      sampleVector = getCosineWeightedSample(Math.random(), Math.random());
      sampleTransformed = new Vector(sampleVector.x * basis.tangent.x + sampleVector.y * normal.x + sampleVector.z * basis.bitangent.x,
                                 sampleVector.x * basis.tangent.y + sampleVector.y * normal.y + sampleVector.z * basis.bitangent.y,
                                 sampleVector.x * basis.tangent.z + sampleVector.y * normal.z + sampleVector.z * basis.bitangent.z);
      mcRay = new Ray(intersectionPoint.clone().add(sampleTransformed.clone().mul(0.000001)), sampleTransformed);

      diffuse.add(RayTracer.traceRay(mcRay, scene, camera, {
        MC_DEPTH: options.MC_DEPTH - 1,
        MC_SAMPLES: options.MC_SAMPLES,
        AREA_LIGHT_SAMPLES: options.AREA_LIGHT_SAMPLES
      }));
    }
    diffuse.mul(1 / options.MC_SAMPLES);
  }
  return Vector.add(diffuse, specular).mul(oneOverProb);
}


RayTracer.traceRay = function(ray, scene, camera, options)
{
  var color = new Vector(0, 0, 0);
  //Depth test - finding closest object
  var minT = 1e12, currentT;
  var object = null;
  var objectI;
  for(var i = 0; i &lt; scene.objects.length; ++i)
  {
    currentT = scene.objects[i].intersects(ray);
    if(currentT &gt; 0 &amp;&amp; currentT &lt; minT)
    {
      objectI = i;
      minT = currentT;
      object = scene.objects[i];
    }
  }

  var emissiveObjects = [];
  for(var i = 0; i &lt; scene.objects.length; ++i)
  {
    if(i == objectI) continue;
    else if(scene.objects[i].isFinite &amp;&amp; scene.objects[i].material.emittance.lengthSq() &gt; 0.3)
      emissiveObjects.push(scene.objects[i]);
  }

  if(object == null) return new Vector(0, 0, 0);

  var indirectLighting = new Vector(0, 0, 0);
  var directLighting = new Vector(0, 0, 0);

  var intersectionPoint = ray.getPoint(minT);
  var normal = object.getNormalAt(intersectionPoint);
  var toEye = camera.position.clone().sub(intersectionPoint).normalize();
  var albedo = object.material.color.clone().mul(object.material.diffuseFactor);

  //Direct illumination
  for(var n = 0; n &lt; scene.lights.length; ++n)
  {
    //Searching for objects occluding light
    var shadowRay = scene.lights[n].getShadowRay(intersectionPoint);
    var inShadow = RayTracer.visabilityTest(shadowRay, scene.objects,
  scene.lights[n].occlusionTestLimit(shadowRay)).occlusion;

    if(!inShadow)
    {
      var lighting = scene.lights[n].getLightingInfo(intersectionPoint, normal, toEye);

      directLighting.add(scene.lights[n].color.clone().mul(
    lighting.diffuse * lighting.attenuation * scene.lights[n].intensity / Math.PI))
    }
  }

  color.add(Vector.componetesMul(object.material.color, scene.ambient));

  directLighting.add(RayTracer.sampleAreaLights(scene, emissiveObjects, intersectionPoint, normal, options.AREA_LIGHT_SAMPLES));
  indirectLighting = RayTracer.indirectLighting(scene, camera, intersectionPoint, normal, options);

  color.add(object.material.emittance.clone().clamp(0, 1));
  color.add(Vector.componetesMul(directLighting.add(indirectLighting), albedo));

  return color
};
</code></pre>

<p>The problem is that when I remove recursion depth test and add russian roulette to my indirect illumination function I get "Maximum call stack size exceeded" error. Same problem is when I implement roulette in <em>traceRay</em> function. But when I use only one Monte Carlo sample, everything works fine.</p>

<p>My russian roulette algorithm works as follows: at the beginning of a function, I am checking if a pseudo-random number is less then some constant threshold. If so, I am returning black color. In other case, function does what it would do without roulette, but the returned value is divided by the threshold.</p>

<p>So, the question is: how do I implement Russian Roulette properly?</p>

CC BY-SA 3.0
2017-04-27T04:24:29.463Z
Can we see some code for this? It sounds like you function continues recursing when it meets the RR condition so it's probably a coding problem rather than a problem with the algorithm. As a side note, it is possible implement  path tracing without needing recursion, GPU implementations rely on this.
PaulHK
CC BY-SA 3.0
2017-04-27T04:47:58.113Z
Have you stepped through it in a debugger to see whether the pseudo-random number is being generated the way you think? And that everything else you're doing is happening the way you think?
user1118321
CC BY-SA 3.0
2017-04-27T08:38:31.060Z
"Unclear wht you're asking" isn't very specific, but I'm closing this question because it can't be answered without the code that produces the error. If you [edit] your question and make it answerable, it can be reopened.
Dan Hulme
CC BY-SA 3.0
2017-04-27T14:58:56.470Z
Sorry! I've edited my question.
vendrick
CC BY-SA 3.0
2017-04-28T09:47:11.397Z
why did you comment out the depth test? it's what should prevent the stack overflow
ratchet freak
CC BY-SA 3.0
2017-04-28T17:12:47.760Z
@ratchetfreak It is, because Russian Roulette algorithm should stop the resursion randomly (to keep the estimator unbiased). As far as I know, I should be like that.
vendrick
CC BY-SA 3.0
2017-05-04T19:43:24.273Z
I've added the pathtracing tag again, and I've left the raytracing tag too as they both seem relevant.
trichoplax is on Codidact now
<raytracing><pathtracing><javascript>
Russian Roulette - Maximum call stack size exceeded
vendrick
# Russian Roulette - Maximum call stack size exceeded

(Asked by: username_0 on 2017-04-26)

I am trying to write my own path tracer in JavaScript, but I have a problem with the implementation of russian roulette. First, let me describe how my path tracer works.

I have a function called *traceRay* where I am looking for ray-objects intersections and doing some shading. Shading is divided into direct and indirect illumination. I have a separate function that does Importance Sampling only and it is being called inside *traceRay*. This function gets Monte Carlo samples count and max recursion depth as parameters, generates sample rays and calls *traceRay* again (if max recursion depth is not exceeded).

```
RayTracer.indirectLighting = function(scene, camera, intersectionPoint, normal, options)
{
  var prob = 0.5;
  var oneOverProb = 1/prob;
  if(Math.random() < prob) return new Vector(0,0,0);

  var diffuse = new Vector(0, 0, 0);
  var specular = new Vector(0, 0, 0);

  if(options.MC_SAMPLES > 0)// && options.MC_DEPTH > 0)
  {
    var basis = createCoordinationSystem(normal);
    var sampleVector, sampleTransformed, mcRay;
    for(var i = 0; i < options.MC_SAMPLES; ++i)
    {
      sampleVector = getCosineWeightedSample(Math.random(), Math.random());
      sampleTransformed = new Vector(sampleVector.x * basis.tangent.x + sampleVector.y * normal.x + sampleVector.z * basis.bitangent.x,
                                 sampleVector.x * basis.tangent.y + sampleVector.y * normal.y + sampleVector.z * basis.bitangent.y,
                                 sampleVector.x * basis.tangent.z + sampleVector.y * normal.z + sampleVector.z * basis.bitangent.z);
      mcRay = new Ray(intersectionPoint.clone().add(sampleTransformed.clone().mul(0.000001)), sampleTransformed);

      diffuse.add(RayTracer.traceRay(mcRay, scene, camera, {
        MC_DEPTH: options.MC_DEPTH - 1,
        MC_SAMPLES: options.MC_SAMPLES,
        AREA_LIGHT_SAMPLES: options.AREA_LIGHT_SAMPLES
      }));
    }
    diffuse.mul(1 / options.MC_SAMPLES);
  }
  return Vector.add(diffuse, specular).mul(oneOverProb);
}

RayTracer.traceRay = function(ray, scene, camera, options)
{
  var color = new Vector(0, 0, 0);
  //Depth test - finding closest object
  var minT = 1e12, currentT;
  var object = null;
  var objectI;
  for(var i = 0; i < scene.objects.length; ++i)
  {
    currentT = scene.objects[i].intersects(ray);
    if(currentT > 0 && currentT < minT)
    {
      objectI = i;
      minT = currentT;
      object = scene.objects[i];
    }
  }

  var emissiveObjects = [];
  for(var i = 0; i < scene.objects.length; ++i)
  {
    if(i == objectI) continue;
    else if(scene.objects[i].isFinite && scene.objects[i].material.emittance.lengthSq() > 0.3)
      emissiveObjects.push(scene.objects[i]);
  }

  if(object == null) return new Vector(0, 0, 0);

  var indirectLighting = new Vector(0, 0, 0);
  var directLighting = new Vector(0, 0, 0);

  var intersectionPoint = ray.getPoint(minT);
  var normal = object.getNormalAt(intersectionPoint);
  var toEye = camera.position.clone().sub(intersectionPoint).normalize();
  var albedo = object.material.color.clone().mul(object.material.diffuseFactor);

  //Direct illumination
  for(var n = 0; n < scene.lights.length; ++n)
  {
    //Searching for objects occluding light
    var shadowRay = scene.lights[n].getShadowRay(intersectionPoint);
    var inShadow = RayTracer.visabilityTest(shadowRay, scene.objects,
  scene.lights[n].occlusionTestLimit(shadowRay)).occlusion;

    if(!inShadow)
    {
      var lighting = scene.lights[n].getLightingInfo(intersectionPoint, normal, toEye);

      directLighting.add(scene.lights[n].color.clone().mul(
    lighting.diffuse * lighting.attenuation * scene.lights[n].intensity / Math.PI))
    }
  }

  color.add(Vector.componetesMul(object.material.color, scene.ambient));

  directLighting.add(RayTracer.sampleAreaLights(scene, emissiveObjects, intersectionPoint, normal, options.AREA_LIGHT_SAMPLES));
  indirectLighting = RayTracer.indirectLighting(scene, camera, intersectionPoint, normal, options);

  color.add(object.material.emittance.clone().clamp(0, 1));
  color.add(Vector.componetesMul(directLighting.add(indirectLighting), albedo));

  return color
};

```

The problem is that when I remove recursion depth test and add russian roulette to my indirect illumination function I get "Maximum call stack size exceeded" error. Same problem is when I implement roulette in *traceRay* function. But when I use only one Monte Carlo sample, everything works fine.

My russian roulette algorithm works as follows: at the beginning of a function, I am checking if a pseudo-random number is less then some constant threshold. If so, I am returning black color. In other case, function does what it would do without roulette, but the returned value is divided by the threshold.

So, the question is: how do I implement Russian Roulette properly?

**Tags:** raytracing, pathtracing, javascript

> **Comments:**
> **username_1**: Can we see some code for this? It sounds like you function continues recursing when it meets the RR condition so it's probably a coding problem rather than a problem with the algorithm. As a side note, it is possible implement  path tracing without needing recursion, GPU implementations rely on this.  
> **username_2**: Have you stepped through it in a debugger to see whether the pseudo-random number is being generated the way you think? And that everything else you're doing is happening the way you think?  
> **username_3**: "Unclear wht you're asking" isn't very specific, but I'm closing this question because it can't be answered without the code that produces the error. If you [edit] your question and make it answerable, it can be reopened.  
> **username_0**: Sorry! I've edited my question.  
> **username_4**: why did you comment out the depth test? it's what should prevent the stack overflow  
> **username_0**: @username_4 It is, because Russian Roulette algorithm should stop the resursion randomly (to keep the estimator unbiased). As far as I know, I should be like that.  
> **username_5**: I've added the pathtracing tag again, and I've left the raytracing tag too as they both seem relevant.  

---

## 1 answers

### Answer by username_5 on 2017-04-30. Score: 5 | Accepted answer

# Forking defeats Russian Roulette

A key difference between path tracing and ray tracing is that unlike ray tracing, which can have a branching tree of rays splitting at each intersection, path tracing follows a single path with no recursive branching.

Russian Roulette requires that only one recursive function call be made each time through the function. However, the code currently branches at each function call, so each call triggers several more calls. This prevents the roulette process from killing the recursion. New recursive function calls are being introduced faster than they can be killed off. The problem is similar to a [fork bomb](https://en.wikipedia.org/wiki/Fork_bomb), growing exponentially, so that the killing cannot keep up.

The clue that led me to look for this problem was that you said that it works fine when the number of Monte Carlo samples is set to 1. In this case the function is only called once each time, so the recursion can only maintain the same number of rays, not introduce new ones. So there is no forking and when the recursion is killed that is the end of it.

If you want more than one Monte Carlo sample per pixel, you will need to move that loop out of the recursive function so that the number of samples does not grow.

# Pseudocode examples

### Approach 1

```
function RECURSIVE_FUNCTION()
{
    RECURSIVE_FUNCTION()
}

```

*This sends 1 ray that bounces around the scene but does not fork.*

---

### Approach 2

```
function RECURSIVE_FUNCTION()
{
    for(var i = 0; i < 10; ++i)
    {
        RECURSIVE_FUNCTION()
    }
}

```

*This sends 10 rays that each spawn 10 new rays, giving 100 rays, then 1000, then 10000...*

---

If you want 10 samples per pixel, use the function from approach 1, and call it 10 times. Currently the code uses approach 2, which causes far more than 10 samples per pixel, exploding to arbitrarily large numbers of rays until the stack overflows.

*Note that I've simplified the recursive calls in the pseudocode for the sake of explanation, but the same problem presents itself in the real code:* `traceRay` *calls* `indirectLighting` *once, then* `indirectLighting` *calls* `traceRay` *multiple times depending on* `MC_SAMPLES`*, then each of those calls to* `traceRay` *calls* `indirectLighting` *again. Each time through this cycle there are* `MC_SAMPLES` *times as many calls as the previous time, and Russian Roulette cannot cull enough of these calls to prevent runaway growth.*

> **Comments:**
> **username_0**: I am wondering where it would be better to put the code for Russian Roulette: in traceRay or in the indirectLighting function?  
> **username_5**: That sounds like a potential new question...  

---

