Metafont-inspired font design using nonlinear constraint optimization and Webassembly

Modern fonts work by drawing the outline of each letter out by hand. This is a very labour-intensive operation as each letter has to be redrawn for each weight. Back in the late 70s Donald Knuth created METAFONT, which has a completely different approach that mimics the way letters are drawn by hand. In this system you specify a pen shape and a stroke path. The computer would then calculate what sort of a mark this stroke would leave on paper and draw the result. The pen shape as well as the stroke were defined as mathematical equations of type "the stroke shall begin so that its topmost part is exactly at x-height and shall end so that its bottom is at the baseline".

The advantage of this approach is that it is fully parametrizable. If you change the global x-height, then every letter is automatically recalculated. Outline fonts can't be slanted by shearing because it changes the strokes' widths. Parametric fonts do not have this issue. Different optical weights can be obtained simply by changing the size of the pen nib. You could even go as far as change the widths of individual letters during typesetting to make text justification appear even smoother.

METAFONT was never widely used for font design. The idea behind it was elegant, though, and is worth further examination, for example are there other ways of defining fonts parametrically and what sort of letter shapes would they produce. Below we describe one such attempt.

How would that look in practice?

In a nutshell you write a definition that mathematically specifies the shape:

Then the system will automatically create the "best possible" shape that fulfills those requirements:

Note that this output comes from the Python Scipy prototype version, not the Webassembly one. It calculates a slightly different shape for the letter and does not do the outline yet.

How does it work?

First the program parses the input file, which currently can specify only one stroke. Said stroke consists of one or more cubic splines one after the other. That is, the end point of spline n is the starting point of spline n+1. It then converts the constraints into mathematical form. For example if you have a constraint that a point must be on a diagonal line between (0, 0) and (1, 1), then its coordinates must be (t, t) where t is a free parameter with values in the range [0, 1]. The free parameters can be assigned any values and the resulting curve will still fulfill all the requirements.

The followup question is how do we select the free parameters to pick the most pleasing of all curves to quote Knuth's terminology. If you thought "deep learning" then you thought wrong. This is actually a well known problem called nonlinear optimization. There are many possible approaches but we have chosen to use the (draws a deep breath) Broyden–Fletcher–Goldfarb–Shanno algorithm. This is the default optimization method in Scipy. There is also a C port of the original Fortran implementation.

The last thing we need is a target function to minimize. There are again many choices (curve length, energy, etc). After some experimentation we chose the maximum absolute value of the second derivative's perpendicular component over the entire curve. It gave the smoothest end result. Having defined a target function, free variables and a solver method we can let the computer do what it does best: crunch numbers. The end result is written as SVG using TinyXML2.

There are known problems with the current evaluation algorithm. Sometimes it produces weird and non-smooth results. LBFGS seems to be sensitive to the initial estimate and there are interesting numerical problems when evaluating the target function when switching between two consecutive curves.

Try it yourself

The Webassembly version is available here. You can edit the definition text and then recompute the letter shape with the action button. Things to try include changing the width and height (variables w and h, respectively) or changing the location constraints for curve points.

The code can also be compiled and run as a native program. It is available in this Github repository.

Future work and things that need fixing

• Firefox renders the resulting SVG files incorrectly
• All mathy bits are hardcoded, optimization functions et al should be definable in the character file instead
• Designing strokes by hand is not nice, some sort of a UI would be useful
• The text format for specifying strokes needs to be designed
• Should be able to directly specify some path as a straight line segment rather than a bezier
• You should be able to specify more than one stroke in a character
• Actual font file generation, possibly via FontForge
• "Anti-drawing" or erasing existing strokes with a second stroke