Real-time rasterization system for a column-oriented printing apparatus or the like

Claim 2

A real-time rasterization system for controlling the formatting and manipulations of font and character information of images of selected characters to be output to a column-oriented printing apparatus having a predefined worst-case data transfer rate, comprising: a programmable data processing means for receiving input data representing the character information of the selected characters and font data representing the outlines of the font information of the images of a plurality of selected character sets and for generating column-oriented print data for outputting the selected characters to the printing apparatus, the programable data processing means having: means for generating a series of edge points defining an outline for each of the selected characters represented by the input data using the font data for one of the selected character sets, each edge point defining a coordinate having values representing a column and a height in the column for the edge point; means for storing the edge points for each of the selected characters in an intermediate edge list data base as a series of edge segments, each edge segment stored as one or more edge lists, each edge list having only one column crossing per column such that the outline represented by the edge segment does not loop back on itself; means for retrieving the edge points from the intermediate edge list data base as a series of column crossing points representing all edge points having the same value for the coordinate representing the column; and means for rasterizing the series of column crossing points to produce a column of bit map data representing the print data to be output to the column-oriented printing apparatus, whereby the creation of the intermediate edge list data base allows the data processing means to perform the rasterization of the selected characters in real-time such that the print data is made available to the column-oriented printing apparatus at a rate sufficiently fast enough to keep up with the worst-case data transfer rate of the column-oriented printing apparatus.

Claim 3

The real-time rasterization system of claim 1 wherein the means for generating the series of edge points operates asynchronously from the means for retrieving the edge points.

Claim 4

The real-time rasterization system of claim 1 wherein the means for rasterizing the column crossing points produces the column of bit map data by applying a fill rule between successive column crossing points in the column.

Claim 5

The real-time rasterization system of claim 1 wherein the edge list comprises: a header record having: a start coordinate defining the right most edge point; a direction defining whether the edge segment is a forward edge or a reverse edge; a winding defining the direction sense used for a winding rule calculation; an edge data pointer pointing to the next edge point to be used in the edge list; and a next edge pointer pointing to the next edge list in the intermediate edge list data base; and a plurality of data points representing a contiguous string of edge points whose column numbers increase monotonically.

Claim 6

The real-time rasterization system of claim 4 wherein the data points are one byte values representing a one column horizontal movement up or down, a one column diagonal movement up or down, or a vertical movement of any number of pixel points along the current column.

Claim 7

The real-time rasterization system of claim 1 wherein the means for retrieving the edge points use a master edge list identifying all of the edge segments for a selected character and an active edge list identifying all of the edge segments for a selected character that contain edge points in the column currently being retrieved.

Claim 8

The real-time rasterization system of claim 1 further comprising: buffer means for receiving the print data and storing the print data in a first-in, first-out sequence; and second programmable data processing means for retrieving the print data from the buffer in response to a control signal from the printing apparatus and outputting the print data to the printing apparatus, whereby the print data is retrieved from the buffer means by the second programmable data processing means asynchronously with the storing of the print data produced by the means for rasterizing the column crossing points.

Claim 9

In combination with a column-oriented printing apparatus and a programmable data processing means for receiving input data representing the character information of the selected characters and font data representing the outlines of the font information of the images of a plurality of selected character sets and for generating print data for outputting the selected characters to the column-oriented printing apparatus, a rasterization system for controlling the formatting and manipulations of the font and character information of the selected characters to be output to the column-oriented printing apparatus, comprising: means for generating a series of edge points defining an outline for each of the selected characters represented by the input data using the font data for one of the selected character sets, each edge point defining a coordinate having values representing a column and a height in the column for the edge point; means for storing the edge points and a fill rule for each of the selected characters in an intermediate edge list data base as a series of edge segments, each edge segment stored as one or more edge lists, each edge list having only one column crossing per column such that the outline represented by the edge segment does not loop back on itself; means for retrieving the edge points from the intermediate edge list data base as a series of column crossing points representing all edge points having the same value for the coordinate representing the column; and means for rasterizing the column crossing points using the fill rule to produce a column of bit map data representing the column-oriented print data to be output to the printing apparatus.

