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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.