Rendering text

There was a time where rendering text with a computer was the top of the available technology. I’m not even speaking about text on screen, but text on paper.
What we take for granted today with high res screens, crisp fonts and invisible contour was pure science fiction some decades ago.
And it’s even more fun to think that text rendering is still a domain of research nowadays. Because of more pixels, more mobility, more CPU/GPU power, rendering text evolves everyday.
Let me tell you a bit of history and explain a few algorithms that are used today for rendering glyphs.

Before the screen

French micro computer Micral.

With memory becoming cheaper and more efficient, things improved quickly.

The terminal

Type things and it prints the result. That’s just a terminal. Computer takes one whole room.

Characters could then be stored in the memory as small matrices of bits (let say 8x8). With ink on the paper for 1 and no ink for 0. A character in memory would only be 8 bytes. 1Kb for whole ASCII chart. This would be the standard for 20 or 30 years.

Then came the light

HP terminal

At home, early computers from the 80s could display 40 x 25 characters on screen with a 8x8 resolution. Making glorious 320x200 pixels displays. It stayed like that for some years during the 80s, from Commodore C64 to MS-DOS on your brand new Intel 386 PC.

Infamous C64 boot up screen

Some more characters appears to feel the remaining space in the ASCII chart (ASCII is 127 characters, more diverse glyphs appeared for localized text to get up to 255 characters). Computers were essentially made in the west. ASCII stands for America Standard Code for Information Interchange.

Vectors

This thing is from 1973. 10 years before Apple Macintosh.

Needless to say, rendering 10s of Kilobytes of curves on a 8Mhz computer was difficult. Years passed and today, we can render 1000s of characters on 144Hz screens.

Games

Nes game sprites dump. See the characters top right. https://forum.nim-lang.org/t/4445

With higher resolution, efficient GPUs, things improved with the XBox and PlayStation generation. Glyphs were pre-rendered in textures. With footprint depending on character size and precomputed antialiasing. Text was a succession of textured quads with the texture corresponding to the texture portion needed.

There are many bitmap font generator. Like this one for Mac.

In 2007, Chris Green from Valve released a paper titled “Improved Alpha-Tested Magnification for Vector Textures and Special Effects “ https://steamcdn-a.akamaihd.net/apps/valve/2007/SIGGRAPH2007_AlphaTestedMagnification.pdf
Instead of storing the glyph as is, in the texture, a signed distance field (each pixel is the smallest distance to a glyph curve) is computed offline and a bit more of a complex shader is applied when rendering. Thanks to the GPU hardware, it allows way more smoothed curve approximation, at higher resolution. It also opens the door for effects like different colors for the border, anti aliasing, … and for a smaller memory footprint.

Glyph packed into a distance field texture. The darker the pixel, the further from the glyph border.

It had a huge impact on the game industry. Trading a bit of GPU power for quality would be the trend for the coming years.

GPU rendering

Triangulated mesh

Curve outlines (a) are triangulated with green filled and curve filled (b) end result (c )

Inner shapes are rendered as a triangulated mesh. The mesh is computed offline. Triangles with curves are also rendered with a triangle but a pixel shader computes the curve. I won’t dive in details about quadratic curves but it’s basically a bilinear interpolation. By moving the control points in a texture and doing bilinear texture sampling, it’s possible to compute that curve.
IMHO, computing the triangulated mesh is the most difficult part. Moreover, because GPU computes 2x2 blocks and discards pixel that are not part of a triangle, edges are computed more than once in the shader. With small glyphs on screen, the overhead can be important. I think this technique shines when rendering SVG or for big on screen text.

https://playground.babylonjs.com/#4905IE#6 Red curve is computed thanks to GPU bilinear interpolation.

A nice paper on bilinear quadratic curve computation: https://blog.demofox.org/2016/02/22/gpu-texture-sampler-bezier-curve-evaluation/

Curve intersection

Each glyph is rendered using a few triangles. A generic solution is to use 2 triangles per glyph (to make a quad). A more efficient version is to balance between 1 and a few triangles to have a hull that is closer to the glyph shape. Too many triangles can be counter efficient (see previous 2x2 block computation).
Then, for each pixel, the algorithm determines if it’s inside or outside the shape made from curves. To do so, it computes the number of crossed curves in a particular direction.
The paper details algorithm to speed up that computation. I’ll show you a naïve version where for each pixel, the sign to the curve is used to check if inside or outside. The important info here is limited triangle mesh and computation per pixel. As it is per pixel and vector info, it looks good for any size.

https://playground.babylonjs.com/#TDIWFC#1 Glyph curves are stored in a texture. At runtime, each curve is tested to see if the texel in inside or outside the curve. 2 Triangles forming a quad is used here.

This has been a long way from the first displays to the technics with pixel shaders. I think the quest for newer font rendering systems will never end. Hardware continues to improve year after year. Maybe in the coming months, someone will come up with a faster, better, nicer algorithm running in a compute shader. We are standing on shoulders of giants.

Images courtesy of Wikipedia.org

Cedric Guillemet (@skaven_) / Twitter

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store