Fast pixelshader 2D raytracing

Question

I'd like to do a simple 2D shadow calculation algorithm by rendering my environment into a texture, and then use raytracing to determine what pixels of the texture are not visible to the point light (simply handed to the shader as a vec2 position) .

A simple brute force algorithm per pixel would looks like this:

line_segment = line segment between current pixel of texture and light source

For each pixel in the texture:
{
  if pixel is not just empty space && pixel is on line_segment
       output = black
  else
       output = normal color of the pixel

}

This is, of course, probably not the fastest way to do it. Question is: What are faster ways to do it or what are some optimizations that can be applied to this technique?

Answer 1

Assuming you don't want to use standard shadow mapping, you could use a signed distance field to do it. This involves building a texture that tells you, for each pixel, the distance to the nearest opaque surface in any direction. The distances are negative when you're inside an opaque object and positive when outside (this allows the surfaces to be positioned with sub-pixel precision; the distance field texture can be substantially lower resolution than your world).

You can then trace through this texture at runtime: starting from a pixel, look up the distance field at that pixel, and then move by that distance along a vector toward the light source. Look up the distance field at the new point and repeat.

If you make it to the light source, the original point is unoccluded; if you go too many iterations or the distance value falls below some small threshold, the original point is in shadow. This algorithm is called "sphere tracing" in 3D; I guess in your case it'd be "circle tracing". :)

There are a few articles out on the Web about signed distance fields and sphere tracing, mostly in a 3D context (for tracing against voxel fields and such), but the same concepts should work in 2D.

Also, note that the distance field textures can be precomputed for the environment and for any moving objects you want to cast shadows, and combined in real time by using min blending (that is, a blending mode that takes the minimum of the two pixels being blended - glBlendEquation(GL_MIN) in OpenGL, or D3D11_BLEND_OP_MIN in D3D11).