Claim 10

In combination with a column-oriented printing apparatus and a programmable data processing means for receiving input data representing the character information of the selected characters and font data representing the outlines of the font information of the images of a plurality of selected character sets and for generating print data for outputting the selected characters to the column-oriented printing apparatus, a rasterization system for controlling the formatting and manipulations of the font and character information of the selected characters to be output to the column-oriented printing apparatus, comprising: means for generating a series of edge points defining an outline for each of the selected characters represented by the input data using the font data for one of the selected character sets, each edge point defining a coordinate having values representing a column and a height in the column for the edge point; means for storing the edge points and a fill rule for each of the selected characters in an intermediate edge list data base as a series of edge segments, each edge segment stored as one or more edge lists, each edge list having only one column crossing per column such that the outline represented by the edge segment does not loop back on itself; means for retrieving the edge points from the intermediate edge list data base as a series of column crossing points representing all edge points having the same value for the coordinate representing the column; and means for rasterizing the column crossing points using the fill rule to produce a column of bit map data representing the column-oriented print data to be output to the printing apparatus.

Claim 11

The combination of claim 8 wherein the means for generating the series of edge points operates asynchronously from the means for retrieving the edge points.

Claim 12

The combination of claim 8 wherein the edge list comprises: a header record having: a start coordinate defining the right most edge point; a direction defining whether the edge segment is a forward edge or a reverse edge; a winding defining the direction sense used for a winding rule calculation; an edge data pointer pointing to the next edge point to be used in the edge list; and a next edge pointer pointing to the next edge list in the intermediate edge list data base; and a plurality of data points representing a contiguous string of edge points whose column numbers increase monotonically.

Claim 13

The combination of claim 10 wherein the data points are one byte values representing a one column horizontal movement up or down, a one column diagonal movement up or down, or a vertical movement of any number of pixel points along the current column.

Claim 14

The combination of claim 8 wherein the means for retrieving the edge points use a master edge list identifying all of the edge segments for a selected character and an active edge list identifying all of the edge segments for a selected character that contain edge points in the column currently being retrieved.

Claim 15

The combination of claim 8 further comprising: buffer means for receiving the print data and storing the print data in a first-in, first-out sequence; and means for retrieving the print data from the buffer in response to a control signal from the printing apparatus and outputting the print data to the printing apparatus, whereby the print data is retrieved from the buffer means asynchronously with the storing of the print data produced by the means for rasterizing the column crossing points.

Claim 16

A rasterization system for controlling the formatting and manipulations of font and character information of images of selected characters to be output to a column-oriented printing apparatus, comprising: a programmable data processing means for receiving input data representing the character information of the selected characters and font data representing the outlines of the font information of the images of a plurality of selected character sets and for generating print data for outputting the selected characters to the column-oriented printing apparatus, the programable data processing means having: means for generating a series of first edge points defining an outline for each of the selected characters represented by the input data using the font data for one of the selected character sets, each edge point defining a coordinate having values representing a column and a height in the column for the edge point; means for generating a pair of second edge points defining a stroking outline for each of the first edge points; means for storing the second edge points for each of the selected characters in an intermediate edge list data base as a series of edge segments, each edge segment stored as one or more edge lists, each edge list having only one column crossing per column such that the outline represented by the edge segment does not loop back on itself; means for retrieving the second edge points from the intermediate edge list data base as a series of column crossing points representing all edge points having the same value for the coordinate representing the column; and means for rasterizing the column crossing points to produce a column of bit map data representing the column-oriented print data to be output to the printing apparatus.

Claim 17

