1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
|
<HTML>
<HEAD>
<!-- Created with AOLpress/2.0 -->
<!-- AP: Created on: 18-Jul-2003 -->
<!-- AP: Last modified: 28-Apr-2010 -->
<TITLE>FontForge's math</TITLE>
<LINK REL="icon" href="fftype16.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.
<P>
Now a cubic <A href="bezier.html">Bézier</A> spline is determined
by its two end points (P<SUB>0</SUB> and P<SUB>1</SUB>) and two control points
(CP<SUB>0</SUB> and CP<SUB>1</SUB>, which specify the slope at those end
points). Here we know the end points, so all we need is to find the control
points. The spline can also be expressed as a cubic polynomial:
<BLOCKQUOTE>
S(t) = a*t<SUP>3</SUP> + b*t<SUP>2</SUP> + c*t +d<BR>
-- with --<BR>
d = P0<BR>
c = 3*CP0 - 3*P0<BR>
b = 3*CP1 - 6*CP0 + 3*P0<BR>
a = P1 - 3*CP1 + 3*CP0 - P0<BR>
<!--S<SUB>x</SUB>(t) = 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>
S<SUB>y</SUB>(t) = 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>--> substituting<BR>
S(t) = (P1 - 3*CP1 + 3*CP0 - P0)*t<SUP>3</SUP> +<BR>
(3*CP1 - 6*CP0 + 3*P0)*t<SUP>2</SUP> +<BR>
(3*CP0 - 3*P0)*t +<BR>
P0<BR>
rearranging<BR>
S(t) = (-3*t<SUP>3</SUP> + 3*t<SUP>2</SUP>) * CP1 +<BR>
(3*t<SUP>3</SUP> - 6*t<SUP>2</SUP> + 3*t) * CP0 +<BR>
(P1-P0)*t<SUP>3</SUP> + 3*P0*t<SUP>2</SUP> - 3*P0*t + P0
</BLOCKQUOTE>
<P>
Now we want to minimize the sum of the squares of the difference between
the value we approximate with the new spline, S(t<SUB>i</SUB>), and the actual
value we were given, P<SUB>i</SUB>.
<TABLE>
<TR>
<TD> </TD>
<TD><IMG src="Sigma28x33.png" width="28" height="33"></TD>
<TD>[ S(t<SUB>i</SUB>) - P<SUB>i</SUB>]<SUP>2</SUP></TD>
</TR>
</TABLE>
<P>
Now we have four unknown variables, the x and y coordinates of the two control
points. To find the minimum of the above error term we must take the derivative
with respect to each variable, and set that to zero. Then we have four equations
with four unknowns and we can solve for each variable.
<TABLE>
<TR>
<TD> </TD>
<TD><IMG src="Sigma28x33.png" width="28" height="33"></TD>
<TD>2* (-3*t<SUP>3</SUP> + 3*t<SUP>2</SUP>)*[
S<SUB>x</SUB>(t<SUB>i</SUB>) - P<SUB>i.x</SUB>] = 0</TD>
</TR>
<TR>
<TD> </TD>
<TD><IMG src="Sigma28x33.png" width="28" height="33"></TD>
<TD>2* (-3*t<SUP>3</SUP> + 3*t<SUP>2</SUP>)*[
S<SUB>y</SUB>(t<SUB>i</SUB>) - P<SUB>i.y</SUB>] = 0</TD>
</TR>
<TR>
<TD> </TD>
<TD><IMG src="Sigma28x33.png" width="28" height="33"></TD>
<TD>2* (3*t<SUP>3</SUP> - 6*t<SUP>2</SUP> + 3*t)*[
S<SUB>x</SUB>(t<SUB>i</SUB>) - P<SUB>i.x</SUB>] = 0</TD>
</TR>
<TR>
<TD> </TD>
<TD><IMG src="Sigma28x33.png" width="28" height="33"></TD>
<TD>2* (3*t<SUP>3</SUP> - 6*t<SUP>2</SUP> + 3*t)*[
S<SUB>y</SUB>(t<SUB>i</SUB>) - P<SUB>i.y</SUB>] = 0</TD>
</TR>
</TABLE>
<P>
Happily for us, the x and y terms do not interact and my be solved separately.
The procedure is the same for each coordinate, so I shall only show one:
<TABLE>
<TR>
<TD> </TD>
<TD><IMG src="Sigma28x33.png" width="28" height="33"></TD>
<TD colspan="3">2* (-3*t<SUP>3</SUP> + 3*t<SUP>2</SUP>)*[
S<SUB>x</SUB>(t<SUB>i</SUB>) - P<SUB>i.x</SUB>] = 0</TD>
</TR>
<TR>
<TD> </TD>
<TD><IMG src="Sigma28x33.png" width="28" height="33"></TD>
<TD colspan="3">2* (3*t<SUP>3</SUP> - 6*t<SUP>2</SUP> + 3*t)*[
S<SUB>x</SUB>(t<SUB>i</SUB>) - P<SUB>i.x</SUB>] = 0</TD>
</TR>
<TR>
<TD colspan="5" align="center">=></TD>
</TR>
<TR>
<TD> </TD>
<TD><IMG src="Sigma28x33.png" width="28" height="33"></TD>
<TD>(-3*t<SUP>3</SUP> + 3*t<SUP>2</SUP>)*</TD>
<TD>[ (-3*t<SUP>3</SUP> + 3*t<SUP>2</SUP>) * CP1<SUB>x</SUB> +<BR>
(3*t<SUP>3</SUP> - 6*t<SUP>2</SUP> + 3*t) * CP0<SUB>x</SUB> +<BR>
(P1<SUB>x</SUB>-P0<SUB>x</SUB>)*t<SUP>3</SUP> +
3*P0<SUB>x</SUB>*t<SUP>2</SUP> - 3*P0<SUB>x</SUB>*t + P0<SUB>x</SUB> -
P<SUB>i.x</SUB> ]</TD>
<TD>= 0</TD>
</TR>
</TABLE>
<TABLE>
<TR>
<TD> </TD>
<TD>CP1<SUB>x</SUB></TD>
<TD><IMG src="Sigma28x33.png" width="28" height="33"></TD>
<TD>(-3*t<SUP>3</SUP> + 3*t<SUP>2</SUP>)*(-3*t<SUP>3</SUP> + 3*t<SUP>2</SUP>)</TD>
<TD>=</TD>
<TD>-</TD>
<TD><IMG src="Sigma28x33.png" width="28" height="33"></TD>
<TD>(-3*t<SUP>3</SUP> + 3*t<SUP>2</SUP>)*</TD>
<TD>[ (3*t<SUP>3</SUP> - 6*t<SUP>2</SUP> + 3*t) * CP0<SUB>x</SUB> +<BR>
(P1<SUB>x</SUB>-P0<SUB>x</SUB>)*t<SUP>3</SUP> +
3*P0<SUB>x</SUB>*t<SUP>2</SUP> - 3*P0<SUB>x</SUB>*t + P0<SUB>x</SUB> -
P<SUB>i.x</SUB> ]</TD>
</TR>
</TABLE>
<TABLE>
<TR>
<TD rowspan="3"> </TD>
<TD rowspan="3">CP1<SUB>x</SUB></TD>
<TD rowspan="3">=</TD>
<TD rowspan="3">-</TD>
<TD><IMG src="Sigma28x33.png" width="28" height="33"></TD>
<TD>(-3*t<SUP>3</SUP> + 3*t<SUP>2</SUP>)*</TD>
<TD>[ (3*t<SUP>3</SUP> - 6*t<SUP>2</SUP> + 3*t) * CP0<SUB>x</SUB> +<BR>
(P1<SUB>x</SUB>-P0<SUB>x</SUB>)*t<SUP>3</SUP> +
3*P0<SUB>x</SUB>*t<SUP>2</SUP> - 3*P0<SUB>x</SUB>*t + P0<SUB>x</SUB> -
P<SUB>i.x</SUB> ]</TD>
</TR>
<TR>
<TD colspan="3">
<HR>
</TD>
</TR>
<TR>
<TD colspan="3"><TABLE align="center">
<TR>
<TD><IMG src="Sigma28x33.png" width="28" height="33"></TD>
<TD>(-3*t<SUP>3</SUP> + 3*t<SUP>2</SUP>)*(-3*t<SUP>3</SUP> + 3*t<SUP>2</SUP>)</TD>
</TR>
</TABLE>
</TD>
</TR>
</TABLE>
<P>
Now this can be plugged into the other equation
<TABLE>
<TR>
<TD> </TD>
<TD><IMG src="Sigma28x33.png" width="28" height="33"></TD>
<TD>(3*t<SUP>3</SUP> - 6*t<SUP>2</SUP> + 3*t)*</TD>
<TD>[ (-3*t<SUP>3</SUP> + 3*t<SUP>2</SUP>) * CP1<SUB>x</SUB> +<BR>
(3*t<SUP>3</SUP> - 6*t<SUP>2</SUP> + 3*t) * CP0<SUB>x</SUB> +<BR>
(P1<SUB>x</SUB>-P0<SUB>x</SUB>)*t<SUP>3</SUP> +
3*P0<SUB>x</SUB>*t<SUP>2</SUP> - 3*P0<SUB>x</SUB>*t + P0<SUB>x</SUB> -
P<SUB>i.x</SUB> ]</TD>
<TD>= 0</TD>
</TR>
</TABLE>
<P>
And we can solve for CP0<SUB>x</SUB> and then CP1<SUB>x</SUB>. The algebra
becomes very messy, with lots of terms, but the concepts are simple.
<P>
Thus we know where the control points are. We know where the end points are.
We have our spline.
<H3>
Why that didn't (quite) 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>
Generally we will know the slopes at the end points as well as the end points
themselves.
<P>
Let's try another approach, based on better geometry. Givens:
<UL>
<LI>
the start point
<LI>
the slope at the start point
<LI>
the end point
<LI>
the slope at the end point
</UL>
<P>
We want to find the two control points. Now it may seem that specifying the
slope specifies the control point but this is not so, it merely specifies
the direction in which the control point lies. The control point may be anywhere
along the line through the start point in that direction, and each position
will give a different curve.
<P>
So we can express the control point by saying it is CP<SUB>0</SUB> =
P<SUB>0</SUB> + r<SUB>0</SUB>
<IMG src="delta0.png" width="28" height="28" align="top"> where
<IMG src="delta0.png" width="28" height="28" align="top"> is a vector in
the direction of the slope, and r<SUB>0</SUB> is the distance in that direction.
Similarly for the end point: CP<SUB>1</SUB> = P<SUB>1</SUB> + r<SUB>1</SUB>
<IMG src="delta1.png" width="28" height="28" align="top">
<P>
We want to find r<SUB>0</SUB> and r<SUB>1</SUB>.
<P>
Converting from bezier control points into a polynomial gives us<BR/>
S(t) = a*t<SUP>3</SUP> + b*t<SUP>2</SUP> + c*t + d
<UL>
<LI>
d = P<SUB>0</SUB>
<LI>
c = 3*(CP<SUB>0</SUB> - P<SUB>0</SUB>)
<LI>
b = 3*(CP<SUB>1</SUB> - CP<SUB>0</SUB>) - c
<LI>
a = P<SUB>1</SUB>-P<SUB>0</SUB> - c - b
</UL>
<P>
Substituting we get
<UL>
<LI>
d = P<SUB>0</SUB>
<LI>
c =
3*r<SUB>0</SUB>*<IMG src="delta0.png" width="28" height="28" align="top">
<LI>
b =
3*(P<SUB>1</SUB>-P<SUB>0</SUB>+r<SUB>1</SUB>*<IMG src="delta1.png" width="28"
height="28" align="top">-2*r<SUB>0</SUB><IMG src="delta0.png" width="28"
height="28" align="top">)
<LI>
a = 2*(P<SUB>0</SUB>-P<SUB>1</SUB>) +
3*(r<SUB>0</SUB><IMG src="delta0.png" width="28" height="28" align="top">
- r<SUB>1</SUB>*<IMG src="delta1.png" width="28" height="28" align="top">)
</UL>
<P>
For least squares we want to minimize
<IMG src="Sigma13x16.png" width="13" height="16">(S(t<SUB>i</SUB>) -
P<SUB>i</SUB>)<SUP>2</SUP>.<BR/>
taking derivatives with both r0 and r1 we get:
<TABLE>
<TR>
<TD> </TD>
<TD><IMG src="Sigma28x33.png" width="28" height="33"></TD>
<TD colspan="3">2* (3*t<SUP>3</SUP> - 6*t<SUP>2</SUP> +
3*t)*<IMG src="delta0.png" width="28" height="28" align="top">*[
S(t<SUB>i</SUB>) - P<SUB>i</SUB>] = 0</TD>
</TR>
<TR>
<TD> </TD>
<TD><IMG src="Sigma28x33.png" width="28" height="33"></TD>
<TD colspan="3">2* (-3*t<SUP>3</SUP> +
3*t<SUP>2</SUP>)*<IMG src="delta1.png" width="28" height="28" align="top">*[
S(t<SUB>i</SUB>) - P<SUB>i</SUB>] = 0</TD>
<TD colspan="5" align="center">dividing by constants and substituting, we
get</TD>
<TD> </TD>
<TD><IMG src="Sigma28x33.png" width="28" height="33"></TD>
<TD>(3*t<SUP>3</SUP> - 6*t<SUP>2</SUP> + 3*t)*[</TD>
<TD>P<SUB>0</SUB> - P<SUB>i</SUB> + 3 *
(P<SUB>1</SUB>-P<SUB>0</SUB>*t<SUP>2</SUP> + 2 * (P<SUB>0</SUB> -
P<SUB>1</SUB>)*t<SUP>3</SUP> +<BR>
<IMG src="delta0.png" width="28" height="28" align="top">*(3*t -
6*t<SUP>2</SUP> + 3*t<SUP>3</SUP>) * r<SUB>0</SUB> + <BR>
<IMG src="delta1.png" width="28" height="28" align="top">*(3*t<SUP>2</SUP>
- 3*t<SUP>3</SUP>) * r<SUB>1</SUB> +</TD>
<TD>] = 0</TD>
<TD> </TD>
<TD><IMG src="Sigma28x33.png" width="28" height="33"></TD>
<TD>(-3*t<SUP>3</SUP> + 3*t<SUP>2</SUP>)*[</TD>
<TD>P<SUB>0</SUB> - P<SUB>i</SUB> + 3 *
(P<SUB>1</SUB>-P<SUB>0</SUB>*t<SUP>2</SUP> + 2 * (P<SUB>0</SUB> -
P<SUB>1</SUB>)*t<SUP>3</SUP> +<BR>
<IMG src="delta0.png" width="28" height="28" align="top">*(3*t -
6*t<SUP>2</SUP> + 3*t<SUP>3</SUP>) * r<SUB>0</SUB> + <BR>
<IMG src="delta1.png" width="28" height="28" align="top">*(3*t<SUP>2</SUP>
- 3*t<SUP>3</SUP>) * r<SUB>1</SUB> +</TD>
<TD>] = 0</TD>
</TR>
</TABLE>
<P>
Again we have two linear equations in two unknowns (r0, and r1), and (after
a lot of algebraic grubbing) we can solve for them. One interesting thing
here is that the x and y terms do not separate but must be summed together.
<H3>
Singular matrices
</H3>
<P>
Very occasionally, a singular matrix will pop out of these equations. Then
what I do 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).
<P>
This is very, very slow.
<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>
FontForge can't deal with an infinite number of locations, so it samples
the curve (approximately every em unit), and finds the two normal points.
These are on the edge of the area to be stroked, so FontForge can approximate
new contours from these edge points (using the <A href="#Approximating">above
algorithm</A>).
<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.
<P>
Unfortunately, the normal points are not always on the edge of the filled
region. If the curve makes a sharp bend, then one of the normal points may
end up inside the pen when it is centered somewhere else on the original
contour (similar to the case of a joint above).
<P>
So FontForge makes another pass through the edge points and figures out which
ones are actually internal points. After that it will approximate contours.
<P>
Now if we start with an open contour, (a straight line, for example) then
we will end up with one closed contour. While if we start with a closed contour
we will end up with two closed contours (one on the inside, and one on the
outside). Unless there are places where the curve doubles back on itself,
then when can get arbetrarily many closed contours.
<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>
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.-->FontForge does not currently
support this (some of the assumptions behind this algorithm are broken if
the pen changes shape too rapidly).
<H3>
A pen at a varying angle
</H3>
<P>
FontForge does not support this.
<P>
</DIV>
</BODY></HTML>
|
