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