A rasterization system for controlling the formatting and manipulations of font and character information of images of selected characters to be output to a column-oriented printing apparatus, comprising: a programmable data processing means for receiving input data representing the character information of the selected characters and font data representing the outlines of the font information of the images of a plurality of selected character sets and for generating print data for outputting the selected characters to the column-oriented printing apparatus, the programable data processing means having: means for generating a series of first edge points defining an outline for each of the selected characters represented by the input data using the font data for one of the selected character sets, each edge point defining a coordinate having values representing a column and a height in the column for the edge point; means for generating a pair of second edge points defining a stroking outline for each of the first edge points; means for storing the second edge points for each of the selected characters in an intermediate edge list data base as a series of edge segments, each edge segment stored as one or more edge lists, each edge list having only one column crossing per column such that the outline represented by the edge segment does not loop back on itself; means for retrieving the second edge points from the intermediate edge list data base as a series of column crossing points representing all edge points having the same value for the coordinate representing the column; and means for rasterizing the column crossing points to produce a column of bit map data representing the column-oriented print data to be output to the printing apparatus.

Claim 18

The rasterization system of claim 14 wherein the means for generating the pair of second edge points operates asynchronously from the means for retrieving the second edge points.

Claim 19

The rasterization system of claim 14 wherein the means for rasterizing the column crossing points produces the column of bit map data by applying a fill rule between successive column crossing points in the column.

Claim 20

The rasterization system of claim 14 wherein the edge list comprises: a header record having: a start coordinate defining the right most edge point; a direction defining whether the edge segment is a forward edge or a reverse edge; a winding defining the direction sense used for a winding rule calculation; an edge data pointer pointing to the next edge point to be used in the edge list; and a next edge pointer pointing to the next edge list in the intermediate edge list data base; and a plurality of data points representing a contiguous string of edge points whose column numbers increase monotonically.

Claim 21

The rasterization system of claim 17 wherein the data points are one byte values representing a one column horizontal movement up or down, a one column diagonal movement up or down, or a vertical movement of any number of pixel points along the current column.

Claim 22

The real-time rasterization system of claim 14 wherein the means for retrieving the second edge points use a master edge list identifying all of the edge segments for a selected character and an active edge list identifying all of the edge segments for a selected character that contain edge points in the column currently being retrieved.

Claim 23

A rasterization system for controlling the formatting and manipulations of font and character information of images of selected characters to be output to a column-oriented printing apparatus, comprising: input means for receiving all of the font and character information; format means operably connected to the input means for formatting the relative positions of the selected characters to be output to the printing apparatus using the font and character information; outline means operably connected to the format means for generating edge points for each pixel coordinate of an outline of the selected character using the font information, each edge point defining a coordinate having values representing a column and a height in the column for the edge point; edge list means operably connected to the outline means for storing the edge points in an edge list data base as a series of edge segments, each edge segment stored as one or more edge lists, each edge list having only one column crossing per column such that the outline represented by the edge segment does not loop back on itself, and for retrieving the edge points from the edge list data base as a series of column crossing points representing all edge points having the same value for the coordinate representing the column; and rasterization means operably connected to the edge list means for receiving the column crossing point and producing a column bit map data representing column-oriented print data to be output to the printing apparatus.

Claim 24

A rasterization system for controlling the formatting and manipulations of font and character information of images of selected characters to be output to a column-oriented printing apparatus, comprising: input means for receiving all of the font and character information; format means operably connected to the input means for formatting the relative positions of the selected characters to be output to the printing apparatus using the font and character information; outline means operably connected to the format means for generating edge points for each pixel coordinate of an outline of the selected character using the font information, each edge point defining a coordinate having values representing a column and a height in the column for the edge point; edge list means operably connected to the outline means for storing the edge points in an edge list data base as a series of edge segments, each edge segment stored as one or more edge lists, each edge list having only one column crossing per column such that the outline represented by the edge segment does not loop back on itself, and for retrieving the edge points from the edge list data base as a series of column crossing points representing all edge points having the same value for the coordinate representing the column; and rasterization means operably connected to the edge list means for receiving the column crossing point and producing a column bit map data representing column-oriented print data to be output to the printing apparatus.

