# How to prevent moire artifacts in this light casting algorithm?

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. 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
currentAlpha = (transpPixel.b + transpPixel.g * 10.0f + transpPixel.r * 100.0f) / 111.0f;
// calculate color
lightRay.rgb = min(colorPixel.rgb, lightRay.rgb) - (1.0f - currentAlpha) - transmit;
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 new algorithm to draw these light rays (or any other method that is highly parallellizable) 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 way too expensive, there must be a cheaper solution.

• Given the large amounts of code in the question, this is borderline off-topic, though I guess most people who know how to answer this kind of question will be familiar enough with OpenGL. Answerers, please bear in mind that, as a site, we're not looking for code dumps, and the question does ask for algorithms, not OpenGL hacks. – David Richerby Sep 13 '17 at 10:46
• The answer doesnt need any OpenGL knowlegde. Its a graphics algorithm, AKA how to cover a whole surface with lines coming from an origin in the most effective way (=use the fewest lines but there cant be any uncolored pixels). And yes, I need an algorithm for this (I guess there is a more formal mathematical way to ask this question), not an actual implementation. A link to a paper/pseudocode/wikipedia page is perfect. – sydd Sep 13 '17 at 12:56
• I think asking for "an algorithm", as you've done, gives the right message. – David Richerby Sep 13 '17 at 13:16