<p>I can find two possible reasons for the image not converging.</p>

<h2>#1. Every sample is the same</h2>

<p>For every sample, you generate random rays. You do that when you shoot the ray through a pixel (for anti-aliasing and DoF) and when you sample the hemisphere (for a new indirect bounce). The problem would be if for every sample, it would generate the same direction, then every sample is the exact same colour and you would not be doing any converging.</p>

<p>Most of the times when generating random numbers on the GPU, we generate them in advance and save them to a texture. When we need a number, we just sample the texture. Of course, for every pixel you want a different random value, and you would then use something like the thread id or the pixel coordinate to sample the texture. Then, every frame must also be different, so you would also use the frame counter to offset the thread id. But, notice how there is nothing to make sure that every sample also has a new random number. If for every sample you generate the same random direction, then every sample is the exact same colour and you would not be doing any converging.</p>

<p>This can often easily be fixed by keeping track of how many random numbers you 
already have generated and use that to offset every lookup. Basically, have a struct that holds the u and v values for the texture lookup. You initialize it with the thread id or pixel coordinate together with either the frame count or just a random number you generate on the CPU and pass it to the kernel as a global offset to the random values. Make sure that the struct is initialized in the very beginning of the kernel (where you initialize total_color). Then when you need a random number, you pass a reference to that struct to the method that generates a random number, it then looks up the random number in the texture and then it offsets the u and v values in the struct so that the next time you will get a different number.</p>

<p>Of course, I have not seen how you generate the rays (both on shooting a ray through a pixel and sampling a hemisphere), so I cannot say for sure if this is the problem, but it does seem very much like it.</p>

<h2>#2. Not properly averaging multiple frames</h2>

<blockquote>
  <p>I thought taking 64 samples 2 times, and averaging them would be analogous to taking 128 samples once.</p>
</blockquote>

<p>This is actually true. You average samples to get an image.
$$IMG1 = \frac{sample1 + sample2 + sample3 + samples4}{4}$$
Which you then do again for the second image.
$$IMG2 = \frac{sample5 + sample6 + sample7 + samples8}{4}$$
Which you then combine.
$$RESULT = \frac{IMG1 + IMG2}{2}=$$
$$\frac{\frac{sample1 + sample2 + sample3 + samples4}{4}+ \frac{sample5 + sample6 + sample7 + samples8}{4}}{2}=$$
$$\frac{\frac{sample1 + sample2 + sample3 + samples4 + sample5 + sample6 + sample7 + samples8}{4}}{2}=$$
$$\frac{sample1 + sample2 + sample3 + samples4 + sample5 + sample6 + sample7 + samples8}{8}$$
As you can see, it would indeed be like sampling twice as much.</p>

<p>However, your piece of code does not properly combine two images.</p>

<pre><code>float4 prev_color = read_imagef(outputImage, sampler, pixel);
color += prev_color;
color /= 2.0f;
write_imagef(outputImage, pixel, color);    
</code></pre>

<p>When we look at what you are doing.
$$outColor = \frac{newColor + oldColor}{2}$$
Where $outColor$ is the colour saved in the image.
$newColor$ is the colour you just calculated.
$oldColor$ is the color of the previous frame.</p>

<p>We see that it does what it is supposed to do, it averages both frames.</p>

<p>Of course, when the third frame comes around, $outColor$ becomes $oldColor$ as you swap the buffers of outputImage and inputImage. Thus, we can substitute it.
$$outColor = \frac{newColor + \frac{prevColor + oldColor}{2}}{2}$$
Where $prevColor$ was the color calculated the previous frame.</p>

<p>Although, this does not seem that good.
$newColor$ contributes <strong>50%</strong>, while $prevColor$ and $oldColor$ only contribute <strong>25%</strong>. This is a problem. You want every frame to contribute equally because then you are just adding up the samples. This means that you need to compensate for this.</p>

