iPhone 3D Programming : Crisper Text with Distance Fields (part 1) - Generating Distance Fields with Python

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 1. The fuzziness can be alleviated by replacing blending with 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 2 shows a distance field for the mystical Aum symbol. Figure 3 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).

1. Generating Distance Fields with Python

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 1.

Example 1. 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)


					  

2. Use Distance Fields Under ES 1.1 with Alpha Testing

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.

3. Adding Text Effects with Fragment Shaders

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 2.