How do I efficiently calculate the distance to the edge of a shape?

Question

I'm trying to implement something like an "inner glow".

That is, I have an image which defines the shape of an object, and then I want to create overlay that is a gradient that goes from the edge of the shape and into the shape itself. In programs like Photoshop and Krita, this is called an inner glow.

If I could first produce a texture which contained values that represented distance along the inward travel path from the edge, the rest would be easy.

I want this to happen in a shader, but any general insights about the problem would be helpful, I guess. One idea that I was working with, was to just blur the outline, and call the result shades around the edges the "distance", but this might be an unnecessarily expensive operation on the GPU, maybe not, I don't know.

A naive approach would be to check all distances to all other pixels, which comes out to something like 256⁴ square root calculations for a 256x256 pixel image. I believe that's not optimal. Also I don't know if that's even possible in a shader.

Answer 1

A texture that stores distance from the edge of the shape, like you described, is called a "distance field" (you'll find lots of results if you google that phrase). Distance fields can be calculated efficiently on the GPU using the jump flooding algorithm (JFA).

This is a multi-pass algorithm that works by sampling pixels at a distance of first ½ the image size, then ¼, then ⅛, and so on down to single pixels. At the end it comes out with a texture with the shortest distance from each pixel to any of the initial "seed" pixels you put in (which would be along the edge of your shape). For more details see the paper, or also check out this blog post by Alan Wolfe which also has some shadertoys with example implementations.

Another article which may interest you is The Quest For Very Wide Outlines by Ben Golus, which addresses this exact issue, discusses a wide variety of GPU implementations (and settles on JFA), and addresses some of the implementation details such as using JFA on an antialiased edge.