# Essential Math WeblogThoughts on math for games

## 3/29/2015

### Rendering Signed Distance Fields, Part 3

Filed under: Mathematical,Tutorial — Jim @ 1:59 pm

So Part 1 and Part 2 laid the groundwork for rendering signed distance fields. Now I’ll present a general shader for doing so. This is a reimplementation that retraces the work originally presented by Qin, et al (basically, I missed that paper during my original research).

We can begin by slightly modifying our shader for uniform scaling to use the dFdx() function rather a given inverse scale:
 float distance = texture_lookup(st); float afwidth = 0.7071*dFdx(uv); float coverage = smoothstep(afwidth, -afwidth, distance); 
This shader allows us to use uniform scaling with geometry that is of a proportionally different size from the original distance field, as long as the ratio of width to height of the quad is the same as the distance field.

Here I use the OpenGL convention of using st to represent the normalized texture coordinates, and uv to represent the non-normalized texel space coordinates (the Skia shaders use the opposite convention). Then dFdx(uv) gives the inverse of the mapping from texel space coordinates to pixel coordinates, which is what we want. It’s important that we use non-normalized texel space coordinates here; using normalized texture coordinates introduces an additional scale.

The values for uv and st can either be set in the vertex attributes, or, to save on vertex buffer size, one can be computed from the other in the vertex shader, passing in the texture dimensions as a uniform. In either case, the two values can be passed down as inputs into the fragment/pixel shader.

This is all fine and good, but this still doesn’t handle the cases of non-uniform scale, shear, and (most important for 3D environments) perspective. For this, we’ll need something similar to the shader for ellipses — namely scale afwidth based on how a vector normal to the outline curve is transformed. In that case, we used an approximation to distance that makes use of the gradient vector, or

$dist(x, y) \approx \frac{f(x, y)}{\| \nabla f(x, y) \|}$

And then multiplied the Jacobian by the gradient to get the final distance approximation:

$dist(x, y) \approx \frac{f(x, y)}{\| \mathbf{J} \cdot \nabla f(x,y) \|}$

