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

[mskala at ansuz.sooke.bc.ca]

Further to my previous message - writing code to remove inflection points
seemed like a simple enough task that I decided to go ahead and attempt
it rather than just saying "it should be easy."  A draft is below.

Note that this eliminate_inflections macro, unfortunately like very many
other pieces of code in this realm, has a lot of limitations.  It ought to
be possible to compute the locations of all inflection points exactly by
solving the cubic equations that define the splines.  I have not done so.
Instead, this macro works by numerically testing the curvature from points
sampled along the curve, and doing a binary search.  That's less efficient
and less elegant, but simpler to understand, and it may avoid some
boundary-case problems with the exact approach.  This is not guaranteed to
work with curves that contain cusps, loops, very short segments, or a
number of other things like that that you shouldn't have anyway because
they will screw up other parts of the system.  It does *not* generally
solve all of the other complicated issues discussed in my other mail; it
is *only* aimed at inflection points in particular.

Attached as a MIME attachment is a Postscript font demonstrating the
issue.  The letter "a" is an extreme case of what happens when stroking a
curve with inflection points, using the MetaType1 algorithm which is
documented as not being valid for curves with inflection points.  The
letter "b" is the result of manually adding a new node at the inflection
point.  Note it still deviates from the ideal (non-spline) envelope; the
curve gets thinner at some places where we might not want it to.  Only the
drastic crossovers caused by the inflection point have been eliminated.
The letter "c" is the result of automatically removing the inflection
point.  Note it doesn't perfectly match the manual result ("b") because
we're hitting a worst case for the simplistic binary search; I nonetheless
think it's good enough, because the remaining deviations from ideal
stroking caused by other things are much bigger than the difference
created by this particular issue.  Someone with tighter requirements ought
to be using manually-inserted nodes; this macro could also be enhanced
further to detect the special case of cross product=0 (a search midpoint
happened to hit the inflection point exactly) and break out of the loop
early.

Below my signature in the body of this message is the source code for the
font, but you probably won't be able to compile it yourself as-is because
it's written to use the version of MetaType1 embedded in Tsukurimashou -
that being the only one I had handy (I no longer keep an mtype13
installation for general use).  I had to run a couple of the
postprocessing steps manually to generate the Postscript.  Nonetheless, it
should be possible to cut and paste the eliminate_inflections() macro
marked by the comment lines cleanly into any other METAFONT-language code;
the macro isn't Tsukurimashou- or MetaType1-dependent and the rest can be
taken as just an illustration of how the macro might be used.

I hope this is useful, but I still think manually inserting nodes is the
better approach for most purposes.

-- 
Matthew Skala
mskala at ansuz.sooke.bc.ca                 People before principles.
http://ansuz.sooke.bc.ca/

nonstopmode;
def errorstopmode = nonstopmode enddef;

generating:=0;

slang:=0;

input fntbase.mp;

pf_info_quad 1000;
pf_info_space 1000, 0, 0;
pf_info_fixedpitch true;
pf_info_capheight 900;
pf_info_xheight 585;
pf_info_ascender 985;
pf_info_descender 265;

default_nib:=fix_nib(100,100,0);

path scurve;
scurve:=(500,500)..(200,500){dir 240}..{dir 240}(800,200)..(500,200);

beginfont;

encode("a") (97); standard_introduce("a");
beginglyph("a");
  pen_stroke()(scurve)(glyph);
  Fill glyph;
  fix_hsbw(1000,0,0);
endglyph;

encode("b") (98); standard_introduce("b");
beginglyph("b");
  pen_stroke()(insert_nodes(scurve)(1.5))(glyph);
  Fill glyph;
  fix_hsbw(1000,0,0);
endglyph;

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% INFLECTION REMOVAL CODE

% By Matthew Skala, 31 August 2012
% mskala at ansuz.sooke.bc.ca
% Public domain

min_inflection_length:=3;
path inflection_small_circle,inflection_large_circle;
inflection_small_circle:=fullcircle scaled (min_inflection_length/3);
inflection_large_circle:=fullcircle scaled (2*min_inflection_length/3);

vardef eliminate_inflections(expr pa) =
  begingroup
    save p,q;
    path p,q;

    p:=pa;

    if abs((point 1 of p)-(point 0 of p))<min_inflection_length:
      q=p;
    else:

      forever:
        exitif length(p)=1;
        if known q:
          q:=q&eliminate_inflections(subpath (0,1) of p);
        else:
          q:=eliminate_inflections(subpath (0,1) of p);
        fi;
        p:=subpath (1,infinity) of p;
      endfor;

      save x,y,t,turn;
      numeric x[],y[],t[];
      boolean turn[];

      z0=point 0 of p;
      z1=p intersectionpoint (inflection_small_circle shifted z0);
      z2=p intersectionpoint (inflection_large_circle shifted z0);
      turn1=(angle((z1-z0) rotated -angle(z2-z1))>0);

      z8=point 1 of p;
      z7=(reverse p) intersectionpoint (inflection_small_circle shifted z8);
      z6=(reverse p) intersectionpoint (inflection_large_circle shifted z8);
      turn7=(angle((z7-z6) rotated -angle(z8-z7))>0);

      if turn1=turn7:
        if known q:
          q:=q&p;
        else:
          q=p;
        fi;
      else:

        t.lo=0;
        t.hi=1;

        forever:
          t.mid:=0.5[t.lo,t.hi];
          exitif abs((point t.hi of p)-(point t.lo of p))
            <min_inflection_length;

          x3:=whatever;x4:=whatever;x5:=whatever;
          y3:=whatever;y4:=whatever;y5:=whatever;
          z4=point t.mid of p;
          z3=(subpath (0,t.mid) of p)
            intersectionpoint (inflection_small_circle shifted z4);
          z5=(subpath (t.mid,infinity) of p)
            intersectionpoint (inflection_small_circle shifted z4);
          turn4:=(angle((z4-z3) rotated -angle(z5-z4))>0);

          if turn4=turn1:
            t.lo:=t.mid;
          else:
            t.hi:=t.mid;
          fi;
        endfor;

        if known q:
          q:=q&subpath (0,t.mid) of p;
        else:
          q:=subpath(0,t.mid) of p;
        fi;
        q:=q&subpath(t.mid,infinity) of p;
      fi;
    fi;

    q
  endgroup
enddef;

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

encode("c") (99); standard_introduce("c");
beginglyph("c");
  pen_stroke()(eliminate_inflections(scurve))(glyph);
  Fill glyph;
  fix_hsbw(1000,0,0);
endglyph;

endfont;
-------------- next part --------------
A non-text attachment was scrubbed...
Name: strokes.pfb
Type: application/x-font
Size: 3001 bytes
Desc: 
URL: <http://tug.org/pipermail/metapost/attachments/20120831/4870ae01/attachment-0001.bin>