Creating Signed Distance Maps

Signed Distance Map Example

I think signed distance functions have to be the single most amazing thing I’ve ever stumbled upon in my mathematical adventures. It’s such a simple idea like polynomial equations and yet its programmers delight sometimes to create them as they’re quite a complex thing to compute in certain scenarios.

My interest and discovery for signed distance functions were brought on in search of extremely fast and high-quality text rendering solution. Valve did some research into this and released a paper called Improved Alpha-Tested Magnification for Vector Textures and Special Effects which I think is a great name for a paper that has an equally proportional title to the complexity of generating the source material… complex. Basically, you’re able to take the traditional alpha mask for fonts and pass and create a gradient around it so you can smoothly handle a gradient rather than a sharp edge and the added benefit that the fonts kind of work like vector fonts with preservation of sharp edges.

Getting Started:

So skipping all of the background mathematics and just diving right in am I right… What the math is a signed distance map anyway!

So from a programmers perspective, a signed distance map is a bitmap where every single pixel is a value between 0 and 1 indicating how far a pixel is from a specific source within a specified radius. So for example, let’s say I’m at coordinate (7,3) and I have a point at (7,13) then my relative position to that point is [0,10] so I’m 10 units away. Now we just apply our sampling radius and diving against our position, let’s say 20 pixels which would give us a value of 0.5 or 50% intensity.

All you have to do is apply this general idea of sampling how far away am I from my source and then convert that down to a value between 0 and 1, anything less than zero you just forget about and treat it as zero but that has some pretty amazing applications outside of text rendering.

The only issue with the general formula is that if you try to brute-force the algorithm, you’re stuck with a problem with a complexity that looks like width² * height². This is pretty terrible if you double the resolution of your image you’re looking at 16 times the amount of computation. I’m going to stick with the brute force for now and we can talk about optimisation and how to compute signed distance maps on the GPU at a later date.

Here is a code example which you’ve probably gone straight to without reading any of the above anyway:

class SignedDistanceMap
{
    Bitmap Input, Output;

    public static void Main()
    {
        SignedDistanceMap sdm = new SignedDistanceMap("example.png");
        sdm.Save("output.png");
    }

    public bool Scan(ref float max_value, int x_pos, int y_pos, int x_scan, int y_scan, int scan_radius)
    {
        var distance = (float)Math.Sqrt(x_scan * x_scan + y_scan * y_scan);
        if (distance > scan_radius) return true; // Optimization #1

        var pixel_value = 0.0f;
        var img_pos_x = x_pos + x_scan;
        var img_pos_y = y_pos + y_scan;
        if (img_pos_x < 0 || img_pos_x >= Input.Width) return true;
        if (img_pos_y < 0 || img_pos_y >= Input.Height) return true;
        Color color = Input.GetPixel(img_pos_x, img_pos_y);
        pixel_value = Math.Max(Math.Max(color.R, color.G), color.B) / 255.0f;

        if (pixel_value <= max_value) return true; // Optimisation #2

        var sample_distance = scan_radius - distance;
        var sample_distance_ratio = sample_distance / scan_radius;
        var sample_value = pixel_value * sample_distance_ratio;

        max_value = Math.Max(max_value, sample_value);

        return pixel_value != 1.0f; // Optimisation #3
    }

    public void Sample(int x_pos, int y_pos, int scan_radius)
    {
        float max_value = 0.0f;

        if (Scan(ref max_value, x_pos, y_pos, 0, 0, scan_radius)) // Optimisation #3
            for (var x_scan = -scan_radius; x_scan < scan_radius; x_scan++)
                for (var y_scan = -scan_radius; y_scan < scan_radius; y_scan++)
                    Scan(ref max_value, x_pos, y_pos, x_scan, y_scan, scan_radius);

        max_value = Math.Min(max_value, 1.0f);
        max_value = Math.Max(max_value, 0.0f);
        var byte_value = (int)(255 * max_value);
        Output.SetPixel(x_pos, y_pos, Color.FromArgb(byte_value, byte_value, byte_value));
    }

    public SignedDistanceMap(string filename, int scan_radius = 10)
    {
        Input = Bitmap.FromFile(filename) as Bitmap;
        Output = new Bitmap(Input.Width, Input.Height);

        for (var x_pos = 0; x_pos < Input.Width; x_pos++)
            for (var y_pos = 0; y_pos < Input.Width; y_pos++)
                Sample(x_pos, y_pos, scan_radius);
    }

    public void Save(string filename)
    {
        Output.Save(filename, System.Drawing.Imaging.ImageFormat.Png);
    }
}
  • First, we load the Input bitmap
  • Then we create the Output bitmap
  • Iterate through each pixel in the Input and “Sample” around it
  • Each Sample needs to “Scan” through each pixel, we store the maximum value across all of the scans
  • Write the sampled value to the output
  • Profit but slowly because this takes forever!!!

Just some extra notes. I didn’t want to have to check for either 0 or 1 values within the input image so I decided it might be easier to just multiply the value of the pixel into the weight so if a pixel say had a value of 90% its still likely to affect the final output but to a lesser degree which I think is appropriate, perhaps adding some kind of bias though perhaps squaring the input pixel value might be appropriate in order to preserve sharpness? I’ll test that out someday.

Optimization #1: If the distance is outside of the scan radius, we should just discard as it will only cause is to get negative values which we discard anyway.
Optimization #2: If the pixel value is less than or equal to the maximum value, then it’s impossible for it to have an effect anyway so we’ll just return.
Optimization #3: If we’re already sitting on an input value of 1, then there is no need to sample anything else because the result is already 1.

Here is an example of the input and output:

Why does this produce quality results for the font?

The easiest way to visualise why this produces quality fonts is by understanding what kind of detail is being kept on the map. Because you’re looking at this on a computer screen and our eyes perceive shades of black better against a white contrast for detail, here is the same output but inverted. You should now be able to better see the features which are being preserved in the signed distance map.

You can see that the sharp angles are preserved as a crease like an effect and this is what allows you to achieve vector like results with the signed distance fields. Its still retaining crease information and if you look at the edge corners of the letters you’ll notice the same effect in reverse where they’re ever so slightly darker and this is the effect of preserving a larger angle. These bitmaps are also able to retain a lot of information at low resolutions because you’re using more of the available space to try and store information with the halo effect around the font opposed to standard alpha maps.

Next time I’ll give an example for creating signed distance maps just like this one using OpenGL shaders which can make quick work of a task like this at much bigger resolutions!