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?

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).

• Thanks! You'll get an upvote if you can actually find a link to a signed distance field generation algorithm that isn't brute force. Actually you'll get an upvote anyways, but I'm gonna wait to see if this motivates you to help me find it :) – TravisG Apr 4 '12 at 18:04
• An algorithm for generating the distance field is described in this GDC talk: directtovideo.wordpress.com/2012/03/15/… (slides 28-32). The basic idea: render surfaces into the distance field (in 2D, this would be by drawing lines a couple pixels wide) to get the accurate subpixel distances, then do a few "sweep" passes on rows and columns to propagate those through the rest of the field. Haven't tried it myself, but it sounds efficient. – Nathan Reed Apr 4 '12 at 20:06
• Thanks for that. Can you explain (best edit it into your answer) what "min blending" is? Google doesn't give any good results for "min blending" – TravisG Apr 5 '12 at 11:05
• @heishe - Done. – Nathan Reed Apr 5 '12 at 17:14
• FYI: I've tried to read a lot of papers the past few days on distance transforms, and almost all of them are hard to understand. Since I don't understand the method shown on those four slides, I've created a follow up question here: gamedev.stackexchange.com/questions/27019/… – TravisG Apr 8 '12 at 14:51