Patent Publication Number: US-5299299-A

Title: Scan line full figure filling device for display units and printers

Description:
BACKGROUNDS OF THE INVENTION 
     1. Field of the Invention 
     The present invention relates to a figure filling device applied to display units and printers and particularly relates to a figure filling device capable of pasting arbitrary tiling patterns in so-called &#34;scan line fill&#34; processing where scanned lines on the memory defined by X-Y coordinates are filled one by one. 
     2. Description of the Prior Art 
     In recent years, software for attractive presentation for use on office automation machines such as personal computers, word processors and workstations has become available. Such software not only expresses characters, graphs and tables but also more complicatedly shaped figures on the display screen. When such displayed images are printed, all figures are represented as polygons with their internal areas filled, since printers usually have much higher resolution--several times the resolution of display units. Specifically, a line having a width of one pixel is too thin to use because of high resolution, and it is necessary to always use thick lines or squares as processing units. There are several methods to fill the inside of polygons including squares, but any method requires scan line fill at the last stage. Therefore, the throughput of the entire system largely depends on the speed of the scan line fill processing. 
     Conventional software as described above is capable of filling figures not only with a single color but also with arbitrarily tiling patterns by referring them. A tiling pattern is a rectangular pattern with a certain size placed like a tile to fill the area subjected to fill processing. To keep proper continuance of patterns, it is necessary to sequentially determine the location to be referred to in the tiling pattern when performing scan line fill. 
     Conventional methods to determine the pattern reference location are described here. One of such methods limits the tiling patterns to those with 16×16 or 32×32 pixels for simple processing. For example, suppose 16 bits constitute one word and 16×16 pixels make a tiling pattern in a monochrome device treating one pixel as one bit. In this case, regardless of the X coordinate of the start point of the scan line, the same word data is always used for horizontal direction. It is necessary to determine firstly which of the 16 word data in the Y direction is to be selected, but this can be decided by the lower four bits of the Y coordinate of the start point, and the calculation is quite simple. 
     In another method where tiling patterns can be of any size, the processing becomes quite troublesome. Firstly, it is required to determine the point on the tiling pattern to which the drawing start point of the scan line corresponds. The X coordinate of the drawing start point is divided by the vertical width of the tiling pattern to obtain the remainder, which is used as the X coordinate on the pattern. Then, the Y coordinate of the drawing start point is divided by the height of the tiling pattern to obtain the remainder, which is used as the Y coordinate on the pattern. This means that two divisions are required. Divisions are generally performed by a restoring method. In this method, the dividend and the divisor are aligned for the number of digits first, and the divisor is shifted to the left one bit by one bit to obtain the number of shifts required until the divisor exceeds the dividend. Then, with shifting the divisor to the right, the dividend is subjected to subtraction. If the result is negative, the divisor is added again. The value left after such shifting and subtraction repeated for the number of shifts as determined above is the remainder. 
     As mentioned above, recent software programs feature desk top publishing, desk top presentation or other similar functions and are capable of fine and beautiful drawing. Naturally, any size of tiling patterns can be defined in such programs. Therefore, it is required to improve the speed of scan line fill processing. In addition, with WYSIWYG (What you see is what you get) becoming popular, it is desired that the image on the display screen and the image provided by the printer give the same impression. To obtain the same impression image irrespective of the resolution of the printing device such as a printer, the resolution can be arbitrarily changed. It is required to change the size of the filing pattern in addition to the conversion of the coordinate data for the figure in order to obtain the same image using different devices with different resolutions. Therefore, it is now becoming more important to fill the figures using arbitrary tiling patterns. 
     In an application of scan line fill, scan lines each having a length of some dots are continuously drawn (for filling). A typical example is the outline font where the outline of a character is expressed with straight and curved lines and the coordinates of those segments are kept as the original information. The outline font is now becoming popular as one of the basic functions for word processors. Drawing in the outline font function is deemed to be filling of polygons, and can be reduced to the drawing for each of the horizontal lines, or in other words, the scan line fill. Since a character usually has a size of 60 dots×60 dots approximately, it is easily understood that the number of dots continuously existing on a single scan line is often several dots. Further, in division into scan lines, adjacent segments are continuously generated. The segment filling processing itself requires only a short time since each segment has only a dozen dots at most. Therefore, the essential point in such application is the speed of calculation to determine the reference start point of the filling pattern. When the conventional method is used to determine the remainder, it takes time in proportion to the number of significant digits of the dividend and the divisor; this means that even when the filling itself requires only a few clocks, determination of the pattern reference start point needs some tens of clocks, resulting in lengthy processing time. 
     SUMMARY OF THE INVENTION 
     An object of the present invention is to provide a filling device which enables reduction of overhead in remainder calculation and thereby improves the speed of processing. 
     According to a preferred embodiment of the present invention to attain the above object, a figure filling device to fill a figure on the memory defined by X-Y coordinates scan line by scan line with reference to the specified pattern comprises a coordinate storage means to store the coordinate data for the ends of the scan line to be newly filled, the coordinate data for the ends of the previously processed scan line, and the coordinate data for the reference point of the previous pattern, a pattern coordinate determination means to determine the coordinate data for reference point of the new pattern by operating the coordinate data for the ends of the scan line to be newly filled, the coordinate data for the ends of the previously processed scan line and the coordinate data for the reference point of the previous pattern stored in said coordinate storage means in filling of a new scan line, a pattern address determination means to determine the address on the memory corresponding to the coordinate of said reference point of the new pattern, a scan line address determination means to calculate the address on the memory corresponding to the coordinate of the ends of said newly filled scan line, a data processing means to read a filling pattern from said pattern address on the memory and scan line data from said scan line address on the memory, to perform predetermined processing using said filling pattern and said scan line data and to write the result to said scan line address, and an address update means to update said pattern address and said scan line address. 
     According to a further preferred embodiment, the pattern coordinate determination means uses the remainder from division where the value obtained by adding the difference between the coordinates for the ends of said new scan line from the coordinates for the ends of said previously processed scan line to said reference point of the previous pattern by the height and the width of said new scan line as the coordinate data of the reference point of the new pattern. 
     According to another preferred embodiment, the processing where said pattern coordinate determination means determines the coordinates for the reference point of the new pattern comprises a procedure to subtract the Y coordinate for the ends of said new scan line from the Y coordinate for the ends of said previous scan line and to add the Y coordinate of the reference point of said previous pattern, a procedure to take the remainder from the division to divide the result of the above operation regarding the Y coordinate by the height of the new pattern as the Y coordinate for the reference point of the new pattern, a procedure to subtract the X coordinate of the ends of said new scan line from the X coordinate of the ends of said previous scan line and to add the X coordinate for the reference point of said previous pattern and a procedure to take the remainder from the division to divide the result of the above operation regarding the X coordinate by the height of the new pattern as the X coordinate for the reference point of the new pattern. 
     According to still another embodiment according to the present invention to attain the above object, a figure filling device comprises a first processor provided with a coordinate storage means to store the coordinate data for the ends of the scan line to be newly filled, the coordinate data for the ends of the previously processed scan line, and the coordinate data for the pattern reference point, a coordinate determination means to determine the coordinate data for reference point of the new pattern by operating the coordinate data for the ends of the scan line to be newly filled, the coordinate data for the ends of the previously processed scan line and the coordinate data of the previous pattern reference point stored in said coordinate storage means in filling of a new scan line, a pattern address determination means to determine the address on the memory corresponding to the coordinate of said reference point of the new pattern and a scan line address determination means to calculate the address on the memory corresponding to the coordinate of the ends of said newly filled scan line, as well as a second processor provided with a data processing means to read a filing pattern from said pattern address on the memory and scan line data from said scan line address on the memory, to perform predetermined processing using said filling pattern and said scan line data and to write the result to said scan line address and an address update means to update said pattern address and said scan line address. 
     According to another preferred embodiment, the first processor transfers said pattern address and scan line address data to said second processor and is further provided with a control means to instruct the start of processing to the second processor upon completion of the data transfer. 
     Other objects, characteristics and effects of the present invention will be clarified by the detailed description below. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 is a block diagram to show the configuration of a figure filling device according to a first embodiment of the present invention; 
     FIG. 2 is a flowchart to illustrate the contents of the preprocessing by the figure filling device in FIG. 1; 
     FIG. 3 is a diagram to show an example of a tiling pattern coordinate system; 
     FIG. 4 is a diagram to show an example of coordinate system for area to be filled; 
     FIG. 5 is a flowchart to illustrate the contents of the actual filling processing by the figure filling device in FIG. 1; 
     FIG. 6 is a block diagram to show the configuration of a figure filling device according to a second embodiment of the present invention; 
     FIG. 7 is a diagram to show the procedures of pipeline processing by the figure filling device in FIG. 6; and 
     FIG. 8 is a diagram to compare the preprocessing procedure by the present invention with that by conventional method. 
    
    
     DESCRIPTION OF THE PREFERRED EMBODIMENT 
     Referring to the attached drawing figures, preferred embodiments of a figure filling device according to the present invention will be described. 
     FIG. 1 is a block diagram to show the configuration of a figure filling device according to a first embodiment of the present invention. This embodiment realizes the scan line fill supporting arbitrarily sized tiling patterns on relatively simple hardware. 
     A figure filling device according to this embodiment comprises a parameter input unit 10, a register file 20 provided with a plurality of registers, an arithmetic unit 30, a programmable controller 40, a memory control unit 50 and a data processing unit 60. The numerals 100 to 170 indicate buses. Control signals output from the programmable controller 40 to other components are omitted here. 
     The parameter data input to the device (coordinate data for scan lines and tiling pattern reference points as described later) are provided from the parameter input unit 10 via the bus 100 and stored in the predetermined register in the register file 20 comprising a plurality of registers. The processing starts when all parameters have been input. When the device is reset, all registers in the register file 20 are initialized to &#34;0&#34;. The output from this register file 20 is connected with two inputs of the arithmetic unit 30 via the buses 120 and 130. 
     The flow of processing is controlled by the programmable controller 40, which outputs all control signals such as operation timing signals and selection signals for access to the register file 20, the arithmetic unit 30, the memory control unit 50 and the data processing unit 60. The programmable controller 40 is provided with a program for figure filling as shown in FIGS. 2 and 5. 
     Now referring to FIGS. 2, 3 and 4, determination of reference points of tiling patterns (preprocessing) is described. 
     FIGS. 3 and 4 show coordinates for the tiling pattern and the area to be filled. The tiling pattern coordinate system in FIG. 3 has the origin of coordinates &#34;ORG&#34;, which is an arbitrarily given address, and defines the width of the tiling pattern &#34;W&#34; and its height &#34;H&#34;. In this system, any tiling pattern can be selected from a plurality of tiling patterns by updates with using the origin &#34;ORG&#34; as the pointer. Besides, a tiling pattern can be made to any size by change of the pattern width &#34;W&#34; and the height &#34;H&#34;. FIG. 3 shows a shaded tiling pattern. 
     The origin of the coordinate system for the area to be filled (subjected to drawing) in FIG. 4 can be set independently from that of the tiling pattern coordinate system. The filled area in the figure is divided into two scan lines 400 and 401. The scan lines 400 and 401 are continuous in the Y coordinate direction. In other words, the Y coordinate of the scan line 400 is larger than the Y coordinate of the scan line 401 by &#34;1&#34;. These scan lines 400 and 401 are filled by pasting the tiling pattern as shown in FIG. 3. Suppose the start point of the scan line already filled is (oldXs, oldYs), and its end point is (oldXe, oldYe); and the start point of the scan line to be newly filled is (newXs, newYs), and its end point (newXe, newYe). 
     FIG. 2 shows the contents of preprocessing for fill processing, which characterizes the present invention. Referring to FIG. 2, the Y coordinate for the reference start point of the tiling pattern &#34;newYp&#34; is determined in Steps 200 and 201. The value &#34;A&#34; in Step 200 is obtained by adding the difference between the Y coordinate &#34;oldYs&#34; for the previously processed scan line and the Y coordinate &#34;newYs&#34; for the scan line to be presently processed to the Y coordinate &#34;oldYp&#34; at the reference end point of the tiling pattern previously referenced. The remainder (mod) when dividing this &#34;A&#34; by the tiling pattern height &#34;H&#34; is the Y coordinate &#34;newYp&#34; at the reference start point of the tiling pattern. 
     In Steps 202 and 203, the X coordinate &#34;newXp&#34; at the reference start point of the tiling pattern is determined. The value &#34;B&#34; in Step 202 is obtained by adding the difference between the X coordinate &#34;oldXp&#34; for the end point of the previously processed scan line and the X coordinate &#34;newXs&#34; for the start point of the scan line to be presently processed to the Y coordinate &#34;oldXp&#34; for the reference end point of the tiling pattern previously referenced. The remainder (mod) when this &#34;B&#34; is divided by the tiling pattern width &#34;W&#34; is &#34;newXp&#34;. In other words, coordinates for the new reference start point is determined by calculating the position in relation to the previous reference point. Step 204 is the determination of a real memory address &#34;PA&#34; based on such coordinate values. In Step 204, the Y coordinate &#34;newYp&#34; of the reference start point is multiplied by the width &#34;PITCH&#34; of the entire tiling pattern coordinate system, and the X coordinate &#34;newXp&#34; of the reference start point and coordinate data of the origin &#34;ORG&#34; of the area where the tiling pattern is stored are added to the product of the above multiplication so as to determine the memory address &#34;PA&#34; from X-Y coordinates. 
     Referring to the configuration shown in FIG. 1, the flow of data in preprocessing shown in FIG. 2 is described now. The register file 20 stores as parameters the start point coordinates (oldXs, oldYs) and the end point coordinates (oldXe, oldYs) of the previously processed scan line, the start point coordinates (newXs, newYs) and the end point coordinates (newXe, newYe) of the newly filled scan line, coordinates of the reference end point (oldXp, oldYp) of the previously referenced tiling pattern, width &#34;W&#34; and height &#34;H&#34; of the tiling pattern and other data according to the predetermined order. 
     In execution of Step 200, the data at the addresses storing the Y coordinate &#34;oldYs&#34; for the reference end point of the previously referenced tiling pattern and the Y coordinate &#34;newYs&#34; for the presently processed scan line are read and input to the arithmetic unit 30. The arithmetic unit 30 determines the difference between the Y coordinate &#34;oldYs&#34; and the Y coordinate &#34;newYs&#34; and the result is stored via the bus 140 into the work register in the register file 20. The procedure up to here takes one clock. Then, the work register and the register storing the &#34;oldYp&#34; are read and subjected to addition at the arithmetic unit 30 and the result &#34;A&#34; is stored in the work register in the register file 20. 
     Next, the work register storing the arithmetic operation result &#34;A&#34; and the register to store the height &#34;H&#34; of the tiling pattern are read for remainder determination according to Step 201 at the arithmetic unit 30. The result of this determination is stored in the register as &#34;newYp&#34;. The X coordinates in Steps 202 and 203 are also subjected to the same operation. The arithmetic unit 30 multiplies the &#34;newYp&#34; determined according to Step 204 by the width &#34;PITCH&#34; of the pattern coordinate space and adds &#34;newYp&#34; to the product of the above multiplication. By further adding the origin &#34;ORG&#34; of the area storing the tiling pattern, the pattern address &#34;PA&#34; can be determined. 
     Now referring to the flowchart of FIG. 5, the fill processing executed after the completion of the above preprocessing is described. 
     In Step 500, the drawing address &#34;DA&#34; for the area to be actually filled is determined. &#34;DP&#34; designates the drawing pitch and &#34;DORG&#34; the origin of the area. Step 501 is the procedure to determine the number of pixels to be filled. This value serves as the counter for the number of loops in the filling routine. In Step 502, a tiling pattern is read from the address &#34;PA&#34;. In Step 503, data are read from the address &#34;DA&#34; in the filled area and subjected to the predetermined operation with the already read tiling pattern and the operation result is rewritten to the address &#34;DA&#34;. The predetermined operation here means so-called raster operation. Examples of such operation include replacement of the filled area with the read out tiling pattern and overwriting of the area. The number of loops is checked in Steps 504 and 505 and when the counter counts 0, the processing for one scan line is completed. 
     In Step 506, it is checked whether the reference point of the tiling pattern is at the right end. If so, the address and the X coordinate of the tiling pattern reference point are initialized in Steps 507 and 508. If not, both the X coordinate and the address are incremented in Steps 509 and 510. In Step 511, the filling address is incremented in horizontal direction. Thus, scan line fill is executed. 
     The determined address is transferred from the register file 20 to the memory control unit 50 via the bus 150 and then output to the external memory (not shown) via the bus 160. The data processing unit 60 inputs or outputs data to or from the external memory via the bus 170. The bus 170 for connecting with the external memory is an 8-bit bus. 
     FIG. 8 compares the time required for preprocessing between conventional method and the present invention. The conventional method does not require Steps 200 and 202, but in Step 201, needs five or six program loops of restoring method. Since a typical display unit has a resolution of 1280×1024 dots, coordinate representation of a point near the center of the screen requires about 10 significant bits for the X coordinate and 9 significant bits for the Y coordinate. Popular tiling patterns usually have about 4 significant bits vertically and horizontally, and the number of shifts equals the difference of their bits, which is 6 bits. Therefore, the loop of restoring is required 6 times for X and 5 for Y coordinates. The nearer the coordinates of the filled area is to 0, the smaller the number becomes, but approximately 75% area of the screen requires the above number of loops. 
     In contrast, the present invention generally requires only one restoring in Steps 201 and 203 particularly in a case where closely located areas are continuously filled such as in outline font function (scan lines are continuous in Y axis direction). The required number of execution clocks for instructions constituting the internal loop in Steps 201 and 203 is about 10 at least. Therefore, this invention can reduce the number of clocks to 30 clocks while the conventional method requires about 110 to 130 clocks for 11 to 13 loops in the entire step. As described above, the filling processing itself requires only 20 to 30 clocks for short scan lines, and what is essential is the improvement of calculation speed to obtain the reference start point for filling. 
     Next, referring to FIG. 6, the configuration of a figure filling device according to a second embodiment of the present invention is described. In FIG. 6, a figure filling device of the present invention divides the scan line fill processing into two processes performed by a preprocessor 300 and a pixel processor 310. 
     The preprocessor 300 comprises a parameter input unit 320, a register file 321, an arithmetic unit 323, and a programmable controller 325. The pixel processor 310 comprises a register file 322, an arithmetic unit 324, a programmable controller 326, a memory control unit 327 and a data processing unit 328. The numerals 340 to 351 indicate buses and the numeral 360 indicates a busy signal. The busy signal 360 disables data transfer from the preprocessor 301 while the pixel processor 310 is in operation. 
     The basic algorithm is the same as in the first embodiment. The description here focuses on how the two processors share the processing. 
     The preprocessor 300 is in charge of Steps 200 to 204 in FIG. 2 and Steps 500 and 501 in FIG. 5. The five parameters obtained from these steps including the pattern address &#34;PA&#34;, the drawing address &#34;DA&#34;, the number of filled pixels &#34;C&#34;, the pattern reference coordinate &#34;Xp&#34;, the pattern width &#34;W&#34; are transferred to the pixel processor 310. The pixel processor 310 is in charge of Steps 502 to 511 in FIG. 5. 
     Next, referring to FIG. 6 and the pipeline processing as shown in FIG. 7, the operation of the two processors is described now. In FIG. 7, the time from parameter data input to the parameter input unit 320 via the bus 341 to the storing of data into the register file 321 via the bus 341 is indicated by &#34;A&#34;. Upon completion of data input, the preprocessor 300 starts the processing at the timing &#34;B&#34;. The preprocessor 300 transfers the processed data to the pixel processor 310 at the timing &#34;C&#34;. Upon completion of data transfer, the pixel processor 310 starts processing at the timing &#34;D&#34;. At the same time, new parameters can be input to the preprocessor 300. Therefore, two scan lines can be filled simultaneously in the order of A, B, C and D. 
     In FIG. 7, the processing time for &#34;A&#34; and &#34;B&#34; at the second time and thereafter is hidden behind the processing time for &#34;D&#34;. In other words, thanks to the effect of pipeline processing, the total processing time depends solely on the time &#34;C&#34; for transfer to the pixel processor 310 and the processing time &#34;D&#34; at the pixel processor 310 in the steady state. In addition, even if the processing time at the preprocessor 300 is longer than that of the pixel processor 310, or the time A+B is longer than the time C+D, the total processing time is A+B. Therefore, when compared with the method using only one processor as in the first embodiment, the performance is expected to be improved twice at most. The components added to the first embodiment are a programmable controller 326, a register file 322, and an operation unit 324 only, resulting in much higher cost performance. For example, to double the processing speed of the device according to the first embodiment, doubled frequency may be used for the entire system, but this causes the price of the processor itself quite expensive and requires an external memory using doubled price chip, resulting in very high cost for the entire system. 
     The determination of the reference start point of a new tiling pattern is based on the reference end point of the previously processed tiling pattern in the first embodiment. However, it can be also realized using the reference start point of the previous tiling pattern. Such design is also in the scope of the preset invention. For relative determination of the reference point of the tiling pattern, the X coordinate of the scan line is updated for each drawing shown in FIG. 5 in the first embodiment. However, if such determination of reference start point of the new tiling pattern is based on the previous tiling pattern&#39;s reference start point as described above, the need of updating is eliminated. 
     When filling the area of more complicatedly shaped figures such as a triangle, a square, a trapezoid or other arbitrary polygons, so-called scan line conversion where the scan lines are determined based on the coordinates for the outline of the figure is required. For example, a triangle can be broken down into scan lines by generating X coordinates for two of the three edges at the same Y coordinate. This processing is to be performed with shifting the Y coordinate one by one. Accordingly, it is obvious that the scan line fill according to the present invention can be effectively applied to filling of any figure by means of combination with the higher level coordinate calculations. 
     The buses 170 and 351 for communication with the external memory in the first and the second embodiments have 8 bits, because they assume a 256 color display with 8 bits for one pixel. However, for the purpose of the present invention, the number of bits in such buses may be 16, 24 or any other value. In addition, when applied to a memory having a plurality of pixels in a word (so-called packed pixel configuration), the present invention can be easily realized by adding a shift and merge mechanism for pattern data at the data processing unit 60 or the data processing unit 328. The shift and merge mechanism is the technology in public domain adopted in commercially available LSI for graphics processing as the technology for transfer of data in a rectangular area or bit block transfer. The present invention can be realized for any pixel having any number of bits and any word length. 
     This invention does not limit the type of raster operation at the data processing unit 60 or 328. Besides, the address may be determined with the hardware multiplier incorporated in the arithmetic unit 30 or 323, or alternatively calculated by repetitive additions of microprogram control type in the above embodiment. 
     Obviously many modifications and variations of the present invention are possible. It is intended to cover in the appended claims all such modifications as fall within the true spirit and scope of the invention.