How do I efficiently calculate the distance to the edge of a shape?
A texture that stores distance from the edge of the shape, like you described, is called a &quot;distance field&quot; (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 &quot;seed&quot; 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.