[metapost] Trying to use MT1 to make outline fonts... (again)

[mskala at ansuz.sooke.bc.ca]

On Fri, 31 Aug 2012, Shriramana Sharma wrote:
> On Tue, Jun 19, 2012 at 6:17 PM,  <mskala at ansuz.sooke.bc.ca> wrote:
> > I use all three - circular, non-circular elliptical, with rotation, and
> > without rotation.  The "simplified" stroking algorithm generally works
> > pretty well in practice.  When I have trouble with it, I can often work
> > around the issues by adding extra points along my path using the MT1
> > insert_nodes() macro.  The lack of a true pen stroke calculation is
> > noticed, but is not prohibitive.
>
> Regarding this thread of some time back:
>
> I wonder if the above means that the problem Piska described in his
> article http://www-hep2.fzu.cz/~piska/TUG2004/piskatb2.pdf p 6 fig 13
> is solvable? I'd appreciate it if Matthew (or anyone else) can
> clarify.

Okay, let's start with some background.  Paths in METAFONT are always
cubic splines - that is, curves made up of chunks of cubic curves laid end
to end.  What we want to do is take a closed spline called the pen
(usually a special case such as a circle - although, technically, it won't
be an exact circle because exact circles can't be achieved in this model)
and sweep it along another spline called the stroke, and compute one or
more splines that describe the boundary of the set of all points ever
enclosed by the pen in its travels.

The first problem is that the boundary we want to calculate is not a
spline in general.  It cannot be exactly described as a piecewise cubic
curve.  That would be true even if we were dealing with a very simple case
like sweeping a circle along an ellipse:  if the stroke ellipse is long
and thin, then we end up with a funny pointy thing on the inside and on
the outside something that looks sort of like an ellipse but is actually
like a sixth-order curve or something.  It cannot be expressed exactly by
a finite number of cubic segments.  Therefore if we want to call the
result of this stroke operation a spline then we *must* accept some amount
of approximation.  The question is how much approximation we will accept
and how much work we will do to achieve it.

MetaType1's approach is to place the pen at each node of the stroke, and
then try to connect them.  You basically get one node in the result for
each node in the original stroke.  The resulting splines match the
hypothetical "correct" splines (except remember, no correct splines really
exist because they would not be splines...) at the nodes; in between, they
may not match.  Figure 12 of the Píška paper shows a relatively minor
example.  Because the left and right sides of the result are linked to
each other only at the endpoints, their deviations from the hypothetical
ideal may be in opposite directions at any given point and so the width of
the stroke varies in a way that wouldn't happen with a true circular pen
placed continuously at every point along the stroke.

In Figure 13, it's obvious in the upper letter (sorry, I don't know if
that's the "i" or the "a" - I'm not familiar with Devanagari) what's going
wrong.  There's a stroke that curves back on itself forming a shape
something like the Latin letter "s," and that part of it evidently had
only four nodes in the stroke path.  It goes upper right to upper left to
lower right to lower left, and between upper left and lower right, the
stroke makes two 90-degree turns in opposite directions, with the result
that this kind of deviation changes the width so much as to make the width
negative.  The left and right sides of the envelope intersect twice,
temporarily changing places, before reaching the lower-right node.  Note
that including both a left and a right turn in the same segment of the
input path creates an inflection point, and this case is specifically
forbidden in the MetaType1 documentation, which reads:

% The following macros approximate the envelope of an elliptical or a razor
% pen. The exact solution is impossible---in general, the envelope is not
% a B\'ezier curve, therefore some heuristics is, in general, unavoidable.
% We assumed that the backbone of a figure is such that
% the envelope does not form loops at smoothly joined nodes. Moreover,
% all B\'ezier segments appearing in the process {\bf should not}
% contain inflection points (the reason for this limitation is the
% method of finding an approximation of a pen envelope). If the latter
% condition is not fulfilled, one may expect weird results (see the usage
% of the |...| operator in the code of |pen_stroke_edge|).

