diff options
author | Norbert Preining <norbert@preining.info> | 2019-09-02 13:46:59 +0900 |
---|---|---|
committer | Norbert Preining <norbert@preining.info> | 2019-09-02 13:46:59 +0900 |
commit | e0c6872cf40896c7be36b11dcc744620f10adf1d (patch) | |
tree | 60335e10d2f4354b0674ec22d7b53f0f8abee672 /fonts/utilities/mf2ps/doc/paper |
Initial commit
Diffstat (limited to 'fonts/utilities/mf2ps/doc/paper')
-rw-r--r-- | fonts/utilities/mf2ps/doc/paper | 1755 |
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 |