[metapost] METATYPE1 pen-stroking and tight curves

[mskala at ansuz.sooke.bc.ca]

As discussed here a few weeks ago, METATYPE1's pen-stroking macro, because
of the nature of the problem it's solving, can at best produce an
approximation of the theoretical ideal envelope.  On some kinds of input,
the approximation isn't very good; one particular area of difficulty seems
to be when the path being stroked has a segment with tight but smooth
curvature.  The ideal envelope in such a case would include a sharp corner
even though no sharp corner exists in the input; and pen_stroke() will
sometimes produce a deep indentation in the envelope instead of a sharp
corner.  The visual effect looks a little bit like the "ink traps" that
are sometimes deliberately included in traditional metal type designs
intended for printing on newsprint, but the ones from pen_stroke are
uncontrolled and usually undesirable.

I've made some progress on a solution in the context of my Tsukurimashou
project:  code can, with reasonable success, automatically detect path
segments likely to cause this problem and introduce extra path nodes.
The extra nodes create a loop in the envelope, which will be deleted
(leaving the desired sharp corner behind) in the FontForge postprocessing
I'm already doing.  This approach does require that postprocessing step;
something similar might be possible within METATYPE1, but it wouldn't be
so easy and I haven't explored it.

The actual code I'm using is somewhat specific to Tsukurimashou and
couldn't easily be pasted into other projects, but you can read
it in this version-control commit:
   http://en.sourceforge.jp/projects/tsukurimashou/svn/view/trunk/mp/intro.mp?root=tsukurimashou&r1=255&r2=332

A fragment showing the basic operation would look something like this:

        l:=0;
        forever:
          exitif l=length p;
          begingroup
            save x,y;
            numeric x[],y[];
            z0=(point l of p)/100;
            z1=(postcontrol l of p)/100;
            z2=(precontrol (l+1) of p)/100;
            z3=(point (l+1) of p)/100;
            if ((z1-z0) dotprod (z3-z2))/((z2-z1) dotprod (z2-z1))<0.5:
              p:=insert_nodes(p)(l+0.5);
            else:
              l:=l+1;
            fi;
          endgroup;
        endfor;

This finds the four control points for each segment; if they meet a
condition that tests whether the segment is tightly curved, then the
segment gets split into two (using METATYPE1's insert_nodes macro); and
this test and split is applied recursively as long as necessary until no
segments in the path meet the tight-curve condition.  It took a fair bit
of trial and error to come up with a condition that would work; in
particular (since the actual curve is not changed, only the location of
the nodes) it will NOT do to compute the mathematical "curvature" of the
path at a given point.  That won't change on a split, nor will some
conditions I first thought might make sense involving the magnitudes of
the first and second derivatives.  It's important that the split pieces of
a "tight curve" segment, even if they also qualify as "tight curve"
segments themselves, must be *less* tight, so that splitting enough times
will eventually leave us with non-tight segments on which the recursion
can terminate.  The condition above seems to work.

Also note that the points are all divided by 100; that's needed to prevent
numerical overflows in the dot product operation, when the coordinates (as
is typical in my fonts and probably yours too) typically range from 0 to
1000.  If one is using the more advanced per-node "options" features of
pen_stroke, then the node indices for those options will also have to be
updated to take into account the insertion of the new nodes.  The
additional code in Tsukurimashou not shown in the above fragment deals
with interfacing to Tsukurimashou's existing system for tracking the
indices of pen_stroke option settings.

One unforeseen issue with this fix was that because I already have a
substantial body of glyph designs written for the basic METATYPE1
pen_stroke macro without the fix, it turns out that some of my existing
curves actually depended on the old non-ideal behaviour, and this fix
(which brings the pen strokes closer to the theoretical ideal) makes them
look bad.  Most cases of this issue seem to involve curves where a single
long segment changes drastically in its amount of curvature from one end
of the segment to the other.  For instance, in the central vertical stroke
of ホ (U+30DB, Japanese katakana syllable "ho") I had (in the original
design, which is now a couple of years old) a single path segment that
started out as a nearly straight line near the top of the character, and
then hooked sharply to the left at the bottom.  That turned out to be an
artifact of how pen_stroke works:  it put a node in the envelope at the
top following the direction of the curve there, and a node in the envelope
at the bottom following the direction of the curve there, and it connected
them to form a curve I liked, without explicitly following the stroke path
in between.  The new version of the code added a node in the middle, which
revealed that the underlying path I'd been stroking actually included an
inflection point followed by a substantial bulge to the right, which had
been hidden by the approximation of pen_stroke and looked bad when stroked
under a more accurate approximation.  I had to redesign the curve so that
it actually followed the path I intended, instead of only appearing to do
so because of pen_stroke's inaccuracy.  A few other similar cases of
dependence on the approximate behaviour remain to be fixed in
Tsukurimashou, and I also found a couple of glyphs that had "ink trap"
flaws from completely different causes that only happened to look similar
to the effects of pen_stroke inaccurary.  Those will need other solutions.
Nonetheless, this change eliminates most of the "ink trap" flaws in
Tsukurimashou.

This "existing code might depend on pen_stroke inaccuracy" issue would
only be applicable when this kind of fix is retrofitted onto an existing
system written for unfixed METATYPE1 pen_stroke.  It shouldn't be an issue
for new designs, nor for code converted from bitmap METAFONT, either of
which should generally look better with the fix and appropriate
postprocessing than without it.  I still think it's not realistic to
expect a completely automated conversion from bitmap METAFONT to
METATYPE1, but this technique should help reduce the amount of human
effort required to work around the approximation issues.
-- 
Matthew Skala
mskala at ansuz.sooke.bc.ca                 People before principles.
http://ansuz.sooke.bc.ca/