<p>Hi Matthew. I've also been working on the same problem but from a different angle. Would you please explain why/how you arrived at or at least justify that formula involving those dot products?</p>
<p>Thanks.</p>
<p>Sent from my Android phone</p>
<div class="gmail_quote">On Sep 19, 2012 10:00 PM, <<a href="mailto:mskala@ansuz.sooke.bc.ca">mskala@ansuz.sooke.bc.ca</a>> wrote:<br type="attribution"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
As discussed here a few weeks ago, METATYPE1's pen-stroking macro, because<br>
of the nature of the problem it's solving, can at best produce an<br>
approximation of the theoretical ideal envelope. On some kinds of input,<br>
the approximation isn't very good; one particular area of difficulty seems<br>
to be when the path being stroked has a segment with tight but smooth<br>
curvature. The ideal envelope in such a case would include a sharp corner<br>
even though no sharp corner exists in the input; and pen_stroke() will<br>
sometimes produce a deep indentation in the envelope instead of a sharp<br>
corner. The visual effect looks a little bit like the "ink traps" that<br>
are sometimes deliberately included in traditional metal type designs<br>
intended for printing on newsprint, but the ones from pen_stroke are<br>
uncontrolled and usually undesirable.<br>
<br>
I've made some progress on a solution in the context of my Tsukurimashou<br>
project: code can, with reasonable success, automatically detect path<br>
segments likely to cause this problem and introduce extra path nodes.<br>
The extra nodes create a loop in the envelope, which will be deleted<br>
(leaving the desired sharp corner behind) in the FontForge postprocessing<br>
I'm already doing. This approach does require that postprocessing step;<br>
something similar might be possible within METATYPE1, but it wouldn't be<br>
so easy and I haven't explored it.<br>
<br>
The actual code I'm using is somewhat specific to Tsukurimashou and<br>
couldn't easily be pasted into other projects, but you can read<br>
it in this version-control commit:<br>
<a href="http://en.sourceforge.jp/projects/tsukurimashou/svn/view/trunk/mp/intro.mp?root=tsukurimashou&r1=255&r2=332" target="_blank">http://en.sourceforge.jp/projects/tsukurimashou/svn/view/trunk/mp/intro.mp?root=tsukurimashou&r1=255&r2=332</a><br>
<br>
A fragment showing the basic operation would look something like this:<br>
<br>
l:=0;<br>
forever:<br>
exitif l=length p;<br>
begingroup<br>
save x,y;<br>
numeric x[],y[];<br>
z0=(point l of p)/100;<br>
z1=(postcontrol l of p)/100;<br>
z2=(precontrol (l+1) of p)/100;<br>
z3=(point (l+1) of p)/100;<br>
if ((z1-z0) dotprod (z3-z2))/((z2-z1) dotprod (z2-z1))<0.5:<br>
p:=insert_nodes(p)(l+0.5);<br>
else:<br>
l:=l+1;<br>
fi;<br>
endgroup;<br>
endfor;<br>
<br>
This finds the four control points for each segment; if they meet a<br>
condition that tests whether the segment is tightly curved, then the<br>
segment gets split into two (using METATYPE1's insert_nodes macro); and<br>
this test and split is applied recursively as long as necessary until no<br>
segments in the path meet the tight-curve condition. It took a fair bit<br>
of trial and error to come up with a condition that would work; in<br>
particular (since the actual curve is not changed, only the location of<br>
the nodes) it will NOT do to compute the mathematical "curvature" of the<br>
path at a given point. That won't change on a split, nor will some<br>
conditions I first thought might make sense involving the magnitudes of<br>
the first and second derivatives. It's important that the split pieces of<br>
a "tight curve" segment, even if they also qualify as "tight curve"<br>
segments themselves, must be *less* tight, so that splitting enough times<br>
will eventually leave us with non-tight segments on which the recursion<br>
can terminate. The condition above seems to work.<br>
<br>
Also note that the points are all divided by 100; that's needed to prevent<br>
numerical overflows in the dot product operation, when the coordinates (as<br>
is typical in my fonts and probably yours too) typically range from 0 to<br>
1000. If one is using the more advanced per-node "options" features of<br>
pen_stroke, then the node indices for those options will also have to be<br>
updated to take into account the insertion of the new nodes. The<br>
additional code in Tsukurimashou not shown in the above fragment deals<br>
with interfacing to Tsukurimashou's existing system for tracking the<br>
indices of pen_stroke option settings.<br>
<br>
One unforeseen issue with this fix was that because I already have a<br>
substantial body of glyph designs written for the basic METATYPE1<br>
pen_stroke macro without the fix, it turns out that some of my existing<br>
curves actually depended on the old non-ideal behaviour, and this fix<br>
(which brings the pen strokes closer to the theoretical ideal) makes them<br>
look bad. Most cases of this issue seem to involve curves where a single<br>
long segment changes drastically in its amount of curvature from one end<br>
of the segment to the other. For instance, in the central vertical stroke<br>
of ホ (U+30DB, Japanese katakana syllable "ho") I had (in the original<br>
design, which is now a couple of years old) a single path segment that<br>
started out as a nearly straight line near the top of the character, and<br>
then hooked sharply to the left at the bottom. That turned out to be an<br>
artifact of how pen_stroke works: it put a node in the envelope at the<br>
top following the direction of the curve there, and a node in the envelope<br>
at the bottom following the direction of the curve there, and it connected<br>
them to form a curve I liked, without explicitly following the stroke path<br>
in between. The new version of the code added a node in the middle, which<br>
revealed that the underlying path I'd been stroking actually included an<br>
inflection point followed by a substantial bulge to the right, which had<br>
been hidden by the approximation of pen_stroke and looked bad when stroked<br>
under a more accurate approximation. I had to redesign the curve so that<br>
it actually followed the path I intended, instead of only appearing to do<br>
so because of pen_stroke's inaccuracy. A few other similar cases of<br>
dependence on the approximate behaviour remain to be fixed in<br>
Tsukurimashou, and I also found a couple of glyphs that had "ink trap"<br>
flaws from completely different causes that only happened to look similar<br>
to the effects of pen_stroke inaccurary. Those will need other solutions.<br>
Nonetheless, this change eliminates most of the "ink trap" flaws in<br>
Tsukurimashou.<br>
<br>
This "existing code might depend on pen_stroke inaccuracy" issue would<br>
only be applicable when this kind of fix is retrofitted onto an existing<br>
system written for unfixed METATYPE1 pen_stroke. It shouldn't be an issue<br>
for new designs, nor for code converted from bitmap METAFONT, either of<br>
which should generally look better with the fix and appropriate<br>
postprocessing than without it. I still think it's not realistic to<br>
expect a completely automated conversion from bitmap METAFONT to<br>
METATYPE1, but this technique should help reduce the amount of human<br>
effort required to work around the approximation issues.<br>
--<br>
Matthew Skala<br>
<a href="mailto:mskala@ansuz.sooke.bc.ca">mskala@ansuz.sooke.bc.ca</a> People before principles.<br>
<a href="http://ansuz.sooke.bc.ca/" target="_blank">http://ansuz.sooke.bc.ca/</a><br>--<br>
<a href="http://tug.org/metapost/" target="_blank">http://tug.org/metapost/</a><br></blockquote></div>