## Signed Distance Fields February 18th, 2009

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 -

struct Point { 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.

if ( g < 128 ) { 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.

void Compare( Grid &g, Point &p, int x, int y, int offsetx, int offsety ) { 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 dist1 = (int)( sqrt( (double)Get( grid1, x, y ).DistSq() ) ); int dist2 = (int)( sqrt( (double)Get( grid2, x, y ).DistSq() ) ); int dist = dist1 - dist2;

Here's the full source code for this article:

### Written by Richard Mitton,

software engineer and travelling wizard.

Follow me on twitter: http://twitter.com/grumpygiant