Patent Publication Number: US-4580236-A

Title: Graphic display apparatus with a vector generating circuit

Description:
BACKGROUND OF THE INVENTION 
     The present invention relates to a graphic display apparatus with a vector generating circuit. 
     As a vector generating system in the graphic display apparatus, the Bresenham system is been well known. It is described in detail in an article &#34;Algorithm for Computer Control of a Digital Plotter&#34; by J. E. Bresenham, IBM Syst. J4(1), 25-30, 1965. Therefore, it is briefly explained here. 
     As shown in FIG. 2, when a start point P s  and an end point P E  of a vector are given, q m  and q n  are compared in order to select one of points P i  and P j  to be displayed next to P s . The selected one is closer to a straight line to be displayed. In an example of the vector shown in FIG. 2, ##EQU1## where ΔX is a distance in X-direction and ΔY is a distance in Y-direction. An initial value R o  in a discrimination R is defined by the following, 
     
         R.sub.o =ΔX*(q.sub.m -q.sub.n)=2*ΔY-ΔX   (4) 
    
     When R o  ≧0, P j  is selected, and when R o  &lt;0, P i  is selected. When one of points P i+1  and P j+1  is selected, the next value R 1  for the discrimination is given by the following, 
     
         R.sub.1 =ΔX*(q.sub.m+1 -q.sub.n+1)=R.sub.0 +2*(ΔY-ΔX)(5) 
    
     if P j  was selected previously, and 
     
         R.sub.1 =ΔX*(q.sub.m+1 -q.sub.n+1)=R.sub.0 +2*ΔY(6) 
    
     if P i  was selected previously. Depending on which one of P j  and P i  was selected previously, that is, on a sign of the previous discrimination R 0 , an increment 2*(ΔX-ΔY) or 2*ΔY is added to the discrimination R 0  in order to obtain the next discrimination R 1 . In the illustrated example, all of ΔX, ΔY and ΔX-ΔY are positive or zero. Depending on the combination of the signs of ΔX, ΔY and ΔX-ΔY, the value of the discrimination R differs from that described above and the address is determined by incrementing or decrementing. Many prior art pattern processing apparatus generate the vectors by the Bresenham system but they take a long time to generate the vectors because the addresses are generated by microprograms. 
     The vector generation method is briefly explained below. FIG. 1 shows a graphic display apparatus previously considered and attempted by the present inventors but not known in public. Numerals 101-103 denote registers for storing an initial value R, a positive increment P and a negative increment N, respectively, numeral 108 denotes an arithmetic logic unit (ALU), numeral 109 denotes a circuit for generating an address of a microinstruction, numeral 110 denotes a control storage for storing the microinstruction, numeral 111 denotes a microinstruction decode circuit, numeral 112 denotes a register for holding an X-direction end address X E  of a vector, numeral 113 denotes a register for holding a Y-direction end address Y E , numeral 114 denotes a counter for holding an X-direction write address X s , numeral 115 denotes a register for holding a Y-direction write address Y s , numerals 116 and 117 denote compare circuits, numeral 118 denotes an AND gate, numeral 119 denotes a refresh memory for storing information of each picture cell at each position corresponding to the picture cell on a display device (not shown), numeral 120 denotes a write timing signal generating circuit for the refresh memory 119, numeral 121 denotes an AND gate, and numeral 122 denotes a write data forming circuit for the refresh memory 119. The method for generating the vector in the above graphic display apparatus is now explained in connection with an example in which a vector from a point (X o , Y o ) to a point (X 3 , Y 2 ) shown in FIG. 2 is generated. Based on the Bresenham algorithm, the initial value R of the discrimination, the positive increment P and the negative increment N are calculated by the following formulas. 
     
         R=2*ΔY-ΔX                                      (1) 
    
     
         P=2*(ΔY-ΔX)                                    (2) 
    
     
         N=2*ΔY                                               (3) 
    
     where ΔY is a Y-direction component (Y E  -Y s ) of the vector, and ΔX is an X-direction component (X E  -X s ). In the example shown in FIG. 2, ΔY=2 and ΔX=3, and R, P and N are 1, -2 and 4, respectively. It is now assumed that R, P and N are set in the registers 101-103 of FIG. 1, the start point (X 0 , Y 0 ) is set in the counters 114 and 115 and the end point (X 3 , Y 2 ) are set in the registers 112 and 113. FIG. 3 shows only a portion of vector generating microprogram stored in the control storage 110 of FIG. 1. Referring to the microprogram of FIG. 3, when a microinstruction 301 is fetched from the control storage 110, a control line 144 for designating the writing to the refresh memory 119 is enabled by the decoder 111. The signal on the control line 144 is ANDed with an output timing signal 135 from the timing signal generator 120 by the AND gate 121 to produce a write pulse 133 to the refresh memory 119. The outputs of the counters 114 and 115 are supplied to the refresh memory 119 as addresses. In the present example, a dot is generated at the position (X 0 , Y 0 ) shown in FIG. 2. The data to be written into the refresh memory 119 is determined by an output signal 136 from the data generator 122. When the refresh memory 119 comprises a plurality of planes each corresponding to one color, the data may be a plurality of bits each corresponding to one color. In the present example, however, for the sake of simplicity, the colors are ignored and it is assumed that the refresh memory 119 comprises one plane which stores only intensity data. It is assumed that the data line 136 always carries a logical &#34;1&#34; signal. When a microinstruction 302 is next fetched from the control storage 110, the microinstruction address generating circuit 109 generates an address of a microinstruction 303 if the conditioning signal 134 is valid, and generates an address of a microinstruction 308 if the signal 134 is invalid. The conditioning signal 134 is an AND function of the signals 137 and 138 and the compare circuit 116 renders the signal 134 valid when the contents of the registers 112 and 114 are equal, and the compare circuit 117 renders the signal 138 valid when the contents of the registers 113 and 115 are equal. In the present example, the conditioning signal 134 is valid when the address reaches the point (X 3 , Y 2 ). Accordingly, when the address is at the point (X 0 , Y 0 ), the microinstruction address generating circuit 109 generates the address of the microinstruction 303 as the next microinstruction address. When the microinstruction 303 is fetched, the control line 140 is enabled by the decoder 111. The control line 140 causes the counter 114 to count up. The microinstruction 304 is next fetched and the microinstruction address generating circuit 109 generates the address of the microinstruction 305 as the address of the microinstruction to be next fetched if the conditioning signal 139 is valid, and generates the address of the microinstruction 307 if the conditioning signal 139 is invalid. The conditioning signal is rendered valid by the ALU 108 when the content of the register 101 is positive. In the present example, the content R is 1 and the microinstruction 305 is next fetched. The microinstruction 305 renders the control line 142 valid, which causes the counter 115 to count up. When the microinstruction 306 is next fetched, the contents of the registers 101 and 102 are added in the ALU 108 to produce a sum and the sum is stored in the register 101 through a bus 130. A control signal therefor is similar to a control signal in a conventional microprogram controlled system and hence it is omitted in FIG. 1. The microinstruction 307 is executed when the conditioning signal 139 is invalid. It instructs to add the contents of the registers 101 and 103 and store a sum in the register 101. After the execution of the microinstruction 306 or 307, the address generating circuit 109 is controlled to fetch the microinstruction 301. The above microinstructions are executed until the conditioning signal 134 becomes valid. As a result, dots are generated at points (X 0 , Y 0 ), (X 1 , Y 1 ), (X 2 , Y 1 ) and (X 3 , Y 2 ) shown in FIG. 2, so that a vector is generated. 
     In the vector generation method, in the graphic display apparatus described above, five to six microinstructions are needed to generate one dot, the vector cannot be generated at a high speed. 
     SUMMARY OF THE INVENTION 
     It is an object of the present invention to provide a graphic display apparatus capable of generating a vector at a high speed. 
     In order to achieve the above object, in accordance with an aspect of the present invention, there are provided registers for storing the value R of the vector discrimination, the positive increment P and the negative increment N, and flip-flops for storing magnitude information of ΔX, ΔY, and ΔX-ΔY. Depending on the contents of those flip-flops, the address counter of the refresh memory is counted up or down. In addition, a control circuit for updating the value R of the vector discrimination is provided. In this manner, the vector can be generated at a high speed. The registers and the flip-flops are constructed in two stages so that the data for generating the next vector can be prepared while the current vector is generated. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 shows a configuration of a graphic display apparatus, previously considered by the present inventors, 
     FIG. 2 shows an example of vector to be generated by the apparatus of FIG. 1, 
     FIG. 3 shows a microprogram flow in the dot generation used in the apparatus of FIG. 1, 
     FIG. 4 shows a graphic display apparatus in accordance with one embodiment of the present invention, 
     FIG. 5 shows a vector generating circuit used in FIG. 4, 
     FIG. 6 shows a microprogram for starting the vector generating circuit used in the present invention, and 
     FIG. 7 shows a timing chart for generating the vector. 
    
    
     DESCRIPTION OF THE PREFERRED EMBODIMENTS 
     FIG. 4 shows a graphic display apparatus in accordance with an embodiment of the present invention. In FIG. 4, the like numerals to those shown in FIG. 1 designate like elements. Numeral 500 denotes a vector generating circuit. Numerals 414 and 415 denote counters in which start addresses X s  and Y s  of a vector to be generated are set, respectively, and numerals 412 and 413 denote registers in which end addresses X E  and Y E  of the vector are set, respectively. Numerals 104 and 105 denote registers for an X-address (X s ) and Y-address (Y s ) of a start point P s , respectively. Numerals 106 and 107 denote registers for an X-address (X E ) and Y-address (Y E ) for an end point P E , respectively. FIG. 5 shows a detail of the vector generating circuit 500. Numerals 501 and 531 denote registers for storing the positive increment P, numerals 502 and 532 denote registers for storing the negative increment N, numeral 503 denotes a multiplexer, numeral 504 denotes an adder, numeral 505 denotes a multiplexer, numerals 506 and 536 denote registers for holding the value R of the discrimination, numeral 507 denotes an inverter, numeral 508 denotes a flip-flop for storing a sign of ΔX, numeral 509 denotes a flip-flop for storing a sign of ΔY, numeral 510 denotes a flip-flop for storing a sign of ΔX-ΔY, numerals 511-513 denote flip-flops for storing the contents of the flip-flops 508-510, respectively, numerals 514 and 515 denote OR gates, numerals 516-519 denote NAND gates and numeral 520 denotes a flip-flop for indicating that the vector generating circuit 500 is in operation. 
     In order to explain the present embodiment, reference is again made to FIG. 2 to explain the example in which the vector from the point (X 0 , Y 0 ) to the point (X 3 , Y 2 ) is generated. It is assumed that the value R of the discrimination, the positive increment P and the negative increment N in the registers 101-103, respectively, have been set in the registers 506, 501 and 502, respectively, and the start point (X 0 , Y 0 ) and the end point (X 3 , Y 2 ) have been set in the counters 414 and 415, respectively. The sign of ΔX is set in the flip-flop 508, the sign of ΔY is set in the flip-flop 509 and the sign of ΔX-ΔY is set in the flip-flop 510. Signals for these signs have a logical &#34;0&#34; for a plus sign and a logical &#34;1&#34; for a minus sign. In the present example, ΔX, ΔY and ΔX-ΔY are 3, 2 and 1, respectively. Accordingly, all of the flip-flops 508, 509 and 510 are set to &#34;0&#34;. FIG. 6 shows that portion of the microprogram stored in the control storage 110 of FIG. 4, which generates the vector. Referring to FIG. 6, the microinstructions 602 to 612 are executed in order to prepare data necessary for execution of a microinstruction 613, as will be explained later on. When a microinstruction 613 is fetched from the control storage 110, the control line 401 is rendered valid by the decoder 111. In response to the signal on the control line 401, the flip-flop 520 is set as shown in FIG. 7 and the contents of the flip-flops 508-510 are set to the flip-flops 511-513, respectively. The registers 531 and 532 store the outputs of the registers 501 and 502, respectively, in response to the signal 401. The register 536 stores the output of the multiplexer 505 in response to the signal 401. The multiplexer 505 selects the register 506 or the line 524 depending on whether the signal 402 is &#34;0&#34; or &#34;1&#34;. At the rise of the signal 401, the signal 402 is still &#34;0&#34;. Thus, the multiplexer 505 selects the register 506 at this time. Accordingly, the register 536 stores the value R of the register 506 in response to the signal 401. In the present embodiment, the contents of the flip-flops 511-513 are logical &#34;0&#34; and the values X 0 , Y 0 , X 3  and Y 2  are set in the registers 112, 113, 114 and 115, respectively, and the values -2 and 4 are set in the registers 531, 532 and 536. When the flip-flop 520 is set, the signal line 402 is rendered valid. The signal on the signal line 402 is ANDed with the output timing signal 135 from the timing signal generator 120 by the AND gate 121 to produce a timing pulse T 1  which is applied to the refresh memory 119 as a write signal 133. At this moment, the outputs of the counters 114 and 115 are supplied to the refresh memory 119 as the address signal. In the present embodiment, the address is (X 0 , Y 0 ) and &#34;1&#34; is written at the addressed position of the refresh memory 119 at the timing T 1  of FIG. 7. The multiplexer 503 selects the line 521 when the control line 527 is logical &#34;0&#34; and selects the line 522 when the control line 527 is logical &#34;1&#34;, and connects the selected line to the line 523. The control line 527 is connected to a sign bit field of the register 536 and it is logical &#34;0&#34; when the value of the register 536 is zero or positive, and logical &#34;1&#34; when it is negative. The write signal 133 is also supplied to the register 536. At the rise of the pulse T 1 , the signal 402 is already &#34;1&#34; so that the multiplexer 505 selects the line 524. On the other hand, the register 536 stores &#34;+1&#34; at this time and the signal 527 is &#34;0&#34;. Accordingly, the multiplexer 503 selects the line 521 and the output is &#34;-2&#34;. Accordingly, the adder 504 adds the output &#34;-2&#34; and the output &#34;1&#34; of the register 536 to produce an output &#34;-1&#34;. Accordingly, at the rise of the write pulse T 1 , the multiplexer 505 produces the output &#34;-1&#34;. 
     In this manner, the value &#34;-1&#34; is set in the register 506 by the write pulses T 1  as shown in FIG. 7. 
     On the other hand, the write signal 133 is also supplied to the NAND gates 516-519. Those gates are connected to the flip-flops 511-513 through the OR gates 514 and 515. The OR gate 514 receives an inverted output of the flip-flop 513 and an inverted output of the sign bit of the value R of the register 536, inverted by the inverter 507. Accordingly, the OR gate 514 produces an output &#34;1&#34; when ΔX-ΔY≧0 or R≧0. The OR gate 515 receives the output of the inverter 507 and the non-inverted output of the flip-flop 513. Accordingly, the OR gate 515 produces an output &#34;1&#34; when ΔX-ΔY&lt;0 or R≧0. The NAND gate 516 receives the output of the OR gate 514, the inverted output of the flip-flop 511 and the write pulse 133. Accordingly, the output 406 of the NAND gate 516 is &#34;0&#34; in response to the write pulse 133 when ΔX≧0 and ΔX-ΔY≧0 or R≧0. Unlike the NAND gate 516, the NAND gate 517 receives the non-inverted output of the flip-flop 511. Accordingly, the output 407 of the NAND gate 517 is &#34;0&#34; in response to the write pulse 133 when ΔX&lt;0 and ΔX-ΔY≧0 or R≧0. The NAND gate 518 receives the inverted output of the flip-flop 512 and the output of the OR gate 515. Accordingly, the output 408 of the NAND gate 518 is &#34;0&#34; in response to the write pulse 133 when ΔY&lt;0 and ΔX-ΔY&lt;0 or R≧0. Unlike the NAND gate 518, the NAND gate 519 receives the non-inverted output of the flip-flop 512. Accordingly, the output 409 of the NAND gate 519 is &#34;0&#34; in response to the write pulse 133 when ΔY&lt; 0 and ΔX-ΔY&lt;0 or R≧0. The AND gates 517 and 519 are effective to count down the address (for example, when the vector is to be generated from P E  to P s  in FIG. 2). In the present embodiment, they always produce outputs &#34;0&#34;. As described above, in the present embodiment, ΔX, ΔY and ΔX-ΔY are positive, and the content of the register 536 is &#34;1&#34; when the write pulse T 1  on the line 133 is generated. Accordingly, the gates 516 and 518 are enabled and the signals 406 and 408 are &#34;0&#34;. The signals 406 and 407 are supplied to the address counter 114 and the signals 408 and 409 are supplied to the address counter 115. When the signals 406 and 408 change from &#34;0&#34; to &#34;1&#34;, the address counters 114 and 115 count up, respectively, and when the signals 407 and 409 change from &#34;0&#34; to &#34;1&#34;, the counters 114 and 115 count down, respectively. In the present embodiment, at the end of writing of the refresh memory 119, that is, when the signal 133 changes from &#34;1&#34; to &#34;0&#34;, the signals 406 and 408 change from &#34;0&#34; to &#34;1&#34; and the contents of the address counters 114 and 115 represent X 1  and Y 1 , respectively. At this time, the outputs of the compare circuits 116 and 117 are &#34;0&#34;. Accordingly, the signal 134 from the AND gate 118 is not valid and the flip-flop 520 remains in the set state. Therefore, when the next output timing signal 135 is generated, &#34;1&#34; is written into the address (X 1 , Y 1 ) of the refresh memory 119 by the write pulse T 2  shown in FIG. 7. When the write signal 133 changes to &#34;1&#34;, the content of the register 536 is &#34;-1&#34; and only the gate 406 is enabled and the contents of the address counters 114 and 115 are X 2  and Y 1 , respectively. The multiplexer 503 selects the line 522 because the value of the register 536 is negative, and a new value &#34;3&#34; is set in the register 536. When the next write pulse T 3  is applied to the signal line 135, &#34;1&#34; is written into the address (X 2 , Y 1 ) of the refresh memory 119, and at the end of writing, the content of the register 536 is &#34;1&#34;, and when the signals on the lines 406 and 408 change from &#34;0&#34; to &#34;1&#34;, the address counters 114 and 115 are counted up to represent X 3  and Y 2 , respectively. After the dot has been generated at (X 3 , Y 2 ), the flip-flop 520 is reset by the signal line 531. This state is informed to the microinstruction address generating circuit 109 through the signal line 402. During the generation of the dot, the microinstructions 602-612 (FIG. 6) from the control storage 110 are executed in parallel with the dot generation. The microinstruction 602 supplies the control signal to the ALU 108 to subtract the content of the register 104 from the content of the register 106 to set the sign of ΔX of the vector to be next generated in the flip-flop 508, and produces the control signal 421 to set the sign 542 in the flip-flop 508. The microinstructions 603 and 604 produce the control signal 420 to the ALU 108 to set the sign of ΔY in the flip-flop 509 and set the sign of ΔX-ΔY in the flip-flop 510, respectively, and produce the control signals 422 and 423 to set those signs 542 in the flip-flops 512 and 513, respectively. Similarly, the microinstructions 605-611 produce the control signal 420 to supply the contents of the registers 101, 102, 103, 104, 105, 106 and 107 to the bus 130 to set the values of P, N, R, X s , Y s , X E  and Y E  in the registers 501, 502, 506, 414, 415, 412 and 413, respectively, and produce the control signals 424, 425, 426, 427, 428 and 429 for setting. The microinstruction 612 controls the microinstruction address generating circuit 109 to fetch the microinstruction 613 if the conditioning signal 402 is valid and fetch the microinstruction 612 if the conditioning signal 402 is invalid. Thus, at the end of the dot generation, the conditioning signal 402 is valid and the control is shifted to the microinstruction 613 to execute the next processing. 
     In this manner, the preparation for generating the next vector is carried out during the generation of the current vector. In the present embodiment, the registers are of two-stage configuration. Even when the registers 412, 413, 414, 415, 501, 502 and 506 and the flip-flops 508, 509 and 510 are not provided, it is possible to generate the vector at a higher speed than the prior art previously considered graphic display apparatus and the purpose of the present invention is attained. 
     As described hereinabove, according to the present invention, the dot can be generated at the same speed as that of the execution of one microinstruction and hence the vector can be generated five to six times faster than the apparatus of FIG. 1. Since the microprogram control unit can process other jobs during the generation of the vector, the initial value necessary to generate the next vector can be set and the high speed processing is attained.