Chris Green of Valve Software wrote a very cool
graphics paper in 2007 that I think deserves more attention.^{[5]} The paper describes a simple way to preserve high-quality
edges in vector art (typically text) when storing the art in a relatively
low-resolution texture. If you’d like to minimize distraction while coming
up to speed with OpenGL, go ahead and skip this section; distance fields
are a somewhat advanced concept, and they are not required in simple
applications. However, I find them fascinating!

Let’s review the standard way of rendering text
in OpenGL. Normally you’d store the glyphs in a texture whose format is
`GL_ALPHA`

, and you’d set up a fairly standard blending
configuration, which would probably look like this:

glEnable(GL_BLEND); glBlendFunc(GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA);

If you’re using ES 1.1, you can then set the
color of the text using `glColor4f`

. With ES 2.0, you can store the color in a uniform
variable and apply it in your fragment shader.

That’s a perfectly reasonable approach, but if you zoom in far enough on your texture, you’ll see some fuzzy stair-stepping as shown in the leftmost panel in Figure 7-5. The fuzziness can be alleviated by replacing blending with alpha testing (Alpha Testing), but the stair-stepping remains; see the middle panel.

You’ll almost always see stair-stepping when
zooming in with bilinear filtering. Third-order texture filtering (also
known as *cubic filtering*) would mitigate this, but
it’s not easy to implement with OpenGL ES.

It turns out there’s a way to use bilinear
filtering and achieve higher-quality results. The trick is to generate a
*signed distance field* for your glyphs. A distance
field is a grid of values, where each value represents the shortest
distance from that grid cell to the glyph boundary. Cells that lie inside
the glyph have negative values; cells that lie outside have positive
values. If a grid cell lies exactly on the boundary of the glyph, it has a
distance value of zero.

To represent a distance field in an OpenGL texture, we need a way to map from the signed distance values to grayscale. One approach is to represent a distance of zero as half-black (0.5) and then to choose maximum and minimum distances, which get mapped to 1.0 and 0. (This effectively clamps large distances, which is fine.) Figure 7-6 shows a distance field for the mystical Aum symbol. Figure 7-7 zooms in on a portion of the Aum distance field with the original glyph boundary represented as a black line.

The concept of a distance field may seem obscure, but it’s useful in many surprising ways. Not only does it provide a way to preserve quality of edges (with both ES 1.1 and ES 2.0), but it also makes it easy to apply a bevy of text effects, such as shadows and outlines (these are ES 2.0 only).

Before diving in to the application of
distance fields, let’s take a look at how to generate them. The most
popular way of doing this is actually quite simple to implement, despite
having a ridiculously complex name: “the eight-points signed sequential
Euclidean distance transform algorithm,” or 8SSEDT for short. The basic
idea is to store a pair of integers at each grid cell
(`dx`

and `dy`

), which represents the
number of cells between it and the nearest cell on the opposite side of
the vector boundary. Each cell is initialized to either (0, 0) or (+∞,
+∞), depending on whether the cell is inside the vector. The algorithm
itself consists of “propagating” the distances by having each cell
compare its dx:dy pair to its neighbor and then adding it to the current
cell if it’s closer. To achieve a signed distance, the algorithm is run
on two separate grids and then merges the results.

Let’s momentarily go back to using Python and the PIL library since they provide a convenient environment for implementing the algorithm; see Example 7-9.

Example 7-9. Distance field generation with Python

