Signed Distance Fields

I was first exposed to Signed Distance Fields through this white paper written by Chris Green from Valve Software. Valve often make technical documentation on their graphics technology available, which is awesome.  In this case, the technique was used in Team Fortress 2, specifically for some of the signs and decals in the game.

Signed Distance Fields are a different way of storing (typically monochrome) bitmap data.  Instead of each pixel in the bitmap representing the intensity at that point, it represents the distance to the nearest non black pixel in the source image. Pixels outside of the shape have positive distance values, while pixels inside the shape have negative distance values, hence the "signed" part of the name.

Figure 1. An example of how a signed distance field looks at the pixel level.

Note that in reality the distance field is made up of floating point data, but for illustrative purposes I've shown them as integers.

To create a signed distance field you apply a distance transform to a source image. Then, to render the original image you do the following:

For each distance value in the field,
    is the value <= 0?
    if yes, draw the pixel
    if no, ignore it.

The thing that makes signed distance fields really useful is what happens if you need to resize the image. The distance values are interpolated by the 3D hardware in the same way as intensity values in a traditional bitmap, but because the edge comes from a test, it remains crisp. This means you can magnify the bitmap many times and not suffer the blurry or chunky edges that traditional bitmaps exhibit due to filtering artifacts.

Creating the Distance Field

There are many different transforms you can use to calculate the distance field.  It turns out that the best approach is to use a high resolution source image and then downsample the result to an acceptable size for your application, as the nature of the distance field preserves a lot of the information.

The brute force method (by which I mean calculating the euclidean distance between a given pixel and every other pixel in the bitmap) will generate a perfect distance field but is particularly slow for large bitmaps as it has O(n^2) complexity. There are faster (albeit less accurate) algorithms out there though the selection of algorithm isn't too important, as it doesn't need to be done at runtime. Valve actually used the brute force solution and ran the processing as a batch job overnight on their servers. I chose a faster approach simply because I was eager to get some results.

Figure 2. An example of what the final distance field looks like in Bulldog.

An application of Distance Fields

Since the source data for Distance Fields is generally monochromatic, their usefulness is limited, however one application that is particularly well suited to distance fields is drawing text.

For example, a TrueType or OpenType font (or "typeface" to use the correct term) is stored in a vector format. This means each of the glyphs (characters in the typeface) are represented as shapes with x,y coordinates for their corners and control points. This is converted into a bitmap or "rasterised" for display on the screen. Depending on the size of the text you want, the x,y coordinates are scaled and the curves that represent the shape of the letter are scaled too. The rasterisation process can be a little slow even on modern hardware, so in games the preferred technique is to pre-rasterise the font at the size you want, store it as a bitmap and then construct the text required by picking individual letters from the bitmap.

This technique is very fast, but has some limitations. You need to create a seperate font bitmap for every size and style combination you want to use in your game since bitmaps don't scale well. Take for example a game that wants to have 2 different typefaces, say a normal looking sans serif typeface like Arial, and maybe a fancier caligraphy typeface for ye olde books and scrolls and the like. You may want to support 3 different sizes for stylistic reasons, such as titles/captions or tooltips. Or perhaps you want to support a wide range of screen resolutions and don't want people to require a microscope to read your UI elements. Already we have 2 * 3 = 6 different bitmaps you need to create and manage in the game. It gets even worse if you want to support italics or bold styles as well.

The signed distance field approach helps alleviate this burden by taking the sizing out of the equation since the distance field can be scaled up and down with less graphical artifacts.

As an added bonus distance field data can be used to anti-alias the edges. This can be achieved by adding an additional term to the distance test to smoothly ramp from lit to unlit for distance values within a certain range. The Valve paper covers a few other effects, such as drop shadows and outlines.

In Bulldog, I implemented signed distance field fonts using a pixel shader, which makes juggling the distance field data considerably easier.

The shader code is surprisingly simple, and for simple anti-aliased text is as follows:

float4 ps( VS_OUTPUT IN) : COLOR
{
    // get the alpha value from the distance field texture
    float rawAlpha = tex2D( TextureSampler, IN.TilingCoords).a;


    clip (rawAlpha - (0.5f-delta));

    return float4(fillColour, smoothstep(0.5f-delta,0.5f+delta,rawAlpha) );
}

delta is a constant which determines how far from the edge of the letter the anti-aliasing extends. The actual shader code I use in bulldog is slightly more complex as it handles borders and reversed characters (such as when selecting text in a textbox), as well as adjusting the anti-aliasing for different font sizes. I'll write up a more detailed post on the new font system I built using signed distance fields at some point. In the mean-time, here's an example of the same font rendered at several different sizes:

Figure 3. An example of the font output at 12, 24 and 64 pixels high.

As a last note, I should mention I've also used signed distance fields in an unusual way in a different part of Bulldog, but that's a post for another time...

Math.Pow(x,2) vs x * x

I've recently commented on posts on gamedev.net where the author posted some code they were concerned about the speed of. In each example I noted they were using the Math.Pow() function to calculate the square of a number.

In each circumstance I recommended they alter their code to multiply the two values together. This was mostly based on the "gut feel" that Math.Pow() should be slower. That's fairly poor practise, and because I loathe giving people a bum steer, I decided I should do a quick benchmark on my CPU.

100 million iterations in a tight loop. (x is a double):

Math.Pow(x,2)	8.540 seconds
x * x	1.152 seconds

Similarly, as an aside, Math.Sqrt(x) is significantly faster than Math.Pow(x,0.5):

Math.Pow(x,0.5)	8.543 seconds
Math.Sqrt(x)	1.737 seconds

The results are pretty clear. Stay away from Math.Pow(x,2) and Math.Pow(x,0.5). I did some further benchmarking on higher integer powers, and Math.Pow() stays the same, while x * x * x ... gets slower as you'd expect. The breakeven point is somewhere around x ^ 20 I think. So it's still better to do the direct multiplication for x ^ 3 and x ^ 4.

I was actually surprised by the performance of Math.Sqrt(x), I thought it would be alot slower than it turned out to be. The important lesson here is to always benchmark.