twitter:
I’m writing this article because the last time I had to generate a signed-distance field, I couldn’t find much good code to actually do it. So I’m posting this to help out anyone looking for info.
What’s a signed-distance field?
Imagine you’ve got a black-and-white image, where let’s say the black parts are considered inside, and the white parts are considered outside. What you want is a quick method of looking up how far it is from any given point to the inside.
A SDF is just an image where each pixel contains the distance to the nearest point on the boundary. So if a pixel is outside, it’ll contain maybe +10 if it’s 10 pixels away. If it’s inside, it’ll contain -10.
Source code
There’s a simple linear-time algorithm for computing a SDF. (there’s also a n-log-n algorithm if you want to do it on a GPU, but I’m just giving the simple CPU case here). The algorithm is called 8SSEDT, and there’s a paper on it here. Careful though, as there’s some bugs in the paper.
We define our pixel grid like so –
{
int dx, dy;
int DistSq() const { return dx*dx + dy*dy; }
};
struct Grid
{
Point grid[HEIGHT][WIDTH];
};
dx/dy contain the offset from this pixel to the nearest pixel on the opposing side. We’ll actually need two grids, as each one only contains the positive distance. To get the true signed distance, we’ll have to do it twice and merge the results.
We initialize the grids to either (0,0) if the pixel is ‘inside’, or (+INF,+INF) if it’s outside. Note: don’t make your +INF value too big or it’ll overflow when you square it.
{
Put( grid1, x, y, inside );
Put( grid2, x, y, empty );
} else {
Put( grid2, x, y, inside );
Put( grid1, x, y, empty );
Now all we have to do is run the propagation algorithm. See the paper for exactly what’s happening here, but basically the idea is to see what the neighboring pixel has for it’s dx/dy, then try adding it onto ours to see if it’s better than what we already have.
{
Point other = Get( g, x+offsetx, y+offsety );
other.dx += offsetx;
other.dy += offsety;
if (other.DistSq() < p.DistSq())
p = other;
}
void GenerateSDF( Grid &g )
{
// Pass 0
for (int y=0;y<HEIGHT;y++)
{
for (int x=0;x<WIDTH;x++)
{
Point p = Get( g, x, y );
Compare( g, p, x, y, -1, 0 );
Compare( g, p, x, y, 0, -1 );
Compare( g, p, x, y, -1, -1 );
Compare( g, p, x, y, 1, -1 );
Put( g, x, y, p );
}
for (int x=WIDTH-1;x>=0;x--)
{
Point p = Get( g, x, y );
Compare( g, p, x, y, 1, 0 );
Put( g, x, y, p );
}
}
// Pass 1
for (int y=HEIGHT-1;y>=0;y--)
{
for (int x=WIDTH-1;x>=0;x--)
{
Point p = Get( g, x, y );
Compare( g, p, x, y, 1, 0 );
Compare( g, p, x, y, 0, 1 );
Compare( g, p, x, y, -1, 1 );
Compare( g, p, x, y, 1, 1 );
Put( g, x, y, p );
}
for (int x=0;x<WIDTH;x++)
{
Point p = Get( g, x, y );
Compare( g, p, x, y, -1, 0 );
Put( g, x, y, p );
}
}
}
And that’s it! All you have to do afterwards is run a quick pass to reconstruct the final signed distance value from the two positive ones:
int dist2 = (int)( sqrt( (double)Get( grid2, x, y ).DistSq() ) );
int dist = dist1 - dist2;
Here’s the full source code for this article:
8ssedt.zip
[155.54KB] - 8SSEDT source code + demo
Hi. Thanks for the nice concise code. I’ve been trying to understand the technique whereby you store two different distance fields in the red and green channels of the font bmp. Apparently it helps preserve the sharp points of the font. Are you aware of the technique and how you generate the two distance fields? Valve mention the technique in their paper…but it’s kinda vague.
Thanks in advance,
Neil
· Sep 14, 12:30 PM · #
Hi,
nice article, but I really don’t like how you state “Careful though, as there’s some bugs in the paper.” but don’t actually tell what those bugs are. That comes off as FUD-spreading, trying to assert your competence.
Do you remember anymore what the problems were with the original paper?
· Feb 2, 02:46 AM · #
Ooh, get you.
I did write this 3 years ago, so I’ve forgotten it all by now.
I read through the paper again, and I could have sworn there was a typo in their diagram of the mask weights originally, which necessitated a careful read-through of the text to work out the correct ones. But I can’t find anything wrong in there now so damned if I know.
· Feb 2, 04:39 PM · #