import os import math from PIL import Image inside, outside = (0,0), (9999, 9999) def invert(c): return 255 - c def initCell(pixel): if pixel == 0: return inside return outside def distSq(cell): return cell[0] * cell[0] + cell[1] * cell[1] def getCell(grid, x, y): if y < 0 or y >= len(grid): return outside if x < 0 or x >= len(grid[y]): return outside return grid[y][x] def compare(grid, cell, x, y, ox, oy): other = getCell(grid, x + ox, y + oy) other = (other[0] + ox, other[1] + oy) if distSq(other) < distSq(cell): return other return cell def propagate(grid): height = len(grid) width = len(grid[0]) for y in xrange(0, height): for x in xrange(0, width): cell = grid[y][x] cell = compare(grid, cell, x, y, -1, 0) cell = compare(grid, cell, x, y, 0, -1) cell = compare(grid, cell, x, y, -1, -1) cell = compare(grid, cell, x, y, +1, -1) grid[y][x] = cell for x in xrange(width - 1, -1, -1): cell = grid[y][x] cell = compare(grid, cell, x, y, 1, 0) grid[y][x] = cell for y in xrange(height - 1, -1, -1): for x in xrange(width - 1, -1, -1): cell = grid[y][x] cell = compare(grid, cell, x, y, +1, 0) cell = compare(grid, cell, x, y, 0, +1) cell = compare(grid, cell, x, y, -1, +1) cell = compare(grid, cell, x, y, +1, +1) grid[y][x] = cell for x in xrange(0, width): cell = grid[y][x] cell = compare(grid, cell, x, y, -1, 0) grid[y][x] = cell def GenerateDistanceField(inFile, outFile, spread): print "Allocating the destination image..." image = Image.open(inFile) image.load() channels = image.split() if len(channels) == 4: alphaChannel = channels[3] else: alphaChannel = channels[0] w = alphaChannel.size[0] + spread * 2 h = alphaChannel.size[1] + spread * 2 img = Image.new("L", (w, h), 0) img.paste(alphaChannel, (spread, spread)) width, height = img.size print "Creating the two grids..." pixels = img.load() grid0 = [[initCell(pixels[x, y]) \ for x in xrange(width)] \ for y in xrange(height)] grid1 = [[initCell(invert(pixels[x, y])) \ for x in xrange(width)] \ for y in xrange(height)] print "Propagating grids..." propagate(grid0) propagate(grid1) print "Subtracting grids..." signedDistance = [[0 for x in xrange(width)] for y in xrange(height)] for y in xrange(height): for x in xrange(width): dist1 = math.sqrt(distSq(grid0[y][x])) dist0 = math.sqrt(distSq(grid1[y][x])) signedDistance[y][x] = dist0 - dist1 print "Normalizing..." maxDist, minDist = spread, -spread for y in xrange(height): for x in xrange(width): dist = signedDistance[y][x] if dist < 0: dist = -128 * (dist - minDist) / minDist else: dist = 128 + 128 * dist / maxDist if dist < 0: dist = 0 elif dist > 255: dist = 255 signedDistance[y][x] = int(dist) pixels[x, y] = signedDistance[y][x] print "Saving %s..." % outFile img.save(outFile) if __name__ == "__main__": inFile, outFile = 'Aum.png', 'DistanceFieldAum.png' GenerateDistanceField(inFile, outFile, spread = 15)

Don’t let Example 7-9 scare you! You’re in good shape if you simply grok the concept of a distance field. The formal proof of the generation algorithm is beyond the scope of this book, but you can always flip back to Generating Distance Fields with Python to review it at a high level.

To make use of a distance field with iPhone models that support only OpenGL ES 1.1, simply bind the distance field texture and enable alpha testing with a threshold value of 0.5:

glDisable(GL_BLEND); glEnable(GL_ALPHA_TEST); glAlphaFunc(GL_LESS, 0.5);

Remember, blending applies an equation at every pixel to determine the final color, while alpha testing compares the source alpha with a given value and leaves the framebuffer unchanged if the comparison fails.

One of the reasons I love distance fields is that they enable more than quality enhancements. On iPhone models that support OpenGL ES 2.0, distance fields can be used in conjunction with a fragment shader to achieve a variety of special effects, all using the same source bitmap. See Figure 7-8.

The first distance field effect that I want to cover is smoothing, as shown in the leftmost panel in Figure 7-8.

Go back and take another look at the big stair steps in the left-most panel in Figure 7-5; they correspond to the texels in the source image. Alpha testing with a distance field fixed this up (rightmost panel), but it still exhibits pixel-level aliasing. This is because the rasterized pixels are always either fully lit or discarded; there are no shades of gray. We can fix this up with a fragment shader.

Before diving into the shader code, let’s
take a look at GLSL’s `smoothstep`

function. Here’s the
declaration:

float smoothstep(float edge0, float edge1, float x)

`smoothstep`

