# Introduction

Popularized by Valve, signed distance fields provide an efficient way to display text in games at an arbitrary resolution. In this four part series, I'll show how you can generate a texture atlas of signed distance fields from TrueType fonts as shown above.

The technique in the original Valve paper is to take a high resolution input bitmap, create a corresponding high resolution signed distance field, then downscale that to the desired final resolution. I'll show an alternative approach that uses only the desired resolution and produces exact distances in a reasonable amount of time. The trade off is the need to use a lot of math, including some calculus.

While this series is tailored towards TrueType fonts, the algorithm can be used to generate signed distance fields from a vector defined shape given it's closed and made up of straight lines or quadratic Bézier curves. Rust will be my language of choice throughout the code examples and I won't be explaining what a signed distance field actually is and the related spread factor, that is not the focus of this series.

Here's the breakdown: in part one, we'll look at the algorithm and setup the code for parts two and three which will call into a function for calculating the distance and a function for calculating the sign of that distance. The distance calculation is covered in part two and the calculation for sign of the distance is covered in part three. Part four will cover generating the texture atlas from the set of distance fields.

# The algorithm

Let's start with the following pseudo code for generating our set of signed distance fields.

```
for each glyph g {
for each pixel center p in g's signed distance field {
let min_dist = +infinity
let total_cross_num = 0
for each curve c in g {
let dist = shortest distance from p to c
let cross_num = crossing number of c with respect to p
if dist < min_dist {
min_dist = dist
}
total_cross_num += cross_num
}
let signed_dist = if total_cross_num % 2 == 0 {
-min_dist
} else {
min_dist
}
}
}
```

Calculating the distance and crossing number is done in constant time so looking at this psuedo code can give an idea of the algorithm's run time complexity. You can also see two things required to calculate the signed distance of a pixel, the unsigned distance and the crossing number. The unsigned distance is covered in part two and the crossing number is covered in part three. It's worth noting this algorithm lends well to parallel computing as calculating the signed distance of a pixel is independent of other pixels and glyphs.

Let's take a look at the algorithm in more detail.

```
// Initialize freetype
let library = freetype::Library::init().unwrap();
let face = library.new_face(font_file_path, 0).unwrap();
face.set_pixel_sizes(0, size).unwrap();
let fields = Vec::empty();
// Iterate over characters
for char_code in 33..127 {
face.load_char(char_code, LoadFlag::empty()).unwrap();
let metrics = face.glyph().metrics();
let width = metrics.width as usize / 64 + spread * 2;
let height = metrics.height as usize / 64 + spread * 2;
let left_edge_padded = metrics.horiBearingX as f64 / 64.0 - spread_f64;
let top_edge_padded = metrics.horiBearingY as f64 / 64.0 + spread_f64;
let outline = face.glyph().outline().unwrap();
let mut field = Vec::with_capacity(height);
// Iterate over texels in our distance field
for row in 0..height {
let mut field_row = Vec::with_capacity(width);
for col in 0..width {
let mut min_dist = f64::MAX;
let mut total_cross_num = 0;
let p = Vector {
x: left_edge_padded + col as f64 + 0.5,
y: top_edge_padded - row as f64 - 0.5
};
// Find the minimum distance from p to each curve
for contour in outline.contours_iter() {
let mut start = *contour.start();
for curve in contour {
let s = Vector {
x: start.x as f64 / 64.0,
y: start.y as f64 / 64.0
};
let (end, dist, cross_num) = match curve {
Curve::Line(end) => {
let e = Vector {
x: end.x as f64 / 64.0,
y: end.y as f64 / 64.0
};
let dist = find_dist_to_line(&p, &s, &e);
let cross_num = find_cross_num_of_line(&p, &s, &e);
(end, dist, cross_num)
},
Curve::Bezier2(control, end) => {
let c = Vector {
x: control.x as f64 / 64.0,
y: control.y as f64 / 64.0
};
let e = Vector {
x: end.x as f64 / 64.0,
y: end.y as f64 / 64.0
};
let dist = find_dist_to_bezier(&p, &s, &c, &e);
let cross_num = find_cross_num_of_bezier(&p, &s, &c, &e);
(end, dist, cross_num)
},
Curve::Bezier3(_, _, _) => {
panic!("cubic beziers not supported");
}
};
if dist < min_dist {
min_dist = dist;
}
total_cross_num += cross_num;
start = end;
}
}
// Clamp the signed distance to the spread and normalize it to a u8
let dist_signed = if total_cross_num % 2 == 0 { -min_dist } else { min_dist };
let dist_clamped = dist_signed.min(spread_f64).max(-spread_f64);
let dist_positive = dist_clamped + spread_f64;
let dist_scaled = (dist_positive * 255.0 / (spread_f64 * 2.0)).round() as u8;
field_row.push(dist_scaled);
}
field.push(field_row);
}
fields.push(field);
}
let atlas = generate_atlas(&fields);
```

First, we initialize FreeType, load in our TrueType font file and set the desired font size. Then, we iterate over the characters we'll generate signed distance fields for. I'm using the range of 33 to 127 (33 is inclusive but 127 is exclusive) which is all the printable ASCII characters. When this outer loop is done, we'll have a set of signed distance fields, one for each character. Then, we generate a texture atlas from the set of signed distance fields.

