<HTML>
<HEAD>
<!-- Created with AOLpress/2.0 -->
<!-- AP: Created on: 18-Jul-2003 -->
<!-- AP: Last modified: 4-Apr-2006 -->
<TITLE>FontForge's math</TITLE>
<LINK REL="icon" href="ffanvil16.png">
<LINK REL="stylesheet" TYPE="text/css" HREF="FontForge.css">
</HEAD>
<BODY>
<DIV id="in">
<H1 ALIGN=Center>
FontForge's math
</H1>
<P>
<EM>Being a brief description of the mathematics underlying various of
FontForge's commands<BR>
It is presumed that you understand about parameterized splines, if not look
at the description of <A HREF="bezier.html">Bézier curves</A>.</EM>
<UL>
<LI>
<A HREF="pfaeditmath.html#Linear">Linear Transformations</A>
<LI>
<A HREF="pfaeditmath.html#maxima">Finding maxima and minima of a spline</A>
<LI>
<A HREF="#Rasterizing">Rasterizing a Glyph</A>
<UL>
<LI>
finding intersections
<LI>
removing overlap
</UL>
<LI>
<A HREF="pfaeditmath.html#Approximating">Approximating a spline</A>
<LI>
<A HREF="pfaeditmath.html#Stroke">Stroking a spline</A>
<LI>
<A HREF="bezier.html#ps2ttf">Approximating a cubic spline by a series of
quadratic splines</A>
</UL>
<P>
<HR>
<H2>
<A NAME="Linear">Linear</A> Transformations
</H2>
<P>
A linear transformation is one where the spline described by transforming
the end and control points will match the transformed spline. This includes
most of the common transformations you might wish:
<UL>
<LI>
translation
<TABLE CELLPADDING="2">
<TR>
<TD><I>x'</I></TD>
<TD>=</TD>
<TD><I>x + dx</I></TD>
</TR>
<TR>
<TD><I>y'</I></TD>
<TD>=</TD>
<TD><I>y + dy</I></TD>
</TR>
</TABLE>
<LI>
scaling
<TABLE CELLPADDING="2">
<TR>
<TD><I>x'</I></TD>
<TD>=</TD>
<TD><I>s<SUB>x</SUB> * x</I></TD>
</TR>
<TR>
<TD><I>y'</I></TD>
<TD>=</TD>
<TD><I>s<SUB>y</SUB> * y</I></TD>
</TR>
</TABLE>
<LI>
rotation
<TABLE CELLPADDING="2">
<TR>
<TD><I>x'</I></TD>
<TD>=</TD>
<TD><I>cos(A)*x + sin(A)*y</I></TD>
</TR>
<TR>
<TD><I>y'</I></TD>
<TD>=</TD>
<TD><I>-sin(X)*x + cos(A)*y</I></TD>
</TR>
</TABLE>
<LI>
skewing
<TABLE CELLPADDING="2">
<TR>
<TD><I>x'</I></TD>
<TD>=</TD>
<TD><I>x + sin(A)*y</I></TD>
</TR>
<TR>
<TD><I>y'</I></TD>
<TD>=</TD>
<TD><I>y</I></TD>
</TR>
</TABLE>
</UL>
<P>
<HR>
<H2>
Finding <A NAME="maxima">maxima</A> and minima of a spline
</H2>
<P>
The maximum or minimum of a spline (along either the x or y axes) may be
found by taking the first derivative of that spline with respect to t. So
if we have a spline
<BLOCKQUOTE>
<PRE> x = a<SUB>x</SUB>*t<SUP>3</SUP> + b<SUB>x</SUB>*t<SUP>2</SUP> + c<SUB>x</SUB>*t +d<SUB>x</SUB>
y = a<SUB>y</SUB>*t<SUP>3</SUP> + b<SUB>y</SUB>*t<SUP>2</SUP> + c<SUB>y</SUB>*t +d<SUB>y</SUB>
</PRE>
</BLOCKQUOTE>
<P>
and we wish to find the maximum point with respect to the x axis we set:
<BLOCKQUOTE>
<PRE> dx/dt = 0
3*a<SUB>x</SUB>*t<SUP>2</SUP> + 2*b<SUB>x</SUB>*t + c<SUB>x</SUB> = 0
</PRE>
</BLOCKQUOTE>
<P>
and then using the quadratic formula we can solve for t:
<TABLE CELLPADDING="2">
<TR>
<TD ROWSPAN=3>t=</TD>
<TD><P ALIGN=Center>
-2*b<SUB>x </SUB>± sqrt(4*b<SUB>x</SUB><SUP>2</SUP> -
4*3*a<SUB>x</SUB>*c<SUB>x</SUB>)</TD>
</TR>
<TR>
<TD><P ALIGN=Center>
-----------------------------------</TD>
</TR>
<TR>
<TD><P ALIGN=Center>
2*3*a<SUB>x</SUB></TD>
</TR>
</TABLE>
<P>
<HR>
<H2>
<A NAME="POI">Finding points of inflection</A> of a spline
</H2>
<P>
A point of inflection occurs when d<SUP>2</SUP>y/dx<SUP>2</SUP>==0 (or infinity).
<P>
Unfortunately this does not mean that d<SUP>2</SUP>y/dt<SUP>2</SUP>==0 or
d<SUP>2</SUP>x/dt<SUP>2</SUP>==0.
<TABLE CELLPADDING="2">
<TR>
<TD>d<SUP>2</SUP>y/dx<SUP>2 </SUP>=</TD>
<TD>d/dt ((dy/dt)/(dx/dt)) / dx/dt</TD>
</TR>
<TR>
<TD></TD>
<TD>( ((dx/dt) * d<SUP>2</SUP>y/dt<SUP>2</SUP>) - ((dy/dt) *
d<SUP>2</SUP>x/dt<SUP>2</SUP>)) / (dx/dt)<SUP>3</SUP></TD>
</TR>
</TABLE>
<P>
After a lot of algebra this boils down to the quadratic in t:
<TABLE CELLPADDING="2">
<TR>
<TD ROWSPAN=3> </TD>
<TD>3*(a<SUB>x</SUB>*b<SUB>y</SUB>-a<SUB>y</SUB>*b<SUB>x</SUB>)*t<SUP>2</SUP>
+</TD>
<TD></TD>
</TR>
<TR>
<TD>3*(c<SUB>x</SUB>*a<SUB>y</SUB>-c<SUB>y</SUB>*a<SUB>x</SUB>)*t +</TD>
<TD></TD>
</TR>
<TR>
<TD>c<SUB>x</SUB>*b<SUB>y</SUB>-c<SUB>y</SUB>*b<SUB>x</SUB></TD>
<TD>= 0</TD>
</TR>
</TABLE>
<P>
If you examine this closely you will note that a quadratic spline
(a<SUB>y</SUB>==a<SUB>x</SUB>==0) can never have a point of inflection.
<P>
<HR>
<H2>
<A NAME="Rasterizing">Rasterizing</A> a glyph
</H2>
<P>
<HR>
<H2>
<A NAME="Approximating">Approximating</A> a spline
</H2>
<P>
Many of FontForge's commands need to fit a spline to a series of points.
The most obvious of these are the Edit->Merge, and Element->Simplify
commands, but many others rely on the same technique. Let us consider the
case of the Merge command, suppose we have the following splines and we wish
to remove the middle point and generate a new spline that approximates the
original two:
<P>
<IMG SRC="mergepre.png" WIDTH="192" HEIGHT="120" ALIGN="Middle"> =>
<IMG SRC="mergepost.png" WIDTH="192" HEIGHT="120" ALIGN="Middle">
<P>
FontForge uses a least squares approximation to determine the new spline.
It calculates the locations of several points along the old splines, and
then it guesses<SUP><A HREF="#guess-t">1</A></SUP> at t values for those
points. We want:
<BLOCKQUOTE>
x = a<SUB>x</SUB>*t<SUP>3</SUP> + b<SUB>x</SUB>*t<SUP>2</SUP> +
c<SUB>x</SUB>*t +d<SUB>x</SUB><BR>
y = a<SUB>y</SUB>*t<SUP>3</SUP> + b<SUB>y</SUB>*t<SUP>2</SUP> +
c<SUB>y</SUB>*t +d<SUB>y</SUB>
</BLOCKQUOTE>
<P>
That best fit these points. Well, from the definition of a parameterized
spline (and the fact that we know the end-points):
<TABLE CELLPADDING="2">
<TR>
<TD> </TD>
<TD>d<SUB>x </SUB>= P0<SUB>x</SUB> </TD>
<TD>d<SUB>y</SUB> = P0<SUB>y</SUB></TD>
</TR>
<TR>
<TD></TD>
<TD>a<SUB>x</SUB>+b<SUB>x</SUB>+c<SUB>x</SUB>+d<SUB>x </SUB>= P1<SUB>x</SUB></TD>
<TD>a<SUB>y</SUB>+b<SUB>y</SUB>+c<SUB>y</SUB>+d<SUB>y </SUB>= P1<SUB>y</SUB></TD>
</TR>
</TABLE>
<P>
From least squares we know:
<TABLE CELLPADDING="2">
<TR>
<TD ROWSPAN=4><IMG SRC="lparen-174.png" WIDTH="22" HEIGHT="174" ALIGN="Middle"></TD>
<TD><IMG SRC="Sxiti3.png" WIDTH="50" HEIGHT="35"></TD>
<TD ROWSPAN=4><IMG SRC="rparen-174.png" WIDTH="22" HEIGHT="174" ALIGN="Middle">=<IMG
SRC="lparen-174.png" WIDTH="22" HEIGHT="174" ALIGN="Middle"></TD>
<TD><IMG SRC="Sti6.png" WIDTH="32" HEIGHT="35"></TD>
<TD><IMG SRC="Sti5.png" WIDTH="32" HEIGHT="35"></TD>
<TD><IMG SRC="Sti4.png" WIDTH="32" HEIGHT="35"></TD>
<TD><IMG SRC="Sti3.png" WIDTH="32" HEIGHT="35"></TD>
<TD ROWSPAN=4><IMG SRC="rparen-174.png" WIDTH="22" HEIGHT="174" ALIGN="Middle">*<IMG
SRC="lparen-174.png" WIDTH="22" HEIGHT="174" ALIGN="Middle"></TD>
<TD>a<SUB>x</SUB></TD>
<TD ROWSPAN=4><IMG SRC="rparen-174.png" WIDTH="22" HEIGHT="174" ALIGN="Middle"></TD>
</TR>
<TR>
<TD><IMG SRC="Sxiti2.png" WIDTH="50" HEIGHT="35"></TD>
<TD><IMG SRC="Sti5.png" WIDTH="32" HEIGHT="35"></TD>
<TD><IMG SRC="Sti4.png" WIDTH="32" HEIGHT="35"></TD>
<TD><IMG SRC="Sti3.png" WIDTH="32" HEIGHT="35"></TD>
<TD><IMG SRC="Sti2.png" WIDTH="32" HEIGHT="35"></TD>
<TD>b<SUB>x</SUB></TD>
</TR>
<TR>
<TD><IMG SRC="Sxiti.png" WIDTH="50" HEIGHT="35"></TD>
<TD><IMG SRC="Sti4.png" WIDTH="32" HEIGHT="35"></TD>
<TD><IMG SRC="Sti3.png" WIDTH="32" HEIGHT="35"></TD>
<TD><IMG SRC="Sti2.png" WIDTH="32" HEIGHT="35"></TD>
<TD><IMG SRC="Sti.png" WIDTH="32" HEIGHT="35"></TD>
<TD>c<SUB>x</SUB></TD>
</TR>
<TR>
<TD><IMG SRC="Sxi.png" WIDTH="50" HEIGHT="35"></TD>
<TD><IMG SRC="Sti3.png" WIDTH="32" HEIGHT="35"></TD>
<TD><IMG SRC="Sti2.png" WIDTH="32" HEIGHT="35"></TD>
<TD><IMG SRC="Sti.png" WIDTH="32" HEIGHT="35"></TD>
<TD><P ALIGN=Center>
n</TD>
<TD>d<SUB>x</SUB></TD>
</TR>
</TABLE>
<P>
And similarly for y. So this gives us 12 equations and 8 unknowns, so we're
a bit over-specified. Well it must be a spline, so we need the first four
equations, and then I use the bottom two equations for x, and the corresponding
two for y.
<H3>
Why that didn't work
</H3>
<P>
The above matrix yields a curve which is a good approximation to the original
two. But it has one flaw: There is no constraint placed on the slopes, and
(surprisingly) the slopes at the end-points of the above method are not close
enough to those of the original, and the human eye can now detect the join
between this generated spline and the two that connect to it.
<P>
I tried constraining the slopes by adding new yet more equations to our over
specified system, We know that
<TABLE CELLPADDING="2">
<TR>
<TD>d<I>y</I><SUP>t=0</SUP></TD>
<TD>=</TD>
<TD>(d<I>y</I>/d<I>x</I>)<SUP>t=0</SUP> * d<I>x</I><SUP>t=0</SUP></TD>
</TR>
<TR>
<TD>d<I>y</I><SUP>t=1</SUP></TD>
<TD>=</TD>
<TD>(d<I>y</I>/d<I>x</I>)<SUP>t=1</SUP> * d<I>x</I><SUP>t=1</SUP></TD>
</TR>
<TR>
<TD COLSPAN=3><P ALIGN=Center>
- or -</TD>
</TR>
<TR>
<TD>c<SUB>y</SUB></TD>
<TD>=</TD>
<TD>old-c<SUB>y</SUB>/old-c<SUB>x</SUB> * c<SUB>x</SUB></TD>
</TR>
<TR>
<TD>3*a<SUB>y</SUB>+2*b<SUB>y</SUB>+c<SUB>y</SUB></TD>
<TD>=</TD>
<TD>(3*old-a<SUB>y</SUB>+2*old-b<SUB>y</SUB>+old-c<SUB>y</SUB>)/(3*old-a<SUB>x</SUB>+2*old-b<SUB>x</SUB>+old-c<SUB>x</SUB>)
* (3*a<SUB>x</SUB>+2*b<SUB>x</SUB>+c<SUB>x</SUB>)</TD>
</TR>
<TR>
<TD COLSPAN=3><P ALIGN=Center>
- or -</TD>
</TR>
<TR>
<TD>c<SUB>y</SUB> * old-c<SUB>x</SUB></TD>
<TD>=</TD>
<TD>old-c<SUB>y</SUB> * c<SUB>x</SUB></TD>
</TR>
<TR>
<TD>(3*a<SUB>y</SUB>+2*b<SUB>y</SUB>+c<SUB>y</SUB>) *
(3*old-a<SUB>x</SUB>+2*old-b<SUB>x</SUB>+old-c<SUB>x</SUB>)</TD>
<TD>=</TD>
<TD>(3*old-a<SUB>y</SUB>+2*old-b<SUB>y</SUB>+old-c<SUB>y</SUB>) *
(3*a<SUB>x</SUB>+2*b<SUB>x</SUB>+c<SUB>x</SUB>)</TD>
</TR>
</TABLE>
<P>
(where old-a<SUB>y</SUB>, old-b<SUB>y</SUB>, etc. are the values of the original
spline at that end-point)
<H3>
That didn't work either
</H3>
<P>
Sadly this did not work very well. I ended up with singular matrices far
too often (if one of the control points was in the same place as the end-point,
for example).
<P>
So instead I calculate a unit vector tangent to the curve at each end-point
(that is: the slope). Usually this can be done by making the vector from
the end point to its control point be a unit vector, but if the control point
lies on top of the end point other methods must be used (setting t=.001 or
t=.999 and calculating a difference vector is one method).
<P>
Then apply the original algorithm.
<P>
Now I look at the end points, and calculate vectors from them to their new
control points. Then find the dot-products of these vectors with the original
slope unit vectors. (this gives us our first approximation to a new location
for the control points (CP = EP + len*Unit-Slope)
<P>
Now for each of these vectors I subtract off the contribution from the original
slope (leaving me with component normal to the original slope), and take
the dot product of this normal component with the slope from the <I>other</I>
end-point, and multiply this by the unit slope of the <I>other</I> end point
and adjust its control point by this amount (CP<SUB>o</SUB> +=
len2*Unit-Slope<SUB>o</SUB>).
<H3>
Nor did that
</H3>
<P>
What I do now is calculate the slope vectors at the endpoints and then try
many reasonable lengths for those vectors and see which yields the best
approximation to the original curve (this gives us our new control points).
No need for least squares at all.
<HR>
<H4>
<SUP><A NAME="guess-t">1</A></SUP>Guessing values for t
</H4>
<P>
FontForge approximates the lengths of the two splines being merged. If
Point<SUB>i </SUB>= Spline1(old-t<SUB>i</SUB>), then we approximate ti by<BR>
t<SUB>i</SUB> = old-t<SUB>i</SUB>
*len(spline1)/(len(spline1)+len(spline2)<BR>
and if Point<SUB>i </SUB>= Spline2(old-t<SUB>i</SUB>)<BR>
t<SUB>i</SUB> = len(spline1)/(len(spline1)+len(spline2) +
old-t<SUB>i</SUB> *len(spline2)/(len(spline1)+len(spline2)<BR>
That is we do a linear interpolation of t based on the relative lengths of
the two splines.
<P>
<HR>
<H2>
Calculating the outline of a <A NAME="Stroke">stroked</A> path
</H2>
<H3>
A circular pen
</H3>
<P>
PostScript supports several variants on the theme of a circular pen, and
FontForge tries to emulate them all. Basically PostScript "stroke"s a path
at a certain width by:
<P>
at every location on the curve<BR>
find the normal vector at that location<BR>
find the two points which are width/2 away from the curve<BR>
filling in between those two points<BR>
end
<P>
This is essentially what a circular pen does. The only aberrations appear
at the end-points of a contour, or at points where two splines join but their
slopes are not continuous. PostScript allows the user to specify the behavior
at joints and at end-points.
<P>
<IMG SRC="expand-pre.png" WIDTH="126" HEIGHT="86" ALIGN="Middle">
=> <IMG SRC="expand-post.png" WIDTH="131" HEIGHT="91" ALIGN="Middle">
<P>
For the main body of the spline we can use the above method to generate two
sets of points (one to the left and one to the right of the original curve)
and then use the approximation method above to generate a spline from that
(note the slopes of the new splines at their end points should be parallel
to those of the original, so we can use the slope of the original in the
above algorithm).
<P>
Unfortunately that doesn't always work. If the spline makes a very sharp
bend, the our approximation method above is unable to produce a good
approximation. When that happens FontForge attempts to break the spline in
two, adding a point near the sharp bend. The approximation of the two sub-splines
is generally much better. (How does FontForge figure out where to break a
line? It uses two methods, one just adds points to the extrema of the original
curve, and the other looks for places where the innermost path intersects
itself).
<P>
PostScript pens can end in
<UL>
<LI>
A flat edge -- this is easy, we just draw a line from the end of one spline
to the end of the other
<LI>
A rounded edge -- here we just draw a semi-circle (making sure it goes in
the right direction).
<LI>
A butt edge -- just draw lines continuing the two splines, moving with the
same slope and width/2 units long, and then join those end-points with a
straight line.
</UL>
<P>
Things are a bit more complex at a joint
<IMG SRC="expand-joint-pre.png" WIDTH="61" HEIGHT="78" ALIGN="Middle"> =>
<IMG SRC="expand-joint-post.png" WIDTH="69" HEIGHT="80" ALIGN="Middle">,
the green lines in the right image show where the path would have gone had
it not been constrained by a joint, so on the inside of the joint FontForge
must figure out where this intersection occurs. While on the outside FontForge
must figure out either a round, miter or bevelled edge.
<H3>
An elliptical pen
</H3>
<P>
This is really just the same as a circular pen. Let us say we want an ellipse
which is twice as wide as it is high. Then before stroking the path, let's
scale it to 50% in the horizontal direction, then stroke it with a circular
pen, and then scale it back by 200% horizontally. The result will be as if
we had used an elliptical pen.
<P>
Obviously if the ellipse is at an angle to the glyph's axes, we must apply
a more complicated transformation which involves both rotation and scaling.
<H3>
A rectangular pen (a calligraphic pen)
</H3>
<P>
Things are subtly different between a rectangular pen and a circular pen.
We can no longer just find the points which are a given distance away and
normal to the curve. Except where the spline is parallel to one edge of the
pen, a the outer contour of a rectangular pen will be stroked by one of its
end-points. So all we need do is figure out where a spline is parallel to
the pen's sides, and look at the problem in little chunks between those difficult
points.
<P>
If we are between difficult points then life is very simple indeed. The edge
will always be stroked by the same end-point, which is a fixed distance from
the center of the pen, so all we need to do is translate the original spline
by this distance (and then fix it up so that t goes from [0,1], but that's
another easy transformation).
<P>
When we reach a point where the spline's slope is parallel to one edge of
the pen, then on the outside path we draw a copy of that edge of of the pen,
and on the inside edge we calculate a join as above.
<H3>
An arbitrary convex polygonal pen
</H3>
<P>
FontForge does not currently do this (the UI for specifying an arbitrary
polygon is a little difficult), but the same method which works for a rectangle
can be extended without too much difficulty to any convex polygon. (MetaFont
fonts can be drawn with such a pen. I don't know if any are)
<H3>
A pen of variable width
</H3>
<P>
If you have a wacom tablet then FontForge also supports variable width pens.
Extending the above algorithms is fairly simple.
<H3>
A pen at a varying angle
</H3>
<P>
FontForge does not support this. I don't see a good UI for it. (MetaFont
fonts can be drawn with such a pen).
<P>
</DIV>
</BODY></HTML>