Claim 25

The rasterization system of claim 20 wherein the input means includes metric means for handling the font information.

Claim 26

The rasterization system of claim 20 wherein the format means comprises: setup formatting means for generating a character origin and a font index for the first character of the selected characters and for the first character of the selected characters each time a new font is designated in the character information; and run time formatting means for generating information about the character size and character format.

Claim 27

The rasterization system of claim 20 further comprising transform means operably connected to the outline means for performing the coordinate transformations of the font information for the selected character to generate the appropriate size outline of the selected character.

Claim 28

The rasterization system of claim 23 wherein the transform means utilizes a transformation matrix to perform the coordinate transformations.

Claim 29

The rasterization system of claim 24 wherein the transformation matrix is constructed by multiplying together in the specified order; a scaling matrix, an italicizing matrix, a rotation matrix, and a translation matrix.

Claim 30

The rasterization system of claim 20 wherein the edge list comprises; a header record having: a start coordinate defining the right most edge point; a direction defining whether the edge segment is a forward edge or a reverse edge; a winding defining the direction sense used for a winding rule calculation; an edge data pointer pointing to the next edge point to be used in the edge list; and a next edge pointer pointing to the next edge list in the edge list data base; and a plurality of data points representing a contiguous string of edge points whose column numbers increase monotonically.

Claim 31

The rasterization system of claim 26 wherein the data points are one byte values representing a one column horizontal movement up or down, a one column diagonal movement up or down, or a vertical movement of any number of pixel points along the current column.

Claim 32

The rasterization system of claim 20 wherein the edge list means stores the edge points in the edge list data base asynchronously from retrieving the edge points.

Claim 33

The rasterization system of claim 28 wherein the edge list means retrieves the edge point from the edge list data base in response to a signal from the rasterization means.

Claim 34

The rasterization system of claim 20 wherein the rasterization means produces the column of bit map data by applying a fill rule between successive column crossing points in the column.

Claim 35

The rasterization system of claim 20 further comprising bit map means operably connected to the rasterization means transferring the font information for certain of the selected characters for which a bit map is contained in the font information to the rasterization means to be output to the printing apparatus.

Claim 36

The rasterization system of claim 20 further comprising: buffer means operably connected to the rasterization means for receiving the print data and storing the print data in a first-in, first-out sequence; and output means operably connected to the buffer means for retrieving the print data from the buffer means in response to a control signal from the printing apparatus and outputting the print data to the printing apparatus.

Claim 37

The rasterization system of claim 32 wherein the buffer means requests additional print data from the rasterization means when the output level of the buffer means falls below a preset level.

Claim 38

