summaryrefslogtreecommitdiff
path: root/fonts/utilities/mf2ps/doc/paper
diff options
context:
space:
mode:
authorNorbert Preining <norbert@preining.info>2019-09-02 13:46:59 +0900
committerNorbert Preining <norbert@preining.info>2019-09-02 13:46:59 +0900
commite0c6872cf40896c7be36b11dcc744620f10adf1d (patch)
tree60335e10d2f4354b0674ec22d7b53f0f8abee672 /fonts/utilities/mf2ps/doc/paper
Initial commit
Diffstat (limited to 'fonts/utilities/mf2ps/doc/paper')
-rw-r--r--fonts/utilities/mf2ps/doc/paper1755
1 files changed, 1755 insertions, 0 deletions
diff --git a/fonts/utilities/mf2ps/doc/paper b/fonts/utilities/mf2ps/doc/paper
new file mode 100644
index 0000000000..d93f426299
--- /dev/null
+++ b/fonts/utilities/mf2ps/doc/paper
@@ -0,0 +1,1755 @@
+.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
+.[
+knu86
+.]
+.[
+knu87
+.]
+program for a font all the necessary information in order to
+create an equivalent \*(pS
+.[
+PostScript language reference manual
+.]
+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
+.[
+knu84
+.]
+and other DVI-based formatters,
+available on \fHditroff\fR
+.[
+Ker82
+.]
+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
+.[
+bechtolsheim
+.]
+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,
+.[
+Knu84
+.]
+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
+.[
+lempel ziv
+.]
+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,
+.[
+Car87
+.]
+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
+.[
+henderson outline fonts
+.]
+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
+.[
+toal private
+.]
+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
+.[
+hobby postscript output system
+.]
+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:
+.[
+Carr
+.]
+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,
+.[
+beebe private
+.]
+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
+.[
+beebe private
+.]
+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,
+.[
+adobe type 1
+.]
+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"
+.[
+$LIST$
+.]
+.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