Path tracer isn't converging

Question

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 inputImageget 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.

Answer 1

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.