<p>There is an extremely simple solution to this. Multiply $oldColor$ by the amount of frames <em>excluding the current frame</em> and to then divide by the amount of frames <em>including the current frame</em>. you would then get this.
$$outColor = \frac{newColor + 2*\frac{prevColor + oldColor}{2}}{2 + 1}$$ Which would cancel out the divide and give you.
$$outColor = \frac{newColor + prevColor + oldColor}{3}$$ (The $+1$ is because we multiplied by 2 at the top, basically making it a total of 3 parts, and thus we need to divide by 3.)</p>

<p>If you would be calculating the fifth frame you would do it like this.</p>

<pre><code>float4 prev_color = read_imagef(outputImage, sampler, pixel);
color += prev_color * 4.0f;
color /= 5.0f;
write_imagef(outputImage, pixel, color);  
</code></pre>

<p>If you would be calculating the tenth frame you would do it like this.</p>

<pre><code>float4 prev_color = read_imagef(outputImage, sampler, pixel);
color += prev_color * 9.0f;
color /= 10.0f;
write_imagef(outputImage, pixel, color);  
</code></pre>

<p>This does mean that you need to pass through a counter which tells you how many frames you already have calculated. Most progressive or interactive path tracers actually only do one sample per frame (make sure that the ray through the pixel is randomly jittered), since it would take less time to calculate one frame, so that you see changes much earlier and often it is fine if you edit your scene using only one sample since you still get enough information.</p>

CC BY-SA 4.0
2018-08-26T17:40:20.573Z
Omg, I don't know about the 2nd problem but after reading your first point it actually does come to my mind, that my RNG uses global invocation IDs as seed. This do imply that at every launch, each pixel would get the same sequence of Random numbers. Will get back to this shortly after updating the results. Thanks.
gallickgunner
CC BY-SA 4.0
2018-08-26T18:45:06.263Z
@gallickgunner Here you find an example [ShaderToy](https://www.shadertoy.com/view/MlcczX) robustly accumulating (e.g., Welford) radiance estimates with 1spp/frame (and correct gamma correction) using different seeds per frame.
Matthias
CC BY-SA 4.0
2018-08-26T19:55:43.283Z
@bram0101 - Thanks a lot bro. Been on this for a couple of days and that's what happens if you don't rest :) Corrected both mistakes. The path tracer seems to converge now but I still have to take care of a better technique for RNG.  I am trying to tackle it with a similar approach mentioned in the link given by matthias. Use a time variable, passed by the cpu, to randomize the seed for each pixel, each pass.
gallickgunner
CC BY-SA 4.0
2018-08-26T16:51:40.470Z
2018-08-26T16:51:40.470Z
bram0101
<p>So I just completed a naive path tracer that uses explicit direct light sampling.
Problem is the path tracer isn't converging. It's like a raytracer, showing a single image on each pass. More info on how am I doing this is provided below. I am using OpenCL 1.1.</p>

<pre><code>  __kernel void render(__write_only image2d_t outputImage, __read_only image2d_t inputImage, int reset)
{
    float total_color;  // initalized to black
    for(int i = 0; i &lt; samples_x; i++)
    {
        for(int j = 0; j &lt; samples_y; j++)
        {       
            float4 direct_color, indirect_color; initialized black.
            Shoot ray through pixel.

            HitInfo new_info, old_info;
            If( !intersects(ray, old_info) )
            {
                total_color += Background_color
                continue;
            }
            else
            {
                direct_color = computeDirectLighting(old_info);             
                float4 color_arr[BOUNCES];
                float cosine_falloff[BOUNCES];
                for(int i = 0; i &lt; BOUNCES; i++)
                {       
                    new_ray = sampleHemisphere();

                    if( !intersects(new_ray, new_info) )
                    {
                        color_arr[i] = sky_color;
                        cosine_falloff[i] = max(dot(old_info.normal, new_ray.dir), 0.0f);
                        break;
                    }
                    else if ( intersects light source)
                    {
                        i--;
                        continue;
                        (Sample again)                      
                    }

                    color_arr[i] = computeDirectLighting(new_info);
                    cosine_falloff[i] = max(dot(old_info.normal, new_ray.dir), 0.0f);
                    old_info = new_info;
                }

                for(i = color_arr.length() - 1; i &gt;= 0; i--)
                {
                    indirect_color += color_arr[i];
                    indirect_color *= cosine_falloff[i];
                }
            }

            total_color += direct_color + indirect_color;

        }
    }


    }
    color /= (samples_x * samples_y);

    if ( reset == 1 )
    {   
        write_imagef(outputImage, pixel, color);
    }
    else
    {           
        float4 prev_color = read_imagef(outputImage, sampler, pixel);
        color += prev_color;
        color /= 2.0f;
        write_imagef(outputImage, pixel, color);    
    }
}
</code></pre>