I think that one should be called user error, not a problem in the
algorithm.  It's garbage in, garbage out:  this macro requires input
without inflection points, the requirement is documented, and Píška
nonetheless gave it input WITH inflection points.  No wonder it doesn't
work!  Removing inflection points isn't even difficult.  MetaType1
provides a macro called insert_nodes, which splits segments into smaller
pieces without changing the curve.  Calling that with the t-value of the
inflection point would split the bad segment into two smaller ones (one
turning right, one turning left) and the result would be much more
visually appealing.

By the way, I think FontForge also forbids inflection points in curves to
be stroked, and Postscript and OpenType software in general prefers that
they be avoided in outlines.

Less extreme cases, like the one in Figure 12, can also be attacked by a
similar technique:  the width is guaranteed to be correct at the location
of each node, so if we insert a new node anywhere the deviation from the
ideal envelope is too great, we can reduce the deviation to zero at that
point and generally bring the curve closer to ideal.

The simplest way to do it is by human intervention.  That's how I do it in
Tsukurimashou.  When the font designer knows or guesses that another node
will be required, they can add one.  For the specific case of inflection
points, it should be possible to write code to detect inflection points
and add nodes exactly at them.  I have not done that but I imagine I
could.  The case of "too much" deviation from ideal envelopes, other than
at inflection points, is harder to imagine doing automatically, both
because it requires computing the ideal envelopes in the first place (a
chicken-and-egg problem) and because it involves a subjective call on what
is "too much" deviation.  It is possible to imagine some kind of iterative
process of adding a point, seeing if it makes a difference, and keeping
only the ones that are needed, but this would be a lot of work (both to
code and for the computer at run time).  I think human intervention may
really be the best way to go.  But remember that because the hypothetical
ideal result is not a piecewise cubic curve, it is not reasonable to
expect to achieve it exactly.  We are necessarily computing a piecewise
cubic *approximation* of the hypothetical ideal result, and then talking
about how close that approximation ought to be.

I don't know what is wrong with the lower letter in Figure 13.  It looks
okay to me, but I don't read Devanagari and there may well be something
seriously wrong that I don't notice.  There are certainly some places in
the stroke where the envelope is much narrower than at other points; I'm
not sure how much of that is just the intended effect of the very narrow
elliptical pen being used and how much is considered an "error," but it's
also clear to me that there are very few nodes on those paths.  I think it
might be preferable to add some more nodes to the paths before concluding
that MetaType1 can't stroke paths correctly.

One problem I consider more serious is that when a stroke curves through a
tight, small-radius bend (that is, smaller than the size of the pen), part
of the envelope may *correctly* curve around and intersect itself.  This
corresponds to a point where the hypothetical ideal envelope would contain
a sharp corner, even though there are no sharp corners in the input.
Often the MetaType1 macros will fail to create the loop (making the path
turn -90 degrees instead of +270 degrees, for instance), so the curve
becomes much thinner at that point instead of creating the sharp corner.
Something similar is visible in the lower left of the upper letter in
Píška's Figure 13.

The MetaType1 documentation also mentions this case vaguely in the line
about "the envelope does not form loops at smoothly joined nodes."  It's
harder to address these by inserting nodes.  What I've been doing is
inserting nodes to force creation of a loop, and then trusting FontForge's
overlap removal to cut it out.  But I haven't solved this in all relevant
cases yet, and some errors of this nature are visible in the current
Tsukurimashou fonts, for instance in the character 態 (U+614B) where it
happens three times.  I think it can be fixed by manual insertion of
nodes, but it's fiddly because it's related to parameterization - all
three cases in 態 are associated with a lower-level macro that looked good
in the character for which I first designed it, at a different size, but
then became a problem when the same letter-component was scaled down for
use in other characters.

So all in all, my point of view on MetaType1-style path stroking is:

* No path stroking that takes cubic splines as both input and output can
  ever produce perfect results, not even when the pens are restricted to
  circles.