A rasterization system for controlling the formatting and manipulations of font and character information of images of selected characters to be output to a column-oriented printing apparatus, comprising: input means for receiving all of the font and character information; format means operably connected to the input means for formatting the relative positions of the selected characters to be output to the printing apparatus using the font and character information, comprising: setup formatting means for generating a character origin and a font index for the first character of the selected characters and for the first character of the selected characters each time a new font is designated in the character information; and run time the formatting means for generating information about the character size and character format; outline means operably connected to the format means for generating edge points for each pixel coordinate of an outline of the selected character using the font information, each edge point defining a coordinate having values representing a column and a height in the column for the edge point; transform means operably connected to the outline means for performing the coordinate transformations of the font information for the selected character to generate the appropriate size outline of the selected character utilizing a transformation matrix to perform the coordinate transformations wherein the transformation matrix is constructed by multiplying together in the specified order; a scaling matrix, an italicizing matrix, a rotation matrix, and a translation matrix; edge list means operably connected to the outline means for storing the edge points in an edge list data base as a series of edge segments and for retrieving the edge points from the edge list data base as a series of column crossing points representing all edge points having the same value for the coordinate representing the column asynchronously from storing the edge points, the edge segments being stored in the edge list data base as a plurality of edge lists, each edge list having only one column crossing per column such that the outline represented by the edge segment does not loop back on itself, the edge list comprising: a header record having: a start coordinate defining the right most edge point; a direction defining whether the edge segment is a forward edge or a reverse edge; a winding defining the direction sense used for a winding rule calculation; an edge data pointer pointing to the next edge point to be used in the edge list; and a next edge pointer pointing to the next edge list in the edge list data base; and a plurality of data points representing a contiguous string of edge points whose column numbers increase monotonically, the data points being one byte values representing a one column horizontal movement up or down, a one column diagonal movement up or down, or a vertical movement of any number of pixel points along the current column; rasterization means operably connected to the edge list means for receiving the column crossing point and producing a column bit map data representing column-oriented print data to be output to the printing apparatus; bit map means operably connected to the rasterization means transferring the font information for certain of the selected characters for which a bit map is contained in the font information to the rasterization means to be output to the printing apparatus; buffer means operably connected to the rasterization means for requesting and receiving print data from the rasterization means when the output level of the buffer means falls below a preset level and storing the print data in a first-in, first-out sequence; and output means operably connected to the buffer means for retrieving the print data from the buffer means in response to a control signal from the printing apparatus and outputting the print data to the printing apparatus.

Claim 39

A rasterization system for controlling the formatting and manipulations of font and character information of images of selected characters to be output to a column-oriented printing apparatus, comprising: input means for receiving all of the font and character information; format means operably connected to the input means for formatting the relative positions of the selected characters to be output to the printing apparatus using the font and character information, comprising: setup formatting means for generating a character origin and a font index for the first character of the selected characters and for the first character of the selected characters each time a new font is designated in the character information; and run time the formatting means for generating information about the character size and character format; outline means operably connected to the format means for generating edge points for each pixel coordinate of an outline of the selected character using the font information, each edge point defining a coordinate having values representing a column and a height in the column for the edge point; transform means operably connected to the outline means for performing the coordinate transformations of the font information for the selected character to generate the appropriate size outline of the selected character utilizing a transformation matrix to perform the coordinate transformations wherein the transformation matrix is constructed by multiplying together in the specified order; a scaling matrix, an italicizing matrix, a rotation matrix, and a translation matrix; edge list means operably connected to the outline means for storing the edge points in an edge list data base as a series of edge segments and for retrieving the edge points from the edge list data base as a series of column crossing points representing all edge points having the same value for the coordinate representing the column asynchronously from storing the edge points, the edge segments being stored in the edge list data base as a plurality of edge lists, each edge list having only one column crossing per column such that the outline represented by the edge segment does not loop back on itself, the edge list comprising: a header record having: a start coordinate defining the right most edge point; a direction defining whether the edge segment is a forward edge or a reverse edge; a winding defining the direction sense used for a winding rule calculation; an edge data pointer pointing to the next edge point to be used in the edge list; and a next edge pointer pointing to the next edge list in the edge list data base; and a plurality of data points representing a contiguous string of edge points whose column numbers increase monotonically, the data points being one byte values representing a one column horizontal movement up or down, a one column diagonal movement up or down, or a vertical movement of any number of pixel points along the current column; rasterization means operably connected to the edge list means for receiving the column crossing point and producing a column bit map data representing column-oriented print data to be output to the printing apparatus; bit map means operably connected to the rasterization means transferring the font information for certain of the selected characters for which a bit map is contained in the font information to the rasterization means to be output to the printing apparatus; buffer means operably connected to the rasterization means for requesting and receiving print data from the rasterization means when the output level of the buffer means falls below a preset level and storing the print data in a first-in, first-out sequence; and output means operably connected to the buffer means for retrieving the print data from the buffer means in response to a control signal from the printing apparatus and outputting the print data to the printing apparatus.

