Patent Publication Number: US-4653108-A

Title: Electrical circuit for a microprocessor graphic system

Description:
BACKGROUND OF THE INVENTION 
     The present invention relates to an electrical circuit for determining the resultant inner and outer contours of multiple polygonal superposed images stored in a memory unit. Such images are frequently used to represent sections of a workpiece and tool in microprocessor controlled numerical machine stations. 
     In using these tools, it is frequently advantageous to check the accuracy of the programming with the aid of a graphical representation of the processed workpiece. 
     Multidimensional representation of workpieces by sectional representation on microprocessor based graphic systems using software display algorithms is common practice. However, this representation is costly in terms of the apparatus and the computational time required. The computational time is especially critical in real time graphic display systems. Simple less expensive microprocessor systems can be used for the graphics display, but the quality of the representation is sacrificed due to the limited computational abilities of these microprocessor systems. Such systems are described in European Pat. Nos. EP-A2-0 089 561 and EP-A2-0 089 562. Also a display device using a read/write memory selectively addressable by an address unit is described in German No. DE-A-28 50 710. To date, commonly used software for generating workpiece images on microprocessor based graphic systems is not totally satisfactory for real time representation. 
     SUMMARY OF THE INVENTION 
     The present invention is directed to an electrical circuit for use in the graphics component of numeric machine tool controls, which operates simply and rapidly to generate real time graphic representations. 
     According to this invention, an electrical circuit is provided for determining the inner and outer contours of several polygonal superposed stored images. This circuit includes a memory unit which comprises a plurality of individually addressable memory cells sufficient to store the superposed images. This memory unit further comprises address inputs for selecting the memory cell to be accessed and an output for communicating the contents of the cell addressed. An address logic is provided in electrical communication with said memory unit address inputs, and a temporary storage element is provided in electrical communication with said memory unit output. A flow control unit is electrically connected with the address logic unit the temporary storage element and operates to sequence said address logic unit and said temporary storage element. The memory unit, the address logic unit, the temporary storage unit and the flow control unit all cooperate to access a cell of the memory unit with an address which is dependent upon the contents of the previously addressed cell of the memory unit. The dependent claims set forth further advantageous features of this invention. 
     An advantage of the present invention is that it allows an unsophisticated computer control graphics system to graphically display structures in an efficient manner because the invention uses a hardware implemented algorithm rather than a software program. The circuit of the present invention reduces the time required for the graphic representation by one or two orders of magnitude in comparison with software oriented display systems. 
     Another particular advantage of the preferred embodiment described below is the ability of the circuit to be integrated with other components to construct a graphics display controller for displaying images. When used in conjunction with numeric machine tools, the high speed graphics processing capability of the present invention allows the display of a real time representation of the effect of the tool on a work piece in three dimensions. These images provide the machine operator with a valuable aid. 
     The invention itself, together with further objects and attendant advantages, will best be understood by reference to the following detailed description, taken in conjunction with the accompanying drawings. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 is a schematic representation of a preferred embodiment of the graphic control circuit of this invention. 
     FIG. 2 is a schematic diagram showing the manner in which the outer contour of two section planes, offset obliquely with respect to one another, is determined by the circuit of FIG. 1. 
     FIG. 3 is a schematic diagram showing the manner in which the inner contour of two section planes, offset obliquely with respect to one another, is determined by the circuit of FIG. 1. 
    
    
     DETAILED DESCRIPTION OF THE PRESENTLY PREFERRED EMBODIMENTS 
     The electrical circuit shown in FIG. 1 employs a memory unit M into which the superposed images are stored. The memory unit M contains a plurality of memory cells, and each cell is individually addressable and contains an image point datum, called a pixel. 
     The address logic unit A is capable of addressing each individual image point and contains two up-down counters ZX and ZY, which are controlled by four bistable flip-flop circuits FF1-FF4. The input signals to the flip-flop circuits FF1-FF4 are generated by a logic network G1-G6 which in turn receives input data from the image point memory unit M, thereby creating a recursive network. To determine the contour of several overlapping images, the initial coordinates are deposited into the address counters ZX and ZY. In the example shown in FIG. 2, these coordinates are X=3, Y=3. The counting direction to the next image point to be searched is determined from the path of the contours and deposited into the flip-flops FF1-FF4. For example, the next image point to be tested in FIG. 2 has coordinates X=2, Y=3. 
     In order for the address logic unit A to control the counters ZX and ZY to follow a line in the desired X- or Y-direction, the following logical conditions control: 
     
         XR.sub.n+1 =YR.sub.n ⊕P.sub.n                          (1) 
    
     
         YR.sub.n+1 =XR.sub.n ⊕P.sub.n                          (2) 
    
     
         XI.sub.n+1 =(XR.sub.n ⊕YR.sub.n)·P.sub.n      (3) 
    
     
         YI.sub.n+1 =(XR.sub.n ⊕YR.sub.n)·P.sub.n      (4) 
    
     The signals XR and YR control the counting direction of the respective counters ZX and ZY (1=forward, 0=backward). XI and YI represent the counter enabling signals (1=counter inhibited, 0=counter enabled). P n  is the content of the memory cell containing the image point stored at the address represented by the control signals XR n , YR n , XI n , and YI n . Of the sixteen possible combinations of these variables only eight are permitted. The eight signals determine the addressing of the image point as left, right, up, down, up left diagonal, down left diagonal, up right diagonal, and down right diagonal. These directions are controlled by the equations (1)-(4) above. 
     In initializing these variables it should be understood that an allowed combination must be chosen. The following equations establish the allowed combinations: 
     
         XR=YR for XI=1                                             (5) 
    
     
         YR=XR for YI=1                                             (6) 
    
     Because equations (1)-(4) above are recursive, the four flip-flops FF1-FF4 are used as temporary storage for the feedback linkage network G1-G6. The output signals XR and YR are connected to the Up-Down inputs V/R of the two address counters ZX and ZY, respectively. And, the inhibiting signals XI and YI are connected to the Count Enable inputs E of the counters ZX and ZY, respectively. These four variables therefore establish whether and in what direction the counters ZX and ZY count the subsequent clock impulse that is supplied over the line S1 by the flow control S. FF5 is used to temporarily store the state of the image element (pixel on or pixel off) just addressed, and the output of FF5 delivers the signal P. 
     The clock inputs CL of the counters ZX and ZY, and the flip flops FF1-FF5 are controlled by the signals S1-S3 of the flow control S. These signals are required because of the set up times and access times of the individual components. Flip-flop FF6 and logic gate G7 generate an interrupt signal I when two consecutive image points, P n  and P n+1  are equal. This occurs when a corner point is reached. 
     As noted in FIGS. 2 and 3 it is evident that the signal P stored in FF5 for the image point memory cell, always contains alternate values of 0, 1, 0, 1 etc., when processing a straight line. A right corner is determined by the detection of an activated pixel to the right of the straight line. A left corner is determined by the detection of an activated pixel to the left of the straight line. Hence upon reaching a right corner the value 0 would be stored twice in succession in FF5. Similarly, on reaching a left corner the value 1 would be stored twice in succession in FF5. Flip-flop circuit FF6 delays the signal P by one cycle of S2 and the resultant signal V, when exclusively OR&#39;d with the original signal P and negated, forms the signal I. Therefore, when a corner point is determined, I is activated and may be used to signal a microprocessor to read the contents of counters ZX, ZY. 
     The following table illustrates the operation of the linkage rules of equations (1)-(4): 
     
         ______________________________________                                    
