High-Quality Font Rendering for Embedded Systems

Setting up high-quality font rendering in a memory-constrained embedded system sounds like it would be hard. However, like many other problems in embedded systems, this one has pretty much already been solved by game developers. It turns out that getting proper font rendering, with kerning and all, can easily be done in a day’s work.

The game development communities are actually a great place to look for a lot of algorithms. Anything with graphics (even simple things like fonts), geometry/spatial algorithms (collision detection/prediction), or physical simulations have all gotten a lot of attention from the game developers. And their solutions are often mindful of memory and realtime constrains, which are of particular interest in embedded systems.

My particular use case is rendering text to a tiny black and white display (smaller than 150×50) in a resource-constrained environment (32k of RAM total) written in C.

1. Generate Bitmap Font

A google search for “bitmap font generator” turns up quite a few things. I tried out these:

• FontBuilde
• UBFG

Both worked pretty well for my purposes, since they were relatively simple, open source, and supported proper kerning.

To use them, feed in a TrueType font and a set of characters from that font you want to use. The generator outputs a png containing graphics of all the characters and a datafile (usually in xml) that specifies the bounding box of each character in the image and placement/kerning information for the characters.

2. Convert the Image Format

A .png image is too heavy duty for my use case. I need a format that’s more easily used on my platform. ImageMagick is a convenient tool to convert from .png to a simpler binary form.

Older X11 image formats (such as: .xdm, .pdm, .xpm) are particularly convenient for systems written in C, especially .xdm and .xpm) as you can just #include them. For other binary formats, I can use xxd -i to convert to a C “header file” format that I can just #include into my project and then parse manually.

3. Convert Placement/Kerning Data

For the extra placement/kerning data, you can either parse the .xml output or, since they are open source, just add a custom exporter to FontBuilder/UBFG. The .xml output looks something like this:

Which I converted to C switch statements that look something like this:

struct rect
{
  int16_t const x;
  int16_t const y;
  int16_t const w;
  int16_t const h;
};

struct char_info
{
  int8_t offset_x;
  int8_t offset_y;
  uint8_t advance;

  struct rect rect;
};

static struct char_info lookup_char(uint16_t const c)
{
  switch(c)
  {
...
    case 65:    /* A */
      return (struct char_info)
        { .offset_x = 0,
          .offset_y = 18,
          .advance  = 15,
          .rect = (struct rect){
            .x   = 22,
            .y   = 47,
            .w   = 15,
            .h   = 18,
          },
        };
    case 66:    /* B */
      return (struct char_info)
        { .offset_x = 2,
          .offset_y = 18,
          .advance  = 16,
          .rect = (struct rect){
            .x   = 38,
            .y   = 47,
            .w   = 12,
            .h   = 18,
          },
        };
...
}

I then did something similar for kerning pairs:

int8_t lookup_kerning_offset(uint16_t c1, uint16_t c2)
{
  switch(c1)
  {
  ...
    case 65:  /*  A  */
      switch(c2)
      {
        case 84:  /*  T  */
        case 89:  /*  Y  */
        case 86:  /*  V  */
          return -2;
        case 32:  /*     */
        case 87:  /*  W  */
          return -1;
        default:
          return 0;
      }
    case 66:  /*  B  */
      switch(c2)
      {
        default:
          return 0;
      }
  ...
  }
}

The nice thing about using a switch statement here is that the compiler is generally quite good about converting it to a mishmash of lookup tables and binary search and producing a well optimized result.

4. Draw the Text!

The code to render a string looks something like this:

uint16_t draw_character(struct bit_image frame_buffer,
                        struct bit_image font_image,
                        uint16_t const c,
                        uint16_t const next_char,
                        uint16_t const x,
                        uint16_t const y)
{
  struct char_info const i = lookup_char(c);
  int16_t const kerning_offset = kerning_offset(c, next_char);
  copy_bit_rect(frame_buffer, font_image, x + i.offset_x, y - i.offset_y, i.rect);
  return x + i.advance + kerning_offset; 
}

void draw_string(struct bit_image frame_buffer,
                 struct bit_image const font,
                 char const * const str,
                 uint16_t const str_len,
                 uint16_t const x,
                 uint16_t const y)
{
  uint16_t x_pos = x;
  if (str_len > 0)
  {
    for(uint16_t i = 0; i < str_len - 1; i++)
    {
      x_pos = draw_character(frame_buffer,
                             font_image,
                             str[i],
                             s.str[i + 1],
                             x_pos,
                             y);
    }
    x_pos = draw_character(frame_buffer,
                           font_image,
                           str[str_len - 1],
                           0,
                           x_pos,
                           y);

  }
}

Then we can do:

draw_string(frame_buffer, font_image, "fonts thing!", 12, 25);

End result:

Not too bad for a tiny monochrome display :)