 |
Description  |
|
|
FIELD OF THE INVENTION
The device of this invention is a control device for high performance, high
quality display devices used in typesetters, image-setters, color
printers, laser printers and video displays. The device is preferably a
single chip. The control device is useful in interpreting font outlines,
including rendering hints, and translating hints and outlines to provide
rasterized bit maps of characters filled with black, white or other colors
or patterns.
BACKGROUND
Rendering an image on a raster display requires the formation of the raster
image at some point in the printing process. In the case of characters, a
raster bit map of each needed character can be stored in memory and then
simply copied from memory to a printer input buffer whenever that
character is required. A complete set of characters can be maintained in
memory, but this requires storing each particular character in every
needed point size and resolution, which can use up large quantities of
memory. Alternatively, a set of characters can be encoded in some way,
then converted into a bit map for a particular size character at a
particular resolution appropriate for a selected display device.
Characters which will be reused can be stored in cache memory to
facilitate faster printing. A typical printing job requires a full set of
lower case characters and many but not all capital letters at a single
size and resolution. Thus bit maps of each of these characters can be
generated and held in cache memory for the duration of the job, after
which the cache memory can be flushed and filled with characters needed
for the next job. Typical printer memory can accommodate a small number of
fonts, enough for a simple job. When a job calls for a large number of
fonts and/or point sizes, the capacity of cache memory may be exceeded,
requiring some character bit maps to be generated multiple times.
In a preferred embodiment, the device is used to convert PostScript.RTM.
Type 1 font outlines to bit maps. PostScript was developed by Adobe
Systems Inc. (hereinafter "Adobe"), the assignee of the subject invention.
The PostScript system was developed to communicate high-level graphic
information to digital laser printers. It is a flexible, compact and
powerful language for rendering characters from stored outline fonts, for
expressing graphic regions and for performing general programming tasks.
The preferred embodiment of the device of this invention is described in
the context of a PostScript printer, typesetter or image-setter.
The PostScript language, use and applications are thoroughly described in a
number of books published by Adobe, including POSTSCRIPT LANGUAGE
REFERENCE MANUAL (Second Edition, 1990) and POSTSCRIPT LANGUAGE PROGRAM
DESIGN (1988), each of which is incorporated herein by reference.
PostScript and related page description languages are useful with
typesetters, image-setters, color printers and high throughput printers as
well as high-resolution video or other display devices.
The present invention is useful in many currently available printing
environments. Outline fonts are used in conjunction with many typesetting
and printing combinations, using Apple.RTM. Macintosh.RTM., IBM.RTM. PC,
Sun.RTM. and other UNIX-based computers with one or more of several
marking (printing) or display devices. Current software includes Adobe's
PostScript and ATM.TM. software and hardware, and outline font programs
from Bitstream and Compugraphic. Page description languages used to
control printers include Adobe's PostScript language, Hewlett Packard's
PCL, Canon's LIPS, NEC's NPDL and other languages by Kyocera and Xerox.
Printers, video display and other such devices are sometimes called marking
devices or marking engines. A raster image processor (RIP) associated with
a marking engine converts input information and commands into a rasterized
(bit-mapped) region suitable for display on the associated output device.
Commercially available devices include the Apple LaserWriter.RTM., the
Linotronic.RTM. 100 and 300, the Adobe Atlas RIP, the Emerald RIP and
Hewlett-Packard DeskWriter.TM. and LaserJet.TM.. A marking engine
generally prints characters from stored bit maps by simply transferring
the pattern of bits from memory to the output device. This requires a bit
map of the character in the correct size and resolution.
The main advantage of outline fonts over bit mapped fonts is also the main
disadvantage. An outline font can be used to generate a bit map for a
character of any size from a single outline font. This provides
flexibility and compact storage, but costs time in preparing each required
bit map and incurs the added burden of ensuring that all bit map
renditions have aesthetic appeal. A bit mapped font can be specifically
edited to produce optimal results, but only for a specific size.
Additional sizes require additional bit maps. Bit mapped fonts have
traditionally enjoyed a speed advantage as well in that the bit map can be
printed directly. The trade-off is speed vs. storage capacity
requirements.
Essentially all programs using outline fonts must convert outline
information into a bit map before printing a character on a raster
printer. In a typical application, outlines are defined in a high
resolution coordinate system, generally called character space. In order
to print on a marking engine, the outline must be scaled to the required
size and mapped to a coordinate system appropriate for the marking engine.
The second coordinate space is generally called device space. The outline
in device space is filled with a series of pixels to approximate the
original outline. Characters may be adjusted or "hinted" in either
character space or device space to improve alignment of the final
character on the device space pixel grid.
Previous methods of converting character outlines to scaled character bit
maps were software based, which allowed flexibility but significantly
limited the speed at which character bit maps could be generated. The
limitations of software based renderers become particularly acute for
printing jobs which require a large number of different fonts or sizes,
since each character at each size in each font must be available to the
marking engine as a bit map. If a required character is not available in
the required size and font, then the corresponding outline must be
adjusted and converted. The limitations of software-based renderers are
also significant in printing foreign languages such as Japanese which use
a large number of characters with only limited repetition. Each time a
character bit map is not available in cache memory, a new bit map must be
generated. The bit map is usually stored, displacing a previously stored
character bit map if the available memory is full.
The problem of scaling outlines to produce bit maps has been a challenge
for many years. Many of the problems of analyzing outlines to produce bit
maps at an arbitrary scale have been solved in the Adobe ATM product. The
methods used in ATM are described in U.S. patent application Ser. Nos.
388,336 and 388,339 by Paxton et al. and U.S. patent application Ser. Nos.
539,222 and 552,788 by Byron et al., all assigned to Adobe and all
incorporated herein by reference. Some of the methods described therein,
such as analyzing outlines, identifying crosses and tracing paths have
been improved and form the basis for the present invention.
SUMMARY OF THE INVENTION
The present invention provides an apparatus and method for converting font
outlines to rasterized bit maps. One method for displaying rasterized
objects begins by accessing outline data, representing the object in a
first coordinate space, from computer memory or storage, then transforms
the outline data to corresponding data representing the object in a second
coordinate space, where regional relationship information in the outline
data in the first coordinate space is maintained in the second coordinate
space. This method includes: a) transforming the outline data of an object
from the representation in a first coordinate space to an initial
representation in a second coordinate space using a linear transformation;
b) applying the regional relationship data primarily to the representation
of the object in the second coordinate space to derive a non-linear
transformation expressed as a plurality of linear transformation matrices;
c) applying the non-linear transformation to outline data of the object in
first coordinate space to derive a second representation in second
coordinate space; d) converting the second representation of the outline
data of the object in the second coordinate space to raster data
describing the object in a form suitable for display; and e) storing the
raster data or displaying the object on a raster device.
From another perspective, the method scales an outline of an object in a
first coordinate space to a second coordinate space, after first accessing
outline information from storage. It then identifies the coordinates of
one or more select points at first coordinates in the second coordinate
space and compares those coordinates with desired or preselected
coordinates in the second coordinate space, measuring the difference in
the second coordinate space for the desired versus the actual coordinates.
The method then derives a non-linear transformation approximated by a
plurality of piecewise linear transformation matrices and applies an
appropriate linear transformation matrix to convert the outline from first
coordinate space directly to adjusted second coordinate space. Finally,
the method fills and stores the outline of the object in a form suitable
for display on a raster device and may display the outline.
To convert curved outlines to straight line segments suitable for
calculating the desired bit map, this invention includes a method using
four parallel adders for each dimension to perform a midpoint subdivision
and flatness test on a Bezier curve, which is defined by a first set of
control points. The control points are normalized using a first control
point as a reference. The Bezier curve is divided approximately at its
midpoint into second and third Bezier curves and is tested for flatness by
determining whether the distance between each internal control point and
the closest endpoint is within 1/3 the net endpoint-to-endpoint distance
plus a flatness factor, which, for example, might be one-half the width of
a pixel.
Once the outline has been reduced to a series of line segments, each line
segment is examined to see whether and where it crosses midlines between
pixel centers. Subdividing the pixel into subunits facilitates calculating
the final bit maps. The apparatus of the invention offers several
advantages over the prior art use of software by simplifying scaling and
subdividing line segments. The scaled segments which cross midlines are
tested to see in what subdivision of the pixel the cross occurred, and the
information about these crosses is compiled and correlated to effect
center fill of the outlined image, with both dropout and collision control
.
BRIEF DESCRIPTION OF THE DRAWINGS
FIG. 1 illustrates generally how the apparatus of this invention is
connected to other components of a graphics processing system.
FIG. 2 illustrates the major functional blocks of the coprocessor of the
invention.
FIG. 3 illustrates the major functional blocks of the micromachine.
FIGS. 4a and 4b illustrate transformation and mapping of coordinates.
FIG. 5 illustrates a flow chart showing the major steps of the current
method.
FIGS. 6a, 6b and 7 illustrate mapping a character into device space and
hinted device space.
FIGS. 8a and 8b illustrate representative Bezier curves and control points.
FIG. 9 illustrates subdividing a Bezier curve.
FIG. 10 illustrates the major functional blocks of the Bezier and state
machine.
FIGS. 11a and 11b illustrate the major steps in the method of subdividing
Bezier curves and calculating flatness.
FIG. 12 illustrates the major steps in the method of determining flatness.
FIG. 13 illustrates the major functional blocks of the Cscan unit.
FIG. 14 illustrates line generating DDAs.
FIGS. 15a and 15b illustrate crosses and subdivided pixels.
FIG. 16 illustrates a tile structure of pixels.
FIG. 17 illustrates a close up of the tile structure of FIG. 16.
FIGS. 18a, 18b, 18c and 18d illustrate details of dropout conditions.
FIG. 19 illustrates overtracing.
FIG. 20 illustrates a hardware fill and dropout detection circuit.
DETAILED DESCRIPTION OF THE INVENTION
The method and apparatus of this invention is particularly useful for
converting character outlines into bitmaps suitable for display on a
raster printing or display device. Outlines are generally defined at a
very high resolution in character space, frequently set to be 1000 pixels
high for each character. A character outline may be defined as a series of
lines and curves starting at a certain point on a pixel grid. See
generally ADOBE TYPE 1 FONT FORMAT (the "Black Book", 1990). The outline
generally must be transformed to display space, which generally has units
equal to the maximum resolution available on a selected display device.
The outline is scaled to a requested size, rendered as a bit map and
displayed on the selected display device.
The apparatus of this invention is designed for incorporation in a single
chip co-processor to be used in conjunction with a microprocessor in a
raster printer controller. For convenience, the preferred embodiment of
the present invention will be referred to as the font rendering
co-processor hereinafter called the "FRC". Referring to FIG. 1,
co-processor 10 is connected to main bus 16 of a printing or display
device, and thereby connected to controlling microprocessor 12 and system
memory 13. Co-processor 10 can be connected to and can use optional
private cache memory 11 or it can contain internal memory or use system
memory 13 for storing intermediate and final values. The apparatus may
include a display controller 15 (for video systems) and/or printer
interface 14 (for printer systems) to drive appropriate output devices,
which are well known to one skilled in the art.
Referring to FIG. 2, the main elements of co-processor 10 are micromachine
21, Bezier and stack machine 22 and Cscan unit 23, each of which are
connected via front channel bus 26 to each other and to front channel
interface 24, which in turn is connected to main bus 16 (shown in FIG. 1)
via line 30. Each of units 21, 22 and 23 also are connected via back
channel bus 27 to each other and to back channel interface 25, which in
turn is connected to optional private memory 11 (shown in FIG. 1) via line
31. Micromachine 21 and Bezier and stack machine 22 are connected together
through pipeline 28. Similarly, Bezier and stack machine 22 and Cscan unit
23 are connected together through pipeline 29. The operation of each unit
and the information passed along each pipeline are described in detail
below. Each of the buses and channels in FIG. 2 can be modified under
program control so that if one bus fails or does not function properly,
co-processor 10 can be reconfigured to use alternative interconnections
between the units.
The primary function of co-processor 10 is to intelligently render Type 1
font programs into device specific raster bit maps. The process of
rendering a Type 1 font program can be broken into three main areas: 1)
"hinted" transformation of Bezier control points; 2) linearization of a
character outline; and 3) intelligent filling of an outline. These steps
are implemented by micromachine 21, Bezier and stack machine 22 and CScan
unit 23.
Micromachine 21
Micromachine 21 implements the first step of interpreting the hints in a
Type 1 font program and applying those hints to convert a Type 1 font
program into a stream of intelligently transformed Bezier control points.
Hints, described in more detail below, are essentially directions from the
type designer encoded with a font or character that suggest, for example:
keeping certain features of equal or similar widths; setting x-heights to
fall within a certain range at large point sizes and within a more limited
range at smaller point sizes; and other factors or parameters that aid in
maintaining the general characteristics of a font over a wide range of
scaled sizes.
Referring to FIG. 3, the main components of micromachine 21, subsystem 110
and datapath 109, are shown. Subsystem 110 is a collection of logic
circuits which implement the first stage of hinting of the Type 1 font
program. Subsystem 110 includes sequencer 101 which controls and
coordinates the operations of subsystem 110. The major blocks of subsystem
110 are generally known and understood in the industry. Sequencer 101
performs the functions of a generic microprocessor, including branching,
branching to subroutines and branching on condition. The instructions for
sequencer 101 are contained in ROM 102, holding, for example, 896 words in
the preferred implementation where a microinstruction word is 58 bits
wide. Subsystem 110 includes RAM 103 holding, for example, 128 words of
microinstruction RAM, loadable under the control of a ROM-resident
program. Having RAM 103 on board and connected to sequencer 101 allows
sequencer 101 to execute software that does not have to be resident in
coprocessor 10 unless and until required. The complexity of the Type 1
programming language and its continuing evolution favor incorporating this
form of flexibility.
Sequencer 101 controls a series of logic elements and storage areas in
datapath 109 by exchanging control signals and flags over buses 104 and
105, respectively. Datapath 109 includes register file 106, StemList RAM
107 and functions block 108. Functions block 108 includes: logical
functions; one or more adder/subtractors; status flags; a 24.times.24 bit
multiplier and a fixed point divider. Functions block 108 carries out
renderer-specific operations, such as stem search operations such as Width
and Center, functions that have been specifically implemented in the FRC
to accelerate the rendering process.
To generate a bit map at a specific size, an outline must generally be
scaled to the correct size when displayed on the marking engine. In
addition, it is helpful to identify certain features and align similar
features on pixel boundaries with balanced feature dimensions. The method
to distort outlines should be simple and fast, preferably implemented both
in software and hardware.
Referring to FIG. 5, the general steps of transforming and adjusting an
outline are to first map at least some points to coordinates in device
space, identify any adjustments that need to be made, e.g. to keep stem
widths similar in size or to keep features aligned on pixel boundaries,
then derive a transformation matrix which will achieve the needed
distortions. The transformation matrix can then be applied to key points
in the character outline data to convert the outline into device space.
Prior art methods require two steps to achieve the transformation while
the current method saves a step. The scaled and adjusted outline is then
linearized, step 117, filled and rasterized, step 118, and prepared for
display on a raster device or printer. The current method calculates and
uses differences in device space, step 115, and then transforms original
outline data to hinted device space, step 116, neither of which has been
done before.
Transforming Outline Data--Background
Referring to FIGS. 4a, 4b, 6a, 6b and 7, the shape of a character can be
modified in one or more particular axes, for example, the X axis. It is
desirable to align certain features with pixel boundaries in display space
and to give features dimensions that include full pixels, when possible.
Referring to FIG. 6a, outline 121 shows a direct transformation of outline
data from character space to device space using only scaling. To display
this particular outline at the scaled point size requires making many
choices well known to one skilled in the art, for example whether or not
to display pixels 128 through 129, at (x,y) coordinates (3,1) through
(3,7), or pixel 130, at (12,13). Outline 121 includes a serif feature
including line segments 131 and 132 and this feature may not be
displayable below a certain point size or resolution. Referring to FIGS.
6B and 7, outline 121 has been distorted in hinted device space to outline
133, generally maintaining the dimensions of the original outline but
using whole pixels when possible. FIG. 7 is a compound drawing showing how
outline 133 is much easier to display on the pixel grid than is outline
121.
A typical character includes one or more regions, such as vertical or
horizontal stems, that should be balanced in any rendered bit map, both
within a character and between characters in a font. Examples of vertical
stems are the uprights in an "H", "B" or "P", e.g. stem 122 in FIG. 6a, as
well as the vertical extreme of a bowl of a "B" or "P", e.g. stem 124 in
FIG. 6a. Note a "B" has two bowls and thus may have two or three vertical
stems. Referring to FIG. 6a, stems 125 and 127 are horizontal stems. It is
generally desireable to balance both vertical and horizontal stems. A
lower case "o" in one type face may be even and circular and may call for
equal horizontal and vertical stems while another "o" may narrow at the
top and bottom and may call for equal horizontal stems with a different
dimension from equal vertical stems. Type designers and users also make
use of counters, which are generally specific spaces which affect the
shape or design of a character. Vertical counter 123 and horizontal
counter 126 are two examples.
A character can be divided into zones, each of which may include a vertical
stem or a space between or outside stems. Distorting each zone by
compression or expansion allows scaling the character while retaining
balance between various zones to produce a satisfactory rendering of the
character. A typical scaling process may include both compression and
expansion of zones. For example, if an important zone when scaled is less
than a pixel wide, it might be expanded to be one pixel wide (along with
corresponding zones of equal significance) and the intervening zones might
be compressed to balance the rendering. Referring to FIG. 4a, zones 1 and
3 represent important features, such as the uprights of an "H" or the
upright and bowl of a "P"), whereas zones 0, 2, and 4 are essentially
background and will be distorted as a result of any manipulations
performed on zones 1 and 3. Thus zones 1 and 3 can be considered
distortion zones and zones 0, 2 and 4 can be considered compensation
zones. Choosing which distortions to apply is based on type design
considerations and display characteristics such as display resolution and
character size. Methods of specifying distortions are known to those
skilled in the art. One method of specification is hinting, used in the
Type 1 font description and described in detail below.
Deriving the Transformation Matrix
Since the character outline will be transformed from character space to
device space to produce the device specific rendering, it seems logical to
use the same transformation to achieve any required distortion. A desired
series of distortions is implemented through a transformation matrix.
Transformation matrix operations can be separated into zonal areas using a
list of matrices, one for each zone. Together, these matrices represent a
piecewise transformation matrix for converting coordinates in character
space to coordinates in device space. Referring to FIG. 4a, zones 0, 1, 2,
3 and 4 correspond to matrices M0, M1, M2, M3, and M4 (the matrices are
not shown) and modified zones 0', 1', 2', 3, and 4, correspond to matrices
M0', M1', M2', M3', and M4'. Zones 0 and 4 extend to the end of the space
defined for the character. For all points between a zone's edges, the
corresponding matrix is applied to transform points in character space to
device space. Points that share edges with two zones can be assigned
randomly to one zone or the other or can be assigned to a zone by a rule,
for example, always use the zone to the left.
The transformation matrix for each zone is identical in the simple case of
no distortion. By way of example, zones 1 and 3 are distorted by
compressing them by 50% through a simple, linear transformation, the new
matrices for these zones would be:
M1'=M1*0.5
M3'=M3*0.5
where
MZ is the matrix for points in zone Z in a first coordinate space and
MZ' is the matrix for points in zone Z in a second coordinate space.
Referring to FIGS. 4a and 6a, zone 1 of FIG. 4a corresponds to stem 122,
the upright stem of the "P", zone 2 of FIG. 4a corresponds to counter 123,
zone 3 corresponds to stem 124, the bowl of the "P", and zones 0 and 4
correspond to the left and right bearings, respectively, that separate the
"P" from adjacent characters. The values in FIG. 4a are selected for
illustration and for ease of calculation and do not correspond exactly to
the dimensions of FIG. 6a.
Optimal rasterization often requires not only scaling, but also alignment
of zones to pixel columns in device space, for example, to fall on pixel
boundaries. For example, zones 1 and 3 can be compressed by 50% solely by
moving the rightmost edge. This is equivalent to shrinking the width of
each stroke in a character, effectively making a thinner character, known
to typographers as a lighter weight. This type of compression is often
necessary simply to set major stroke widths equal to an integral number of
pixels. Compare FIG. 6a, with unadjusted stroke widths of approximately
2.4 pixels, to FIG. 6b, with stroke widths compressed to two pixels.
Referring to FIG. 4a:
______________________________________
original modified
______________________________________
zone 1
CS.sub.n CS.sub.n ' 200 (not moved)
CS.sub.n+1 300
CS.sub.n+1 ' 250 (width has been compressed by
______________________________________
50%)
where:
n: edge "n", left edge of zone
n + 1: right edge of zone
CS.sub.n : Character space edge "n" (unadjusted)
CS.sub.n ': Adjusted (hinted) character space edge "n
The left edge CS.sub.n ' of zone 2 shifts with the right edge CS.sub.n+1 '
of zone 1 as zone 1 is compressed, expanding zone 2 by 50 units, but the
right edge of zone 2 stays fixed, for an adjusted width of 250 units.
______________________________________
zone 2
______________________________________
CS.sub.n 300
CS.sub.n ' 250 (shares edge with zone 1)
CS.sub.n+1 500
CS.sub.n+1 ' 500 (shares edge with zone 3)
______________________________________
If points in device space need to be adjusted to meet typographic design
criteria, the complete transformation matrix generally will be non-linear.
Here, zone 2 becomes larger by 25% while zone 1 becomes smaller by 50%, so
the zones must use different matrices.
The compensation factor (C.sub.f) provides the scaling factor needed to
distort a zone. C.sub.f is simply the ratio of the adjusted width of a
zone divided by the original width of zone. The ratio of the compensation
factor is shown below:
##EQU1##
Prior art methods of implementing zonal transformations may generate
discontinuities as an abrupt change in transformation matrix values
transitioning from zone to zone, for example, in going from zone 1 to zone
2. Simply setting C.sub.f =1.25 and scaling up zone 2 by 25% would
transform the left edge of zone 2 to 250*1.25=312.5; and would transform
the right edge of zone 2 to 500*1.25=625. These are not the desired
values. These discontinuities may produce a noticeable effect at each
edge. To eliminate these discontinuities, the transformation matrix can be
modified to include a translation factor:
x'[Z]=(x-CS.sub.n)*C.sub.f +CS.sub.n ' Eqn. 1
where:
x=point x in zone Z
(x-CS.sub.n)=Normalizes original point x in current zone Z as a "width"
C.sub.f =Compensation Factor, amount zone is distorted
CS.sub.n '=Translation factor, restoration to new coordinate space
For zone 2, this becomes:
x'[2]=(x-300)*C.sub.f +250
The transformation of the right edge of zone 2 becomes
(500-300)*1.25+250=500, precisely the value desired.
This process is repeated in a similar manner, calculating C.sub.f and
offset translation for each zone, to yield a piecewise, generally
non-linear transformation matrix, [S.sub.x,S.sub.y ].
The above example shows the conversion of the original coordinate data in
character space (CS) to a new coordinate space called hinted character
space (CS'). In the prior art ATM method, these distortions were first
made in device space (the actual target of all character modifications)
then backed into character space through an inverse transformation matrix
(that is, a transformation matrix that "undoes" the device space
transformation matrix) to create the CS' coordinate data. Converting the
CS' data points to hinted device space (DS') requires applying the final
transformation matrix [S.sub.x, S.sub.y ] to the original coordinate data
[Cx.sub.n, Cy.sub.n ] in CS.
##EQU2##
The DS' data points then can be filled using prior art methods or the
methods described below. The filled outline can be stored or displayed
directly.
The Current Method
The present invention combines compensation transformation and device space
transformation to allow higher throughput and streamlined operation. This
method distorts an object outline by creating a series of transformation
matrices applied on a zonal basis. This method is sometimes referred to as
a piecewise-nonlinear transformation using a transformation matrix list to
emulate the operation of a nonlinear transformation function.
Transforming Outline Data and Deriving the Transformation Matrix
The FRC implements zonal distortions in a slightly different yet
mathematically identical manner. In contrast to the above example, the FRC
does not track either the final width of a zone, e.g. 113 for zone 1 and
114 for zone 2 in FIG. 4a, or a zone's new right edge (300.fwdarw.250 for
zone 1), but tracks the delta of change (112 or -50 units for both zones 1
and 2). Making a zone smaller is treated as a negative value. This change
makes the calculation of the C.sub.f simpler:
##EQU3##
The equation for transformation becomes:
##EQU4##
For zone 2:
x'.sub.CS [2]=(x-300)*(1.0+C.sub.f)+250
x'.sub.DS [2]=(x-300)*(S.sub.f +C'.sub.f)+DS'.sub.n
The equation includes a new factor, S.sub.f or scale factor for the f
dimension (x or y). These equations can be simplified.
The distorted width of the zone in device space (the DS' width) can be
divided by the unhinted character space width (CS width) to produce the
combined device space transformation/compensation factor value. The
equation to fully transform a coordinate becomes:
##EQU5##
which can be restated as:
##EQU6##
Simplified:
x'.sub.DS [Z]=x.sub.CS *C.sub.fc +(DS'.sub.n -CS.sub.n *C.sub.fc)Eqn. 3
The constant term is set equal to K:
K=DS'.sub.n -CS.sub.n *C.sub.fc Eqn. 4
where:
C.sub.fc : Composite compensation factor
S.sub.f : Scale factor, e.g. S.sub.x in the x direction
C'.sub.f : C.sub.fc -S.sub.f
Since only one level of transformation operation is required, the number of
multiplications performed by the rendered has been decreased.
This method can be implemented using the following pseudocode.
PseudoProcedure CreateMap #Repeat for each axis, typically x and y
##EQU7##
Applying the Transformation to the Outline Data
The compensation matrices and the device space matrices can be combined and
applied to the original outline data to derive the desired final
transformation in a single step. Prior art distortions transform
characters from CS to CS', hinted character space, and subsequently into
hinted device space DS'. Many mathematical steps (and significant time)
can be avoided if hinting stays in device space. The present invention
bypasses the CS' coordinate system to simplify operations. The new
compensation factors include the actual device space transformation in
addition to the distortion factors.
##EQU8##
The DS' data points then can be filled methods or the methods described
below. The filled outline can be stored or displayed directly.
Hinting
The rasterization process can be deliberately distorted to improve the
appearance and/or legibility of characters being generated. Specific
information can be included in the font data to direct or guide a renderer
to make adjustments and corrections in the scaling and rasterization of
the final bit map and produce a more optimal result. One such process is
referred to as hinting and the data generally included in the font outline
is referred to as hints. Hints are typically applied in device space but
can also be applied in character space before scaling the outline data.
The process of hinting involves identifying certain common characteristics
of classes of objects and defining a series of processes to maintain the
aesthetic nature (and, in the case of fonts, legibility) of the object
being rendered, even at extremely large or small sizes. Basic hinting
methods and applications are described at length along with the Type 1
font encoding specification in ADOBE TYPE 1 F0NT FORMAT (the "Black Book",
1990), incorporated herein by reference. The FRC implements these
operations in a novel manner.
Hinting commands include stem hinting commands hstem, vstem, hstem3 and
vstem3. In accordance with the distortion methods described earlier, a
stem is analogous to a distortion zone. The areas between stems, called
counters in typographical terms, become the compensation zones. The
program designer or type designer can choose certain rules to control the
placement of the edges of a stem for optimal rendering and the width of
the stem for consistent stroke color. These methods result in distortions
that are then used to create the distortion matrix list. The Type 1 font
specification includes additional zones specified by the BlueValues[ ] and
OtherBlues[ ] arrays, which allow coordination with the placement of the
stem zones to ensure proper character height rendering at small sizes, as
discussed below. The term height includes both ascenders above the
X-height and other typographic top zones, as well as descenders below the
baseline and other typographic bottom zones. The following methods are
used to control the width and edge placement of stems. The examples are in
terms of X-coordinates and widths, but corresponding adjustments in
Y-coordinates and height are made in an analogous manner.
Width
The width of the stem in character space is represented by Width.sub.CS.
The width after transformation to device space is represented by
Width.sub.DS, generally with a fractional value. Width.sub.DS can be
represented as i.ff, where i represents the integer portion of the width
and .ff represents the fractional portion. Subsequent processing is made
easier if there are a minimal number of points exactly on certain
thresholds, such as coincident with a pixel center. The width can be
adjusted around selected threshold points, where the threshold points are
set by design to achieve visually acceptable, or, better yet, optimal,
renderings. For example, the values of the width can be restricted to a
specified range determined by a lower boundary (0.625) and an upper
boundary (0.900). FIG. 4b illustrates one width evaluation and shows
adjustment of width 136 by delta.sub.width 137 to bring the | | |