Inside the loop, we load the character and gather the required metrics. Note the metrics are defined in a 26.6 fixed float format, so we must divide by 64 to get the metrics in fractional units of pixels. FreeType will perform hinting when loading the glyph. One benefit of this is that the width and height will be multiples of 64 so we can cast them to an integer type and divide by 64 without losing accuracy. We want these to be whole integer values so they can define the glyph's signed distance field size in pixels. Also, note the adjustment needed to account for the spread of the signed distance field.

Next, we can iterate over all the pixels in the field to calculate a signed distance for each one. Given a pixel, it's distance can be found by calculating the shortest distance from the center of the pixel to each curve of the glyph. Once we have the shortest distance to each curve, the minimum out of those distances is the final distance. In more detail, we calculate the center of the pixel `p`

then iterate over all the contours of the glyph. A contour in this context just makes up a closed shape. Consider the character "o", it has two contours, one for the inner loop and one for the outer loop. Within a contour, we iterate over the curves that make it up, which can either be a straight line or a quadratic Bézier. Note, for a line we only have it's end point and for the Bézier we have it's control and end point. Because the contour is closed, the end of one curve is always the start of the next. To get the start of the first curve, we use `.start()`

of the contour. At this point, for each pixel center `p`

, we're able to iterate over each curve in the glyph and know the curve's start, end and if a Bézier, control point. From here we calculate two things, the shortest distance from `p`

to the curve and the crossing number. These two things give us the signed distance of `p`

.

After calculating the signed distance, we clamp it to the spread making its floating point range [-spread, spread]. The next calculations modify the distance so its range is integer values of [0, 255], the size of a byte.

# Creating a bitmap image

Before moving on, I want to share some bonus code. The below will take a path to an output bitmap image and a `Vec<Vec<u8>>>`

which is the type of a single signed distance field and the final texture atlas. I wouldn't recommend using this as the texture atlas your game will read from, instead you should probably save the atlas in a proprietary format along with all the required metrics to render the text (glyph position in the atlas, bearing, advance, etc.). I also won't explain how the code works as the focus of this series is not about how to create bitmap images. It's simply to aid you in visualizing the distance fields or the final texture atlas.

```
fn save_to_bitmap(file_path: &str, atlas: &Vec<Vec<u8>>) {
let image_width = atlas[0].len();
let image_height = atlas.len();
let image_row_padding_len = (4 - image_width % 4) % 4;
let mut buffer: Vec<u8> = Vec::with_capacity(1078 + (image_width + image_row_padding_len) * image_height);
// Header
buffer.push(66u8);
buffer.push(77u8);
let file_size = 0u32.to_le_bytes();
buffer.extend_from_slice(&file_size);
let reserved = 0u16.to_le_bytes();
buffer.extend_from_slice(&reserved);
buffer.extend_from_slice(&reserved);
let pixel_data_offset = 0u32.to_le_bytes();
buffer.extend_from_slice(&pixel_data_offset);
// Info header
let header_size = 40u32.to_le_bytes();
buffer.extend_from_slice(&header_size);
let image_width_i32 = (image_width as i32).to_le_bytes();
buffer.extend_from_slice(&image_width_i32);
let image_height_i32 = (image_height as i32).to_le_bytes();
buffer.extend_from_slice(&image_height_i32);
let planes = 1u16.to_le_bytes();
buffer.extend_from_slice(&planes);
let bpp = 8u16.to_le_bytes();
buffer.extend_from_slice(&bpp);
let compression_type = 0u32.to_le_bytes();
buffer.extend_from_slice(&compression_type);
let compressed_image_size = 0u32.to_le_bytes();
buffer.extend_from_slice(&compressed_image_size);
let x_pixels_per_meter = 0i32.to_le_bytes();
buffer.extend_from_slice(&x_pixels_per_meter);
let y_pixels_per_meter = 0i32.to_le_bytes();
buffer.extend_from_slice(&y_pixels_per_meter);
let total_colors = 0u32.to_le_bytes();
buffer.extend_from_slice(&total_colors);
let important_colors = 0u32.to_le_bytes();
buffer.extend_from_slice(&important_colors);
// Color table
for i in 0..256 {
let i_u8 = i as u8;
buffer.push(i_u8);
buffer.push(i_u8);
buffer.push(i_u8);
buffer.push(0u8);
}
// Pixel data offset in header
let pixel_data_offset = (buffer.len() as u32).to_le_bytes();
for i in 0..4 { buffer[10 + i] = pixel_data_offset[i] };
// Pixel data
let padding = vec![0u8; image_row_padding_len];
for row in atlas.iter().rev() {
for texel in row {
buffer.push(*texel);
}
buffer.extend_from_slice(&padding);
}
// File size in header
let file_size = (buffer.len() as u32).to_le_bytes();
for i in 0..4 { buffer[2 + i] = file_size[i] };
let mut file = File::create(file_path).unwrap();
file.write_all(&buffer).unwrap();
}
```

# References

- Green, Chris. "Improved Alpha-Tested Magnification for Vector Textures and Special Effects."
*SIGGRAPH*'07, pp. 1-5.

## Discussion (0)