returns 0.0 if
`x`

is less than or equal to `edge0`

and returns 1.0 if `x`

is greater than or equal to
`edge1`

. If `x`

is between these two
values, then it interpolates between 0 and 1. Calling
`smoothstep`

is equivalent to the following:

float t = clamp ((x – edge0) / (edge1 – edge0), 0.0, 1.0); return t * t * (3.0 – 2.0 * t);

To see how `smoothstep`

comes in handy for smoothing, visualize two new boundary lines in the
distance field: one at `edge0`

(a deflated version of
the glyph), the other at `edge1`

(an inflated version
of the glyph). See Figure 7-9; the middle
line is the region where distance = 0.

Alpha should be opaque at
`edge0`

and transparent at `edge1`

. To
achieve smoothing, the fragment shader needs to create an alpha ramp
between these two boundaries. Example 7-10
shows an implementation.

Example 7-10. Naive fragment shader for distance field smoothing

varying mediump vec2 TextureCoord; uniform sampler2D DistanceField; uniform mediump vec3 GlyphColor; const mediump float SmoothCenter = 0.5; const mediump float SmoothWidth = 0.04; void main(void) { mediump vec4 color = texture2D(DistanceField, TextureCoord); mediump float distance = color.a; mediump float alpha = smoothstep(SmoothCenter - SmoothWidth, SmoothCenter + SmoothWidth, distance); gl_FragColor = vec4(GlyphColor, alpha); }

The fragment shader in Example 7-10 is fairly easy to understand, but
unfortunately it suffers from a fundamental flaw. The value of
`SmoothWidth`

is always the same, regardless of how
much the glyph is magnified. As a result, anti-aliasing is too blurry
when the camera is near the texture (Figure 7-10), and it’s ineffective when the camera is
very far away.

Fortunately, the iPhone supports a fragment shader extension to help out with this. Unfortunately, it’s not supported in the simulator at the time of this writing.

It’s easy to deal with this disparity. At runtime, check for extension support using the method described in Dealing with Size Constraints. Compile fragment shader A if it’s supported; otherwise, compile fragment shader B.

The name of this extension is
`OES_standard_derivatives`

. That’s right,
“derivatives.” Don’t run in fear if this conjures up images of a brutal
calculus professor! It’s not as bad as it sounds. The extension simply
adds three new functions to GLSL:

float dFdx(float f); float dFdy(float f); float fwidth(float f)

These functions are available only to the
fragment shader. They return a value proportional to the rate of change
of the argument when compared to neighboring pixels. The
`dFdx`

function returns a rate of change along the
x-axis; the `dFdy`

function returns a rate of change
along the y-axis. The `fwidth`

function provides a
convenient way of combining the two values:

fwidth(f) = abs(dFdx(f)) + abs(dFdy(f))

In our case, when the camera is far away, the rate of change in the on-screen distance field is greater than when the camera is close-up. To achieve consistent anti-aliasing, we’ll simply use a larger filter width when the camera is far away. See Example 7-11 for a new version of the fragment shader that uses derivatives.

Example 7-11. Corrected fragment shader for distance field smoothing

#extension GL_OES_standard_derivatives : enablevarying mediump vec2 TextureCoord; uniform sampler2D DistanceField; uniform mediump vec3 GlyphColor; const mediump float SmoothCenter = 0.5; void main(void) { mediump vec4 color = texture2D(DistanceField, TextureCoord); mediump float distance = color.a;mediump float smoothWidth = fwidth(distance);mediump float alpha = smoothstep(SmoothCenter - smoothWidth, SmoothCenter + smoothWidth, distance); gl_FragColor = vec4(GlyphColor, alpha); }

Using shaders with distance fields can also
achieve a variety of special effects, as shown in Figure 7-8. In the interest of brevity, I won’t go
into too much detail here; much like the smoothing example from the
previous section, all these effects rely on using
`smoothstep`

and various offsets from the
*distance=0* boundary. They also make use of a GLSL
function called `mix`

; here’s its
declaration:

float mix(float x, float y, float a)

You probably already guessed that this function performs linear interpolation between its first two arguments:

mix(x, y, a) = x * (1 - a) + y * a

