If you’re into rendering scalable, high quality fonts in video games using a single texture, there is no doubt you have encountered the infamous paper by Chris Green published in 2007. The basic idea is to get a high resolution image of a font glyph, calculate the distance of any pixel to the closest pixel that is the opposite of its own color (black or white). By using these values as a texture and thresholding on a middle value, we can scale the font in a very smooth fashion using bilinear filtering, which is “free” in a shader. More amazingly, the paper points out that we can shrink the SDF result into an 8-bit 64x64 image and still get fantastic results. This is the basis for this font rendering technique.
The question is, how do you compute this SDF? From the definition it sounds like a computationally expensive operation if a naïve method is used since you’d have to check the distance between every pair of pixels, and O(n²) technique. This is unacceptable for the large resolution we need to calculate.
Now if you’re familiar with this concept you’ve probably encountered the libgdx repository that contains more implementation details on the matter. Perhaps you’ve encountered a GPU algorithm to compute the distance from actual vector graphics. But, other than the widely cited papers by by Danielson and Leymarie and Levine, and this excellent write up that uses dead reckoning, and the tour de force paper by Fabbri et al. featuring O(n) algorithms, you’ll find very little accessible material on actually generating the SDF in an efficient and exact manner.
I will attempt to rectify this matter in this post. I will not deal with the more advanced subject of using three fields to do text rendering known as multi-channel SDF, only the computation of a SDF. My aim is to further the understanding of the SDF problem and to present a solution that gives exact results without incurring the extremely expensive brute force method running cost, nor the programming complexity of algorithms based on Voronoi partitions.
The approach I will take will be closest to that presented in the paper “Fast Euclidean Distance Transform using a Graph-Search Algorithm” which is a recommended reading. The algorithm has been independently formulated by me, but it seems to have an almost identical first stage to the dead reckoning algorithm and makes use of Djikstra’s algorithm.
SDF in one dimension
Let’s start with a very simple, but instructive example. Imagine a single black pixel in the middle of a 1 dimensional image. Let’s represent color with circles in the center of a pixel and also place borders between each of the circles which are also the pixel borders.
I will define the SDF border for the image as any pixel border which has a transition from a black to white pixel or vice versa. This is represented as the solid black lines below:
The distance from the black pixel center to the border is exactly half a pixel:
Here is where the signed part of the SDF comes in. We define the black pixels as the “solid” part of the image while the white pixels are the “blank” parts. Any pixel on the interior should have its distance to the exterior be negative. Similarly, any pixel on the outside of the solid shape will have a positive distance to the nearest solid boundary. Let’s calculate the SDF for this image using the principles outlined so far:
You will be able to confirm that the numbers correspond to the signed distance from the closest of the two boundary lines in the image above. Make sure you verify this for yourself for the next part to make sense. A lot of people may define the black pixel as having a distance 0 and the two white pixels around it as having a distance 1. This is also fine but our more precise and consistent definition will greatly aid us when we go into two dimensions.
SDF in two dimensions
To make life initially simple (don’t get your hopes up, it will get complicated shortly), let’s use the same set up in two dimensions, with a pixel in the middle of a 5x5 square:
The image above shows the boundary created by the pixel and the surrounding “blank” pixels. Depending on the intended boundary shape, the resultant SDF will be different, for example in the case of circles. We use square pixels in the description to follow because it is the easiest shape illustrate. In any case, let’s calculate the SDF for a select few pixels by measuring the distance (in units of pixels, as before) from the pixel center to the closest part of the boundary:
In this result, the square roots arise from the use of the Euclidian distance metric (or Pythagoras for those inclined) and the distance itself is the magnitude of the vectors shown. A different metric will result in a different shape but Euclidian works best
It’s easy enough to do this by hand and for the small example shown here, but what about doing this programmatically? We somehow have to account for the pixels diagonal to the black pixel having their closest point of the boundary be the nearest corner.
There are eight pixels in the region immediately outside of our single solid block, but their vector to the boundary can be computed programmatically: their vector to the boundary will be exactly half of their vector to the center of the pixel.
We could stop here with a less naïve algorithm but one that will still be computationally wasteful: For every pixel in the image, test every distance to every corner or flat edge part of the boundary. As the perimeter will be (in the typical case) a square root of the area involved, we would have reduced our O(n²) problem to a O(n^(3/2)) problem. We can further simplify the solution by searching for the closest boundary pixel of the opposite color for the set of boundary pixels available. In the degenerate case of single pixel stripes across the image however, we’re back to the same bad performance as before.
To reiterate the problem, for every exterior (white) pixel, we want to find the shortest distance to the boundary. We can also obtain this by finding the shortest path to the boundary instead, then calculate the distance making use of vector addition along the way. We should then notice that any path whose destination is the closest boundary edge or corner. Now, keeping track of a heterogenous set of edges, corners and pixels is annoying and would make any program that deals with it a total mess. It’s much easier if we only had to deal with pixels. Happily, you will note in figure 7 that every one of the eight adjacent pixel corresponds to either one of the four edges or four corners of the interior single pixel wall. It is trivial to demonstrate that this is true of any shape!
We can therefore reduce the problem further: To find any path whose destination is to the closest white pixel that is adjacent to the boundary. We will now demonstrate this principle with a larger pixel and extract further simplifying results. Cast your eyes on the figure below with the exterior pixels immediately adjacent to the boundary line marked in blue.
We can find both these adjacent pixels and their shortest paths by scanning through the entire image interior pixels and evaluating any pixel on the exterior, as before giving it half of the vector that directs it to the closest interior pixel center. This can be done by checking if the currently marked pixel is indeed the closest one for this initial pass. We get the result that follows:
Lets do the same thing again for the pixels surrounding the blue pixels, but finding the closest edge or corner of the boundary as described by the basic problem. We will do one layer by finding the smallest new vector each time.
And once again.
Let’s focus on the bottom left hand corner of this figure to demonstrate an important fact that will help us turn our intuitive process so far into an algorithm. Examining figure 12, you will note that for each of the orange pixels, determining the closest blue pixel is sufficient enough to determining the distance to the closest part of the boundary. This is because the blue pixels have already had their closest distances computed and we can simply add the orange pixel’s displacement to them to the overall vector sum.
If you return to both figures 10 and 11 you will notice that this principle holds for all the pixels. If we call the orange pixels the open set and the blue pixels the closed set, then it is sufficient to determine the closest open set pixel to any closed set pixel to determine its closest distance to the boundary using vector addition. Once this is done, an open set pixel joins the closed set and participates in the determination of the closest pixels.
Now, scanning the field each time would give us no advantage over the naïve algorithm shown at the start. Furthermore, being too eager with the calculation and only checking one layer at a time will introduce errors into the computation since the corner points will propagate faster and may override shorter paths coming in from another wave front. We could stage the corner propagation after every other phase has had a chance, but then arbitrating different wave fronts may create additional work that negates the performance advantage the eager method introduces. Instead, algorithms will typically make use of Voroni partitions to account for this situation.
To keep the algorithm simple while still remaining performant, we can instead use Dijkstra’s shortest path algorithm, to find the shortest distance in the open set at each point in time, add all of its neighbors to a queue and use the magnitude distance as the priority value, sorting by the lowest value first. Through the action of the priority queue, only the wave front will propagate from the shortest distance first, guaranteeing us the correct value for the SDF.
We now have enough information to create an algorithm for the calculation of the SDF for the exterior pixels which we will then very easily generalize to the interior pixels. The algorithm is as follows:
Initialization
- Create a boolean array closed, which indicates the closed status for every pixel in the image. Initialize it to false.
- Create a two-integer valued array dist that stores the vector distance for the entire image, initialize it to an “infinite” value (or one greater than the twice the width of the image).
- Create a priority queue, pq which has a key of magnitude distance, and a pair of values indicating which pixel is being updated and the direction of its vector. To make your life easier, the key should be calculated automatically as the item insertions happen.
[A] Seed Phase
- Find every filled (black) pixel in the image.
- For each of these filled pixels, add every unfilled (white) neighbor to pq, with a distance vector equal to half the distance between the pixels. This will be the distance to the boundary.
[B] Propagation Phase
- While the pq queue is not empty, pop the top element, and let us call it current.
- Check if the current pixel’s closed boolean is true, if so, return to step 1.
- Set current pixel closed to true.
- Store current’s distance in dist.
- For every neighbor of current which is not filled and not closed, calculate the distance by adding the current pixel’s own distance to the boundary and the full distance (rather than half as before) to the pixel.
- Use the values calculated in 6 to push the pixel into pq.
- Return to step 1.
And that’s all there is to it. The seed phase will find the immediately adjacent pixels (so called ‘seed pixels’), calculate their half distances, then the propagation phase will fairly propagate a wave front emitted from these pixels. You’ll note that there is an inefficiency in 3.[B], because we are adding pixels to the queue without caring about whether it has already been added. This helps us use standard priority queue data structures which lack the decrease_key operation.
Putting it all together
So now we have an algorithm that can calculated the distance vector for every unfilled pixel, but what about the filled pixel.
It takes a moment to realize that the algorithm described above is perfectly symmetrical. That means we can use it to calculate the distance field for all of the unfilled pixels, then flip the image and calculate it for the filled pixels. This makes it very straight-forward to implement and worth the small effort above the brute force algorithm.
Now that we have the vectors for each pixel, we then use the Euclidian metric to calculate all the distances. To make it a signed distance field, simply negate that distance if its on the interior (i.e. if the pixel is filled).
One final finishing touch: We often want to render the output into an image, usually a 8-bit grayscale image and what we have described so far will only get us a floating point array. This is not hard to get around, simply choose a maximum distance value dependent on the image an application and scale every floating point value in the image such that the threshold is reached at some desired integer value.
C++ Implementation
The following code implements the above described algorithm. You may use the MIT license if you wish to use it in your project but please let me know over on TKMI-kyon if you find it useful in your project.
#include <cassert>
#include <vector>
#include <functional>
#include <queue>
#include <utility>using namespace std;// We use 64-bit integers to avoid some annoying integer math
// overflow corner cases.
using Metric = function<float(int64_t, int64_t)>;float euclidian(int64_t dx, int64_t dy) {
return sqrt(dx * dx + dy * dy);
}vector<float> sdf(
const vector<bool>& in_filled, int width) {
const auto height = in_filled.size() / width;
// Initialize vectors represented as half values.
vector<pair<int, int>> half_vector(
in_filled.size(), {2 * width + 1, 2 * height + 1});
sdf_partial(in_filled, width, &half_vector, euclidian, false);
sdf_partial(in_filled, width, &half_vector, euclidian, true);
vector<float> out(in_filled.size());
for (size_t i = 0; i < half_vector.size(); i++) {
auto [dx, dy] = half_vector[i];
out[i] = metric(dx, dy) / 2;
if (in_filled[i])
out[i] = -out[i];
}
return out;
}void sdf_partial(
const vector<bool>& in_filled, int width,
vector<pair<int,int>>* in_half_vector, Metric metric, bool negate) {
assert(width != 0);
const auto height = in_filled.size() / width;
assert(height != 0);
auto valid_pixel = [&](int x, int y) {
return (x >= 0) && (x < width) && (y >= 0) && (y < height); };
auto coord = [&](int x, int y) { return x + width * y; };
auto filled = [&](int x, int y) -> bool {
if (valid_pixel(x, y))
return in_filled[coord(x, y)] ^ negate;
return false ^ negate;
};
// Allows us to write loops over a neighborhood of a cell.
auto do_neighbors = [&](int x, int y, function<void(int, int)> f){
for (int dy = -1; dy <= 1; dy++)
for (int dx = -1; dx <= 1; dx++)
if (valid_pixel(x + dx, y + dy))
f(x + dx, y + dy);
}; auto& half_vector = *in_half_vector;
vector<bool> closed(in_filled.size()); struct QueueElement {
int x, y, dx, dy;
float dist;
};
struct QueueCompare {
bool operator() (QueueElement& a, QueueElement& b) {
return a.dist > b.dist;
}
};
priority_queue<
QueueElement, vector<QueueElement>, QueueCompare> pq;
auto add_to_queue = [&](int x, int y, int dx, int dy) {
pq.push({ x, y, dx, dy, metric(dx, dy) });
}; // A. Seed phase: Find all filled (black) pixels that border an
// empty pixel. Add half distances to every surrounding unfilled
// (white) pixel.
for (int y = 0; y < height; y++) {
for (int x = 0; x < width; x++) {
if (filled(x, y)) {
do_neighbors(x, y, [&](int x2, int y2) {
if (!filled(x2, y2))
add_to_queue(x2, y2, x2 - x, y2 - y);
});
}
}
} // B. Propagation phase: Add surrounding pixels to queue and
// discard the ones that are already closed.
while (!pq.empty()) {
auto current = pq.top();
pq.pop();
// If it's already been closed then the shortest vector has
// already been found.
if (closed[coord(current.x, current.y)])
continue;
// Close this one and store the half vector.
closed[coord(current.x, current.y)] = true;
half_vector[coord(current.x, current.y)] = {
current.dx, current.dy };
// Add all open neighbors to the queue.
do_neighbors(current.x, current.y, [&](int x2, int y2) {
if (!filled(x2, y2) && !closed[coord(x2, y2)]) {
int dx = 2 * (x2 - current.x);
int dy = 2 * (y2 - current.y);
auto [ddx, ddy] = half_vector[coord(current.x, current.y)];
dx += ddx;
dy += ddy;
add_to_queue(x2, y2, dx, dy);
}
});
}
}
Note that the code will require C++17 to compile but has no other dependencies. The input image should be a vector of booleans with a size of width * height otherwise the assertions in the sdf_partial function will fail.
Example
We have an illustrative example thanks to my friend @FerdysLab9. Shown below is a thresholded image from one of his drawings of a very cute small fairy:
Using the brute force method would take way too long for this image, but takes a fraction of a second with the method outlined in this article:
This image can be shrunk down using bilinear filtering and then used as the SDF image to reproduce the original graphic. If you have Photoshop or a similar program, take the image above and apply “Threshold” and then “Invert” to see it for yourself. You will notice that after some scaling, there is no “smoothing” going on because of the square pixel shape we have chosen for the boundary. Even these edges are reproduced! This may be discussed further in a planned future article. For a bit of fun, we played with the thresholding of the image and created a little animation:
The potential use for this technique should not be underestimated! All kinds of cool effects can be dreamt up!
Closing words
There are plenty more things to discuss about SDFs, fonts and what not. It’s become a personal interest of mine since they’re so darn useful and not just in font rendering.
If you enjoyed this article, please mention me on twitter @tmkikyon. Any corrections and related links would be more than welcome too. Thank you and have a great time!
