In the previous post we looked at the basics of signed distance field generation. Having setup a framework for generating a field, we wrote a series of functions for adding different shapes, all of which:

• Iterated over every pixel in the field
• Calculated the distance to the shape at the centre of the pixel
• Updated the pixel in the field by comparing the new distance to the current one

And of course, here is the git hub repo with it all in!

The process worked well, but also highlighted some inconsistencies when combining shapes, demonstrated when drawing 2 rectangles very close together:

The algorithm has no way of knowing that the central pixels of the large rectangle become very ‘deep’ when the 2 smaller rectangles are drawn overlapping one another. This inconsistency breaks the border effect as shown in the right hand image.

In addition to errors, the algorithm has to iterate over every pixel for every shape drawn, so can get slow pretty quickly!

Bounded/padded shapes

To begin, we’ll attempt to speed things up by implementing a simple optimisation. Rather than updating the entire field for every shape, we’ll pick a subset of pixels to update, and leave the rest alone. This will be substantially faster, as a shape that only affects a small area of the field will only have to iterate over a small number of pixels.

To start, lets create a couple of helpers:

//simple function to clamp an integer xy coordinate to a valid pixel
//coordinate within our field
void ClampCoord(ref int x, ref int y)
{
    if (x = m_x_dims) x = m_x_dims - 1;
    if (y = m_y_dims) y = m_y_dims - 1;
}

This very basic function (which we’ll use later) just clamps a coordinate to within the dimensions of our field.

Building on that, a slightly more complex one:

//takes an axis aligned bounding box min/max, along with a padding value, and 
//outputs the integer pixel ranges to iterate over when using it fill out a field
void CalcPaddedRange(Vector2 aabbmin, Vector2 aabbmax, float padding, 
                     out int xmin, out int ymin, out int xmax, out int ymax)
{
    //subtract the padding, and floor the min extents to an integer value
    xmin = Mathf.FloorToInt(aabbmin.x-padding);
    ymin = Mathf.FloorToInt(aabbmin.y-padding);

    //add the padding and ceil the max extents to an integer value
    xmax = Mathf.CeilToInt(aabbmax.x+padding);
    ymax = Mathf.CeilToInt(aabbmax.y+padding);

    //clamp both coordinates to within valid range
    ClampCoord(ref xmin, ref xmax);
    ClampCoord(ref ymin, ref ymax);
}

This function takes an axis aligned bounding box – aka a none rotated rectangle. It is described by the position of its top left corner (aabbmin), and the position of its bottom right corner (aabbmax). In addition, the function takes a padding value, which we’ll use to fatten the box. It then proceeds to calculate the integer range of pixels we’d need to loop over in order to touch every single pixel within the fattened box.

Now to get moving. Lets add new function in SignedDistanceFieldGenerator.cs to draw a line, which, for want of a better naming convention we’ll call PLine as it is a padded line.

//generates a line, writing only to the pixels within a certain distance
//of the line
public void PLine(Vector2 a, Vector2 b, float pad)
{
    //calculate axis aligned bounding box of line, then use to get integer
    //range of pixels to fill in
    Vector2 aabbmin = Vector2.Min(a, b);
    Vector2 aabbmax = Vector2.Max(a, b);
    int xmin, ymin, xmax, ymax;
    CalcPaddedRange(aabbmin, aabbmax, pad, 
                    out xmin, out ymin, out xmax, out ymax);

    Vector2 line_dir = (b - a).normalized;
    float line_len = (b - a).magnitude;

    for (int y = ymin; y <= ymax; y++)
    {
        for (int x = xmin; x <= xmax; x++)
        {
            //mathematical function to get distance from a line
            Vector2 pixel_centre = new Vector2(x + 0.5f, y + 0.5f);
            Vector2 offset = pixel_centre - a;
            float t = Mathf.Clamp(Vector3.Dot(offset, line_dir), 0f, line_len);
            Vector2 online = a + t * line_dir;
            float dist_from_edge = (pixel_centre - online).magnitude;

            //update the field with the new distance
            Pixel p = GetPixel(x, y);
            if (dist_from_edge < p.distance)
            {
                p.distance = dist_from_edge;
                SetPixel(x, y, p);
            }
        }
    }
}

