How to prevent moire artifacts in this light casting algorithm?

Question

I am writing a 2D light casting algorithm with OpenGL compute shaders. The algorithm is simple: For each light source shoot out light rays from it, the ray begins at the light coordinates, it ends at a pixel in a circle around the light source (the light distance). When calculating the ray sample the pixel underneath it to model light colour/alpha changes. The algorithm works well, but a few pixels are missed, so they stay black causing Moire-like artifacts. The lightrays are calculated in a compute shader parallelly, one thread for each pixel in the light border circle. This means for example for a light with 256 radius, there are 2*256*Pi=1608 threads on the GPU, each calculating a single ray.

Heres the relevant compute shader code:

#define LOCAL_WG_SIZE 128u
const float PI = 3.1415926535897932384626433832795;
const float RAY_LENGTH = 256.0f;

// get the number of the current thread (0...1608)
uint renderNodeNum = local_coords;
// get the endpoint of the ray, it will be on a circle
endPoint.x = int(RAY_LENGTH * sin(float(renderNodeNum) * PI / 1024.0f)) + lightPos.x;
endPoint.y = int(RAY_LENGTH * cos(float(renderNodeNum) * PI / 1024.0f)) + lightPos.y;

// vector approximation. Works, but has moire artifacts.
// I've also tried Bresenham's line algorithm, but it leaves a cross shape as the light fades which looks ugly.
vec2 dt = normalize(vec2(endPoint - lightPos));
vec2 t = vec2(lightPos);
for (int k = 0; k < RAY_LENGTH; k++) {
    coords.x = int(t.x);
    coords.y = int(t.y);

    // calculate transparency
    transpPixel = imageLoad(transpTex, coords);   
    currentAlpha = (transpPixel.b + transpPixel.g * 10.0f + transpPixel.r * 100.0f) / 111.0f;
    // calculate color
    colorPixel = imageLoad(colorTex, coords);
    lightRay.rgb = min(colorPixel.rgb, lightRay.rgb) - (1.0f - currentAlpha) - transmit; 
    currentOutPixel = imageLoad(img_output, coords);
    currentOutPixel.rgb = max(currentOutPixel.rgb, lightRay.rgb);
    currentOutPixel.a = lightRay.a;
    // write color
    imageStore(img_output, coords, currentOutPixel);

    t += dt;
}

Heres is how it looks:

Another example with coloured background that shows light propagation, with the same artifacts:

So I need a better algorithm to draw these light rays (or any other method that is highly parallellizable on a compute shader) that does not leave out some pixels (the black spots in the pic). I could oversample the lightray (for example shoot twice as many rays), but this would be very expensive, there must be a cheaper solution.

Answer 1

In principle you avoid using scatter (casting) behavior with GPU. They have offered random output coordinate write out since only shader model 5 as a need for extreme situations. But you should as general rule write your GPU code in a "gather" fashion.

The difference: the hardware threads are logically soft-locked to one output position in the render target. The scheduler decides to what rectangle (or cube) in the target buffers, the kicked thread group will output results.

So you should work around the designated destination, and figure out the start; instead of working from some start and computing a dynamic destination.

This way not only will you please the hardware by avoiding contention, and race conditions completely; but also you'll avoid holes.