<p>So this is the main outline. When the kernel runs the first time, <code>reset = 1</code>. Thus it writes the color directly into the output image. At each iteration, the buffers of <code>outputImage</code> and <code>inputImage</code>get swapped. After iteration 1, <code>reset = 0</code>.</p>

<p>This means at iteration 2, the kernel reads from the image it wrote to, in iteration 1. It then averages the new color and the previous color. </p>

<p>I thought taking 64 samples 2 times, and averaging them would be analogous to taking 128 samples once. If this is true then my image should converge, but it isn't. It shows only this image constantly.</p>

<p><strong>EDIT</strong>:- 
I think I should clear how I am calculating GI. After the first intersection. I send 1 ray directly to the light source (explicit direct light sampling). Then uniformly sample the hemisphere w.r.t area, and send another ray in this sampled direction. If the new ray hits light source, we sample again. This goes on <code>bounces times</code>. Each bounce the program stores the direct color due to explicit direct light sampling at each hit point. The indirect color is the sum of all these direct colors. Added a simple algo of what I did to the code snippet.</p>

<p>The <code>cosine_falloff</code> array holds all the weakening factors that should be multiplied to the respective indirect colors brought by secondary GI rays.</p>

<p><a href="https://i.sstatic.net/mueb5.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/mueb5.png" alt="enter image description here"></a></p>

<pathtracing><global-illumination><sampling><monte-carlo>
Path tracer isn't converging
gallickgunner
# Path tracer isn't converging

(Asked by: username_0 on 2018-08-26)

So I just completed a naive path tracer that uses explicit direct light sampling.
Problem is the path tracer isn't converging. It's like a raytracer, showing a single image on each pass. More info on how am I doing this is provided below. I am using OpenCL 1.1.

```
  __kernel void render(__write_only image2d_t outputImage, __read_only image2d_t inputImage, int reset)
{
    float total_color;  // initalized to black
    for(int i = 0; i < samples_x; i++)
    {
        for(int j = 0; j < samples_y; j++)
        {       
            float4 direct_color, indirect_color; initialized black.
            Shoot ray through pixel.

            HitInfo new_info, old_info;
            If( !intersects(ray, old_info) )
            {
                total_color += Background_color
                continue;
            }
            else
            {
                direct_color = computeDirectLighting(old_info);             
                float4 color_arr[BOUNCES];
                float cosine_falloff[BOUNCES];
                for(int i = 0; i < BOUNCES; i++)
                {       
                    new_ray = sampleHemisphere();

                    if( !intersects(new_ray, new_info) )
                    {
                        color_arr[i] = sky_color;
                        cosine_falloff[i] = max(dot(old_info.normal, new_ray.dir), 0.0f);
                        break;
                    }
                    else if ( intersects light source)
                    {
                        i--;
                        continue;
                        (Sample again)                      
                    }

                    color_arr[i] = computeDirectLighting(new_info);
                    cosine_falloff[i] = max(dot(old_info.normal, new_ray.dir), 0.0f);
                    old_info = new_info;
                }

                for(i = color_arr.length() - 1; i >= 0; i--)
                {
                    indirect_color += color_arr[i];
                    indirect_color *= cosine_falloff[i];
                }
            }

            total_color += direct_color + indirect_color;

        }
    }

    }
    color /= (samples_x * samples_y);

    if ( reset == 1 )
    {   
        write_imagef(outputImage, pixel, color);
    }
    else
    {           
        float4 prev_color = read_imagef(outputImage, sampler, pixel);
        color += prev_color;
        color /= 2.0f;
        write_imagef(outputImage, pixel, color);    
    }
}

```

