How can I generate signed distance fields (2D) in real time, fast?

In a previous question, it was suggested that signed distance fields can be precomputed, loaded at runtime and then used from there.

For reasons I will explain at the end of this question (for people interested), I need to create the distance fields in real time.

There are some papers out there for different methods which are supposed to be viable in real-time environments, such as methods for Chamfer distance transforms and Voronoi diagram-approximation based transforms (as suggested in this presentation by the Pixeljunk Shooter dev guy), but I (and thus can be assumed a lot of other people) have a very hard time actually putting them to use, since they're usually long, largely bloated with math and not very algorithmic in their explanation.

What algorithm would you suggest for creating the distance fields in real-time (favourably on the GPU) especially considering the resulting quality of the distance fields?

Since I'm looking for an actual explanation/tutorial as opposed to a link to just another paper or slide, this question will receive a bounty once it's eligible for one :-).

Here's why I need to do it in real time:

If you have to precompute these SDFs for large 2D environments (think of a large Terraria-like map), this would mean that you're accepting a rather large overhead in storage space (and map-generation time) in favour of implementing a more complicated algorithm that is fast enough for real time SDF generation.

For example, a relatively small map with 1000*256 (width*height) with a tile size of 10*10 pixels and thus total dimensions of 10000*2560 pixels would already cost you around 2 megabytes of size, if you choose a relatively small SDF resolution of 128x128, assuming that you're storing only the distance values from 0 to 255.

Obviously, this can quickly become too much and is an overhead that I don't want to have.

There's something else:

SDFs can be used for many things (like collision detection), and some useful applications are potentially not even discovered yet. I think a lot of people are going to look for these things in the future, and if we get a comprehensive answer in here, I think we're going to help a lot of people.

Answer

Catalin Zima explains how to achieve dynamic 2D shadows in his article - and he does use a signed distance field (from what I can tell that is just a fancy name for a shadow buffer in this context). His method does need a GPU, and his implementation as-is isn't the best (his dropped below 60Hz at about 20 lights on my machine, mine got about 500 lights); which is to be expected as he has favoured clarity of code over speed.

Implementation

Exactly as implemented by him:

1. Render all shadow casters into a texture.


2. Calculate the distance to the centre of the light for each pixel, and assign that value to the RGB of opaque pixels.


3. Distort the image so that it represents how a 3D camera would have seen those pixels.


4. Squash the image into a 2xN sized image using the unusual resize described in his article (a plain resize won't work).


5. The 2xN image is now your signed distance field for all four quadrants of the light (remember that one quadrant is basically a single camera frustum at 90 degrees).


6. Render the lightmap.


7. Blur the lightmap (based on the distance from the light) so that you get soft shadows.

My final implementation was (each step being a single shader):

1. Do (1).


2. Do (2) and (3).


3. Do (4). His implementation is really slow: if you can try and use GPGPU for this. I couldn't use GPGPU (XNA) so what I did was:
   
   
   
   • Set up a mesh where the first N/2 columns were represents by N/2 quads with the EXACT same position (covering the first column of the final buffer) but differing texture co-ordinates (same thing for the second N/2 columns)
   
   
   • Turn off depth-testing on the GPU.
   
   
   • Use the MIN pixel blending function.
   
   
   
   


4. Do (6) and (7).

It's quite ingenious: it's basically a direct translation of how shadows are handled in 3D into 2D.

Pitfalls

The main pitfall is that some objects shouldn't be shadowed: in my example I was writing a Liero (real-time worms) clone and hence didn't want, for example, the players' worms to be shadowed (at least the one on each player's screen). All I did for these 'special' objects was redraw them as a last step. The irony was that most objects were not shadowed (worms, landscape foreground) so there is an overdraw issue here.