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

-
I googled "what is a signed distance field" and first hit was a GPU version: http.developer.nvidia.com/GPUGems3/gpugems3_ch34.html It's a bit old but might help further your searches. – Patrick Hughes Apr 9 '12 at 19:11
Maybe I'm missing something, but I'm somewhat confused by the statement of why you need to do it in real time (not least, why it's spoiler-tagged); firstly, where do you get the 2MB figure for an SDF of 128x128? Secondly, why do you consider 2MB a particularly heavy memory usage? I agree it's not insubstantial, but it seems a small fraction of your overall map memory usage. And third, how will generating the field in realtime save that memory? You still need to store exactly the same data whether it's generated on the fly or precomputed, no? – Steven Stadnicki Apr 11 '12 at 1:15
More broadly, it could easily be that SDFs aren't the technique you need. More information about your specific situation - static obstacle count, dynamic obstacle count, etc. - and precisely what effect you're hoping to achieve would be helpful in trying to pin down what's most likely to be useful to you. – Steven Stadnicki Apr 11 '12 at 1:48
If I generated the distance field in real time, I would only create those 2MB one time per frame (the total memory overhead would always be the memory needed for one distance field, since I only need the one for the screen). If I have a larger map than my 1000x128 example (I think large Terraria maps go well beyond the 10000's) I need one of those 2mb for every 1000x128 submap of that map. Why I need SDFs in the first place is described in the first question that I linked at the beginning of this question (it's for GPU 2D shadow casting). – TravisG Apr 11 '12 at 10:02
@heishe are you trying to generate 2Mb of data once per frame? Seriously? – kaoD Apr 11 '12 at 19:44

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.

-
Was your adjustment to the resize method the only thing to speed it up to handle 500 lights above 60fps? – TravisG Apr 12 '12 at 9:08
OK, I'll accept the answer since it solves my original problem, but it doesn't really answer what I gave the bounty for. I'll wait and maybe someone comes a long to explain one of the several O(N) methods for signed distance field generation around. – TravisG Apr 12 '12 at 9:17
@heishe regarding your first question: not sure. I did all the optimizations in one pass - I think I remember turning it off and watching the framerate drop substantially though. All-in-all 6 draw calls per light will kill your framerate. As I said it looks like, from what I can tell, you have a 4 signed distance fields at step (5) - but someone who knows more about them will need to confirm that. – Jonathan Dickinson Apr 12 '12 at 9:25
Well, it's a very special case of a signed distance field. In a normal signed distance field, every pixel contains the distance to the closest obstacle. In this algorithm, the distance field only contains one obstacle, and also the obstacle is only 1 pixel in the entire image (the light source), which is why this distance field can be generated in O(N). – TravisG Apr 12 '12 at 9:46
@heishe here is my shader: gist.github.com/2384073 . DistortPS is 2+3. – Jonathan Dickinson Apr 14 '12 at 12:28