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

Bitmap Fonts

While I haven't written anything about Bulldog in the last 6 weeks. I definitely haven't been idle in the coding/design department.

Following on from my last post about the icon graphics, I've drawn about 15 additional icons for in-game objects. I've also started to put together the user interface, with displays for the player's Health, Energy, Water and Morale stats. I've written alot of additional behind the scenes systems that help hold everything together, but aren't really that interesting in terms of function, so haven't bothered to talk about them in the blog.

However, this past weekend I tackled a feature I've had on the TODO list for quite some time : creating a better font rendering engine. The standard font routines available in SlimDX (or DirectX for that matter) are terrible in both performance and functionality.

The usual way of overcoming this is to produce a bitmap representation of a font at a specific size and then create a system that generates quads for every letter in the text you want to render and apply the individual letter bitmaps to the quads for rendering. I've seen this approach go wrong in some commercial AAA games and produce horrible artifacts at the edge of letters where they've partially overlapped without proper blending, so I decided to try a slightly different approach.

Rather than have a quad for every letter, I create a single big quad for the entire text, and then generate a bitmap of the text to be displayed in memory by placing the letter bitmaps in the appropriate positions, then slap that bitmap onto the quad for rendering. There's some overhead to constructing the text bitmap, but it only needs to be generated once (unless the text changes), and from then on its a single large quad with a texture, which should be much faster than 100's of small quads.

To test the font engine, I created a bitmap font with a hand-drawn appearance, so that it has a comic-like quality to it, but still is quite readable and the letter forms are consistent. The font itself was drawn in Illustrator, then output as a high resolution bitmap, which I then downsampled in Photoshop.

A screenshot from Adobe Illustrator showing the curves used to create the letter shapes.

Creating my own font means it should match in better with the overall graphic style of the game, than if I used a very clean font like Arial. The image below shows the completed font at 22 pixel resolution, which I've called "Olivia22".

The finished "Olivia22" font.

Throwing together the bitmap font engine and drawing the font didn't actually take as long as I thought. The font took about 8 hours to do all 95 glyphs, and the font engine was about the same. The part I was surprised about was how long it took to setup the kerning information for the font.


Kerning

Kerning is the process of adjusting the space between letters in a word to make the characters sit together in an aesthetically pleasing manner. Unless you're involved in graphic design it may not be apparent that a process like kerning is even required. Kerning is typically done with pairs of letters. A "kerning pair" defines the gap between two particular letters, and at render time each letter pair is checked against the list of kerning pairs and the second letter is offset left or right by the appropriate amount.

For overhanging letters such as "W" or "V", kerning is particularly important, especially when paired with letters like "A", or any of the curvy lower case letters, such as "o", "c" or "a". So for my font to "read well" I had to create kerning pairs for problem combinations of letters. The process took many hours of adjusting values, running the program against a reference text and inspecting each word individually. Over the course of 6 hours I put together close to 500 kerning pairs and just about had my eyeballs fall out of their sockets.

The image below is part of the rendered reference text, showing the kerned version of the font. (This is actually from a work in progress, so I've since tweaked some of the pairs to be better).

A crop of part of the rendered reference text

Even after so much work the result is far from perfect. The biggest limitation with the way I've implemented the font renderer is that the smallest distance a letter can be moved left or right is an entire pixel. In many situations, the "correct kerning" is a movement of less than a pixel, so the space can never be correct for that particularly instance. This is less of a problem with larger font sizes, but with the 22 pixel high font I've created, the kerning values are within the range of +3 to -3, which is pretty small, and leads to some compromise.

In an ideal world the font renderer would use the original vector graphics as the source for the letters, and create its own anti-aliased versions at whatever size is required, however I can't be bothered creating such a thing at this stage, especially when I'm trying to hit an end of year deadline. Perhaps in the future?

Another thing which has become apparent is that my process of kerning is time consuming and fiddly. My plan is to create another 3 or so variations on the current font, (ie different sizes and normal/bold versions). If its going to be 6 hours of kerning for every one of those I'll go insane. So I've come up with an improved workflow for kerning that should shave hours off the time.

The current workflow involves setting the kerning values in the font's data file, running the test code that takes the reference text and produces an output png of the rendered text, loading the png in photoshop and looking over the entire text to spot problems and then repeating the entire process.

The improved workflow relies on me getting the TextBox control working, and adding the ability to tweak the kerning per character pair directly in the text using the cursor keys. This should greatly speed up the process, as the kerning changes will be visible immediately, and without having to load the output in an external application.