Claim 44

The method of claim 36 wherein the step of generating the series of edge points is performed asynchronously from the step of retrieving the edge points.

Claim 45

The method of claim 36 wherein the step of rasterizing the column crossing points produces the column of bit map data by applying a fill rule between successive column crossing points in the column.

Claim 46

The method of claim 36 wherein the step of storing the edge points in the intermediate edge list data base stores the edge segments as a plurality of edge lists, each edge list having only one column crossing per column such that the outline represented by the edge segment does not loop back on itself.

Claim 47

The method of claim 39 wherein the edge list comprises: a header record having: a start coordinate defining the right most edge point; a direction defining whether the edge segment is a forward edge or a reverse edge; a winding defining the direction sense used for a winding rule calculation; an edge data pointer pointing to the next edge point to be used in the edge list; and a next edge pointer pointing to the next edge list in the intermediate edge list data base; and a plurality of data points representing a contiguous string of edge points whose column numbers increase monotonically.

Claim 48

The method of claim 40 wherein the data points are one byte values representing a one column horizontal movement up or down, a one column diagonal movement up or down, or a vertical movement of any number of pixel points along the current column.

Claim 49

The method of claim 36 wherein the step of retrieving the edge points uses a master edge list to identify all of the edge segments for a selected character and an active edge list to identify all of the edge segments for a selected character that contain edge points in the column currently being retrieved.

Claim 50

The method of claim 36 further comprising the steps of: receiving the print data and storing the print data in a buffer means in a first-in, first-out sequence; and retrieving the print data from the buffer in response to a control signal from the printing apparatus and outputting the print data to the printing apparatus, whereby the print data is retrieved from the buffer means asynchronously with rasterizing the column crossing points.

Claim 55

The method of claim 45 wherein the step of formatting the relative positions of the selected characters comprises the step of: generating a character origin and a font index for the first character of the selected characters and for the first character of the selected characters each time a new font is designated in the character information; and generating run time formatting information about the character size and character format.

Claim 56

The method of claim 45 further comprising the step of performing the coordinate transformations of the font information for the selected character to generate the appropriate size outline of the selected character.

Claim 57

The method of claim 47 wherein the coordinate transformations are performed utilizing a transformation matrix.

Claim 58

The method of claim 48 wherein the transformation matrix is constructed by multiply a scaling matrix by an italicizing matrix by a rotation matrix by translation matrix.

Claim 59

The method of claim 45 wherein the edge list comprises: a header record having: a start coordinate defining the right most edge point; a direction defining whether the edge segment is a forward edge or a reverse edge; a winding defining the direction sense used for a winding rule calculation; an edge data pointer pointing to the next edge point to be used in the edge list; and a next edge pointer pointing to the next edge list in the edge list data base; and a plurality of data points representing a contiguous string of edge points whose column numbers increase monotonically.

Claim 60

The method of claim 50 wherein the data points are one byte values representing a one column horizontal movement up or down, a one column diagonal movement up or down, or a vertical movement of any number of pixel points along the current column.

Claim 61

The method of claim 45 wherein the step of storing the edge points in the edge list data base operates asynchronously from the step of retrieving the edge points.

Claim 62

The method of claim 52 wherein the step of retrieving the edge point from the edge list data base is performed in response to a signal generated by the step of rasterizing column crossing points.

Claim 63

The method of claim 45 wherein the step of rasterizing column crossing points produces the column of bit map data by applying a fill rule between successive column crossing points in the column.

Claim 64

The method of claim 45 further comprising the step of transferring the font information for certain of the selected characters for which a bit map is contained in the font information to the rasterization means to be output to the printing apparatus.

Claim 65

The method of claim 45 further comprising the steps of: receiving the print data and storing the print data in a first-in, first-out sequence in a buffer means; and retrieving the print data from the buffer means in response to a control signal from the printing apparatus; and outputting the print data to the printing apparatus.