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

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.

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.

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.

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.

A method for performing a real-time rasterization of character and font information for a column-oriented printing apparatus using a programmable data processing means, the character and font information being represented as outlines of a plurality of selected characters for a given segment of columns to be output to the printing apparatus, the outlines being stored as a sequence of edge points, each edge point defining a coordinate having values representing a column and a height in the column for the edge point, comprising the steps of:

• differentially encoding the edge points to produce a plurality of edge segments to represent each selected character, each edge segment representing a curve, a line or a move and being defined by a coordinate representing an end of the edge segment in terms of values relative to a previous edge segment such that the edge segment will represent only one column crossing per column, 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;
• storing the edge segments for the selected characters in an edge list data base on a character by character basis;
• and
• for each column to be output to the printing apparatus,
• searching the edge list data base for all edge segments that cross the column to produce a set of column crossing points for the column;
• rasterizing the portions of the selected characters represented by the column crossing points for the column in accordance with a predetermined fill rule;
• and
• outputting the column of the rasterized portions of the selected characters to the printing apparatus.

A method for controlling the formatting and manipulations of font and character information of images of selected characters by a programmable data processing means to be output to a column-oriented printing apparatus, comprising the steps of:

• 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;
• generating a series of edge points defining an outline for each of the selected characters represented by the input data using the font 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;
• storing the edge points for each of the selected characters in an intermediate edge list data 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;
• 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
• 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.

A method for controlling the formatting and manipulations of font and character information of images of selected characters by a programmable data processing means to be output to a column-oriented printing apparatus, comprising the steps of:

• receiving input data representing the character information of the selected characters and font data representing the outlines of the font information of the image of a plurality of selected character sets;
• 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;
• generating a pair of second edge points defining a stroking outline for each of the first edge points;
• 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 segment stored as one or more edge list, 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;
• 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
• rasterzing 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.

A method for controlling the formatting and manipulations of font and character information of images of selected by a characters by a programmable data processing means to be output to a column-oriented printing apparatus, comprising the steps of:

• receiving the font and character information;
• formatting the relative positions of the selected characters to be output to the printing apparatus using the font and character information;
• 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;
• storing the edge points in an edge list data base as a series of edge segment, 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;
• 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
• producing a column bit map data representing column-oriented print data to be output to the printing apparatus.