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
    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:

moire artifacts

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

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.

  • $\begingroup$ 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. $\endgroup$ Sep 13, 2017 at 10:46
  • $\begingroup$ 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. $\endgroup$
    – sydd
    Sep 13, 2017 at 12:56
  • $\begingroup$ I think asking for "an algorithm", as you've done, gives the right message. $\endgroup$ Sep 13, 2017 at 13:16


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.