<p>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.</p>

<p>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.</p>

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

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

CC BY-SA 3.0
2017-10-26T13:45:47.913Z
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.
sydd
CC BY-SA 3.0
2017-10-30T02:09:31.583Z
2D is no different than 3D. check out https://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
v.oddou
CC BY-SA 3.0
2017-10-30T23:16:17.257Z
You mean something like this? https://github.com/matyasf/sparrow-game/blob/master/SparrowGame.Shared/CustomMesh/FragShader.frag This is sadly dog slow, I can render ~5-10 lights. The compute shader above can render ~200 with the same FPS.
sydd
CC BY-SA 3.0
2017-10-31T02:59:19.233Z
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 ?
v.oddou
CC BY-SA 3.0
2017-10-31T08:25:02.957Z
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.
sydd
CC BY-SA 3.0
2017-11-01T01:50:09.557Z
Ok, then in my book there are only 2 ways : either you pay the simulation price, either you find an analytical solution (or a bunch of separated solutions, like Antoine Bouthors did in his 2008 paper for cloud rendering). I can't help you much beyond that
v.oddou
CC BY-SA 3.0
2017-10-26T05:17:38.033Z
2017-10-26T05:17:38.033Z
v.oddou
<p>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.</p>

<p>Heres the relevant compute shader code:</p>

<pre><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 &lt; 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;
}
</code></pre>

<p>Heres is how it looks:</p>

<p><a href="https://i.sstatic.net/h7aHK.png" rel="noreferrer"><img src="https://i.sstatic.net/h7aHK.png" alt="Moire artifacts"></a></p>

<p>Another example with coloured background that shows light propagation, with the same artifacts:</p>

<p><a href="https://i.sstatic.net/on4OX.png" rel="noreferrer"><img src="https://i.sstatic.net/on4OX.png" alt="same Moire artifacts here too"></a></p>

<p>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.</p>

CC BY-SA 3.0
2017-10-25T20:34:04.183Z
Note: I've asked the same question in the comp sci Stack Exchange, but received no answers: https://cs.stackexchange.com/questions/81169/how-to-prevent-moire-artifacts-in-this-light-casting-algorithm
sydd
CC BY-SA 3.0
2017-10-26T13:02:25.377Z
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.
gallickgunner
CC BY-SA 3.0
2017-11-01T01:56:59.837Z
@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.
sydd
<raytracing><glsl><2d><compute-shader>
How to prevent moire artifacts in this light casting algorithm?
sydd
# How to prevent moire artifacts in this light casting algorithm?

(Asked by: username_0 on 2017-10-25)

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](https://i.sstatic.net/h7aHK.png)](https://i.sstatic.net/h7aHK.png)

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

[![same Moire artifacts here too](https://i.sstatic.net/on4OX.png)](https://i.sstatic.net/on4OX.png)

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.

**Tags:** raytracing, glsl, 2d, compute-shader

> **Comments:**
> **username_0**: Note: I've asked the same question in the comp sci Stack Exchange, but received no answers: https://cs.stackexchange.com/questions/81169/how-to-prevent-moire-artifacts-in-this-light-casting-algorithm  
> **username_1**: 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.  
> **username_0**: @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.  

---

## 1 answers

### Answer by username_2 on 2017-10-26. Score: 2

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.

> **Comments:**
> **username_0**: 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.  
> **username_2**: 2D is no different than 3D. check out https://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  
> **username_0**: You mean something like this? https://github.com/matyasf/sparrow-game/blob/master/SparrowGame.Shared/CustomMesh/FragShader.frag This is sadly dog slow, I can render ~5-10 lights. The compute shader above can render ~200 with the same FPS.  
> **username_2**: 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 ?  
> **username_0**: 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.  
> **username_2**: Ok, then in my book there are only 2 ways : either you pay the simulation price, either you find an analytical solution (or a bunch of separated solutions, like Antoine Bouthors did in his 2008 paper for cloud rendering). I can't help you much beyond that  

---