See Example 7-12 for an “übershader” that can
produce any of the aforementioned distance field effects, depending on
how the application sets up the uniforms. If you’re trying to run this
shader on the simulator, you’ll need to remove the top line and replace
the `fwidth`

function with a constant.

As always, you can obtain the complete
source for an app that demonstrates this technique from this
book’s website. The sample in this case is simply called
“DistanceField,” and it uses `#ifdef`

to
automatically avoid derivatives when running in the simulator.

Example 7-12. Distance field übershader

#extension GL_OES_standard_derivatives : enable varying mediump vec2 TextureCoord; uniform sampler2D DistanceField; uniform mediump vec3 OutlineColor; uniform mediump vec3 GlyphColor; uniform mediump vec3 GlowColor; uniform bool Outline; uniform bool Glow; uniform bool Shadow; const mediump vec2 ShadowOffset = vec2(0.005, 0.01); const mediump vec3 ShadowColor = vec3(0.0, 0.0, 0.125); const mediump float SmoothCenter = 0.5; const mediump float OutlineCenter = 0.4; const mediump float GlowBoundary = 1.0; void main(void) { mediump vec4 color = texture2D(DistanceField, TextureCoord); mediump float distance = color.a; mediump float smoothWidth = fwidth(distance); mediump float alpha; mediump vec3 rgb; if (Outline) { mediump float mu = smoothstep(OutlineCenter - smoothWidth, OutlineCenter + smoothWidth, distance); alpha = smoothstep(SmoothCenter - smoothWidth, SmoothCenter + smoothWidth, distance) rgb = mix(GlyphColor, OutlineColor, mu); } if (Glow) { mediump float mu = smoothstep(SmoothCenter - smoothWidth, SmoothCenter + smoothWidth, distance); rgb = mix(GlyphColor, GlowColor, mu); alpha = smoothstep(SmoothCenter, GlowBoundary, sqrt(distance)); } if (Shadow) { mediump float distance2 = texture2D(DistanceField, TextureCoord + ShadowOffset).a; mediump float s = smoothstep(SmoothCenter - smoothWidth, SmoothCenter + smoothWidth, distance2); mediump float v = smoothstep(SmoothCenter - smoothWidth, SmoothCenter + smoothWidth, distance); // If s is 0, then we're inside the shadow; // if it's 1, then we're outside the shadow. // // If v is 0, then we're inside the vector; // if it's 1, then we're outside the vector. // Totally inside the vector (i.e., inside the glyph): if (v == 0.0) { rgb = GlyphColor; alpha = 0.0; } // On a nonshadowed vector edge: else if (s == 1.0 && v != 1.0) { rgb = GlyphColor; alpha = v; } // Totally inside the shadow: else if (s == 0.0 && v == 1.0) { rgb = ShadowColor; alpha = 0.0; } // On a shadowed vector edge: else if (s == 0.0) { rgb = mix(GlyphColor, ShadowColor, v); alpha = 0.0; } // On the shadow's outside edge: else { rgb = mix(GlyphColor, ShadowColor, v); alpha = s; } } gl_FragColor = vec4(rgb, alpha); }

The

`Outline`

,`Glow`

, and`Shadow`

booleans are set from the application to choose which effect to apply. (An alternative strategy would be splitting this into three separate shaders.)This is the offset of the shadow from the glyph. In this case, the aspect ratio of the texture is 2:1, so the X offset is half the size the Y offset. Note that you may need to negate the X or Y value, depending on how your distance field is oriented.

`SmoothCenter`

is the alpha value that represents the*distance = 0*boundary.`OutlineCenter`

tells the shader how far from the glyph edge to render the outline. For an outline that is just inside the glyph, this value should be less than 0.5.`GlowBoundary`

tells the shader how far out to extend the glow. To create a pulsing glow, change this into a uniform, and cycle its value from within the application code.

The shadow effect in Example 7-12 deserves further explanation. It applies anti-aliasing to the transition not only between the vector and the background but also between the shadow and the background and between the vector and the shadow. The shader pulls this off by deciding which of the following five regions the pixel falls into (see Figure 7-11):

Start Free Trial

No credit card required