summaryrefslogtreecommitdiff
path: root/fonts/utilities/mf2ps/doc/paper.ref
blob: bbc511784511ab794e343fcba73718734571f2d3 (plain)
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
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
1157
1158
1159
1160
1161
1162
1163
1164
1165
1166
1167
1168
1169
1170
1171
1172
1173
1174
1175
1176
1177
1178
1179
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189
1190
1191
1192
1193
1194
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
1219
1220
1221
1222
1223
1224
1225
1226
1227
1228
1229
1230
1231
1232
1233
1234
1235
1236
1237
1238
1239
1240
1241
1242
1243
1244
1245
1246
1247
1248
1249
1250
1251
1252
1253
1254
1255
1256
1257
1258
1259
1260
1261
1262
1263
1264
1265
1266
1267
1268
1269
1270
1271
1272
1273
1274
1275
1276
1277
1278
1279
1280
1281
1282
1283
1284
1285
1286
1287
1288
1289
1290
1291
1292
1293
1294
1295
1296
1297
1298
1299
1300
1301
1302
1303
1304
1305
1306
1307
1308
1309
1310
1311
1312
1313
1314
1315
1316
1317
1318
1319
1320
1321
1322
1323
1324
1325
1326
1327
1328
1329
1330
1331
1332
1333
1334
1335
1336
1337
1338
1339
1340
1341
1342
1343
1344
1345
1346
1347
1348
1349
1350
1351
1352
1353
1354
1355
1356
1357
1358
1359
1360
1361
1362
1363
1364
1365
1366
1367
1368
1369
1370
1371
1372
1373
1374
1375
1376
1377
1378
1379
1380
1381
1382
1383
1384
1385
1386
1387
1388
1389
1390
1391
1392
1393
1394
1395
1396
1397
1398
1399
1400
1401
1402
1403
1404
1405
1406
1407
1408
1409
1410
1411
1412
1413
1414
1415
1416
1417
1418
1419
1420
1421
1422
1423
1424
1425
1426
1427
1428
1429
1430
1431
1432
1433
1434
1435
1436
1437
1438
1439
1440
1441
1442
1443
1444
1445
1446
1447
1448
1449
1450
1451
1452
1453
1454
1455
1456
1457
1458
1459
1460
1461
1462
1463
1464
1465
1466
1467
1468
1469
1470
1471
1472
1473
1474
1475
1476
1477
1478
1479
1480
1481
1482
1483
1484
1485
1486
1487
1488
1489
1490
1491
1492
1493
1494
1495
1496
1497
1498
1499
1500
1501
1502
1503
1504
1505
1506
1507
1508
1509
1510
1511
1512
1513
1514
1515
1516
1517
1518
1519
1520
1521
1522
1523
1524
1525
1526
1527
1528
1529
1530
1531
1532
1533
1534
1535
1536
1537
1538
1539
1540
1541
1542
1543
1544
1545
1546
1547
1548
1549
1550
1551
1552
1553
1554
1555
1556
1557
1558
1559
1560
1561
1562
1563
1564
1565
1566
1567
1568
1569
1570
1571
1572
1573
1574
1575
1576
1577
1578
1579
1580
1581
1582
1583
1584
1585
1586
1587
1588
1589
1590
1591
1592
1593
1594
1595
1596
1597
1598
1599
1600
1601
1602
1603
1604
1605
1606
1607
1608
1609
1610
1611
1612
1613
1614
1615
1616
1617
1618
1619
1620
1621
1622
1623
1624
1625
1626
1627
1628
1629
1630
1631
1632
1633
1634
1635
1636
1637
1638
1639
1640
1641
1642
1643
1644
1645
1646
1647
1648
1649
1650
1651
1652
1653
1654
1655
1656
1657
1658
1659
1660
1661
1662
1663
1664
1665
1666
1667
1668
1669
1670
1671
1672
1673
1674
1675
1676
1677
1678
1679
1680
1681
1682
1683
1684
1685
1686
1687
1688
1689
1690
1691
1692
1693
1694
1695
1696
1697
1698
1699
1700
1701
1702
1703
1704
1705
1706
1707
1708
1709
1710
1711
1712
1713
1714
1715
1716
1717
1718
1719
1720
1721
1722
1723
1724
1725
1726
1727
1728
1729
1730
1731
1732
1733
1734
1735
1736
1737
1738
1739
1740
1741
1742
1743
1744
1745
1746
1747
1748
1749
1750
1751
1752
1753
1754
1755
1756
1757
1758
1759
1760
1761
1762
1763
1764
1765
1766
1767
1768
1769
1770
1771
1772
1773
1774
1775
1776
1777
1778
1779
1780
1781
1782
1783
1784
1785
1786
1787
1788
1789
1790
1791
1792
1793
1794
1795
1796
1797
1798
1799
1800
1801
1802
1803
1804
1805
1806
1807
1808
1809
1810
1811
1812
1813
1814
1815
1816
1817
1818
1819
1820
1821
1822
1823
1824
1825
1826
1827
1828
1829
1830
1831
1832
1833
1834
1835
1836
1837
1838
1839
1840
1841
1842
1843
1844
1845
1846
1847
1848
1849
1850
1851
1852
1853
1854
1855
1856
1857
1858
1859
1860
1861
1862
1863
1864
1865
1866
1867
1868
1869
1870
1871
1872
1873
1874
1875
1876
1877
1878
1879
1880
1881
1882
1883
1884
1885
1886
1887
1888
1889
1890
.nr [W \w'10'
.nr [W \w'10'
.pl 11.125i
.de rb
.ta 2m +5m +5m
.nr t1\\n(.i
.ls \\n(sq
.in \\n(sem
..
.de rf
.br
.ne \\n(scu+\\n(sdu
.sp \\n(sdu
.ti -2m
..
.de LE
.sp .5v
..
.de SU
.ne 2v
.br
.ti 1.66P
\f3\\$1\fP
..
.de Su
.ne 2v
.sp 1v
\fB\&\\$1\fP
..
.de su
.ne 3v
.sp 1v
.na
\fB\&\\$1\fP
.br
.ad
..
.de PP
.sp .5v
..
.de qb
.in +\\n(sju
.LL -\\n(sju
.sp .5v
..
.de qe
.in -\\n(sju
.LL +\\n(sju
.sp .5v
..
.de cl
.ta\\n(sou +5m +5m
.in+\\n(snu
..
.de dl
.br
.in-\\n(snu
..
.de ES
.ft C
.sp
.nf
.in +1.66P
..
.de EE
.fi
.ft R
.sp
.in -1.66P
..
.dehd
.HS
.nrhe+1
.ie\\n(cn>1\{\
.ie\\nc>\\n(cn\{\
'sp\\n(bhu-1v
.nr 1F \\n(.f
.nr 1S \\n(.s
.ft
.ps
.nr 2F \\n(.f
.nr 2S \\n(.s
.ft 1
.ps 10
.iee .tl \\*(Te
.el.tl \\*(To
.ft \\n(2F
.ps \\n(2S
.ft \\n(1F
.ps \\n(1S
'sp|\\n(thu
.nrc 1 1
.mkmx\}
.el\{\
.po+\\n(cwu+\\n(csu
'sp|\\n(mxu\}\}
.el\{\
.if\\n(f5\{\
.nr% +\\n(f5
.nrf50 1\}
'sp\\n(bhu-1v
.nr 1F \\n(.f
.nr 1S \\n(.s
.ft
.ps
.nr 2F \\n(.f
.nr 2S \\n(.s
.ft 1
.ps 10
.iee .tl \\*(Te
.el.tl \\*(To
.ft \\n(2F
.ps \\n(2S
.ft \\n(1F
.ps \\n(1S
'sp|\\n(thu\}
.chfx -\\n(tfu
.chfo -\\n(tfu
.if\\n(z1 .fz
.chfo -\\n(tfu
.if!\\n(f0 .ns
.if\\n(f0\{\
.nrf5\\n(f6
.nrf6\\n(f7
.nrf70
.Ff
.ie\\n(fa\{\
.nrfa0
.nrh21\}
.el\{\
.ie\\nx\{.if (\\n(nlu+5v)>(\\n(.p+\\nyu) .nr h1 1\}
.el\{.if \\n(.tu<6v .nr h1 1\}\}\}
.if\\n(h1=1\{\
.nrh10
'bp\}
.if\\n(h2=1\{\
.nrh20
.fo\}
.chfo (\\nyu-1v)
.nrhe-1
.HE
..
.defo
.FS
.if!\\n(he\{.if \\nx .xf\}
.nrfa0
.ie\\n(fg\{\
.nrfa1
.diGA\}
.el\{\
.ie\\n(cn<2\{\
'chfo 32000
'chfx 32000
'sp(\\n(.pu-\\n(nlu-\\n(tfu+\\n(bfu-1v)u
.nr 1F \\n(.f
.nr 1S \\n(.s
.ft
.ps
.nr 2F \\n(.f
.nr 2S \\n(.s
.ft 1
.ps 10
.iee .tl \\*(Be
.el.tl \\*(Bo
.ft \\n(2F
.ps \\n(2S
.ft \\n(1F
.ps \\n(1S
'bp\}
.el.mf\}
.FE
..
.demf
.ie\\n+c<=\\n(cn .hd
.el\{\
.po\\n(cou
.lt 6.63i
'chfo 32000
'chfx 32000
'sp(\\n(.pu-\\n(nlu-\\n(tfu+\\n(bfu-1v)u
.nr 1F \\n(.f
.nr 1S \\n(.s
.ft
.ps
.nr 2F \\n(.f
.nr 2S \\n(.s
.ft 1
.ps 10
.iee .tl \\*(Be
.el.tl \\*(Bo
.ft \\n(2F
.ps \\n(2S
.ft \\n(1F
.ps \\n(1S
'bp\}
..
.defn
.ie\\nx .ne \\n(rcv-2v
.el.ne \\n(rcv
.if\\n(fn .AB"Nesting of footnotes is a no no"
.nrfn1
.daFN
.ev1
.ie\\n+x=1\{\
.sp 10p
\s-5\l'5P\(ul'\s+5
.br\}
.el.sp \\n(srv
.fi
.ad
..
.\" REFER macros .... citations
.nr se 3u \" space to indent in emms
.de []
.][ \\$1
..
.de ][
.if \\$1>5 .tm Bad arg to []
.if !"\\*([O"" .if !\\n([O .as [O .
.[\\$1
..
.ds RB ".RE
.ds [. " [
.ds .] ]
.if n .ds [o ""
.if n .ds [c ""
.if t .ds [o \(lq
.if t .ds [c \(rq
.\" the next lines deal with the problem of .[1] or [1].
.\" refer will write "linexxx\*(<.[1]\*(>.
.\" and either "<." or ">." should produce the .;
.\" similarly for ,
.ds >. .
.ds >, ,
.de [5 \" tm style
\\*([A, \\f2\\*([T\\f1,
.ie \\n(TN \\*([M.
.el UCLA Computer Science Department internal memorandum (\\*([D).
.br
..
.de [0 \" other
.if !"\\*([A"" \\*([A,
.if !"\\*([O"" \\*([O
.if !"\\*([D"" \& (\\*([D).
.br
..
.de [1 \" journal article
.if !"\\*([A"" \\*([A,
.if !"\\*([T"" \\*([o\\*([T,\\*([c
\\f2\\*([J\\f1\c
.if !"\\*([V"" .if n \& Vol.\&\c
.if !"\\*([V"" \& \\f3\\*([V\\f1\c
.if !"\\*([N"" (\\*([N)\c
.if !"\\*([P"" \{\
.ie \\n([P>0 , pp.\c
.el , p.\c
\& \\*([P\c\}
.if !"\\*([I"" .if "\\*([R"" , \\*([I\c
.if !"\\*([D"" \& (\\*([D)\c
\&.
.if !"\\*([O"" \\*([O
.br
..
.de [2 \" book
.if !"\\*([A"" \\*([A,
.if !"\\*([T"" \\f2\\*([T,\\f1
\\*([I\c
.if !"\\*([C"" , \\*([C\c
.if !"\\*([D"" \& (\\*([D)\c
\&.
.if !"\\*([G"" Gov't. ordering no. \\*([G.
.if !"\\*([O"" \\*([O
.br
..
.de [4 \" report
.if !"\\*([A"" \\*([A,
\\*([o\\*([T,\\*([c
\\*([R\c
.if !"\\*([G"" \& (\\*([G)\c
.if !"\\*([I"" , \\*([I\c
.if !"\\*([C"" , \\*([C\c
.if !"\\*([D"" \& (\\*([D)\c
\&.
.if !"\\*([O"" \\*([O
.br
..
.de [3 \" article in book
.if !"\\*([A"" \\*([A,
.if !"\\*([T"" \\*([o\\*([T,\\*([c
.if !"\\*([P"" pp. \\*([P
in \\f2\\*([B\\f1\c
.if !"\\*([E"" , ed. \\*([E\c
.if !"\\*([I"" , \\*([I\c
.if !"\\*([C"" , \\*([C\c
.if !"\\*([D"" \& (\\*([D)\c
\&.
.if !"\\*([O"" \\*([O
.br
..
.\" define warning that mX does not support references as footnotes
.de ]-
.AB"Can't do references as footnotes. Use '-e' or '-s' option with 'refer'
..
.de ]<
.\" define the real ]- next-reference macro
. de ]-
. rm [V [P [A [T
. rm [N [C [B [O
. rm [R [I [E [D
. rf
\\\\*([F.	\c
\\..
.\"now start the reference subsection
\\*(RB
.rb
..
.de ]>
.re
..
.de ]]
this is never
executed
and just
uses up an end-of-file
bug.
..
.de TS
.sp
..
.de TE
.sp .25v
.ce
\\$1
.sp .5v
.ien .ta .8i +.8i +.8i +.8i +.8i +.8i +.8i +.8i +.8i +.8i
.el.ta .5i +.5i +.5i +.5i +.5i +.5i +.5i +.5i +.5i +.5i
..
.de ca
.sp .5v
.ce
\&\\$1
.sp 8p
..
.de CT
.if \\n(ff .F0 "\\$1" "\\n%"
..
.nr sd 1i/24u \" # of inches to space between references (used as u).
.nr sf 1.66P \" space to indent for paragraph (used as u).
.nr sg 1u \" # of spaces needed before trap to start paragraph(used as v).
.nr sh 0u \" # of spaces done to start a new paragraph (used as v).
.nr si 1u \" # of spaces used to start an example (used as v).
.nr sj 1.66P \" space to indent for an example (used as u);
.nr sn 1.66P \" amount of space to indent for list (used as u).
.nr so 1P \" amount of space to temp indent for each list entry (used as u).
.nr sp 1i/12u \" spacing for each element of list (or sublist) (used as u).
.nr sa 1v \" # of spaces to do before subtitles (used as u).
.nr se 3u \" # of spaces to indent for a reference (used as ems).
.nr sm 1i \" # of spaces of need to do a subtitle (used as u).
.nr fv 3 \" set font variable for subtitles to Helvetica
.nr si 1u \" # of spaces used to start an example (used as v).
.nr sk 1u \" # of spaces left at the end of an example (used as v);
.deRT
.ien .ta .8i +.8i +.8i +.8i +.8i +.8i +.8i +.8i +.8i +.8i
.el.ta .25i +.25i +.25i +.25i +.25i +.25i +.25i +.25i +.25i +.25i
..
.RT
.EQ
delim $$
.EN
.ds MF \f(LGMETA\%FONT\fP
.ds TB \fITUG\%boat\fP
.ds BZ B\o'e\(aa'zier
.ds TX T\v'+.2m'\h'-.1m'E\h'-.1m'\v'-.2m'X
.ds LT L\v'-.15m'\h'-.3m'\s-2A\s+2\v'.15m'\h'-.1m'T\v'.2m'\h'-.10m'E\h'-.10m'\v'-.2m'X
.ds BT B\\h'-0.05m'\\s-2I\\h'-0.025m'B\\s0\\h'-0.08m'\\*(TX
.ds pS P\s-2OST\%\s0S\s-2CRIPT\s0
.ds P1 \f2P\fP\v'.2m'\s-3\f11\fP\s+3\^\v'-.2m'
.ds P2 \f2P\fP\v'.2m'\s-3\f12\fP\s+3\^\v'-.2m'
.ds P3 \f2P\fP\v'.2m'\s-3\f13\fP\s+3\^\v'-.2m'
.ds P4 \f2P\fP\v'.2m'\s-3\f14\fP\s+3\^\v'-.2m'
.en
.LL 39.00P
.ls 1
.ds BL ''%''
.hy 14
The next page begins the paper. The macro package I use cannot start
double columning until AFTER some text is printed..
.pn 1
.bp
.MC 2 18.75P 1.5P 1i
.mk xx
\v'-1v'\l'18.7P'
.sp |\n(xxu
\s+2Environment for Translating
.br
\*(MF to \*(pS\s0
.sp 3p
.ti 1.66P
Shimon Yanai and Daniel M. Berry
.sp 8p
\fBAbstract\fP
.PP
This paper describes a program, \fHmf2ps\fP, that translates a
\*(MF font definition into a definition for the same font in the
\*(pS language. \fHmf2ps\fP is constructed out
of the part of the \*(MF program that extracts the envelopes of the
letters; these envelopes are converted into \*(pS outlines.
.su "1\ \ \ Introduction"
.PP
This paper describes a program, \fHmf2ps\fP,
that takes from a \*(MF\*([.10,\|11\*(.]
program for a font all the necessary information in order to
create an equivalent \*(pS\*([.1\*(.]
font definition. The program makes use of the front end of the
\*(MF program to extract the envelopes of the letters to produce the
\*(pS outlines. What makes this process natural is that both \*(MF and
\*(pS make liberal use of \*(BZ curves to describe non-circular
curves.
.pp
By producing this translator, it is hoped to be able to produce from
\*(MF fonts \*(pS outline fonts which are more compact than the
bitmapped fonts produced by the \*(MF program. Certainly the outline
fonts are more easily scaled to other magnifications and possibly even
other design sizes than are bitmaps. Moreover, doing so makes fonts
heretofore available only on \*(TX\*([.9\*(.]
and other DVI-based formatters,
available on \fHditroff\fR\*([.8\*(.]
and other formatters which have evolved,
or have been designed, for use with \*(pS printers. This paper, which is
typeset by \fHditroff\fR, uses a \*(pS version of the
logo font in order to print the word \(lq\*(MF\|\(rq in the same appearance as
in \*(TX-generated documents.
Moreover, these new \*(pS outline fonts can be used in \*(TX also! One
needs only the 
T\v'+.2m'\h'-.1m'E\h'-.1m'\v'-.2m'X\v'+.2m'\h'-.1m'P\h'-.1m'\v'-.2m'S\*([.3\*(.]
software.
.pp
The organization of this paper is as follows. Section 2 presents the
background of this work. Section 3 explains the rationale behind
building the translator and describes a previous attempt at writing the
translator and an approach to avoid. The software engineering aspect of
the translator is described also in Section 3. The details of the
implementation are exposed in Section 4. Section 5 describes the
operation of the program. Section 6 evaluates the results. Finally
Section 7 describes improvements to the translator that are left for
future work.
.su "2\ \ \ Background"
.PP
Typesetter formatting systems such as \*(TX and \fHditroff\fP use fonts
as raw material. The formatters accept mixed text and commands as input
and produce output, which, if sent to the laser printers or typesetters,
yields formatted text printed on pages. The laser printers and
typesetters use fonts, i.e., sets of printable patterns, one per
character, in various representations in order to cause the desired
characters to appear on the printed form. For some printers, bitmaps
are used, with 1's representing inked dots and 0's representing
non-inked dots. Other printers accept commands that cause drawing of
the characters, the printer providing the inked dots according to the
drawing commands. One such popular command language is \*(pS, and its
usual use is to specify the outline of the character with the
interpreting printer filling in the outline with ink. One popular
method of describing fonts is with the \*(MF language, in which
declarative definitions of how to paint the characters are given in
terms of pen path and pen shape. Another popular method is the same
\*(pS that many printers accept. The prime difference is that the \*(MF
program translates the font definitions into bitmaps prior to sending
the font to the printer while a \*(pS printer translates the outlines
into bitmaps at the time of printing. Interestingly, both the \*(MF
language and the \*(pS language use \*(BZ curves for describing the
curves followed by the pen or the outlines. As usually configured
these days, \*(TX uses bitmapped fonts in the Computer Modern family
generated by \*(MF, and \fHditroff\fP uses \*(pS outline fonts supplied
by Adobe.
.pp
The subsequent subsections delve deeper into these issues in order to
be able to state the goal of this paper in the next section.
.Su "2.1\ \ \ Fonts, design sizes, and magnifications."
As mentioned, fonts are the raw material of typesetting. A font is a
set of printable patterns, one for each character, that causes printing
of that character in a particular recognizable style on the page. As
mentioned, these patterns can be represented by bitmaps or drawing
instructions.
.pp
Characters come in various sizes. There are two independent notions of
sizing for fonts, point size or design size and magnification. The
\fIdesign size\fP is the size at which the character is designed to be used
and is, in well-designed text, the size in which the character appears
in final, printed copy. Design size is
usually expressed in units of points, which are each approximately 1/72
of an inch. Most normal text in books, newspapers, and magazines is
printed in 10 point type. Headlines are larger, perhaps as large as 30
points. The \fImagnification\fP of a font is the inverse of the ratio
between the design size of the character and the size of the
character as it emerges on the printer, the assumption being that the
final copy is a photo reduction of the printed copy. Thus, if photo
reduction halves linear dimensions, one prints with magnification 2.
If everything is done right, then after reduction, the letter appears at
its design size.
.pp
A 10 point design sized font printed at mag\%ni\%fi\%ca\%tion 2 is similar to
but not quite the same as a 20 point version of the same font.
For example, the serifs on a large point size are smaller than they would
be if strict linear magnification were used. Other proportions, e.g., of
x-height to cap-height and of width to height, are also
different. While many purists, Knuth
included, insist on using a different pattern for each design size,
many people accept magnification as yielding acceptable fonts at other
point sizes. If the unit of magnification is not too big the results
are acceptable even to many purists.
.Su "2.2\ \ \ Problems with bitmapped fonts."
A bitmap for a character is a rectangular array of bits covering the
so-called bounding box or frame that exactly contains a letter. Figure
1 shows a low resolution bit map for the letter \(lqN\(rq in a sans
serif font. The inked squares or pixels are denoted by \(lq1\(rq bits
and the uninked pixels are denoted by \(lq0\(rq bits.
.fs
.F+
figure fig1.ps
.F-
.ca "Figure 1"
.fe
The low resolution example of Figure 1 illustrates a major problem
with bitmapped fonts. Curved lines and straight lines that are neither
vertical nor horizontal cannot be represented exactly by a rectangular
pattern of pixels. One is forced to approximate them with rectangular
steps. At high resolution, e.g. above 1000 or so, the human eye cannot
see the steps, but at low resolution the steps are quite apparent.
Visible steps are called \(lqjaggies\(rq after the jagged edges.
.pp
Bitmaps for a font must be built for each design size, magnification,
and resolution. If the resolution is fixed, as is the case on most
printers, a bitmap must be built for each design size and
magnification. An attempt to use a given bitmap at a larger design
size or magnification by just enlarging the area of each dot yields a
bad case of jaggies.
.Su "2.3\ \ \ \*(MF and its environment."
.ft 1
\*(MF, a language for the specification of fonts or typefaces, has been
used to provide fonts for the \*(TX family of typesetting systems. A
\*(MF user writes a program for each letter or symbol of an alphabet.
These programs are different from the usual computer programs, because
they are essentially declarative rather than imperative, using an
algebraic language to describe the center stroke or edges of the characters. The
description of a letter in \*(MF is a set of equations describing the
strokes. When combined with parameters describing the pen shape and
size, one gets a full description of a letter. Sizes and shapes of pen
nibs can be varied in \*(MF and the characters can be built up in such
a way that the outlines of each stroke are precisely controlled. Herein
lies the advantage of \*(MF; a font is easily specified and variations
are obtained by varying parameters.
.pp
Currently, the program that converts a set of \*(MF font descriptions
into a bitmapped font translates the description of a letter combined
with a point size and a magnification into a bitmap. This bitmap can be
sent to the printer to get a letter on the page. Herein lies a
disadvantage of \*(MF; a bit map must be kept for each point size and
magnification, and this can require a lot of space.
.Su "2.4\ \ \ The \*(pS language."
The \*(pS language is an interpretive programming language with
graphics capabilities. \*(pS's extensive page description capabilities
are embedded into a general-purpose programming language framework. The
language includes a conventional set of data types such as numbers,
arrays, and strings, control primitives such as conditionals, loops and
procedures, and some unusual features such as dictionaries. In most
\*(pS fonts, each letter is described by an imperative program tracing
the outline of the letter. This tracing may include curves given as
\*(BZ curves, straight lines, arcs, etc. A \*(pS printer interprets
this outline program to draw and fill in the letters on the page. Some
consider the imperative nature of \*(pS to be a disadvantage in
comparison to \*(MF's declarative nature. The main advantage of \*(pS
relative to \*(MF is that one needs to keep only the outline. If, as in
the usual case, the outline is specified in terms of a fixed path
through Euclidean two-space, this outline may be scaled arbitrarily to
yield any magnification. The scaling is done by the \*(pS interpreter
at the printer. Thus the different magnifications do not require any
additional storage space. Actually, the outlines are kept as if they
were for the Adobe-standard 1000 dots
per emm, which at a design size of 10 points amounts to 7200 dpi.
Because a typical phototypesetter has a maximum resolution of
about 2500 dpi, the outlines are said to be arbitrarily
scaleable. If the outlines are kept, as are many \*(MF definitions, as
paths through points calculated by the outline program, then it is
possible to, say, make serifs grow more slowly than linearly. It would
then be possible to have one \*(pS font scaleable to all design sizes.
Generally, outline fonts are not written this way, so that strictly
speaking they are scaleable only to all magnifications.
.pp
In addition, the \*(pS language has a way to work with bitmapped fonts.
While the \*(pS printer can scale them before printing, the end result
is that each of the fixed number of dots in the bitmap is made larger
or smaller. Since the human will see larger dots as jagged lines, such
fonts are not really considered scaleable.
.Su "2.5\ \ \ \*(BZ curves."
Both \*(MF and \*(pS use \*(BZ cubics to specify curves. For the \*(BZ
form, four points are used, the start point, the end point, and two
control points, as shown in the top half of Figure 2.
The tangent vectors of the
endpoints are determined from the line segments \*(P1\*(P2 and
\*(P3\*(P4. The mathematical introduction of the \*(BZ form
when given four points \*(P1, \*(P2, \*(P3, and \*(P4 is
.sp
.in +.125i
$z(t)~=~(1-t) sup 3 "\*(P1" ~+~3t(t-1) sup 2 "\*(P2" ~+~3t sup 2 (1-t) "\*(P3" ~+~t sup 3 "\*(P4" ,$
.sp
.in -.125i
for $0~<=~t~<=~1$.
.pp
Two characteristics of the \*(BZ form tend to make it widely used in
graphics. First, by choosing the control points one can easily mold the
curve to a desired shape. Second, the four control points taken in another
order define a convex polygon, \*(P1 \*(P2 \*(P4 \*(P3 \*(P1 in this case,
the \fIconvex hull\fR\h'-.05m', which bounds the \*(BZ
curve. The convex hull is useful in clipping a curve against a window.
.pp
When a \*(MF user specifies a path, \*(MF creates a list of knots and
control points for the associated cubic spline curves.
If the user has not specified the control points explicitly, \*(MF
itself finds some for the splines of a curve, while \*(pS requires all
the four points to be explicitly given.
.fs
.F+
figure fig2.ps
.F-
.ca "Figure 2"
.fe
.su "3\ \ \ \*(MF to \*(pS compiler\(em why\ and\ how"
.ft 1
.PP
This section describes a major performance problem with \*(MF-generated
fonts that perhaps can be solved by translating them into \*(pS fonts.
The goals of this translation are established. Based on these goals, a
particular approach is adopted to engineer the software largely from
existing components.
.Su "3.1\ \ \ A problem with \*(MF-generated bitmapped fonts."
.ft 1
In \*(MF, one gets one bitmap per point size and magnification. The
size of these bitmaps grows as the square of product of the design size
and
the magnification and requires a large storage space. Files that are
sent to the printer will be large, especially if lots of different
point sizes or magnifications are used. In \*(pS with outline fonts,
there is one outline per character which can be scaled arbitrarily to
any magnification that might be needed. Moreover, \*(pS outline fonts
are generally more compact than bitmapped fonts. For example, an
enclosed rectangle is represented by its four corner points rather than
by all the bits enclosed by the rectangle.
.pp
Certainly the outline fonts are more easily scaled to other
magnifications. By scaling the bitmapped fonts downward, too much
information is lost, and scaling upward introduces the jaggies.
Moreover, the pixel array is device dependent; it is valid for output
devices of only one particular resolution and one choice of possible
data values per pixel. Scaleable fonts have a great advantage \(em you
need only one font description file for all magnifications of that font.
Actually, \*(pS outline fonts are more scaleable even than the \*(MF
originals for another reason. In\*(<,\*([.9\*(.]\*(>,
it is said, \(lqCaution:
before using this `\fBat\fR' feature (i.e. scaling downward or upward) you
should check to make sure that your typesetter supports the font at the
size in question; \*(TX will accept any \(L<desired size\(L> that is positive
and less than 2048 points, but the final output will not be right
unless the scaled font really is available on your printing
device.\(rq Getting \*(pS outline versions of \*(MF fonts is possible
since both are based on \*(BZ curves. Doing so makes fonts heretofore
available only on \*(TX and other DVI-based formatters available on
\fHditroff\fR and other formatters which have evolved to or have been
designed for use with \*(pS printers.
.Su "3.2\ \ \ Goals."
Based on the observations of Section 3.1,
the goal of this research is to produce a \*(MF to
\*(pS compiler, \fHmf2ps\fP. Its operational requirements are items 1
through 5:
.l1 1
.le
It must be possible to translate any legitimate \*(MF font definition
at any given design size into a \*(pS outline font.
.le
The resulting \*(pS outline font should be arbitrarily scaleable.
.le
The resulting fonts should look like the bitmapped fonts when printed
on the same printer.
.le
The resulting \*(pS outline font should be more compact \fIwhen sent to
the printer\fP than a \*(pS version of the \*(MF-generated bitmapped
font.
.e1
.sp .5v
The fourth requirement deserves a bit of explanation and qualification.
First note that what is compared is what is sent to the printer.
Certainly there are compressed versions of the bitmapped fonts that
reduce the disk storage requirements of the bitmapped fonts. However,
they must be uncompressed before sending them to most printers. It is the
printer's storage that is limited; generally disk space is in
abundance. However, since printers these days are general purpose
computers, what a printer accepts may in fact be a compression that it
has been programmed to undo.
.pp
Now for the case in which disk space is of concern, the comparison
should still be relative to printable versions. There exist algorithms,
e.g. that of Lempel and Ziv\*([.13\*(.]
that can be used to compress \*(pS outline fonts which are, after all,
just ASCII files. Therefore, in order not to have a contest between
compression algorithms, the uncompressed versions are compared. Furthermore,
in order not to have a contest between different kinds of printers that may
have differing font representations, \*(pS outline fonts are compared to
\*(pS bitmapped fonts. When
considering disk space, the fact that one bitmapped font is needed for
each magnification is taken into account. Thus, the interest is in
comparing the size of a scaleable outline font to the total storage for
the bitmapped fonts for all magnifications of a given design size.
.cl
.le
The resulting \*(pS outline font should be more compact than the total
of the sizes of the \*(pS versions of the \*(MF-generated bitmapped
fonts at each available magnification. Even this comparison is not
completely fair since only specific magnifications are provided, while
the \*(pS font is arbitrarily scaleable.
.dl
.sp .5v
.pp
Observe finally, that the comparison is against mag\%ni\%fi\%ca\%tions
of a single design size since purists would argue that there should
be a different outline font for each design size.
Since there are those that do not
require this purity, the various design sizes will be compared also.
.pp
The software engineering goal is item 6.
.cl
.le
\fHmf2ps\fP should be written as much as possible using the existing
\*(MF program both to save work and to ensure that all \*(MF-acceptable
font definitions are handled.
.dl
.sp .5v
The evaluation of the results will be
done relative to these goals.
.Su "3.3\ \ \ Previous attempts."
Leslie Carr wrote a collection of programs to produce \*(pS outline
fonts from \*(MF fonts in 1987. Carr's programs take as input the
\fIlog\fR output file of \*(MF which contains a description of all
the paths that \*(MF traces out in drawing a character.
.pp
Carr has problems of information loss as a result of not having entered
into the \*(MF program. This is the reason why Carr's characters are
poor looking. In\*(<,\*([.5\*(.]\*(>,
Carr observes, \(lqIn the \&\fCcmr10\fP font,
the \fIcrisp\fP pen has diameter zero, so serifs have square corners. In
the \&\fCcmtt10\fP font, \fIcrisp\fP is set to a larger value and the serifs
end in semicircles. Because the shape of the current pen can NOT be
taken into account in \*(pS, these differences in the characters shapes
will not be seen. This is a \fBfundamental\fR problem: given a path $p$
and a pen $q$ (whose shape is also an arbitrary path), \*(MF
effectively envelopes $p$ with respect to the shape of $q$; \*(pS can
do nothing other than stroke it to produce a line of constant width.
This incompatibility comes to light when the width of the pen is
significant to the shape of the character\(rq.
.pp
In order to avoid this problem, \fHmf2ps\fP finds the internally
generated envelope, which is used as the boundaries of the inked
region, and uses this envelope as the outline. It does not matter, then,
what the pen path and the pen shape are.
.pp
More recently, during the time that the work described herein was being
done, there were other efforts with similar goals. 
.pp
Doug Henderson\*([.6\*(.]
obtained outline font characters by modifying the \&\fCendchar\fP macro,
which is called for each character after the bitmap is generated, to take
the bitmap for the character and white out all but the bits on the edge.
The number of bits left on the edge is varied according to the resolution
of the bitmap. These outlines, being bitmapped, are just as unscaleable as
are the bitmaps for the filled-in characters.
.pp
Neil Raine and Graham Toal\*([.12\*(.]
have developed software that takes the bitmaps and rediscovers the
outlines by tracing the pixels. The outlines that are used as the basis
for \*(pS fonts are, for the most part, generated from bitmaps at 2400
dpi. They first generate RISC OS outline fonts which are screen fonts
for Acorn's Archimedes RISC computer. These are true scaleable
outlines. Then, these outlines are converted into \*(pS format. Toal
says that the the quality of the fonts produced is not too great at low
resolutions because of shortcomings in Adobe's rendering algorithm. He
adds that at 1200 dpi on a phototypesetter, they are indistinguishable
from \*(MF-generated bitmapped fonts. These authors suspect that
information that is critical for good appearance is lost when tracing
an outline on a bitmap generated from a mathematically described
envelope. Better results should be obtainable using the original
envelope.
.pp
John Hobby\*([.7\*(.]
has developed a program called MetaPost, which translates from an extension
of \*(MF into \*(pS cubic splines and commands.
His goal was to turn \*(MF into a system for
typesetting general graphics, including embedded text. His approach,
similar to ours, was to modify the \*(MF program into what he desired.
Befitting his more general goals, besides modifying the output, he has
added new commands to the input language. Moreover, his translation appears
to be a direct mapping from a \*(MF command sequence to a
\*(pS command sequence.
The result is a program more powerful than \fHmf2ps\fP.
It will be interesting to compare fonts produced by MetaPost and
\fHmf2ps\fP for appearance and performance.
.Su "3.4\ \ \ Methodology."
There are a number of ways to build the compiler. They include
.l1 1
.le
writing the whole compiler from \*(MF to \*(pS from scratch: This has
the advantage that one does not have to get into another person's
software, which is not very pleasant when the software is so big. On
the other hand, one would have to treat the whole job of turning
mathematical equations and any arbitrary pen shape into outlines.
.le
using the \*(MF output as was done by Leslie Carr\*([.5\*(.]:
This has the advantage of not requiring delving into another's
software, but the generated information is not enough if one wants no
deviations from the originals.
.le
getting into the \*(MF program: This requires examining the internals
of the \*(MF program. However, \*(MF and \*(pS make liberal use of
\*(BZ curves to describe non-circular curves. This fact makes the
translation process natural. For each specified path, \*(MF creates
control points for the associated cubic spline curves before
calculating the bit map. \*(MF also calculates the edge offsets implied
by the pen shape. Using the necessary information one can get a new set
of control points that define \*(BZ curves and lines that are needed to
build the \*(pS outline fonts.
.e1
.Su "3.5\ \ \ Software engineering of solution."
The idea is to split the \*(MF program into front end and back end. The
front end takes \*(MF specification of a character, magnification, and
point size, and produces the envelope, i.e., the outline of the
character, and the back end fills the envelope with bits. Taking the
existing front end and writing a new back end that converts the
envelope into a \*(pS specification of an outline is our method of
producing \fHmf2ps\fP. The bit-filling process will be done by the
printer.
.pp
In order to make \*(pS fonts arbitrarily scaleable, we have to ask the
\fHmf2ps\fP program to use a very large magnification, at least to try to
match the grid on which Adobe plots the points of its outlines. Adobe plots
its characters on a $1000~times~1000$ grid. Thus, Adobe's resolution is
1000 dpm (dots per em), which for design size 10 points is 7200 dpi.
Unfortunately, \*(MF, and thus \fHmf2ps\fP accepts resolutions only up to
3000 dpi. The results should be sufficient to produce fonts scaleable
up to magnification 7 or 8, which is a reasonable range in
typesetting.
.pp
This approach helps meet goal 6 because the original unchanged \*(MF
program is used. Thus, exactly the same input is accepted as in the
\*(MF program. There is some extra frosting obtained by the chosen
approach. The program for translating \*(MF to \*(pS is actually a bit
of an interactive environment because the new back end is an extension
of the existing one. This existing back-end provides an interpreter
that executes a \*(MF character definition and displays the defined
character on the screen. Figure 3
shows the dump of a screen containing several windows, one showing a
\*(MF definition, another showing the result of its interpretation, and
a third containing the \*(pS translation of the definition in the first
window. If software to interpret \*(pS definitions were available here,
a fourth window could be set up showing the result of interpreting the
translation of the third window. This would allow comparison of the
character's appearances without having to print them on paper.
.su "4\ \ \ The program"
.PP
In the following discussion, the \*(MF program is often called just
\(lq\*(MF\|\(rq.
.pp
The \*(MF program has been written so that it can be made to run
efficiently in a wide variety of operating environments by making
comparatively few changes. Such flexibility is possible because the
program is written in the \&\fCWEB\fR language which is at a higher level
than Pascal. The preprocessing step that converts \&\fCWEB\fR to Pascal
is able to introduce most of the necessary refinements. Semiautomatic
translation to other languages is also feasible, because the program
does not make extensive use of features that are peculiar to Pascal.
.pp
The program has two important variations: First, there is a long and slow
version called \s-1\fHINIMF\fR\s0, which does the extra calculations needed to
initialize \*(MF's internal tables. It has to be run first. It
initializes everything from scratch without reading a base file, and it
has the capability of dumping a base file. Secondly, there is a shorter and
faster production version called \s-1\fHVIRMF\fR\s0, which cuts the
initialization to a bare minimum. It is a virgin program that needs
to input a base file in order to get started. \s-1\fHVIRMF\fR\s0 typically has
more memory capacity than \s-1\fHINIMF\fR\s0, because it does not need the
space consumed by the dumping and undumping routines, etc.
.pp
In order to generate a compiler that translates \*(MF to \*(pS,
additional external procedures and functions were added to the \*(MF
program so that it runs exactly the same except that when it asks for
an output file name, it asks for an additional name, for the extra
output file that is to contain the \*(pS outlines. Those changes were
made on the Pascal version of the \s-1\fHVIRMF\fR\s0, and were compiled later
with \*(MF's library files.
(It was a complete oversight on our part not to have modified the
\&\fCWEB\fP version of \s-1\fHVIRMF\fP\s0.)
A few extra lines were added to the
macro file, \&\fCplain.mf\fR. These act as flags, identifying that
\*(MF has entered some of the macros.
.Su "4.1\ \ \ Basic idea."
To specify a character in \*(MF, one specifies either
an envelope (outline) or
a center-line path and a pen head.
For the former, \*(MF just fills the envelope with bits.
For the latter, \*(MF pretends that it is drawing the character
with a pen of specified
head shape following the specified path, i.e., the center of the head
stays on the path. The distance from the center-line path and outer
edge of ink trail left by pen head is called the \fIoffset\fR\h'-.1m'.
So, for a character, \*(MF follows the center-line path to calculate the path
of offset points, i.e., the envelope, and then fills the envelope with
bits.
In either case, \*(MF ends up filling an envelope.
.pp
We need to break \*(MF into a front end and a back end at the point
just after the envelope has been calculated. Then we provide a new back
end that converts the envelope into \*(pS instead of filling the
envelope with bits. Note then that the \*(pS printer will fill in the
envelope with bits as it fills the path obtained from the envelope.
.pp
The following subsections describe the data and the calculations
involved in the new back end.
.Su "4.2\ \ \ Data structures."
The main data structures that \*(MF keeps for a character are the
center-line path, the pen shape, and the envelope path. There are a few
operations that can be performed on paths, called transformations.
.SU "4.2.1\ \ \ \*(MF's path representation."
.ft 1
When a \*(MF user specifies a path, \*(MF creates a list of knots and
control points for the associated cubic spline curves. If the knots are
$z sub 0 ,~z sub 1 ,...,~z sub n$, there are control points $z sub k
sup +$ and $z sub k+1 sup -$ such that the cubic splines between the
knots $z sub k$ and $z sub {k+1}$ are defined by the \*(BZ formula
.sp
.in +.4375i
$z(t)~=~B(z sub k, z sub k sup + , z sub k+1 sup - , z sub k+1 ;t)$
.sp .2v
\h'\w'$z(t)~$'u'$=~(1~-~t) sup 3 z sub k ~+~ 3t(t~-~1) sup 2 z sub k sup +$
.sp .2v
\h'5P'$+~ 3t sup 2 (1~-~t)z sub k+1 sup - ~+~ t sup 3 z sub k+1$,
.sp
.in -.4375i
for $0~<=~t~<=~1$.
.pp
There is a 7-word node for each knot $z sub k$, containing one word of
control information and six words for the $x$ and $y$ coordinates of $z
sub k sup -$ and $z sub k$ and $z sub k sup +$. The control
information appears in the \fIleft_type\fR and \fIright_type\fR
fields and they specify properties of the curve as it enters and leaves
the knot. There is also a \fIlink\fR field, which points to the
following knot. Before the \*(BZ control points have been calculated,
the memory space they will ultimately occupy is taken up by information
that can be used to compute them. The \*(MF \fImake_choices\fR
procedure chooses angles and control points for the splines of a curve
when the user has not specified them explicitly.
.SU "4.2.2\ \ \ \*(MF's path transformation."
.ft 1
When \*(MF digitizes a path, it reduces the problem to the special case 
of paths that travel in the \fIfirst octant\fR directions; i.e., each
cubic $z(t)~=~(x(t),y(t))$ being digitized will have the property that
$0~<=~y prime (t)~<=~x prime (t)$. This assumption makes digitizing
simpler and faster than if the direction of motion has to be tested
repeatedly. When $z(t)$ is cubic, $x prime (t)$ and $y prime (t)$ are
quadratic, hence each of the four polynomials, $x prime (t)$, $y prime (t)$, $x
prime (t) - y prime (t)$, and $x prime (t) + y prime (t)$, crosses
through $0$ at most twice. If we subdivide the given cubic at these
places, we get at most nine subintervals. In each of these intervals
each of $x prime (t)$, $y prime (t)$, $x prime (t) - y prime (t)$, and
$x prime (t) + y prime (t)$ has a constant sign. The curve can be
transformed in each of these subintervals so that it travels entirely
in first octant directions, if we exchange $x$ and $- x$, $y$ and $-
y$, and $x$ and $y$ as necessary.
.Su "4.3\ \ \ Pens and envelopes."
There are two kinds of pen heads that may be used, polygonal and
elliptic. There are a number of trade-offs involved in their use. The
first subsection treats the case of an $n$-vertex polygonal pen shape
and the second treats the case of an elliptical pen shape. Both
describe the influence of pen shape on the envelope of the font.
.SU "4.3.1\ \ \ Polygonal pens."
Suppose that the vertices of a polygon are $w sub 0 ,~w sub 1 ,...,~w
sub n-1 , ~w sub n ~=~ w sub 0$ in counterclockwise order. A convexity
condition requires that each vertex turns left when one proceeds from
$w sub 0$ to $w sub 1$ $...$ to $w sub n$. The envelope is obtained if we
offset a given curve $z(t)$ by $w sub k$ when that curve is traveling
in a direction $z prime (t)$ lying between the directions $w sub k - w
sub k-1$ and $w sub k+1 - w sub k$. At times $t$ when the curve
direction $z prime (t)$ increases past $w sub k+1 - w sub k$, \*(MF
temporarily stops plotting the offset curve and inserts a straight line
from $z(t) + w sub k$ to $z(t) + w sub k+1$; notice that this straight
line is tangent to the offset curve. Similarly, when the curve
direction decreases past $w sub k - w sub k-1$, \*(MF stops plotting
and inserts a straight line from $z(t) + w sub k$ to $z(t) + w sub
k-1$; the latter line is actually a retrograde step, which will not be
part of the final envelope under \*(MF's assumptions. The result of
this consideration is a continuous path that consists of alternating
curves and straight line segments. The segments are usually so short,
in practice, that they blend with the curves.
.SU "4.3.2\ \ \ Elliptical pens."
To get the envelope of a cyclic path with respect to an ellipse, \*(MF
calculates the envelope with respect to a polygonal approximation to
the ellipse. This has two important advantages over trying to obtain
the exact envelope:
.l1 1
.le
Polygonal envelopes give better results, because the polygon has
been designed to counteract problems that arise from digitization; the
polygon includes sub-pixel corrections to an exact ellipse that make
the results essentially independent of where the path falls on the
raster.
.le
Polygonal envelopes of cubic splines are cubic splines. Hence it is
not necessary to introduce completely different routines. By contrast,
exact envelopes of cubic splines with respect to ellipses are
complicated curves, more difficult to plot than cubics.
.e1
.Su "4.4\ \ \ Taking out data."
After \*(MF has calculated the paths and the offsets, it is ready to
send the values to the \fImake_moves\fR procedure which generates
discrete moves for any four points that represent a \*(BZ curve. This
is done for each one of the cyclic paths from which the letter is built.
When the offsets are zero, this is done by the \fIfill_spec\fR
procedure. Otherwise this is done by the \fIfill_envelope\fR
procedure. In the latter case, the line segments, which were discussed
earlier, should be taken out also in order to get smooth connections
between the different curves that the cyclic path is built from.
Because \*(pS describes any shape in terms of curves and lines, this is
the point to take advantage of \*(MF's calculations, i.e., when \*(MF
calls the \fImake_moves\fR procedure and when \*(MF draws line
segments for offset corrections.
.Su "4.5\ \ \ Processing the data."
The generated data are not ready yet to be used. First, we should
unskew, i.e., transform from the first octant back to the original, the
paths according to the octant that the paths were traveled in before
they were skewed. This unskewing is done by taking out the octant
number at the moment that the \fImake_moves\fR procedure is called
and then using \*(MF's \fIunskew\fR procedure that sets values $x
prime$ and $y prime$ to the original coordinate values of a point,
given an octant code and coordinates $(x,y)$ after they have been
mapped into the first octant and skewed; the new values are sent to the
\fIsend_p_s\fR procedure. This procedure has eight formal parameters
that are all used when sending a curve. When sending a line,
only four parameters are used, two to denote the start point and two to
denote the end point; the remaining four parameters are sent as zeros
so \fIsend_p_s\fR can distinguish whether a line was sent or a curve.
In the next step, \fIsend_p_s\fR unscales the numbers because \*(MF
works with units of scaled points, of which there are $2 sup 16$ in an
ordinary point. While unscaling, the values are
transformed in order to send them to the \*(pS dictionary
\&\fCFontBBox\fP command. After this pre-processing,
the data are sent to a temporary file.
.SU "4.5.1\ \ \ Getting more information."
When \*(MF calls the \fImake_moves\fR procedure, it does not have any
information on the role that this path is going to play, whether the
current cyclic path is going to be \fIfilled\fP or whether it will act as
a boundary of a region to be \fIerased\fP.
.pp
In order to distinguish between the cases, more information has to be
taken. This is done by copying the \&\fCplain.mf\fR file into a new
file named \&\fCmyplain.mf\fR and adding a few lines to it. The
additional code was added in order to identify \*(MF's use of the
macros. \*(MF uses the variables for date only once, when the program
is started, so it was decided to use them in the rest of the
program.
The \&\fCyear\fR is changed to $-1$ when \*(MF's \&\fCpen_stroke\fR
macro is applied on a cyclic path, i.e., in the characters such as
\(lqo\(rq, \(lqO\(rq, and \(lqQ\(rq, and to $-2$ when the \&\fCerase\fR
macro is called. The \&\fCmonth\fR is changed when the \&\fCfill\fR
macro is called. There are three kinds of paths:
.l1 1
.le
paths to be \fIfilled\fP are processed using the \*(pS \&\fCfill\fR
command.
.le
paths to be \fIstroked\fP are processed using the \*(pS \&\fCeofill\fR
command.
.le
paths to be \fIerased\fP are processed using specialized procedures
which will be discussed later.
.e1
.sp .5v
.pp
A letter cannot always be treated as one unit by means of the
\&\fCfill\fR and \&\fCeofill\fR commands. For instance, the letter
\(lqQ\(rq is built of two different paths, the first of which is
stroked and the second of which is filled. Generating the letter
using the \*(pS \&\fCeofill\fR command causes a hole in the image (see
Figure 4).
.fs
.F+
figure fig4.ps
.F-
.ca "Figure 4"
.fe
So while generating a letter, fill mode can be changed for each cyclic
path. Moreover, when generating a letter whose paths should be filled,
it is not always possible to use just one \&\fCfill\fR command (see
Figure 5).
.fs
.F+
figure fig5.ps
.F-
.ca "Figure 5"
.fe
When a \*(pS \&\fCfill\fR command is applied to a path that is composed
of more than one subpath, say two for the sake of simplicity, and one
subpath is inside the other and is drawn in a direction opposite to the
external one, the internal path is considered a hole and is not filled
(see Figure 6).
.fs
.F+
figure fig6.ps
.F-
.ca "Figure 6"
.fe
So, if several paths are to be filled in this manner, the description
of each one of them should be ended with the \&\fCfill\fR command.
There is one more benefit to using this strategy: The \*(pS \fCcurrent
path\fR stack becomes empty after encountering any kind of \&\fCfill\fR
command. Therefore, using the \&\fCfill\fR command after each path can
help avoid \&\fCstack overflow error\fRs if all paths together are too
long.
.SU "4.5.2\ \ \ Treating erasing paths."
There are three methods of handling the problem of paths that should be
erased by \fHmf2ps\fP itself:
.l1 1
.le
filling with white: Because erasing paths are built in order to erase
an existing filled area and \*(pS overlaps paths (i.e., a region is
shown in the color that was drawn last), erasing paths can be
implemented by filling those paths with white. This solution is the
easiest, but it works only if the background is white and the letter is
drawn in some level of gray. If one wants to draw a letter with
background other than white, the resulting appearance will not be correct.
.pp
.le
calculating new paths resulting from subtracting the erasing paths from
the previous filled paths: Such a solution can be global. However, it
costs a lot in terms of processing time and accuracy, because paths are
given implicitly by four points, and in order to calculate the new
paths, one should find the intersection points of \*(BZ curves, i.e.,
to find points that lie on both \*(BZ curves, and then calculate new
curves, which are difficult to calculate from those points.
.pp
.le
using the \*(pS \&\fCeoclip\fR command: Be\%cause the letters are bounded
in a $1000~times 1000$ box, a primary square path whose segments are
$1000$ units long should be declared and after it all the erasing paths
should be listed. After relocating the erasing paths we are ready to
declare \&\fCeoclip\fR, which means that the clipping path is the
external primary one and the internal paths, the erasing paths, are
holes. This is an elegant solution that uses the power of the language
and is available in simple situations in which there is no intersection
between the erasing paths (see Figure 7).
If there were intersections, a little more
sophisticated use of the \&\fCeoclip\fR command would be needed. Relocation
of the erasing paths is done by the procedure \&\fCdoarrange\fR.
.e1
.fs
.F+
figure fig7.ps
.F-
.ca "Figure 7"
.fe
.pp
There are other problems caused by the erasing paths. Because the
erasing paths have segments in common with paths to be filled, \*(pS must
decide whether the common segments are in the clipping path or not.
\*(pS does not seem to have a consistent policy on that and it seems to
be that the decision is taken arbitrarily (see Figure 8).
.fs
.F+
figure fig8.ps
.F-
.ca "Figure 8"
.fe
An attempt to resolve the clipping path problem led to the first author
sending the following electronic message (obviously, not as nicely
formatted as herein) to Glenn Reid of Adobe Systems, Inc.
.qb
.nf
From simon Tue Mar 21 13:22:32 1989
To: greid@adobe.com
Subject: Problem in PostScript
.fi
.sp
Dear Mr. Reid
.sp
I have got a problem in understanding the PostScript
policy in determining \(lqwhat is in the clipping path\(rq.
I think there is a problem in the boundaries.
Here is an example that shows that problem:
.es
.ft C
 gsave
 initclip
 newpath

 0 0 moveto
 0 1000 lineto
 1000 1000 lineto
 1000 0 lineto
 0 0 lineto

 300 100 moveto
 700 100 lineto
 700 300 lineto
 300 300 lineto
 300 100 lineto

 700 900 moveto
 300 900 lineto
 300 700 lineto
 700 700 lineto
 700 900 lineto

 eoclip

 newpath
 100 100 moveto
 900 100 lineto
 900 900 lineto
 100 900 lineto
 100 100 lineto
 fill
 grestore
.ee
.ft R
As you see, the problem is that on top of the shape, the line
which belongs to the upper \(lqhole\(rq in the clipping path and to the
current path ( to be filled ) is drawn, and on bottom of the
shape it is not.
.sp
This is happening both on the Apple Laser printer and on the
QMS-80.
.sp
I would be glad to have a reply from you.
.sp
.nf
Thanks in advance
Shimon Yanai
C.S Dep.
Technion
.fi
.qe
What Mr. Reid saw when he printed the \*(pS commands contained in the
message is reproduced in Figure 9.
.fs
.F+
figure fig9.ps
.F-
.ca "Figure 9"
.fe
Mr. Reid replied with the following:
.qb
.nf
From: greid@adobe.com (Glenn Reid)
To: Shimon Yanai <simon@techunix>
Cc: greid@adobe.com
Subject: Re: Problem in PostScript
In-Reply-To: Your message of Wed, 22 Mar 89 ...
Date: Wed, 22 Mar 89 11:41:35 PST
.fi
.sp
The problem is that the path you are filling falls exactly on the edge
of the clipping path. This produces a zero-width area to fill, and
unfortunately it sometimes fills and sometimes does not with the
current fill algorithm. I believe that it is related to the direction
of the paths; if the paths are going in opposite directions along the
same line, it will fill with a one-pixel area, but if they are going in
the same direction, it will not fill.
I believe this has been fixed to be more consistent in Display
PostScript, for what it's worth.
.sp
Glenn Reid
.br
Adobe Systems
.qe
.pp
The idea of using opposite directions had been checked before sending
the letter, so the problem had to be solved within the back end of
\fHmf2ps\fP. The
erasing paths near the top of the letter had their $y$ coordinates
increased by 0.8 points, and those near the bottom had their $y$
coordinates decreased by the same amount. This shift is invisible to
the human eye because the font definitions are in terms of hundreds of
points (see Figure 10). This solution was designed to work with most
existing \*(MF fonts. It is possible that there will be fonts that are not
treated well by this solution.
.fs
.F+
figure fig10.ps
.F-
.ca "Figure 10"
.fe
.Su "4.6\ \ \ Optimization."
Optimization is done in order to make the description of the fonts
shorter and to save work in the \*(pS interpreter. This is done in
three ways:
.l1 1
.le
not printing lines with length zero. As was said earlier, the \*(MF
program prints lines to connect offset points. There are times that
after rounding or truncating the output data, the start point and the
end point are equal. In such cases, the lines are eliminated.
.le
checking if the \*(BZ curve acts as a line. From the definition of the
\*(BZ curve, it is known that if the two control points lie on the line
that connects the start point and the end point, the curve is of degree
one. In such cases \fHmf2ps\fP generates a command to print a line from
the start point to the end point, thus saving space and avoiding
redundant calculations for the \*(pS interpreter.
.le
checking if a series of consecutive line segments are in the same line.
This is done by storing the segments in a buffer and checking whether a
new segment is collinear with the last stored.
.e1
.Su "4.7\ \ \ Changed or added routines."
The following is a list of routines that were changed or added in order
to build \fHmf2ps\fP from \*(MF.
.in +1P
.LE
\fIprintchar\fP was modified to get character names.
.LE
\fIfixdateandtime\fP was modified to initialize variables that were used as flags in the macros.
.LE
\fIfillspec\fP was modified to send out data on splines.
.LE
\fIskewlineedges\fP was modified to send out offset lines.
.LE
\fIdualmoves\fP was modified to send out offset lines.
.LE
\fIfillenvelope\fP was modified to send out data on splines.
.LE
\fIdostatement\fP was modified to identify tokens that are strings.
.LE
\fImain\fP was modified to call the \fHmf2ps\fP procedure in the beginning and ending of the program.
.LE
\fIsendcurve\fP was added to unskew spline values and to send them to the next process.
.LE
\fIsendline\fP was added to unskew line values and to send them to the next process.
.LE
\fIok\fP was added to check if two lines are collinear.
.LE
\fIrestore\fP was added to restore the parameters of the last line.
.LE
\fIrecall\fP was added to recall values from the buffer.
.LE
\fIus\fP was added to convert the \*(MF scale so that a letter would fit the
Adobe standard $1000~times~1000$ bounding box.
.LE
\fIsend_p_s\fP was added to create a \*(pS file of lines and curves.
.LE
\fImakemoves\fP was modified to send out spline data.
.LE
\fIdump\fP was added to append information from the file named \&\fCf\fP to the file named \&\fCg\fP.
.LE
\fIcheckerase\fP was added to identify the file that contains \(lqerase\(rq commands, and their position within the file.
.LE
\fIdoarrange\fP was added to put erasing paths at the beginning of the file.
.LE
\fIprint_start\fP was added to signal the beginning of a new cyclic path to be processed.
.LE
\fIprint_end\fP was added to signal the end of the current cyclic path.
.LE
\fIinit_ps\fP was added to make initializations.
.LE
\fImakenewdef\fP was added to make initializations when more than one character
occurs in the input.
.LE
\fIcloseolddef\fP was added to close the last definition.
.LE
\fItini_ps\fP was added to handle the ending of the process.
.LE
\fIauxprintchar\fP was added to print characters.
.LE
\fIauxprint\fP was added to print strings.
.in -1P
.su "5\ \ \ Operation of \fHmf2ps\fP in a \fHU\s-2NIX\s0\fP environment"
.ft 1
.PP
When invoked,
\fHmf2ps\fP
first asks for an output file name. For the example this file is called
\&\fCex1\fP. \fHmf2ps\fP then asks,
.ES
.fi
.na
\(lq\&\fCAre you creating the whole dictionary (y/n)?\fP\(rq.
.EE
.ad
If the answer is other than \(lq\&\fCy\fP\(rq
or \(lq\&\fCY\fP\(rq, it is considered \(lq\&\fCno\fP\(rq. If the
answer is \(lq\&\fCy\fP\(rq or \(lq\&\fCY\fP\(rq, then the whole
dictionary is created. This means that \fHmf2ps\fP creates a \*(pS
dictionary that includes entries for all the characters that are in
the input, e.g., \&\fCcmr10\fP set. This dictionary needs additional
definitions such as \fIleft side bearing, width, bounding box\fP, etc.
These definitions need information on character features that must be
calculated within the program. Otherwise, the whole dictionary is not
created and the program treats the input as a single character
definition that is to be translated into a \*(pS outline definition.
After \fHmf2ps\fP prompts \(lq\&\fC**\fP\(rq, we are in the \*(MF
environment. Now the user inputs
.ES
\s-1\\mode=hires;\\nodisplays;\\input cmr10;\(cr\s0
.EE
After \fHmf2ps\fP has finished, the resulting \*(pS font dictionary can
be used to print text. In order to print text, the font dictionary
should be installed in some formatter's font source directory, and then
it can be loaded through the formatter's commands. The dictionary
followed by appropriate \fHshow\fP and \fHshowpage\fP commands can also
be sent directly to the printer.
.su "6\ \ \ Evaluation of results"
.PP
This section evaluates the \fHmf2ps\fP program relative to goals
established in section 3.2. The program was produced as a variation of
\*(MF and it accepts any \*(MF font definition and produces a \*(pS
outline font scaleable up to magnification 8, or to point size 80 if
you are not a purist. Thus goals 6 and 1 have been entirely met and
goal 2 is partially met. To meet goal 2 fully the program must be
modified to allow large enough arrays to handle magnifications up to
7200; this is left to future work.
.pp
It remains to evaluate the appearance and sizes of the outline fonts
relative to the bitmapped fonts to see if goals 3, 4, and 5 have been
met.
.Su "6.1\ \ \ Appearance."
In order to compare appearances, the outline font (Sub\%sub\%fi\%gure P)
and and the 300 dpi bitmapped font (Sub\%sub\%fi\%gure M) generated from
the same \*(MF definition are used to
print similar sentences at one, two, or three different sizes or
magnifications on three devices of differing resolutions.
The sentences are printed in the \&\fCcmr\fP (Sub\%fi\%gure R),
\&\fCcmtt\fP (Sub\%fi\%gure T), and \&\fClasy\fP (Sub\%fi\%gure S) typefaces.
The bitmapped fonts may be printed at design sizes 7, 8, 10, or 12, and
the outline fonts may be printed at magnifications .7, .8, 1.0, or 1.2.
Finally, the three devices are the 300 dpi LaserWriterII (Figure
11-LW300), the 600 dpi Varityper (Figure 11-VT600), and the 1270 dpi
Linotronic 300 (Figure 11-LT1270). The bitmapped font examples are
formatted with \*(TX while the outline font examples are hand-coded \*(pS
files sent directly to the printer. Since the
formatter with which this paper is printed can use arbitrary \*(pS
fonts, half of the examples could have been done in-line without
pasting in. However, for fairness in the comparison, all examples were
cut out and pasted in.
.pp
There are visible differences due to differences in the formatting
software. \*(TX squeezes the letters closer together than does the \*(pS
engine. Moreover, the interword space is constant in the \*(pS
dictionary but is varied by \*(TX according to the line structure.
These differences are not the differences that are at issue here.
.pp
On the 300 dpi device, the characters from the bitmapped fonts print thinner
than are those of the outline fonts. However, the edges of both sets are
equally smooth or jagged as the case may be in all sizes. Overall, then,
the appearance of the characters of the bitmapped fonts is crisper than
that of the outline fonts.
On the higher resolution devices,
the thicknesses of the characters are closer to being
equal at all sizes. Thus, the \*(MF program does a better job of building a
correctly sized bitmap at 300 dpi than does the 300 dpi \*(pS engine of the
LaserWriterII. The latter seems to round up too much. However, both
seem to get the edges equally smooth even at low sizes and low resolutions.
.pp
At the two higher resolutions, the outline fonts are significantly better
than the outline fonts at lower resolutions and are significantly better
than the bitmapped fonts at the same resolution of printing. However, this
latter is true because the bitmapped fonts were generated by the \*(MF
program specifically to be printed at 300 dpi.
When a 300-dpi bitmap is printed with no scaling at 600 or 1270 dpi, it
remains a 300-dpi bitmap. As expected, the 300-dpi bitmapped fonts print better
at 300 dpi than they do at the two higher resolutions.
.pp
The generated outlines are not fine-tuned for printing at low resolutions,
such as 300 dpi,
as are the \*(MF-generated bitmaps. It might be useful to make use of
the \*(pS facilities for hinting to improve the appearance of the
characters printed from the outlines at low resolutions.
.pp
Figure 12 shows samples of similar sentences printed on the same three
devices using the standard Helvetica, Times
Roman, and Courier \*(pS outline fonts built into most \*(pS-executing
laser printers.
It appears to these authors that the standard \*(pS fonts are
significantly better than those generated from \*(MF fonts. However,
this is not surprising. Adobe uses a grid of $1000~times~1000$ for its
character definitions, resulting in a resolution of 7200 dpi for characters
printed at point size 10.
Because of size limitations of the
\*(MF program the \*(MF outline fonts are using a resolution of 3,000
points per inch. However, when using the letters in small sizes such as
from 10 to 70,
quality differences are hardly visible especially when working
with printers that have a resolution of 300 points per inch such as the
Apple LaserWriter.
Moreover, Adobe makes liberal use of hinting to
improve the appearance of its fonts at low resolutions.
We completely ignored hinting, as we did not see any way to
automatically generate the hints.
.Su "6.2\ \ \ Sizes of fonts."
Recall that it is necessary to compare the size of the \*(pS outline
font for a particular \*(MF definition to the sizes of the bitmapped
fonts in \*(pS fonts for the individual and all magnifications.
.pp
This comparison is made in this section for the \&\fCcmr10\fP font at the
standard set of six magnifications 1, 1.095, 1.2, 1.44, 1.728, and 2.07
(which are approximations of 1.2 raised to the powers 0, .5, 1, 2, 3,
and 4, respectively). In addition, as a gesture to those who are not
purists and accept magnifications of the 10 point design size as
different point sizes, the comparison includes the \&\fCcmr\fP font at
point size 5, 6, 7, 8, 9, 10, 12, and 17, the standard eight design
sizes maintained for use with \*(TX.
.pp
Table 1 shows the sizes in bytes. Thus it is clear that the
\*(pS outline font is bigger than any bitmapped font and that goal 4
fails. Moreover, it is clear that the outline font is bigger than the
sum over all magnifications of one design size and than the sum over
all standard design sizes. Thus goal 5 fails. In fact, this failure is the
reason that the samples of Figure 11 involve only upper case letters. Samples
with complete fonts with both cases often overloaded the printer available
to the students at the time this work was done.
.TS
center;
l r l r l.
Font	Design	Magni-	Bitmap	Outlines
	size	fication	(size in	(size in
			bytes)	bytes)
_
\fCcmr\fP	10	1.0	22,812	245,000
\ \ "	10	1.095	24,231	\ \ \ \ "
\ \ "	10	1.2	26,044	\ \ \ \ "
\ \ "	10	1.44	31,892	\ \ \ \ "
\ \ "	10	1.728	39,614	\ \ \ \ "
\ \ "	10	2.07	50,578	\ \ \ \ "
\fCcmr\fP	5	1.0	16,729	\ \ \ \ "
\ \ "	6	1.0	17,757	\ \ \ \ "
\ \ "	7	1.0	18,820	\ \ \ \ "
\ \ "	8	1.0	20,041	\ \ \ \ "
\ \ "	9	1.0	21,580	\ \ \ \ "
\ \ "	12	1.0	25,658	\ \ \ \ "
\ \ "	17	1.0	37,140	\ \ \ \ "
_
Total			352,896	245,000
.TE "Table 1"
.br
.RT
.pp
However, do note that the outline font is smaller than the sum over all
design sizes and magnifications thereof.
.pp
So in terms of disk space for the non-purists, the outline font
represents a savings. Again notice that not all magnifications of the
bitmapped fonts are maintained and the outline font is arbitrarily
scaleable. Moreover, as the magnification grows the size of the bitmap
grows even more rapidly.
.pp
The disappointment with respect to saving printer and disk memory says
that it is important to spend more effort to optimize the outline
font.
.pp
All is not lost, though! As this paper was being prepared for publication
in \*(TB,
one reviewer, Nelson Beebe, pointed out something that we can only kick
ourselves for not noticing. The \*(pS outline fonts that are generated by
\fHmf2ps\fP are horrendously wasteful in space. They use original, built-in
command names and absolute coordinates. A significant reduction in size can
be obtained by definition and use in the outlines of single-character
command names, e.g., \(lq\fCM\fP\(rq for \(lq\fCmoveto\fP\(rq, and by use
of relative versions of these commands with operands of fewer digits after
the initial absolute \&\fCmoveto\fP of any character. A simple filter was
written to obtain new compressed versions of the \*(pS outline fonts. The
appearances of the output when printing with these new versions is
unchanged, but what is sent to the printer is significantly smaller, about
37.7% smaller. The reduction on a per-letter basis is about 45%.
Table 2 shows the information of Table 1 for the new versions of the
outline fonts.
.TS
center;
l r l r l.
Font	Design	Magni-	Bitmap	Outlines
	size	fication	(size in	(size in
			bytes)	bytes)
_
\fCcmr\fP	10	1.0	22,812	152,670
\ \ "	10	1.095	24,231	\ \ \ \ "
\ \ "	10	1.2	26,044	\ \ \ \ "
\ \ "	10	1.44	31,892	\ \ \ \ "
\ \ "	10	1.728	39,614	\ \ \ \ "
\ \ "	10	2.07	50,578	\ \ \ \ "
\fCcmr\fP	5	1.0	16,729	\ \ \ \ "
\ \ "	6	1.0	17,757	\ \ \ \ "
\ \ "	7	1.0	18,820	\ \ \ \ "
\ \ "	8	1.0	20,041	\ \ \ \ "
\ \ "	9	1.0	21,580	\ \ \ \ "
\ \ "	12	1.0	25,658	\ \ \ \ "
\ \ "	17	1.0	37,140	\ \ \ \ "
_
Total			352,896	152,670
.TE "Table 2"
.br
.RT
.pp
There are still better compressions that can be achieved. According to
Beebe\*(<,\*([.4\*(.]\*(>,
Toal and Raine's outline representation of \&\fCcmr\fP at 10 points
requires about twice the space needed for bitmaps of the same; at 14 to
16 points, the outlines and the bitmaps occupy about the same amount of
space; above 16 points, the outlines are smaller than the bitmaps. It
is clear that better encodings exist than we explored and these must be
explored for any future version of \fHmf2ps\fP.
.pp
One such better encoding appears to be that used by Adobe for its own
proprietary fonts; fonts encoded this way have a FontType of 1.
User defined fonts have a FontType of 3. Beebe\*([.4\*(.]
says that type 1 fonts are handled with greater efficiency than type 3
fonts on most existing \*(pS interpreters, especially those that are based
on Adobe-licensed code.
Adobe has recently published specifications for the type 1 font encoding\*(<,\*([.2\*(.]\*(>,
thus allowing anyone to produced type 1 fonts. Beebe believes that the
market forces will drive other companies to encode their fonts as type 1.
Moreover, as more and more windowing systems based on \*(pS, e.g., NeWS
and NeXT, appear, the attraction of \*(pS outline fonts will increase, as
then the same font can be used for both printing and previewing. Thus, the
incentive will be to convert \*(MF fonts into type 1 \*(pS outline fonts.
.pp
Ultimately, the tradeoff is between the size of the font sent to the
printer, and the time it takes for the printer to decode the program
for the characters. However, with proper cacheing, a big enough cache,
and a not very fancy document, the decoding is done only once per
character for the document!
.su "7\ \ \ Future work"
.PP
For the future, there are a number of improvements that can be made.
Currently, each letter of the \*(pS outline fonts is described as a set
of cyclic paths. When all are filled or stroked, one gets the desired
letter. Some of those cyclic paths have a common boundary that is
inside the letter and is not necessary for the outline description of
the letter as a whole. Eliminating these paths and creating one
outline for the letter will save space. Today this can be done
manually, and is worth the effort because the translation process is
done only once. From that time on, the font is used the way it is.
.pp
As was demonstrated by Beebe's rescue of our result, closer attention
should be paid to obtaining more compact representations of character
outlines, representations for which \*(pS routines can be written to
interpret them into standard outline drawing commands.
Collapsing commands into single characters and using relative movements
saved significant amounts of space. Perhaps, even more dramatic savings can
be obtained by giving coordinates and distances in hexadecimal.
.pp
More effort can be spent on modifying the program in order to allow
magnifications up to 7200 points. Thus, no jaggies will be seen, as
occasionally happens when using higher magnifications, e.g., in our
translated fonts at magnification 8. This could be done by enlarging
the program arrays to handle characters based on 7200 points. A
sophisticated solution is required if one wants to save room while
compiling the input font. In such a case, any linear translation which
is done within the \*(pS program is with a factor less than 1.
.pp
\*(MF was changed for \*(TX 3.0. It is necessary to build a new version of
\fHmf2ps\fP based on this latest version of \*(MF. As the changes to the
\*(MF program deal mainly with ligatures and kerning, the calculation of
envelopes is probably not affected. Therefore, it is likely that
the portion of \*(MF up to the calculation of the envelope can still be
used as a front end for \fHmf2ps\fP with very little change in the
portion of the program we wrote.
.pp
Finally, it might be worthwhile, for the sake of portability to other
systems and enhanceability by \pother
.sp
humans, to rewrite or to write the next
version of \fHmf2ps\fP with \&\fCWEB\fP.
.su "Acknowledgments"
.PP
The authors thank the
\*(TB editors, and Nelson Beebe for their help, sharp comments, and
result-saving ideas.
Dealing with their comments made this a better paper.
.su "References"
.]<
.\"1985-P\s-2OST\s0S\s-2CRIP-3
.ds [F 1
.]-
.ds [L Adb85
.ds [K PostScript
.ds [T P\s-2OST\s0S\s-2CRIPT\s0 Language Reference Manual
.ds [I Adobe Systems Incorporated, Addison-Wesley
.ds [C Reading, MA
.ds [D 1985
.nr [T 0
.nr [A 0
.nr [O 0
.][ 2 book
.\"1990-Adobe-Type-1-Font-Fo-13
.ds [F 2
.]-
.ds [L Adb90
.ds [T Adobe Type 1 Font Format
.ds [I Adobe Systems, Inc.
.ds [D March, 1990
.ds [R Part No. LPS0064
.nr [T 0
.nr [A 0
.nr [O 0
.][ 4 tech-report
.\"Bechtolsheim.S.v.-1989-T\v'+.2m'\h'-.1m'E\h-6
.ds [F 3
.]-
.ds [L Bec89
.ds [A S.\ von\ Bechtolsheim
.ds [T The T\v'+.2m'\h'-.1m'E\h'-.1m'\v'-.2m'X PostScript Software Package
.ds [J TUGboat
.ds [V 10
.ds [N 1
.ds [P 25\(en27
.nr [P 0
.ds [D 1989
.nr [T 0
.nr [A 0
.nr [O 0
.][ 1 journal-article
.\"Beebe.N.-1990-12
.ds [F 4
.]-
.ds [L Bee90
.ds [A N.\ Beebe
.ds [O Private communication, via electronic mail
.ds [D 1990
.nr [T 0
.nr [A 0
.nr [O 0
.][ 0 other
.\"Carr.L.-1987-Of-Metafont-and-Post-8
.ds [F 5
.]-
.ds [L Car87
.ds [A L.\ Carr
.ds [T Of Metafont and PostScript
.ds [J T\h'-.1m'\v'+.2m'E\v'-.2m'Xniques
.ds [V 5
.ds [P 141\(en152
.nr [P 0
.ds [C Seattle, WA
.ds [D August, 1987
.nr [T 0
.nr [A 0
.nr [O 0
.][ 1 journal-article
.\"Henderson.D.-1989-Outline-fonts-with-\-9
.ds [F 6
.]-
.ds [L Hen89
.ds [A D.\ Henderson
.ds [T Outline fonts with \f(LGMETAFONT\fP
.ds [J TUGboat
.ds [V 10
.ds [N 1
.ds [P 36\(en38
.nr [P 0
.ds [D 1989
.nr [T 0
.nr [A 0
.nr [O 0
.][ 1 journal-article
.\"Hobby.J.D.-1989-\f(LGMETAFONT\fP-lik-11
.ds [F 7
.]-
.ds [L Hob89
.ds [A J.D.\ Hobby
.ds [T A \f(LGMETAFONT\fP-like System with PostScript Output
.ds [J TUGboat
.ds [V 10
.ds [N 4
.ds [P 505\(en512
.nr [P 0
.ds [D 1989
.nr [T 0
.nr [A 0
.nr [O 0
.][ 1 journal-article
.\"Kernighan.B.W.-1982-Typesetter-independe-5
.ds [F 8
.]-
.ds [L Ker82
.ds [A B.W.\ Kernighan
.ds [T A Typesetter-independent TROFF
.ds [R Computing Science Technical Report No. 97
.ds [I Bell Laboratories
.ds [C Murray Hill, NJ 07974
.ds [D March, 1982
.nr [T 0
.nr [A 0
.nr [O 0
.][ 4 tech-report
.\"Knuth.D.E.-1984-T\h'-.1m'\v'+.2m'E\v-4
.ds [F 9
.]-
.ds [L Knu84
.ds [K T\dE\u\(*xbook
.ds [A D.E.\ Knuth
.ds [T The T\h'-.1m'\v'+.2m'E\v'-.2m'Xbook
.ds [I Addison-Wesley
.ds [C Reading, MA
.ds [D 1984
.nr [T 0
.nr [A 0
.nr [O 0
.][ 2 book
.\"Knuth.D.E.-1986-\f(LGMETAFONT\fPbook-1
.ds [F 10
.]-
.ds [L Knu86
.ds [A D.E.\ Knuth
.ds [T The \f(LGMETAFONT\fPbook
.ds [I Addison-Wesley
.ds [C Reading, MA
.ds [D 1986
.nr [T 0
.nr [A 0
.nr [O 0
.][ 2 book
.\"Knuth.D.E.-1987-\f(LGMETAFONT\fP:-Th-2
.ds [F 11
.]-
.ds [L Knu87
.ds [A D.E.\ Knuth
.ds [T \f(LGMETAFONT\fP: The Program
.ds [I Addison-Wesley
.ds [C Reading, MA
.ds [D 1987
.nr [T 0
.nr [A 0
.nr [O 0
.][ 2 book
.\"Toal.G.-1990-10
.ds [F 12
.]-
.ds [L Toa90
.ds [A G.\ Toal
.ds [O Private communication, via electronic mail
.ds [D 1990
.nr [T 0
.nr [A 0
.nr [O 0
.][ 0 other
.\"Ziv.J.-1977-Universal-Algorithm--7
.ds [F 13
.]-
.ds [L ZL77
.ds [A J.\ Ziv
.as [A " and A.\ Lempel
.ds [T A Universal Algorithm for Sequential Data Compression
.ds [J IEEE Trans\%actions on Information Theory
.ds [V IT-23
.ds [V 3
.ds [P 337\(en343
.nr [P 0
.ds [D May, 1977
.nr [T 0
.nr [A 0
.nr [O 0
.][ 1 journal-article
.]>
.RT
.sp 2
.ta 1P +1P
.in +6P
.ps 9
.vs 11
.nf
.ti -1P
\(dm	Shimon Yanai
IBM Science and Technology
	Center
Technion City
.sp
Haifa 32000
Israel
yanai@israearn.bitnet
.sp
.ti -1P
\(dm	Daniel M. Berry
Computer Science
Technion
Haifa 32000
Israel
dberry@cs.technion.ac.il
.fi
.in -6P
.RT