The prior art basically has three method and apparatus to represent fonts in computer displays or desk-top publishing applications. These methods are 1) bit mapped representations; 2) vector representations, and 3) curved representations.
A font is defined in bit mapped representations as a matrix of dots, such as 15.times.16 dots. See FIG. 1 for an example of such a Chinese character. If one needs to display or print a font of a different size, for instance 24.times.24, a corresponding dot matrix for that font size is required. When bit mapped fonts are used in Chinese or other Oriental computing and printing systems, a large storage space is needed to keep the dot matrix description of fonts for all styles in different sizes.
The font outline in vector representations is represented by its polygonal approximation. The data points indicating the vertices of the polygon are stored. However, this scheme is not efficient. To approximate a portion of a curve with high accuracy, many small vectors are needed. Moreover, the image output is not very good when these characters are scaled to very large sizes. The net result is that the intersections of the lines are not smooth.
The font outline in curved representations is described by a set of smoothly connected cubic curves. When the character is defined in this way, it is possible to generate different sizes and shapes of characters from the same curved descriptions. All that needs to be done is to specify the scaling factors in an x and y direction.
The process of scaling a character is to carry out a coordinate mapping on the curve representations, and to reconstruct a bit map by using an area filling process. Based on this advantage, the use of outlined fonts have become the trend in desk-top computing and printing systems.
When text is formatted using an outlined font, an efficient and robust process must be provided in order to convert the font described by its outlines into the bit mapped form and fill it in the proper position of the frame buffer for later display or printing.
By robust it is meant that the process should rasterize the fonts of any size with minimum distortion. In outlined fonts, one description is used to generate different sizes of fonts. In such cases problems will appear when the process needs to generate small sized fonts. These problems include broken strokes, over-filling, and distortion. For instance when the fonts are scaled to a small degree, many strokes will become only one pixel wide. If the filling process is not well designed, it may either over-fill or under-fill these strokes. Under-filling will result in broken strokes. Over-filling will result in filling extra blank spaces in the frame buffer. The distortion may be the result of uneven stroke widths for one stroke, merged strokes, and various distortions etc., caused by quantization.
There are many filling processes in the literature. They can be divided into two broad categories; 1). seed fill; and 2). edge fill.
In seed fill processes, a connected contour of the shape to be filled is first drawn on to the drawing buffer. A seed point, known to be in the interior of the shape of the character, is then selected. The process will then fill this pixel and all pixels that can be accessed from the seed pixel. The filling will continue until it reaches the contour points.
The advantage of seed filling is that during the filling process it will not process any pixel outside the contour. However, seed filling presents many problems for conversion of outline characters to bit mapped characters. One drawback of seed filling is the need to supply or find an initial seed point for each contour. The seed point can be supplied as part of the input to the process together with all the contour data. However, when the font size becomes small, one contour may split into two or more separate contours. The seed point as supplied will fall inside one of those contours and only that contour can then be filled resulting in under-filling. If all the seed points need to be found by the process itself before filling takes place, the process will become quite complicated.
Edge filling can also be called scan conversion filling. The first step in edge filling processes is to also draw the font's contour on to a drawing buffer. The next step is to scan the whole drawing buffer line by line and fill the interior of the contour. Within each horizontal scan line, the process will fill segments between the first and second contour pixels, the third and fourth contour pixels, and the subsequent sets of contour pixels. This is based upon the fact that a straight line intersects any closed contour an even number of times. If the first point of the line lies outside the contour, then one can traverse it and decide which segments are in the interior by counting the number of intersections.
All edge filling processes have to cope with special cases such as corner points, and overlapped contours in order for the processes to work correctly all the time. Usually, the processes must scan the whole drawing buffer to fill it correctly. Moreover, the method needs to undertake extra procedures to avoid over-filling and under-filling. Sometimes another buffer of memory is needed to store the contours. This makes the process less efficient.
The objective of this invention is to provide a robust and efficient filling apparatus and process for generating bit mapped characters through their outline descriptions. It needs less memory, processes faster, and avoids over-filling and under-filling.
Compared with other patents, this invention has the following important features and objects of the invention.
The invention converts the curved description of contours into their bit mapped description at first, and then fills the interior of the contour to obtain the bit mapped font.
During the contour conversion process, some chain-code flags are set on the chain-code description to indicate the contour collisions.
During the filling process the chain-code description helps to scan and fill only the interior of the contours to improve speed. The chain-code flags help to avoid the over-filling problem.
The establishment of the filling direction is based on the direction of the contours of the font. This avoids the under-filling problem of the seed fill processes when the font size is small.
Two memory buffers are used in this invention. One is for the image of the font. The size of this buffer is the same as the biggest character with one bit for one pixel. The other is used to store the chain-code and chain-code flags.
A curtailing function is used to avoid the over-filling problem created by the difference between the mathematical or parametric description and the pixel description of the outline.
These differences as to the known prior art are quite apparent when comparing with some of the following relevant patents.
U.S. Pat. No. 4,551,092 is mainly concerned with how to control the stroke width of the characters during character conversion from outline form to bit mapped form, especially when the character size is small. This is called hinting, not filling. The topic of interest in the Patent is different from the object and essence of this invention.
U.S. Pat. No. 4,785,391 and No. 4,959,801 each relate to a like process. One is an improvement to the other. The main teaching in the Patents is a new method to represent the fonts, in order to improve the quality of character generations, especially for small sized characters.
U.S. Pat. No. 5,038,385 deals with contour filling. It firstly scans the contours to establish some marks on the drawing buffer. For example it establishes the first and second type of picture elements. It then obtains direction code sequences as defined by the process. Then, it fills the inside by raster scan, aided by the marks on the drawing buffer and the direction code. The differences between this Patent and the invention hereof are:
1) The Patent generates marks on the drawing buffer to aid filling. On the other hand the invention draws the outline on the drawing buffer and sets some flags on the chain-code description of the contours to aid in filling.
2) The invention generates the chain-code contours to help scan only the inner part of the contour and the contour itself that is to be filled. The Patent to the contrary needs to scan the whole drawing buffer to fill the character.
3) The invention uses one bit in the drawing buffer to represent one pixel of the bit map form. However, the Patent uses at least two bits in the drawing buffer to represent one pixel of the bit map form, in order to have room for the marks.
U.S. Pat. No. 4,967,376 is directed toward contour filling for fonts. It firstly scans the contours to set up some marks on the drawing buffer which can be the left edge mark or the right edge mark. Then it scans the whole drawing buffer to initiate filling. There are several differences as enumerated between this Patent and the invention.
1) This patent generates marks on the drawing buffer to aid filling. However, the invention draws the outline on the drawing buffer and sets some flags on the chain-code description of the contours to aid in filling.
2) The invention generates the chain-code of contours to help to scan only the inner part of the contour and the contour itself to fill. However, the Patent needs to scan the whole drawing buffer in order to provide filling.
3) The invention uses one bit in the drawing buffer to represent one pixel of the bit mapped form. The Patent on the other hand uses two memory planes of the same size. One is the drawing plane and the other is the control plane.
4) Furthermore, the invention has a special curtailing function which the Patent does not have.