However, in the distance field case, we don’t have the implicit function $f(x)$ — we have the distance itself. Can we still use this trick? Well, as it happens, in the ideal case the length of the gradient of a distance field is always 1. If we divide the distance by the length of the gradient, we’re dividing by 1 and just get the distance again. So yes, this still works. Then the fragment shader code (in GLSL) would be
 float distance = texture_lookup(st); vec2 grad_dist = vec2(dFdx(distance, dFdy(distance)); vec2 Jdx = dFdx(uv); vec2 Jdy = dFdy(uv); grad = vec2(grad_dist.x * Jdx.x + grad_dist.y*Jdy.y, grad_dist.x * Jdx.y + grad_dist.y*Jdy.y); float afwidth = 0.7071*length(grad); float coverage = smoothstep(afwidth, -afwidth, distance); 

Well… not quite. The gradient of the distance relative to pixel space is already affected by the transformation matrix, so it’s not actually unit length — effectively we’ve already multiplied it by the Jacobian. So then we have:
 float distance = texture_lookup(st); vec2 grad_dist = vec2(dFdx(distance, dFdy(distance)); float afwidth = 0.7071*length(grad_dist); float coverage = smoothstep(afwidth, -afwidth, distance); 

This is similar to a shader presented by Stefan Gustavson.

So ideally, this would be our shader. But alas, the real world is not so ideal. Suppose we’re using an identity matrix. In this case the approximation of the gradient using the dFdx and dFdy functions is not always unit length as we’d expect, particularly near the edge of the shape we’re rendering (ironically where we we’d like it to be the most accurate). And a similar approximation error exists in the case where the matrix is non-identity. The solution is go back to the previous shader, and to normalize the gradient before multiplying by the Jacobian, or
 float distance = texture_lookup(st); vec2 grad_dist = normalize(vec2(dFdx(distance, dFdy(distance))); vec2 Jdx = dFdx(uv); vec2 Jdy = dFdy(uv); grad = vec2(grad_dist.x * Jdx.x + grad_dist.y*Jdy.y, grad_dist.x * Jdx.y + grad_dist.y*Jdy.y); float afwidth = 0.7071*length(grad); float coverage = smoothstep(afwidth, -afwidth, distance); 

One caveat on this: the values for dFdx() and dFdy() are computed in 2×2 blocks. If you’re not using floats for your distance field and the texture is large enough it’s possible that you can’t accurately represent all the distance values in the interior of the shape — once you exceed the range of your representation you’ll have to clamp to the maximum distance. This may produce 2×2 blocks where all the values are the same. In that case the gradient computed will have a length of 0 (nothing is changing in that area). This will have two effects. First, on some GPUs that use tiled rendering (e.g. some Adrenos) normalizing a zero vector can cause the entire tile to fail, ending up with a square where nothing is rendered. Secondly, even if that doesn’t fail, the length of the transformed gradient will also be 0, which means afwidth will be 0, which means the coverage will be 0. This is probably not the right result (especially in the interior).

The easy answer is to use floats or half floats. However, it’s possible you don’t want to use the extra memory — so the next obvious approach is to check for zero-length gradients (which is what we do in Skia). However, this does add a conditional to your shader, which may not be efficient.

As I write this, a couple of completely untested solutions come to mind. The first is to change the u8 encoding to allow more integer values (e.g. use 4.4 fixed point versus 3.5 fixed point). This may affect the quality of the edges though, as the fractional precision is now more limited. The second is to invert the smoothstep calculation so the interior produces 0 and the exterior produces 1:
 float coverage = 1.0 - smoothstep(-afwidth, afwidth, distance); 
This assumes that there are no distance values outside the contour that are outside the representable range. However, since the texture should be tightly bounded around the contour it’s possible that all values outside the shape are representable. Note that for this second solution you’ll still end up with zero-length gradients so you’ll still have to have a check for those tiled architectures. As said, both these solutions are off the top of my head, so no guarantees here.

And that’s it for distance fields. Hope you liked this series, and if you have any corrections or questions, feel free to comment below.

1. Interesting series. Have you thought about varying the sampling rates to decrease the distortions you mention in part 2? Like using low sample rates where the field has low detail while using high sample rates where the field has high detail?

Comment by John Smith — 4/30/2015 @ 7:58 pm

2. Thanks for the great posts, Jim!

There’s currently a small typo in a couple of the code snippets:

The first Jdy.y should be Jdy.x (according to the Skia code anyway!)

Comment by Steve — 5/18/2015 @ 12:50 pm

3. I bought your book while on vacations in the U.S. the CD-ROM was damaged and now I cannot access to the full contents of the book. I contacted CRC but they cannot do much for me, it sucks, nowadays nearly all books have the resources online instead of a CD-ROM. I don’t know why you guys did this. I cannot travel back to New York to get my CD replaced. I don’t think I’ll never buy a CRC book ever again or a book written by you guys. I just wasted \$60 dls

Comment by Rob — 6/10/2015 @ 8:56 am

4. John Smith – we’ve considered doing that, but it adds a lot of complexity to the algorithm. The GPU is much happier rendering textures of uniform density. One possibility might be to use mipmaps, but making that work with a texture atlas is tricky.

Steve – thanks, I’ll correct it.

Rob – I think we’ve already communicated about this. I can make the source code for the Second Edition available for anyone who needs it. The source code for the Third Edition will be hosted on GitHub, and should be live by the end of the month.

Comment by Jim — 8/4/2015 @ 2:58 pm

5. Hi, nice article, thanks for sharing.

Instead of checking for zero length, you could also add 0.0001 to afwidth to prevent this. As a single MADD instruction, this would not change performance. Also, I noticed that the shader misbehaves when you rotate the shape between 45 and 135 degrees, because then the X and Y derivatives are swapped. I fixed this by using:

grad = vec2(grad_dist.x * max( Jdx.x, Jdx.y ) + grad_dist.y * max( Jdy.x, Jdy.y), grad_dist.x * min( Jdx.x, Jdx.y ) + grad_dist.y * min( Jdy.x, Jdy.y ) );

-Paul

Comment by Paul — 7/25/2016 @ 5:54 pm

6. On second thought (and after doing additional research), I would very much like to erase my previous remarks. Wish I could do that myself, hehe 🙂

-Paul

Comment by Paul — 7/26/2016 @ 9:28 am