<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>