XR         XI    YR       YI  P                                           
______________________________________                                    
n     0        0     1      1   0                                         
n + 1 1        0     1      0   1                                         
n + 2 0        0     1      1   0                                         
n + 3 1        0     1      0   1                                         
n. . .                                                                    
      0        0     1      1   0                                         
                                          Right Corner                    
n. . .                                                                    
      1        0     1      0   0                                         
n. . .                                                                    
      1        0     0      0   1                                         
n. . .                                                                    
      1        1     1      0   0                                         
n. . .                                                                    
      1        0     0      0   1                                         
n. . .                                                                    
      1        1     1      0   0                                         
n. . .                                                                    
      1        0     0      0   1                                         
                                          Left Corner                     
n. . .                                                                    
      1        1     1      0   1                                         
n + i 0        0     1      1   0                                         
______________________________________                                    
 
    
     The flow control S generates the periodic timing signals S1, S2 and S3. S1 carries a counting impulse to activate counters ZX and ZY. S2 activates flip-flops FF5 and FF6 and is delayed from S1 a sufficient time for the addressed memory cells to be accessed. And S3 is used to latch flip-flops FF1-FF4. 
     When a corner has been found, I=1 and the flow control S is stopped. Not that the address counters after recognizing a corner point do not exactly reproduce the corner coordinates. In the example, the counters indicate a corner coordinate of X=3, Y=12; however, the corner is actually located at X=3, Y=11. This deviation of one bit can be corrected with an adding circuit in the read-out of the coordinates. It is also possible to correct the corner coordinates by interposing several gates in the control lines XR, YR, XI, and YI to alter the counter state in an intermediate cycle of the flow control S. The coordinates can then be read out and the old counter state restored. Once the flow control S has been halted at I=1 and the addresses XR and YR have been read, the flow control S can again be started and the process continued. 
     In order to detect a completed revolution, the locations of the first corner coordinates detected, X o  and Y o , can be stored and then compared through exclusive OR gates with the counter state. If the contents of counters XR and YR equal the contents of the stored values X o  and Y o , respectively, all corner coordinates of the polygonal contour have been detected and transferred to the microprocessor. 
     The determination of the inner contour as shown in FIG. 3 is analogous to the above described procedure for determining the outer contour once the initial coordinates and counting directions are initialized into counters ZX and ZY and into flip-flops FF1-FF4. 
     The circuit of the present invention can readily be combined with a vector generator, a refresh control for dynamic memory, and interrupt logic to create a three dimensional graphic controller. The hardware approach to graphic processing taken by the present invention can result in an increase in processing speed of one to two orders of magnitude over a comparable software algorithm. This increase in processing speed enables even simple microprocessor based graphic display systems to display complex representations in real time. 
     The foregoing detailed description has been given for illustrative purposes only. A wide range of changes and modifications can be made to the preferred embodiment described above. It should be understood that it is the following claims, including all equivalents, which are intended to define the scope of this invention.