* It is not possible to take a pen-and-stroke combination written for
  bitmap METAFONT, feed it directly into MetaType1 with no human
  intervention, and expect the result to look the same.  If you want
  vectorized versions of fonts written for METAFONT without human
  intervention, you must use some other approach.
* MetaType1's approach can produce better results than Píška claims.  He
  isn't using it properly.
* With nontrivial amounts of human intervention, MetaType1's approach can
  produce perfectly acceptable results.
* However, it would be nice to have a way of doing it with less human
  intervention.

> I would also like to know what exactly Tsukurimashou uses FontForge
> for (as this is not evident to me from the sources) -- removing
> overlaps was mentioned before, but how about assembling the glyphs
> into a Unicode font?

Yes.  FontForge's role in Tsukurimashou basically consists of:

* Removing overlaps.
* Curve simplification - for instance, removing extra nodes along curves
  if doing so doesn't change the curve too much.  This is especially
  significant because of the presence of extra inserted nodes like the
  ones mentioned above, but I also have a lot of visually-unnecessary
  nodes created for instance by the piecewise way that Genjimon characters
  are constructed.
* Other kinds of "tidying" operations needed to respect file format
  standards, such as integer coordinates and the Postscript requirement
  for a node at every horizontal and vertical extremum.  These might be
  possible in MetaType1 but are easier in FontForge.
* Combining sub-fonts (slices of up to 256 glyphs each, limited by
  Postscript format) to form complete fonts (OpenType, up to 64K glyphs).
  Note that even if Postscript were eliminated from the chain, working on
  large fonts in smaller pieces to be combined later is desirable because
  they can be separately compiled, saving time both by reducing the total
  amount of work and because different slices can be compiled
  simultaneously on a multi-CPU computer.
* Overlaying "interior" glyphs on "background" glyphs to construct some
  special white-on-black glyphs like ❶ (U+2776 DINGBAT NEGATIVE CIRCLED
  DIGIT ONE).  This could probably be achieved in MetaType1, but it seemed
  easier to do it in FontForge rather than trying to figure out how to
  make such glyphs survive the "remove overlaps" step, which would
  require very careful attention to the clockwise/counterclockwise
  directions of the paths.
* Attaching OpenType "feature" information, kerning and other horizontal
  metrics information, Unicode encoding information, and other metadata
  to the fonts.  Some of this information could be handled by MetaType1,
  but not easily, because it would all have to be expressed in TeX's
  idiom and then translated, and some of it (in particular, the contextual
  substitutions) doesn't really exist in the TeX world.

> IMHO converting PS -> PT1 -> OTF using perl/awk as text-processing
> intermediaries is unnecessary if FF is involved. After the MT1
> routines to convert all strokes into filled/unfilled contours, I
> presume that the edge objects can be extracted from the API and a C
> program can write them directly into FF's SFD format after which FF
> can write it directly into an OTF or whatever?

I don't think writing my own code in C to talk to Metapost's API,
extract the curves, and write them in SFD format, would be easier than
what I'm doing.  The less of that "literate programming" code I have to
touch directly, the happier I am.  You've seen yourself how hard it is to
get even very simple work done with the Metapost API.

However, it's true that the multi-step process I'm using does have its own
serious disadvantages, and I ended up touching MetaType1 more intimately
than I originally planned for various reasons.  In a future project I'm
contemplating, the idea has come up of skipping MetaPost entirely and
using homegrown code to write parameterized outlines directly to SFD
files.  I think that would be dependent on also skipping the "stroke path"
step, however; for that particular project the paths I'd be writing would
be outlines, not stroked envelopes, and if I found I needed to do path
stroking, I think I would still want to do it using MetaType1.  In such a
case I'd probably stick with the Tsukurimashou approach (using the
multi-step workflow through Postscript) rather than trying to talk to the
API.
-- 
Matthew Skala
mskala at ansuz.sooke.bc.ca                 People before principles.
http://ansuz.sooke.bc.ca/