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:

Moire artifacts

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

same Moire artifacts here too

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.

  • $\begingroup$ Note: I've asked the same question in the comp sci Stack Exchange, but received no answers: cs.stackexchange.com/questions/81169/… $\endgroup$ – sydd Oct 25 '17 at 20:34
  • $\begingroup$ I don't understand, never heard of light casting before. Isn't what you are trying to do similar to ray-tracing? Just shoot rays from the origin, for every single pixel. That way there won't be any uncolored pixel. $\endgroup$ – gallickgunner Oct 26 '17 at 13:02
  • $\begingroup$ @wandering-warrior That would be waay too slow, this is for a game. To save GPU time I am shooting rays only to the edge of the circle, these colour the path they trace. Just they don't do it evenly, so the artifacts. $\endgroup$ – sydd Nov 1 '17 at 1:56

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.

  • $\begingroup$ Got any links how to do this in a 2D engine? I've tried to write it in a "gather" fashion in a fragment shader - its unbearably slow since it does so many duplicate calculations. $\endgroup$ – sydd Oct 26 '17 at 13:45
  • $\begingroup$ 2D is no different than 3D. check out youtu.be/0YdPHNJjSxI. In convential CPU-style thinking you'll tell yourself for all lights: modify affected pixels. In GPU thinking your start point is already inside the for all pixel loop. So you need the all lights loop "nested" in your fragment code. You must have a structured buffer (or texture, or constant buffer) that tells you lights information so you access light[index].position and SV_Position being the fragment pos, you have the light vector. from this you can do a usual lambert & attenuation calculation $\endgroup$ – v.oddou Oct 30 '17 at 2:09
  • $\begingroup$ You mean something like this? github.com/matyasf/sparrow-game/blob/master/SparrowGame.Shared/… This is sadly dog slow, I can render ~5-10 lights. The compute shader above can render ~200 with the same FPS. $\endgroup$ – sydd Oct 30 '17 at 23:16
  • $\begingroup$ It's slow because it is doing step marching. marching is necessary only for volumetric effects of complex intersection routines. why do you need this ? $\endgroup$ – v.oddou Oct 31 '17 at 2:59
  • $\begingroup$ Because I want volumetric effects, like my original algorithm :) This is not just a simple shadow cast, I want something new. It would be able to render nice god rays, light trough smoke, fog, coloured glass, etc. My aim is to make something that looks a bit different than everything else out there. $\endgroup$ – sydd Oct 31 '17 at 8:25

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.