So this is the main outline. When the kernel runs the first time, `reset = 1`. Thus it writes the color directly into the output image. At each iteration, the buffers of `outputImage` and `inputImage`get swapped. After iteration 1, `reset = 0`.

This means at iteration 2, the kernel reads from the image it wrote to, in iteration 1. It then averages the new color and the previous color.

I thought taking 64 samples 2 times, and averaging them would be analogous to taking 128 samples once. If this is true then my image should converge, but it isn't. It shows only this image constantly.

**EDIT**:-
I think I should clear how I am calculating GI. After the first intersection. I send 1 ray directly to the light source (explicit direct light sampling). Then uniformly sample the hemisphere w.r.t area, and send another ray in this sampled direction. If the new ray hits light source, we sample again. This goes on `bounces times`. Each bounce the program stores the direct color due to explicit direct light sampling at each hit point. The indirect color is the sum of all these direct colors. Added a simple algo of what I did to the code snippet.

The `cosine_falloff` array holds all the weakening factors that should be multiplied to the respective indirect colors brought by secondary GI rays.

[![enter image description here](https://i.sstatic.net/mueb5.png)](https://i.sstatic.net/mueb5.png)

**Tags:** pathtracing, global-illumination, sampling, monte-carlo


---

## 1 answers

### Answer by username_1 on 2018-08-26. Score: 3 | Accepted answer

I can find two possible reasons for the image not converging.

## #1. Every sample is the same

For every sample, you generate random rays. You do that when you shoot the ray through a pixel (for anti-aliasing and DoF) and when you sample the hemisphere (for a new indirect bounce). The problem would be if for every sample, it would generate the same direction, then every sample is the exact same colour and you would not be doing any converging.

Most of the times when generating random numbers on the GPU, we generate them in advance and save them to a texture. When we need a number, we just sample the texture. Of course, for every pixel you want a different random value, and you would then use something like the thread id or the pixel coordinate to sample the texture. Then, every frame must also be different, so you would also use the frame counter to offset the thread id. But, notice how there is nothing to make sure that every sample also has a new random number. If for every sample you generate the same random direction, then every sample is the exact same colour and you would not be doing any converging.

This can often easily be fixed by keeping track of how many random numbers you
already have generated and use that to offset every lookup. Basically, have a struct that holds the u and v values for the texture lookup. You initialize it with the thread id or pixel coordinate together with either the frame count or just a random number you generate on the CPU and pass it to the kernel as a global offset to the random values. Make sure that the struct is initialized in the very beginning of the kernel (where you initialize total\_color). Then when you need a random number, you pass a reference to that struct to the method that generates a random number, it then looks up the random number in the texture and then it offsets the u and v values in the struct so that the next time you will get a different number.

Of course, I have not seen how you generate the rays (both on shooting a ray through a pixel and sampling a hemisphere), so I cannot say for sure if this is the problem, but it does seem very much like it.

## #2. Not properly averaging multiple frames

> I thought taking 64 samples 2 times, and averaging them would be analogous to taking 128 samples once.

This is actually true. You average samples to get an image.
$$IMG1 = \frac{sample1 + sample2 + sample3 + samples4}{4}$$
Which you then do again for the second image.
$$IMG2 = \frac{sample5 + sample6 + sample7 + samples8}{4}$$
Which you then combine.
$$RESULT = \frac{IMG1 + IMG2}{2}=$$
$$\frac{\frac{sample1 + sample2 + sample3 + samples4}{4}+ \frac{sample5 + sample6 + sample7 + samples8}{4}}{2}=$$
$$\frac{\frac{sample1 + sample2 + sample3 + samples4 + sample5 + sample6 + sample7 + samples8}{4}}{2}=$$
$$\frac{sample1 + sample2 + sample3 + samples4 + sample5 + sample6 + sample7 + samples8}{8}$$
As you can see, it would indeed be like sampling twice as much.

However, your piece of code does not properly combine two images.

```
float4 prev_color = read_imagef(outputImage, sampler, pixel);
color += prev_color;
color /= 2.0f;
write_imagef(outputImage, pixel, color);    

```

When we look at what you are doing.
$$outColor = \frac{newColor + oldColor}{2}$$
Where $outColor$ is the colour saved in the image.
$newColor$ is the colour you just calculated.
$oldColor$ is the color of the previous frame.

We see that it does what it is supposed to do, it averages both frames.

Of course, when the third frame comes around, $outColor$ becomes $oldColor$ as you swap the buffers of outputImage and inputImage. Thus, we can substitute it.
$$outColor = \frac{newColor + \frac{prevColor + oldColor}{2}}{2}$$
Where $prevColor$ was the color calculated the previous frame.

Although, this does not seem that good.
$newColor$ contributes **50%**, while $prevColor$ and $oldColor$ only contribute **25%**. This is a problem. You want every frame to contribute equally because then you are just adding up the samples. This means that you need to compensate for this.

There is an extremely simple solution to this. Multiply $oldColor$ by the amount of frames *excluding the current frame* and to then divide by the amount of frames *including the current frame*. you would then get this.
$$outColor = \frac{newColor + 2\*\frac{prevColor + oldColor}{2}}{2 + 1}$$ Which would cancel out the divide and give you.
$$outColor = \frac{newColor + prevColor + oldColor}{3}$$ (The $+1$ is because we multiplied by 2 at the top, basically making it a total of 3 parts, and thus we need to divide by 3.)

If you would be calculating the fifth frame you would do it like this.

```
float4 prev_color = read_imagef(outputImage, sampler, pixel);
color += prev_color * 4.0f;
color /= 5.0f;
write_imagef(outputImage, pixel, color);  

```

If you would be calculating the tenth frame you would do it like this.

```
float4 prev_color = read_imagef(outputImage, sampler, pixel);
color += prev_color * 9.0f;
color /= 10.0f;
write_imagef(outputImage, pixel, color);  

```

This does mean that you need to pass through a counter which tells you how many frames you already have calculated. Most progressive or interactive path tracers actually only do one sample per frame (make sure that the ray through the pixel is randomly jittered), since it would take less time to calculate one frame, so that you see changes much earlier and often it is fine if you edit your scene using only one sample since you still get enough information.

> **Comments:**
> **username_0**: Omg, I don't know about the 2nd problem but after reading your first point it actually does come to my mind, that my RNG uses global invocation IDs as seed. This do imply that at every launch, each pixel would get the same sequence of Random numbers. Will get back to this shortly after updating the results. Thanks.  
> **username_2**: @username_0 Here you find an example [ShaderToy](https://www.shadertoy.com/view/MlcczX) robustly accumulating (e.g., Welford) radiance estimates with 1spp/frame (and correct gamma correction) using different seeds per frame.  
> **username_0**: @username_1 - Thanks a lot bro. Been on this for a couple of days and that's what happens if you don't rest :) Corrected both mistakes. The path tracer seems to converge now but I still have to take care of a better technique for RNG.  I am trying to tackle it with a similar approach mentioned in the link given by username_2. Use a time variable, passed by the cpu, to randomize the seed for each pixel, each pass.  

---

