Abstract:
Pixel processors each having a depth register, an intensity register and an adder are connected in a linear array. Each pixel processor processes one pixel on a horizontal scan line. A token having plane segment information is shifted in one direction in the array, and each pixel processor updates the registers while it performs hidden surface elimination in a time-division fashion. A refresh token for an intensity data output is also shifted in one direction, and intensity data stored in each pixel processor is supplied to an intensity data bus. A hardware of the pixel processor is very much simplified and LSI implementation is facilitated while maintaining a high image output rate.

Description:
BACKGROUND OF THE INVENTION 
     1. FIELD OF THE INVENTION 
     The present invention relates to means for eliminating hidden surface in a three-dimensional computer graphics device for displaying a three-dimensional polyhedral object on a two-dimensional screen. 
     2. DESCRIPTION OF PRIOR ART 
     When a three-dimensional object is to be displayed on a two-dimensional screen, it is necessary to deal with a phenomenon in which a front object hides all or a portion of a rear object. In general, a scan line algorithm which serially processes by a general purpose processor and a Z-buffer algorithm which is suitable for hardware implementation have been known. In the Z-buffer algorithm, color and intensity (hereinafter simply referred to as intensity) of a plane to be displayed and a depth of the plane are stored for each pixel, and each time a new plane is inputted, the stored depth and a new plane depth are compared, and only when the new plane depth is smaller, the stored depth is updated and intensity data of the new plane is registered. When depth registers (generally called Z buffer) are provided for all pixels, a very large memory is required but a control logic is relatively simple. 
     On the other hand, in the scan line algorithm, the fact that when intensity data of each pixel is to be displayed for each raster scan like in a CRT, adjacent pixels and pixels on immediately adjacent scan lines have very strong correlation with the current pixel, is taken into account. It is suitable for a sequential processor but requires many operations and the control logic is complex. 
     As an intermediate method of those hidden line elimination algorithms, an algorithm which utilizes the correlation for cross-scan line and the Z-buffer algorithm within the line has been proposed by N. Gharachorloo et al, &#34;Super Buffer: A Systolic VLSI Graphics Engine for Real Time Raster Image Generator&#34;, 1985 Chapel Hill Conference on Very Large Scale Integration, pp. 285-305. 
     FIG. 1 shows a system block diagram of the proposed means for eliminating hidden surface. Numeral 100 denotes a pixel processor, provided one for each of pixels on an N-pixel scan line. The pixel processor comprises a pixel number register which stores a location of the pixel on the scan line, a depth register which stores a depth coordinate of a plane which is present frontmost as viewed from the pixel location, an intensity register which stores intensity information of the plane, adders for updating the depth coordinate, a pixel number comparator and a depth coordinate comparator. 
     An operation of the means for eliminating the hidden surface thus configured is now explained with reference to a conceptual chart shown in FIG. 2. 
     As shown in FIGS. 2A and 2B, a plane 200 defined in a three-dimensional space (generally called normalized device coordinates) including X and Y coordinates corresponding to an M × N two-dimensional screen and depth information or Z coordinate, is projected onto an XY plane to display it on the screen. In a raster scan type CRT, this process is performed for each horizontal scan. The process is done on the XZ plane sectioned along a current scan line. A sectional plane sectioned along the current scan line is called a plane segment 201. Each plane segment has left end coordinates (X L , Z L ), a right end X coordinate X R , a Z coordinate displacement per unit pixel dZ/dX (hereinafter designated by Z&#39;) and intensity information I. Tokens having those information are supplied to the leftmost pixel processor 100 of the array of pixel processors provided one for each pixel as shown in FIG. 1. Each pixel processor 100 first determines if its location ID on the scan line (pixel number register) meets 
     
         XLi ≦ ID ≦ XRi                               (1) 
    
     If it is met, the pixel processor determines if the Z coordinate Zi of the input token is smaller than data Zb stored in the depth register. If it is met, the data Zi and the intensity information Ii in the input token are stored into the depth register and the intensity register, respectively. When the relation (1) is met, the Z coordinate displacement Zi&#39; is added irrespective of the magnitude of the Z coordinate, and other parameters are outputted as they are to the right side pixel processor. 
     When all plane segments on one scan line have been inputted in the form of token to the leftmost pixel processor of the array, intensity data stored in the pixel processors are read out. To this end, refresh tokens different from the plane segment tokens are inputted to the left end of the array. The refresh token has information to distinguish it from other tokens. The refresh operation is explained with reference to FIGS. 1 and 3. When the pixel processor detects the input of the refresh token R, it outputs the data Ib of the intensity register to the left side pixel processor, and in other cases, it outputs the intensity data from the right side pixel processor to the left side pixel processor. As shown in FIG. 3, the refresh token R propagates in the array and the intensity data is outputted on the left side of the array at every other cycle. 
     In a graphic display device which approximates a three-dimensionally defined object by a polyhedron, transforming coordinates and displaying it on a two-dimensional screen, a smooth shading method may be employed to smoothly change the intensity of displayed polygon in order to enhance a stereographic feeling. 
     The smooth shading method is disclosed by H. Gouraud &#34;Continuous Shading of Curved Surfaces&#34;, IEEE Transactions on Computers, C-20 (6), June 1971, pp. 623-628. 
     FIG. 4 illustrates a principle of the smooth shading method. Intensities I 1 , I 2  and I 3  given to vertices of the polygon are linearly interpolated for edges, and then intensities I.sub.α and I.sub.β at crosspoints of the edges and the raster scan line are linearly interpolated to calculate an intensity Ip of any pixel. 
     SUMMARY OF THE INVENTION 
     It is an object of the present invention to provide means for eliminating hidden surface which facilitates LSI implementation of an array system by constructing pixel processors by simplified hardwares and which allows a high image output rates. 
     The present invention provides means for eliminating hidden surface having pixel processors connected in a linear array, which comprises a depth register for storing a depth, an intensity register for storing intensity data, an adder for determing an extent of a plane segment, adding a depth displacement and comparing depth data in a time-division fashion, input/output means for updating information on an input plane segment token and outputting the updated information through one stage of pipeline registers, and an intensity data bus for outputting the content of the intensity register. 
     Each pixel processor performs various comparisons and data updatings by using one adder in a time-division fashion. As a result, the pixel processor can be implemented by a very simplified circuit. Each pixel processor need not have a unique pixel number ID and the array system may be constructed by the repetition of the identical circuits. Thus, the entire array system can be very easily implemented by an LSI. In spite of the fact that one hardware is used in the time-division fashion, the contents of the intensity registers of the pixel processors can be outputted at a highest rate (1 pixel/cycle time). 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 shows a block diagram of the prior art means for eliminating hidden surface, 
     FIGS. 2A and 2B explain concept common to the means for eliminating hidden surface, 
     FIG. 3 illustrates flow of a refresh token on an array in the prior art means, 
     FIG. 4 illustrates a principle of smooth shading, 
     FIGS. 5A and 5B show block diagrams of one embodiment of the means for eliminating hidden surface of the present invention, 
     FIGS. 6A and 6B show flow charts of processes performed by the pixel processor of the embodiment, 
     FIGS. 7A and 7B illustrate flow of plane segment tokens processed in the pixel processors, and 
     FIGS. 8A, 8B and 8C illustrate flow of plane segment tokens and a refresh token through the array of the embodiment. 
    
    
     DESCRIPTION OF THE PREFERRED EMBODIMENTS 
     FIG. 5A shows a system block diagram of one embodiment of the means for eliminating hidden surface of the present invention, and FIG. 5B shows a detail of the components. In FIG. 5A, numeral 1 denotes a pixel processor which is provided one for each of pixels on an N-pixel scan line, numeral 10 denotes a depth register for storing a depth coordinate of a frontmost plane as viewed from the pixel, and numeral 11 denotes an intensity register for storing intensity information of the plane. 
     An operation without smooth shading in the present embodiment is now explained. 
     A right end information of a plane segment is given by the number of continuous pixels dX is place of a coordinate. A token having left end coordinates (X L , Z L ), the number of continuous pixels dX, a Z coordinate displacement per unit pixel Z&#39;, and intensity information I is supplied to A input port Ai and B input port Bi of the leftmost pixel processor 1 of the array of pixel processors shown in FIG. 5A. Control information CTRLi includes IN flag information which indicates that the plane segment is within the range. The information applied to the input ports in a time-division fashion are summerized as follows. 
     
         ______________________________________CTRL            A port     B port______________________________________T.sub.1  IN flag      X     (IN= 0)                            dX               dX    (IN= 1)T.sub.2             Z            Z&#39;T.sub.3             Z            I______________________________________ 
    
     The operation of the pixel processor is explained with reference to FIGS. 5A, 5B and 6A. At a first timing T 1 , the data at the A input port A 1  and all-&#34;1&#34; pattern are supplied to the adder 12 to decrement the data of the A port by one. If IN flag is 0 and the decremented result is negative, it means that the plane segment is within the range at the current pixel location. Thus, the data dX at Bi is selected by the selector 14, shifted to the A port and latched in the latch 17. The IN flag is changed to &#34;1&#34; and latched in the latch 16. If the IN flag is &#34;1&#34; and the decremented result is negative, it means that the plane segment is outside the range. Thus, the IN flag is changed to &#34;0&#34; and the negative value (maximum integer without sign) is outputted to the A output port. In other cases, CTRLi is outputted as it is to CRTLo, and the adder output is supplied to Ao. 
     At a second timing T 2 , if the IN flag is &#34;1&#34;, Z at the A input port Ai and Z&#39; at the B input port Bi are added and a sum is supplied to the A output port Ao. In other case, the data at Ai is supplied to Ao without updating it. 
     Lastly, at a third timing T 3 , the data at the A output port Ao is held as it was at the timing T 2 . If the IN flag is &#34;1&#34; and the comparison by the adder 12 of the data Z on the A input port Ai and the data Z b  in the depth register 10 shows Z &lt; Z b , the data Z on the A input port and the data I on the B input port are stored into the depth register 10 and the intensity register 11, respectively. 
     At those three timings, the contents of all B input ports Bi are supplied to the B output port Bo through the latch 18. 
     FIG. 7A shows a time sequential flow of tokens having plane segment information while they are processed by the pixel processors. In FIG. 7A, the token A is a plane segment starting from a pixel number X = 1. The pixel processor 0 decrements it by one resulting in 0. Thus, updating of Z and comparison with Z b  are not carried out. In the pixel processor 1, it is further decremented by one resulting in a negative value. Thus, dX is supplied to the A output port instead of X so that dX is decremented in the subsequent pixel processors. The pixel processor 1 further changes the IN flag to &#34;1&#34;, and updates Z and compares it with Z b . In the succeeding stage pixel processors, dX is sequentially decremented by one until the result becomes negative. When it becomes negative, the IN flag is changed back to &#34;0&#34; so that the updating of Z and the comparison with Z b  are not carried out in the subsequent pixel processors (A maximum value is outputted to Ao). Since the operation in each pixel processor may start at the time when it has received the result of the preceding stage pixel processor, one stage of pipeline register is sufficient. 
     FIG. 8A illustrates a flow of tokens having the same plane segment information as that of FIG. 7A while they are processed by the pixel processors. 
     The operation with smooth shading of the present embodiment is now explained. 
     Right end information of the plane segment is given by the number of continuous pixels dX instead of the coordinates. A token having left end coordinates (X L , Z L ), the number of continuous pixels dX, a Z coordinate displacement per unit pixel Z&#39;, intensity information I at the left end and an intensity displacement per unit pixel I&#39; is supplied to the A input port Ai and the B input port Bi of the leftmost pixel processor 1 of the array of pixel processors shown in FIG. 5A. The control information CRTLi includes IN flag information which indicates that the plane segment is within the range. 
     The information applied to the input ports in the time-division fashion are summerized as follows. 
     
         ______________________________________CTRL            A port     B port______________________________________T.sub.1  IN flag      X     (IN= 0)                            dX               dX    (IN= 1)T.sub.2             Z            Z&#39;T.sub.3             Z            --T.sub.4             I            I&#39;______________________________________ 
    
     The operation of the pixel processors is explained with reference to FIGS. 5A and 5B and FIG. 6B. At a first timing T 1 , the data at the A input port Ai and all-&#34;1&#34; pattern are supplied to the adder 12 to decrement the A input data by one. If the IN flag is &#34;0&#34; and the decremented result is negative, it means that the plane segment is within the range. Thus, the data dX at Bi is shifted to the A port by the selector 14 and latched into the latch 17, and the IN flag is changed to &#34;1&#34; and latched to the latch 16. If the IN flag is &#34;1&#34; and the decremented result is negative, it means that the plane segment is outside of the range. Thus, the IN flag is changed to &#34;0&#34; and the negative value (maximum integer without sign) is supplied to the A output port. In other cases, CTRLi is supplied as it is to CTRLo and the output of the adder is supplied to Ao. 
     At a second timing T 2 , if the IN flag is &#34;1&#34;, the data Z on the A input port Ai and the data Z&#39; on the B input port Bi are added and a sum is supplied to the A output port Ao. In other case, the data on Ai is supplied to Ao without updating it. 
     At a third timing T 3 , the same data at the A output port Ao as that at the timing T 2  is held. If the IN flag is &#34;1&#34; and the comparison by the adder 12 of the data Z on the A input port Ai and the data Z b  in the depth register 10 shows Z &lt; Z b , the data Z on the A input port is stored into the depth register 10. 
     Lastly, at a fourth timing T 4 , if the IN flag is &#34;1&#34; and the comparison result is Z &lt; Z b , the data I on the B input port is stored into the intensity register 11. If the IN flag is &#34;1&#34;, the data I on the A input port Ai and the data I&#39; on the B input port Bi are added and a sum is supplied to the A output port Ao. In other case, the data on Ai is supplied to Ao without updating it. 
     At those four timings, the contents of all B input ports Bi are supplied to the B output port Bo through the latch 18. 
     FIG. 7B shows a time sequential flow of tokens having plane segment information while they are processed by the pixel processors. In FIG. 7B, the token A is a plane segment starting from a pixel number X = 1. In the pixel processor 0, it is decremented by one resulting in 0. Accordingly, the updating of Z and comparison with Z b  are not carried out. In the pixel processor 1, it is further decremented by one resulting in a negative value. Thus, dX is supplied to the A output port in place of X, and dX is decremented in the subsequent pixel processors. The pixel processor 1 further changes the IN flag to &#34;1&#34;, and updates Z and compares it with Z b . In the succeeding stage pixel processors, dX is sequentially decremented by one until the decremented result becomes negative. When it becomes negative, the IN flag is reset to &#34;0&#34; so that the subsequent pixel processors do not update Z nor compare it with Z b  (A maximum value is outputted to Ao). Since the operation in each pixel processor may be started in the time when it has received the result of the preceding pixel processor, one stage of pipeline register is sufficient. 
     FIG. 8B shows a flow of tokens having the same plane segment information as that of FIG. 7B while they are processed by the pixel processors. 
     In the above description, whether the smooth shading is used or not, it is possible to insert an identifier to distinguish the plane segment from the refresh token, into non-used T 2  or T 3  timing slot at the path of the CTRL signal. The operation of the pixel processor when it receives the refresh token is explained with reference to FIGS. 5A and 5B and FIG. 8C. 
     When the pixel processor 1 detects the refresh token, it supplies the data I b  in the intensity register 11 to the intensity data bus IBUS. Since the refresh token propagate to the next pixel processor for each cycle, the intensities of the pixels to be displayed are sequentially outputted when the intensity data bus IBUS is monitored. After the refresh token has been inputted to the left and, a plane segment token for a new scan line may be continuously inputted. 
     In the present embodiment, all plane segment data which require updating are collected at the A input/output ports. Alternatively, the data may be exchanged between the A port and the B port so long as the order of input of the data is not changed. 
     A bit width necessary for the addition of Z and Z&#39; is twice as long as the depth precision. For example, if the depth precision is 16 bits, the addition of 32 bits including 16 bit for integer portion and 16 bits for fraction is required. This is almost two times as long as the bit width required for other addition (subtraction and comparison). In the present embodiment, the addition of Z and Z&#39; is carried out only in the second timing T 2 . If the operation is carried out in two cycles, the bit width of the adder may be reduced to one half. Namely, the hardware of the adder may be reduced to one half by processing each token at four timings (T1, T21, T22, T3) when the smooth shading is not included, and in fine timings (T1, T21, T22, T3, T4) when the smooth shading is included. The number of tokens which can be inputted in a unit time decreases but the intensity data is outputted in each cycle because the flow rate of the token on the array does not change.