Glyphs which comprise a font are stored in a font memory as outline data. Such outline data is stored in the form of mathematical functions which describe the curves and straight lines which comprise the glyph. In rasterizing such font data, decisions must be made as to what portions of a glyph outline will be "filled" and which portions will remain un-filled or "white".
Many fonts are rasterized employing a "non-zero winding method". That method achieves rasterization by starting at an outside margin of the image and following a raster scan line through its points of intersection with contours of the glyph. Hereafter, the description will assume that an image is traversed left-to-right, however it is to be understood that image traversal can occur in the opposite direction. It will be further assumed that when a glyph contour is traced, the "ink" is to the right of the contour being traced. If a contour at a point of intersection exhibits a positive (i.e., upward) slope, the point of intersection is assigned a value of plus 1. If, the contour at the point of intersection exhibits a negative (i.e., downward) slope, the point of intersection is assigned a value of minus 1. A running total of the assigned values is maintained and when the sum is non-zero, it is known that pixel locations to the right of the point of intersection where the sum becomes non-zero should be "filled". In other words, at that point of intersection and until a next point of intersection where the running total becomes zero, all pixel locations are printed with a black or other color fill ink.
Each intersection of a raster scan line and a contour is called a transition point and may be either an OFF-to-ON transition or an ON-to-OFF transition, with an OFF-to-ON transition marking the location where a fill action begins. An ON-to-OFF transition marks the location where the fill action stops. In a binary printer, a fill action is manifest by black pixels and the non-fill area is manifest by white pixels (and sometimes vice-versa).
A presently used method for determining the location of fill area pixels is based upon determined "transition pairs". An ON/OFF transition pair is created by taking a leftmost OFF-to-ON transition coordinate and a leftmost ON-to-OFF transition coordinate and pairing them together (assuming a left-to-right scan). A next ON/OFF transition pair is created by taking a next leftmost OFF-to-ON transition coordinate and a next leftmost ON-to-OFF transition coordinate and pairing them. This process is repeated until all transitions are paired.
The process is time consuming and requires a sorting by X coordinates value of both the ON and OFF transitions into two separate lists for each scan line. Then a first OFF/ON transition pair from the OFF/ON transition pair list is paired with a first ON/OFF transition pair from the ON/OFF transition pair list. Overlaps are then determined and the resulting transition pair list is employed to control the print action so as to create appropriate fill areas.
In implementing the above-noted procedure, the prior art has sorted and stored all OFF-to-ON and ON-to-OFF transition coordinates into sequential transition lists until all glyph contours have been traversed. The sorting action is then performed using an insertion sort which requires a sequential comparison of a new X coordinate with coordinates already sorted. The sorting action presents a substantial processing burden to the rasterization function. Further, the prior art either allocates large amounts of memory to the rasterization function (assuming a worst case memory requirement) to hold the transition lists or calculates and constructs linked lists at the expense of substantial computation time.
Accordingly, it is an object of this invention to provide an improved method for determining fill areas in a rasterized glyph representation.
It is another object of this invention to provide an improved method for identifying and sorting transition pairs in a raster representation of a glyph.
It is yet another object of this invention to provide an improved method for determining transition pairs which, as compared to the prior art, reduces the required amount of allocated memory.