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.