How are glyphs filled during render?

Question

I was wondering how programs, e.g. browsers, fill glyphs during rendering and found the flood fill algorithm, but I guess that's rather inefficient for something so basic as glyphs.

So, how is it done?

Answer 1

Truetype rasterizers will scale the outline onto a grid of appropriate size (based on text size and DPI). If the font is hinted, it will then run the hinting instructions to get a "grid-fitted" outline on the grid.

The next step is "scan conversion". For each horizontal row on the grid, it will look at where the outline crosses the row to determine on and off transitions. When doing this, it will check where the outline lies in relation to pixel centers: if the pixel center is within the outline, the pixel is on; and if the outline passes through the pixel center, the pixel is on.

In a bit more detail, a way that scan conversion can be done is to select a starting point on a contour and then walk pixels adjacent to the outline across and up then down. For example, start with the first pixel whose center is on or to the right of the starting contour point: that pixel is flagged for an "on" transition. Then go up a pixel: if the contour wasn't crossed, then go left until the contour is crossed, and flag the pixel on or to the right of the contour as an "on" transition. Or, when going up a pixel if the contour was crossed, then go right until the contour is crossed. Etc. Keep going up to the row that's above the max y point in the contour, and then go back down looking for "off" transitions. When done, you've got pairs of on/off pixels in each row; all the pixels in between get turned on.

There are lots more details, but that gives the general idea.