This is only a slight modification of the earlier brute force implementation. At the beginning of the function the axis aligned bounding box of the line is calculated using its start/end points (a and b):

    Vector2 aabbmin = Vector2.Min(a, b);
    Vector2 aabbmax = Vector2.Max(a, b);

This is then passed into our CalcPaddedRange function, along with a new pad parameter, which outputs the integer range of pixels covered by the fattened bounding box:

    int xmin, ymin, xmax, ymax;
    CalcPaddedRange(aabbmin, aabbmax, pad, 
                    out xmin, out ymin, out xmax, out ymax);

The final change is the loops. Where previously they iterated over every pixel (starting from 0, going up to the width/height of the field), they now only iterate over the calculated range of pixels:

for (int y = ymin; y <= ymax; y++)
{
    for (int x = xmin; x <= xmax; x++)
    {

That’s the lot for this first section – everything else is identical to our earlier brute force version. We’ve not changed the algorithm for drawing a line in the slightest. All we’ve done is work out a reduced number of pixels to fill in.

As with our earlier tests, we can now add a button in SignedDistanceField.cs to generate a padded line:

        if (GUILayout.Button("Padded line"))
        {
            SignedDistanceFieldGenerator generator = new SignedDistanceFieldGenerator(32, 32);
            generator.PLine(new Vector2(8, 15), new Vector2(23, 20), 5);
            field.m_texture = generator.End();
        }

This is a roughly diagonal line in a 32×32 field, with a padding of 5 pixels. At first glance, the resulting render (with a border width of 1 pixel) looks perfectly good:

However, lets look at the distance visualisation:

Our distance visualiser renders a shade of red for positive distances to the nearest pixel, but by scaling the shade down, we can see that outside of the bounding box there’s lots of pixels with a huge distance value where we haven’t yet written anything.

The issue with this approach rears it’s ugly head when we try to make the line get fatter. Lets instead go back to rendering it as normal, but with a border width of about 6 pixels:

Our line has now been chopped off at the edges where we hit pixels that think they’re miles away from the edge of anything!

The reader might point out at this stage that rather than make things better, I’ve actually made things worse. On top of the earlier issues with field inconsistencies, we now have to deal with only partial field data. However, even without further refinement this technique is frequently put to work, as many uses of signed distance fields don’t care about every pixel – often the important ones are very close to the edge or inside of the geometry.

Assume, for example, I knew in my game I was never going to try and create borders fatter than 4 pixels. In that situation, generating all my field shapes with a padding of 5 pixels will give me all the data I need, and may save a lot of time.

Whilst I won’t touch upon it yet, many uses of signed distance fields avoid trying to even store data for empty pixels. When 3D voxels come into play, memory runs out very quickly – a 1024x1024x1024 voxel grid of 4 byte floating point distances would take 4GB of memory! Instead, techniques such as sparse octtrees are used, which can store hi resolution voxel data close to the surface of the geometry, but little to no data for voxels far from the surface.

Before proceeding, PCircle and PRect have also been added. As with the PLine function, these are both almost identical to their brute force counterparts, with the added use of the bounding box.

For a circle, the bounding box is calculated by simply building a square centred at the centre of the circle, with a width and height of 2 * the radius:

//circle bounding box calculation - a square that surrounds the circle
Vector2 aabbmin = centre - Vector2.one * rad;
Vector2 aabbmax = centre + Vector2.one * rad;
int xmin, ymin, xmax, ymax;
CalcPaddedRange(aabbmin, aabbmax, pad, 
                out xmin, out ymin, out xmax, out ymax);

And for a rectangle (aka a box) the bounding box is, you guessed it, the box!

//rectangle bound box 'calculation' - just use the min/max of the rectangle
Vector2 aabbmin = min;
Vector2 aabbmax = max;
int xmin, ymin, xmax, ymax;
CalcPaddedRange(aabbmin, aabbmax, pad, 
                out xmin, out ymin, out xmax, out ymax);

Sweeping

If you really want a clean signed distance field, you’re going to have to sweep it (hahaha yeah I went there). With this technique we assume that the only accurate pixels in the field are those that lie on the edge of the geometry, and that any others may have suffered inconsistencies, or not even been written to at all.

The most common sweeping algorithm has such a great name it has always to be written in full… yes, it’s the 8-points Signed Sequential Euclidean Distance Transform. Catchy! I haven’t actually managed to track down the original paper on it, however Richard Mitton on Coders Notes presents a nice and clean implementation in c++. The one we’ll use for this blog is largely a C# port of his work.

First up, a quick function to identify if a pixel is ‘outside’ or ‘inside’ the surface:

bool IsOuterPixel(int pix_x, int pix_y)
{
    if (pix_x < 0 || pix_y = m_x_dims || pix_y >= m_y_dims)
        return true;
    else
        return GetPixel(pix_x, pix_y).distance >= 0;
}

This really just returns true if the distance value is greater than 0, with an extra catch to treat pixels outside the bounds of the field as outside the geometry.

The algorithm starts by iterating over the existing pixels and clearing out anything that doesn’t contain reliable data. The metric we’ll use is whether a pixel is an edge pixel, defined by this little helper:

bool IsEdgePixel(int pix_x, int pix_y)
{
    bool is_outer = IsOuterPixel(pix_x, pix_y);
    if (is_outer != IsOuterPixel(pix_x - 1, pix_y - 1)) return true; //[-1,-1]
    if (is_outer != IsOuterPixel(pix_x, pix_y - 1)) return true;     //[ 0,-1]
    if (is_outer != IsOuterPixel(pix_x + 1, pix_y - 1)) return true; //[+1,-1]
    if (is_outer != IsOuterPixel(pix_x - 1, pix_y)) return true;     //[-1, 0]
    if (is_outer != IsOuterPixel(pix_x + 1, pix_y)) return true;     //[+1, 0]
    if (is_outer != IsOuterPixel(pix_x - 1, pix_y + 1)) return true; //[-1,+1]
    if (is_outer != IsOuterPixel(pix_x, pix_y + 1)) return true;     //[ 0,+1]
    if (is_outer != IsOuterPixel(pix_x + 1, pix_y + 1)) return true; //[+1,+1]
    return false;
}

Here the pixel is first identified as an outer or inner one. It is then compared to all 8 of its neighbours. If an outer pixel has any inner neighbours, its on an edge, and visa-versa.

With these 2 tools, the ‘clear’ function is as follows:

public void ClearNoneEdgePixels()
{
    for (int y = 0; y < m_y_dims; y++)
    {
        for (int x = 0; x  0 ? 99999f : -99999f;
            SetPixel(x,y,pix);
        }
    }
}

This iterates over every pixel, and identifies any that are not on an edge. In these cases we basically want to update the pixel to say “we still know if you’re inside or outside, but we have no idea how far you are from the surface”. To achieve this the pixel is assigned either a negative or positive very big number. Here’s a couple of examples of the distance visualiser before and after a clear:

In both examples, on the left is a field generated using one of the earlier functions, while the right shows what happens when the ClearNoneEdgePixels function is applied. Be aware for the remainder of the post I’ve switched to point sampled rendering to clearly show individual pixels, hence the ‘blocky’ look!

The reader might note here that most of the soft edges of the ‘padded circles’ have been obliterated, indicating they could have been generated with very tight padding with no negative consequences.

The sweeping algorithm is much simpler if it doesn’t have to worry about outsides/insides or positive/negative distances. As a result, the common approach is to run the algorithm once for inner pixels, and once for outer pixels, then combine the result at the end. To achieve this, we build 2 separate grids:

//reads current field into 2 grids - 1 for inner pixels and 1 for outer pixels
void BuildSweepGrids(out float[] outside_grid, out float[] inside_grid)
{
    outside_grid = new float[m_pixels.Length];
    inside_grid = new float[m_pixels.Length];
    for (int i = 0; i < m_pixels.Length; i++)
    {
        if (m_pixels[i].distance < 0)
        {
            //inside pixel. outer distance is set to 0, inner distance
            //is preserved (albeit negated to make it positive)
            outside_grid[i] = 0f;
            inside_grid[i] = -m_pixels[i].distance;
        }
        else
        {
            //outside pixel. inner distance is set to 0,
            //outer distance is preserved
            inside_grid[i] = 0f;
            outside_grid[i] = m_pixels[i].distance;
        }
    }
}

When hitting a +ve pixel, the distance is written to the outer grid, but 0 is written to the inner grid, causing the inner sweep to ignore it.

Similarly, when hitting a -ve pixel, the distance is written (negated) to the inner grid, but 0 is written to the outer grid, causing the outer sweep to ignore it.

The core of this, and indeed many sweep algorithms can be seen in the following diagram:

In knowing the distance from B to its nearest edge point, we can take a guess at the distance from A to that same edge point, by taking the distance from A to B, and adding it to the distance from B to the edge.

It’s worth noting that the result isn’t perfect – the calculation gives us an upper bound for the distance from A to the edge. In reality, the distance from A to the edge is a little shorter, as shown here:

With some cleverer algorithms it is possible to refine these errors a little, but, for many use cases they can be ignored with minimal issues.

Armed with this observation, we can introduce the Compare function:

//compares a pixel for the sweep, and updates it with a new distance if necessary
public void Compare(float[] grid, int x, int y, int xoffset, int yoffset)
{
    //calculate the location of the other pixel, and bail if in valid
    int otherx = x + xoffset;
    int othery = y + yoffset;
    if (otherx < 0 || othery = m_x_dims || othery >= m_y_dims)
        return;

    //read the distance values stored in both this and the other pixel
    float curr_dist = grid[y * m_x_dims + x];
    float other_dist = grid[othery * m_x_dims + otherx];

    //calculate a potential new distance, using the one stored in the other pixel,
    //PLUS the distance to the other pixel
    float new_dist = other_dist + Mathf.Sqrt(xoffset * xoffset + yoffset * yoffset);

    //if the potential new distance is better than our current one, update!
    if (new_dist < curr_dist)
        grid[y * m_x_dims + x] = new_dist;
}

This function takes a pixel (A) at coordinate [x,y], and another pixel (B) at coordinate [x+xoffset,y+yoffset]. Both pixels may already have valid distances associated with them, or they may still contain really-big-number. A new candidate distance is calculated by adding the distance, A->B, to the distance, B->edge. If the new distance is better than the current one, it is updated.

Now for the backbone of the sweep – the SweepGrid function:

public void SweepGrid(float[] grid)
{
    // Pass 0
    //loop over rows from top to bottom
    for (int y = 0; y < m_y_dims; y++)
    {
        //loop over pixels from left to right
        for (int x = 0; x = 0; x--)
        {
            Compare(grid, x, y, 1, 0);
        }
    }

    // Pass 1
    //loop over rows from bottom to top
    for (int y = m_y_dims - 1; y >= 0; y--)
    {
        //loop over pixels from right to left
        for (int x = m_x_dims - 1; x >= 0; x--)
        {
            Compare(grid, x, y, 1, 0);
            Compare(grid, x, y, 0, 1);
            Compare(grid, x, y, -1, 1);
            Compare(grid, x, y, 1, 1);
        }

        //loop over pixels from left to right
        for (int x = 0; x < m_x_dims; x++)
        {
            Compare(grid, x, y, -1, 0);
        }
    }
}

Utilising the Compare function, this sweeps over all the pixel rows, first from top to bottom, then from bottom to top. For each row, it sweeps from left to right, and right to left. Within these loops, pixels are compared to their neighbours, and distances updated if better ones are found. I don’t want to go into the exact proof that the above set of loops guarantee the correct result, as that’s a scientific paper in itself! However, these videos hopefully show the process in action very convincingly:

The final function that glues it all together and writes the grids back into the field pixels is Sweep:

public void Sweep()
{
    //clean the field so any none edge pixels simply contain 99999 for outer
    //pixels, or -99999 for inner pixels
    ClearNoneEdgePixels();

    //seperate the field into 2 grids - 1 for inner pixels and 1 for outer pixels
    float[] outside_grid,inside_grid;
    BuildSweepGrids(out outside_grid, out inside_grid);

    //run the 8PSSEDT sweep on each grid
    SweepGrid(outside_grid);
    SweepGrid(inside_grid);

    //write results back
    for (int i = 0; i < m_pixels.Length; i++)
        m_pixels[i].distance = outside_grid[i] - inside_grid[i];
}

The only new functionality here is the last write-back, which subtracts the inner grid from the outer one. This in effect just combines the 2 grids, and makes the inner pixels negative again.

If you’re interested, I made the videos using a slightly body new class called AnimatedSweep. It’s not meant to be a shining example of nice code, but it’s there if you want a peak!

Summary

Phew! Turns out sweeping takes more to explain than planned. By now you’ve got a good understanding of writing to distance fields, a way of minimizing performance cost of doing so and a robust technique for cleaning up errors.

We’ve definitely not covered everything on sweeping here. The 8SSD method described so far is technically an optimal version of an ‘8 tap’ algorithm, meaning for any given pixel, all 8 neighbours are checked and the best candidate is selected. In addition, we have the less accurate ‘4 tap’ algorithms which ignore the diagonals, and the more mathematical but highly accurate eikonal equation that I may go over later in the series.

Next episode will add a final powerful tool to your 2D SDF generation kit – generating from images created in anything from MS Paint to Adobe Photoshop.

Check out the code here for the latest stuff.

Signed Distance Fields Part 6: Images

Up until now we’ve focused on the concepts of signed distance fields and how to render them using a special shader. However, a place to stumble once you understand these tools is how to get/find/create the fields in the first place. As it happens, there are loads of different ways that vary depending on source data, and performance/quality requirements. At the end of this post you should have a basic (if inefficient) approach to generating fields that works out the box, and is easy to extend.

As always, the full git repo is on github here.

The Field Generator

Having cleaned up the  signed distance field renderer in the previous post, we’ll switch to another class called SignedDistanceFieldGenerator. For a full listing, see SignedDistanceFieldGenerator.cs. This class provides 2 facilities:

• Starting/finishing generation by allocating a temporary buffer for
  the field, then at the end converting it to a unity texture
• A set of utility functions we’ll gradually add to for generating fields in
  a variety of ways

Our generator starts with the definition of a field pixel:

public struct Pixel
{
    public float distance;
}

This simple class is used to store the properties of a pixel during generation. It contains just 1 value for now:

• distance: as you might expect, this is the calculated signed
  distance for the pixel

We have a constructor that does nothing more than allocate a buffer and initialise all the pixels to a very large distance, meaning they will always be interpreted as ‘outside’ the geometry:

public SignedDistanceFieldGenerator(int width, int height)
{
    m_x_dims = width;
    m_y_dims = height;
    m_pixels = new Pixel[m_x_dims * m_y_dims];
    for (int i = 0; i < m_pixels.Length; i++)
        m_pixels[i].distance = 999999f;
}

A couple of accessors to help with reading/writing the field pixels:

Pixel GetPixel(int x, int y)
{
    return m_pixels[y * m_x_dims + x];
}
void SetPixel(int x, int y, Pixel p)
{
    m_pixels[y * m_x_dims + x] = p;
}

And finally, the slightly more complex ‘End’ function, which converts our array of pixels into a texture:

public Texture2D End()
{
    //allocate an 'RGBAFloat' texture of the correct dimensions
    Texture2D tex = new Texture2D(m_x_dims, m_y_dims, TextureFormat.RGBAFloat, false);

    //build our array of colours
    Color[] cols = new Color[m_pixels.Length];
    for (int i = 0; i < m_pixels.Length; i++)
    {
        cols[i].r = m_pixels[i].distance;
        cols[i].g = 0;
        cols[i].b = 0;
        cols[i].a = m_pixels[i].distance < 999999f ? 1 : 0;
    }

    //write into the texture
    tex.SetPixels(cols);
    tex.Apply();
    m_pixels = null;
    m_x_dims = m_y_dims = 0;
    return tex;
}

Within this ‘End’ function, the first step is to allocate a new texture for our field:

    Texture2D tex = new Texture2D(m_x_dims, m_y_dims, TextureFormat.RGBAFloat, false);

The texture format used here is 'RGBAFloat'. Unlike most formats, this uses a full floating point value for each colour channel. Whilst expensive (128 bits per pixel!), it is the most convenient format to use for these tutorials, as it allows us to store any numbers in our pixels without worrying about ranges or precision. That said, later in this series we’ll look at techniques for storing fields in much more compact formats.

Next, we generate the colours:

    //build our array of colours
    Color[] cols = new Color[m_pixels.Length];
    for (int i = 0; i < m_pixels.Length; i++)
    {
        cols[i].r = m_pixels[i].distance;
        cols[i].g = 0;
        cols[i].b = 0;
        cols[i].a = m_pixels[i].distance < 999999f ? 1 : 0;
    }

Here, the distance is written into the red channel and if the pixel has a sensible distance (indicating it has been written to), it is assigned an alpha value of 1, so the shader can identify it as containing valid data. Strictly speaking this last bit is unnecessary, but it’ll help with our debugging visualisations later. Eventually we will use the green and blue channels to visualise field gradients, but they’re not necessary right now.

The final step simply writes the colours into the texture, clears out any temporary data and returns:

    //write into the texture
    tex.SetPixels(cols);
    tex.Apply();
    m_pixels = null;
    m_x_dims = m_y_dims = 0;
    return tex;

With this lot written, we can start developing different approaches to fill out that grid of pixels, then convert the result to a texture and render it using our SignedDistanceField class.

Brute Force Geometry

The simplest approach to generation is to write a function for each type of geometric primitive we’re interested in (i.e. line/circle/square) that iterates over / potentially modifies every single pixel in the field (hence brute force).

A line

To begin, lets add the function for a line. We’ll call this one “BFLine” to indicate it uses the brute force approach:

//brute force line generator - iterates over every pixel and calculates signed distance from edge of rectangle
public void BFLine(Vector2 a, Vector2 b)
{
    Vector2 line_dir = (b - a).normalized;
    float line_len = (b - a).magnitude;

    for (int y = 0; y < m_y_dims; y++)
    {
        for (int x = 0; x < m_x_dims; x++)
        {
            //mathematical function to get distance from a line
            Vector2 pixel_centre = new Vector2(x + 0.5f, y + 0.5f);
            Vector2 offset = pixel_centre - a;
            float t = Mathf.Clamp(Vector3.Dot(offset, line_dir), 0f, line_len);
            Vector2 online = a + t * line_dir;
            float dist_from_edge = (pixel_centre - online).magnitude;

            //update the field with the new distance
            Pixel p = GetPixel(x, y);
            if (dist_from_edge < p.distance)
            {
                p.distance = dist_from_edge;
                SetPixel(x, y, p);
            }
        }
    }
}

This function:

• Iterates over every pixel in the field, and for each one calculates the distance from the centre of the pixel to the line
• If the calculated distance is lower than the existing one, update it.

The idea here follows naturally from our definition of a signed distance field – each pixel contains the distance to the closest edge of the geometry. A line is really just a single edge when you think about it, so we check every pixel in the field, and if the distance to the line is lower than the distance we have stored, we update it.

I’m going to try and avoid covering the maths for every shape in this blog, as the info is out there and I don’t want to end up writing a maths blog just yet! As this is our first shape though, here it is broken down a little more:

//calculate the centre of the pixel (the +0.5 is because we want the centre, not the corner)
Vector2 pixel_centre = new Vector2(x + 0.5f, y + 0.5f);

//calculate the offset from start of the line (a) to the centre of the pixel
Vector2 offset = pixel_centre - a;

//use a dot product to project the offset onto the line, giving us a 't' value
//then clamp the 't' value to between 0 and line len
float t = Mathf.Clamp(Vector3.Dot(offset, line_dir), 0f, line_len);

//calculate the position of the point of the line using our calculated/clamped t
Vector2 online = a + t * line_dir;

//finally, work out the distance from our pixel to the point on the line
float dist_from_edge = (pixel_centre - online).magnitude;

Before proceeding, lets go back to SignedDistanceField.cs. Right at the bottom you’ll find a ‘custom inspector’ (see the Unity docs here for more info), which lets us add a few extra tools to the inspector for our field object. Within the OnInspectorGUI function is the following code:

SignedDistanceField field = (SignedDistanceField)target;
if (GUILayout.Button("Generate Centre Line"))
{
    SignedDistanceFieldGenerator generator = new SignedDistanceFieldGenerator(16,16);
    generator.BFLine(new Vector2(3.5f, 8.5f), new Vector2(12.5f, 8.5f));
    field.m_texture = generator.End();
}

This button contains the simple code to:

• Create temporary signed distance field generator for a 16×16 field
• Add a line to it using BFLine
• Generate the texture by calling ‘end’ and point our field at it

The resulting render is the one we generated right at the start of this blog:

A circle

Let’s now add the same function for a circle:

//brute force circle generator - iterates over every pixel and calculates signed distance from edge of circle
public void BFCircle(Vector2 centre, float rad)
{
    for (int y = 0; y < m_y_dims; y++)
    {
        for (int x = 0; x < m_x_dims; x++)
        {
            Vector2 pixel_centre = new Vector2(x + 0.5f, y + 0.5f);
            float dist_from_edge = (pixel_centre - centre).magnitude - rad;

            Pixel p = GetPixel(x, y);
            if (dist_from_edge < p.distance)
            {
                p.distance = dist_from_edge;
                SetPixel(x, y, p);
            }
        }
    }
}

Once again, we’re iterating over every pixel, calculating the distance to the edge of the circle, and updating the stored distance if necessary. A new feature in this case however is that the circle is solid, so we generate negative values for pixels inside the circle, and positive values for pixels outside the circle.

As before, we can also add a button to the custom inspector to generate a field using this new function. There’s a few in there, but this is the first one that’s a little more fun:

if (GUILayout.Button("Generate 2 circles"))
{
    SignedDistanceFieldGenerator generator = new SignedDistanceFieldGenerator(16, 16);
    generator.BFCircle(new Vector2(5, 7), 3);
    generator.BFCircle(new Vector2(10, 8), 3.5f);
    field.m_texture = generator.End();
}

Remember our generator doesn’t just write into the pixel buffer – it first checks if the new distance is a better candidate than the stored one. As a result, we can use the function to add a combination of 2 circles, simply by calling it twice with different parameters.

If I remember correctly, the result should be something along these lines:

Note: I may have fiddled with positions/sizes since I took that snap shot. The principle is the same but the numbers might not be!

A rectangle

Without going into too much more detail, here’s the code to generate a rectangle

//brute force rectangle generator - iterates over every pixel and calculates signed distance from edge of rectangle
public void BFRect(Vector2 min, Vector2 max)
{
    Vector2 centre = (min + max) * 0.5f;
    Vector2 halfsz = (max - min) * 0.5f;

    for (int y = 0; y < m_y_dims; y++)
    {
        for (int x = 0; x < m_x_dims; x++)
        {
            //get centre of pixel
            Vector2 pixel_centre = new Vector2(x + 0.5f, y + 0.5f);

            //get offset, and absolute value of the offset, from centre of rectangle
            Vector2 offset = pixel_centre - centre;
            Vector2 absoffset = new Vector2(Mathf.Abs(offset.x), Mathf.Abs(offset.y));

            //calculate closest point on surface of rectangle to pixel
            Vector2 closest = Vector2.zero;
            bool inside;
            if (absoffset.x < halfsz.x && absoffset.y < halfsz.y)
            {
                //inside, so calculate distance to each edge, and choose the smallest one
                inside = true;
                Vector2 disttoedge = halfsz - absoffset;
                if (disttoedge.x < disttoedge.y)
                    closest = new Vector2(offset.x < 0 ? -halfsz.x : halfsz.x, offset.y);
                else
                    closest = new Vector2(offset.x, offset.y < 0 ? -halfsz.y : halfsz.y);
            }
            else
            {
                //outside, so just clamp to within the rectangle
                inside = false;
                closest = new Vector2(Mathf.Clamp(offset.x, -halfsz.x, halfsz.x), Mathf.Clamp(offset.y, -halfsz.y, halfsz.y));
            }
            closest += centre;

            //get offset of pixel from the closest edge point, and use to calculate a signed distance
            Vector3 offset_from_edge = (closest - pixel_centre);
            float dist_from_edge = offset_from_edge.magnitude * (inside ? -1 : 1);

            Pixel p = GetPixel(x, y);
            if (dist_from_edge < p.distance)
            {
                p.distance = dist_from_edge;
                SetPixel(x, y, p);
            }
        }
    }
}

That one may look a little scarier, but only because working out the signed distance to the edge of a rectangle is slightly more complex. If inside, we find the closest point by picking the closest edge and calculating the distance to it, then negate the result (as it’s inside). If outside, we simply clamp our pixel’s centre to within the rectangle, and calculate the distance from the unclamped position to the clamped one.

By now you’re hopefully seeing a pattern appearing, and by the end of this blog there may well be a few more ‘brute force’ functions to play with checked into the git repo.

Indeed, as relatively simple algorithms exist to calculate the distance from any pixel to any edge of any polygon (convex or concave), and also to calculate whether that pixel is inside or outside the polygon, we can generate a field for any arbitrary closed polygon. If the reader wants to have a go at this, here’s a couple of clues:

• You already have the code to find the closest distance from a point to a line (aka edge!)
• You know combining multiple shapes simply involves comparing the existing pixel distance to your new candidate distance.
• To find out if a point is inside or outside a polygon, you simply need to draw a line from anywhere outside your shape to your point, and see how
  many edges it hits along the way. Check out the algorithm
  here

Some problems!

An astute (aka picky!) reader might have noticed a few issues or apparent inconsistencies with the algorithms I’ve described so far. The first point of possible confusion is the slightly misleading ‘is pixel closer’ test:

Pixel p = GetPixel(x, y);
if (dist_from_edge < p.distance)

This is used extensively throughout the code, but at first glance it appears there may be a problem. The distance test works for positive numbers, but for negative numbers, it will technically pass if the distance to the edge of our new shape is closer than the stored one (e.g. -10 is less than -1)!

Fortunately this is not a bug. Currently we are dealing with what are known as Union operations in Constructive Solid Geometry. In simple terms, we want to combine the solid bits of the existing shape with the shape we’re adding. As such, for pixels outside the geometry, we want to keep the closest pixels, but for pixels inside the geometry, we want to keep the deepest pixels.

A scarier problem that’s a little harder to see is that our field can actually become genuinely inconsistent! Lets generate 2 very close rectangles in a relatively hi res (64×64) field:

SignedDistanceFieldGenerator generator = new SignedDistanceFieldGenerator(64, 64);
generator.BFRect(new Vector2(4, 4), new Vector2(60, 35));
generator.BFRect(new Vector2(4, 34), new Vector2(60, 60));
field.m_texture = generator.End();

The result:

At first glance, all looks fine, but what if we go back to visualising the field:

By fiddling with the distance visualiser a bit (see the distance visualisation scale property in the shader), we can clearly show the makeup of our field, the centre line is clearly wrong. Indeed, there shouldn’t actually a centre line!

At its worst, the centre of the rectangle should contain the biggest (negative) distance (it is, after all, the ‘deepest’ pixel), however the distance stored is almost 0. The reason is clear when looking back at our generator. The centre pixel was very close to an inside edge of both rectangles, ergo we’ve only ever tried to write a distance close to 0 into it. In general terms, our distances are correct for outside the solid geometry, but have become inconsistent inside the solid geometry.

This inconsistency rears it ugly head in practice when we try to add a border:

Our border shader algorithm from earlier in the blog assigns a different colour to pixels close to the edge, both inside and outside. As a result, we’ve incorrectly rendered an edge inside the shape.

There’s 2 real approaches to dealing with this. First up, we could just ignore the problem and work around it! Sounds a bit crazy, but sometimes it’s better to ask how you can achieve your goal with the tools you have, rather than spend lots of time making the tools perfect. We could for example create a perfectly reasonable border effect by only colouring pixels outside the field, making the dodgy internal pixels irrelevant. Indeed, many applications deal perfectly well with field inconsistencies, so spending valuable CPU fixing things may be a waste of time! However, if like the Borg perfection be your goal, the next post on sweeping should make you feel much better.

Lastly is our old friend – performance. Our current approach involves iterating over every pixel for every piece of geometry. With the simple stuff so far that’s all well and good, but what if we wanted to render a complex polygon with 5000 edges into a 512*512 texture? 1310720000 operations is what! Fortunately, as we shall see, sweeping comes to the rescue here too.

A quick word on fonts

Right at the start of this series I mentioned SDFs in games had been popularised by fonts, and this post may have taken you some way to seeing why. True type fonts effectively contain a lot of vector based geometry, ideally suited for generating signed distance fields even with the simple approach described above.

Unfortunately, loading ttf files and interpreting their geometry is probably a series in itself. If the reader is interested however, a quick google will reveal a good few c# libraries for loading font geometry. Alternatively, the excellent (and now free) Text Mesh Pro for Unity is SDF driven, and I believe makes it possible to access the raw field data it generates.

Summary

By the time this series is complete, the generator checked in will probably have more functionality than that covered so far. However, with just the tools in this post you now have the power to generate functional signed distance fields. The same principles can even be applied in 3D to voxels, which I may cover down the line! Next up, we’ll move on to refinement/optimisation of fields with an approach called sweeping and look at ways to use it for generating fields from images.

Signed Distance Fields Part 5: Faster generation and sweeping