codersnotes

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?

Before

After

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:

• Source code