.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