GB2178277A - System for display of colour shaded polygons - Google Patents

Abstract

Sets of parameters defining cusps of polygons and corresponding incremental quantities which define the shading of the polygons are stored in a polygon frame buffer. Real time scanline processing is utilised to provide the set of parameter signals from each set of parameters. Each set of parameter signals marks the beginning and end of the part of the scanline crossing the polygon and includes a first signal defining an initial colour and a second signal defining an incremental colour quantity. A plurality of pixel processing units (20) operate on respective ones of the sets of parameter signals. Each unit (20) comprises an interpolator (32) operating on the parameter signal data unit (31) to increment the colour signals at pixel rate or a submultiple CLK/4. The outputs RGB are pipelined and applied to a pixel insertion unit (33) in which pipelined insertion onto a colour bus (22) is effected, subject to control of a priority resolution unit (34) which compares a PRIORITY number included in the parameter signals with a priority number passed from unit to unit on a priority bus (23), the higher priority number being passed on to this bus by the priority resolution (34). The interpolator (32) and priority resolution unit (34) operate during the presence of a signal ACTIVE marking the part of the scanline crossing the polygon.

Description

SPECIFICATION Graphics system for display of shaded polygons The present invention relates to a graphics system for real-time display of shaded polygons. It is well known that high-resolution real time graphics dis plays (catering sayfor 1000 x i000oreven 2000 x 2000 pixels), each with say 24 bits of colourinformation) make impossible demands if implemented using a multiplane bit-plane frame buffer. It is accordingly knowntousewhatwill be called polygon frame buffers which store sets of parameters defining polygons in image space and to employ real-time scan conversion to generate pixel rate signals from the sets of parameters.Examples of such systems are describedin: "Zone Management Processor: A module for gener ating surfaces in raster-scan colour displays"' R L Grimsdale,AA Hadjiaslanis and PJ Willis, Computers and Digital Techniques, Feb 1979, Vol 2, No 1, pp 21-25, and "Computer Generation of Images for Flight Simula- tors" R L Grimsdale, Y C Lok, S. M. Price, R. Westmore and D J Woolens, IEE International Conference on Simulators, Brighton, England 1983.

The systems described in these references produce uniform colour polygons. It is known that picture qualitycan beenhanced by shading and it is possible to implement bi-linear shading in reattime. The most well-knownform of bi-linear shading is Gouraud shading which is described in Chapter 25 of "Principles of Interactive Computer Graphics" W. M Newman and R FSproull,2nd Ed, McGraw Hill. Use of Gouraud shading in a scan converter is described in: "AVLSl - Oriented Architecture for Real-Time Raster Display of Shaded Polygons" D Fussell, and B D Rathi, Proceedings of Graphics interface82,1982, pp 373-380, (hereinafter referred to as Fussel).

Fussel explains the benefits of restricting the systems to triangles (in object space), including the fact that Gouraud shading produces no anomolies with triangles. Bi-linear shading of polygons with more than three sides is not invariantunder rotation.

This same restriction is preferably accepted in the present invention although it is not a mandatory restriction. In Fussel the sets of parameters in the polygon frame buffers are restricted to triangles in image space. Each such triangle is processed by a triangle processorwhich has to perform parallel arithmetic operations at pixel rate which is of the order of MHz. Each processor provides, for each pixel, the colour information plus a Z-coordinate which indicates the distance ofthe surface from the viewer.

Selection is effected down through a tree of compara torsto provide as the output pixel the colour information which pertains to the surface closest to the viewer.

It is difficult and expensive to perform the required parallel arithmetic operations at pixel rate and the object of the present invention is to provide a system which can more readily operate at a very high speed.

According to the present invention there is provided a graphics system for display of shaded polygons, comprising a polygon frame buffer, means for computing and storing in the polygon frame buffer sets of parameters defining cusps of polygons and corresponding incremental quantities which define the shading ofthe polygons, scanline processing means operative in real time synchronously with respect to a raster-scan display to provide from each set of parameters, a set of parameter signals including signals marking the beginning and end of the part of each scanline crossing a polygon and first and second plural-bitsignals defining an initial colourforthe said part ofthe scanline and an incrementel colour quantity, a plurality of pixel processing units operative on respective ones of the sets of parameter signals, a colour bus comprising at least one colour line, and a source of clock pulses, each pixel processing unit being responsive to the set of parameter signals supplied thereto and to the clock pulses to perform bit-serial incrementing, at a bit rate established by the clock pulses, ofthe said first signal in accordance with the said second signal, and to reiterate such incrementing over an interval determined bythe signals marking the beginning and end of the part of a scanline crossing a polygon, thereby to provide a plurality of bits forthecolour bus in respect of each pixel or small group of pixels.

The colour bus caters for a member M of colours.

Thisnumbermaybeonefora monochrome display but is preferably three for a full colour display. Each colour is assigned a plurality N of bits, e.g. 8 bits for a high colour-resolution display, and these bits have to begeneratedforevery pixet, orsmall group of pixels.

Particularly if the pixel resolution is high, it may not be necessaryto recalculate the colours every pixel, although determination of beginnings and endings of scanlines and pixel insertion are always effected on a per pixel basis. Recalculation may suffice once for every small group of pixels such as every four pixels, as in the embodiment described below. Moreover, the scanline procressing means may not operate fully on i every scanline. The first and second plural-bitsignals may be recalculated only every few scanlines, e.g.

every third scanline.

In one implementation of the invention the colour bus has only M lines (one per colour) and a very high clockrate of N x PXCLK is used where PXCLK is a pixel-rate clock. Each pixel processing unit can then be based on one one-bit adder which processes colour quantityand incrementalcolourquantitybitseriallyto provide N bits serially on the corresponding colour bus line which carries packets of N serial bits. This approach may be appropriate in a wafer-scale implementation where high clock rates are feasible and it is desirable to minimise the number of bus lines routed all overthewafer.

At the other extreme, the clock rate may be equal to pixel rate. The colour bus than has to have N lines per colour and each pixel processing unit will require N pipelined one-bit adders as in the embodiment described in detail below. This approach is preferred, at least for a printed circuit implementation, as it minimizes the bit-ratewithinthe pixel processing units.

There are various intermediate approaches. For exampleconsideronecolourwith N =8. Each pixel processing unit could consist of two pipelined sub units clocked at 4 x PXCLK to handle the four least significant and four most significant bits respectively or could consist of four pipelined sub-units clocked at 2x PXCLKto handle pairs of bits. Pipelining is required to take account of carries.

Regardless ofthe implementation, the bits on the colour bus will require some alignment operations before they are finally decoded to provide analogue signals for driving a CRT or other raster scan display. If the clock rate is N x PXCLK, the packets of bits may be clocked serially into a shift register at clock rate and be transferred out in parallel at pixel rate. If the clock rate equals PXCLK,the bits are already in parallel on the colour bus bit with a 1-bitskewfrom line to line. The skew is readily removed by a digital delay of N-l- bits in the least significant bit line, a delay of N-2 bits in the next bit line, and so on, where a 1 -bit delay is aG-pixel delay.In any intermediate scheme acombination of shift register and delaytechniques will yield nonskewed, parallel bits.

The outputs ofthe pixel processing units may go direct on to the colour bits ifthere is no requirement for hidden surface removal or overlaying. Such a requirement is, however, more or less universal and some form of priority arbitration scheme establishing control over pixel insertion is required. A preferred scheme which cooperates with the pipelined pixel processing units is described below but other schemes may be employed, e.g. that of Fussel.

The invention will be descibed in more detail byway of example, with reference to the accompanying drawings, in which: Fig 1 is a block diagram of a system embodying the invention, Fig 2 is a block diagram of one pixel rate unit of Fig 1, Fig 3 is a diagram illustrating pipelined processing within the pixel rate unit of Fig 2, Fig 4 is a more detailed block diagram of a contour control circuit included in Fig 2, Figs is a more detailed block diagram of a priority resolution unit included in Fig 2, Fig 6 is a diagram illustrating the general organization of an RGB interpolarincluded in Fig 2, Fig 7 is a block diagram of one element ofthe RGB interpolator, Fig 8 is a timing diagram explaining operation of the RGB interpolator, Fig. 9 shows a detail ofthe RGB interpolator, and Fig 10 is a more detailed block diagram ofthe pixel insertion unit of Fig 2.

The system illustrated in Fig 1 comprises a host computer 10which is programmed in a high-level language and controls a plurality of object processors 11,12via a communications channel 13. For simplicity only two object processors are shown; there may be very many more.The processor 11 comprises a communications section 14, a configuration section 15,a picture rate process section 16 and a single polygon-processing section 17. The communication and configuration sections are used in a way well known in distributed computing systems in general to accept addressed commands from the host 10, and to establish a configuration required for a given application.

The polygon-processing section 17 operates on a single clipped triangle in image space. The system is restricted to handling trianglesfor reasons explained above. The worst case clipping of a triangle inside a rectangularwindow produces a seven-sided polygon.

The picture rate process 16 performs all the calculations necessary to produce an image plane description of the clipped triangle from its object space description. The clipping is performed in such a way that the shading over its surface is consistent with that which would have been producedoverthesurfaceif the clipping had not been performed.

The object plane description of the polygon (triangle) consists of six parameters for each cusp: x, y, z, red, green, blue, i. three coordinates and three colour values. After transformation to image space and clipping,the image plane description consists of a left side cusp list, a right side cusp list and a surface priority value, explained below. Each cusp in the cusp lists is defined bythree parameters: (1)x,y (2) red, green, blue (3) d(x)/dy (4) d(red)/dy, d(g reen)/dy, d(blue)/dy.

(1 > gives the cusp position in screen coordinates, (2) gives the colour at the cusp, (3) gives the gradient of the edge extending from the cusp and (4) specifiesthe shading.

The polygon-processing section 17 comprises a polygon frame buffer 18, a scanline process section 19 and a pixel rate processing unit 19. The image plane description which is written once per frame into the buffer 18 consists of the cusp lists explained above plus the priority value.

Afixed priority value (unsigned binary number) is used for each surface.Thistogetherwith a backface cull is sufficient to determine whether or not a polygon is in front of other surfaces. Afixed priority scheme imposes two important restrictions on the system.

These are thatthe polygonscannot intersect, and that they must be single sided. These restrictions are accepted because the cost of varying the priority value overthe surface ofthe polygon using bi-linear interpolation is disproportionately high. The problem arises because priority resolution is performed in a bit-wise mannerfrom the most significant bit to the least significant bit (see below), whereas, the additions required to perform the interpolation are performed in a bit-wise manner from the least-significant bit to the most-significant bit. lfthere are N-bits in the prioritywordthen N*(N-1) delayelementswould be required to align the putput of a priority interpolator with the inputto the priority resolver.

As so far described, the system merely represents the application of well-known techniques (see for example the aforementioned book by Newman and Sproull) and no more detailed description will be given. The invention is not concerned with the way in which the image space polygon description is generated but with the way in which it is utilized by the polygon-processing section 17. The object processor 11 presumes that the host processor has carried the analysis down to the level of object space triangles.

The object processor 12 illustrates another possible approach. The host processor 10 specifies n-gons (or n-hedra) and the picture rate process 16 performs the analysis into n clipped image space triangles processed by n (illustrated as n =3) polygon-processing sections 17.

Turning now to the construction and operation of these sections 17, the scanline process 19 operates on the cusp lists in the buffer 18 to generate, in each scanline,thefollowing parameters: X LEFT = X ON, defining the start ofthe active part of the scanline, i.e. the partcrossingthe polygon.

(XLEFT-XRlGHT) = X EXTENT, defining the length ofthe active part of the scanline, PRIORITY, i.e. the surface prioritywhich essentially gives the surface a fixed z-coordinate.

RED LEFT= RED GREEN LEFT = GREEN BLUE LEFT = BLUE, together defining the colour at the start ofthe active part ofthe scanline, d(RED)/dx = RED DX d(GREEN)ldx = GREEN DX d(BLUE)/dx= BLUE DX, togetherdefining the incremental change of colour (change perfour pixels}.

The way in which these paramatersare generated is shown by the pseudo-Pascal listing and full algorithm appended to this description. It is assumed in the listings that interpolation takes place at every scan line, andforeach group of pixels. The hardware described below assumes that interpolation takes place at quarter pixel rate. In the algorithm a group counter is used to achieve this. In the pseudo-pascal listings the group counter is represented by the variable G COUNTER and the number of pixels in each pixel group is represented bytheconstant DX CLR STEP.

The pixel rate process 20 takes the parameters provided bythe scanline process 19, converts X ON and X EXTENT into a timing waveform ACTIVE which marks offthe active part of the scanline, and during the interval of ACTIVE true repeatedly increments, RED, GREEN and BLUE at a quarter pixel rate by RED DX, GREEN DX and BLUE DX respectively. The hardware which performs these operations will be described below but the operations can be expressed by the pseudo-Pascal listing algorithm appended to the end ofthis description.

Referring again to Fig 1, the pixel rate processes 20 are synchronized to VIDEO CLOCKS passed from unit to unit on a bus 21. These clocks comprise HSYNC (horizontal sync) and PXCLK, the pixel rate clock, RED, GREEN and BLUE are all output as skewed 8-bit values on buses 39 for insertion on to a 8-bit R, G and B buses 22. Whether insertion takes place or not is determined by a priority contest between the number on a priority bus 23 and the local value of PRIORITY. If the bus wins, insertion does nottake place and the priority bus carries the bus number on to the next unit 20. If PRIORITY wins, insertion does take place and PRIOR ITY is passed on as the bus numbertothe next unit 20.

In this way, the final output of the R, G, B buses 22 represents the pixel colourforthe highest priority surface pertaining to that pixel, but with skewed bits, which may be de-skewed as explained above.

Fig 2 illustrates one pixel rate processing unit 20. A contour control unit 30 receivesXON and X EXTENT by way of a DATA bus 31 from the scanline process 19 and operates synchronously with PXCLKto generate ACTIVE. Thestartand emd of ACTIVE must be timed correctly to within one pixel as the full pixel resolution must be utilized to create non-ragged edges. The values RED, RED DX etc are supplied to an R G B interpolator 32 which operates at quarter pixel rate defined by a clock signal denoted CLKI4. This is generated within thecontoursignal 30 in such a way asto be phase-lockedtothelefthand edgeofthe polygon being drawn.The interpolator 32 sta rts interpolating when ACTIVE goes true and produces outputs R, G, B on the buses 39, which are fed to a pixel insertion unit 33 through which pass the 8-bit colour buses 22. Whether insertion takes place or not is determined by an ENABLE signal provided by a priority resolution unit 34 which compares PRIORITY with the number on the priority bus 23.

Each of the incremental quantities RED DX etc is a fractional quantity and for simplicity it is assumed in this embodimentthat RED, GREEN, BLUE, R, G, and B and priority are all 8-bit quantities and that RED DX, GREEN DX and BLUE DX are all fixed point numbers with 8 fractional bits in addition to the 8 integer bits used for RED, GREEN and BLUE. Fig. 3 then shows the relative time positions of the bits involved in computations. On the time axis in Fig. 3, each little square occupies one pixels.

Atan initialtimetOthe priority resolution unit 34 starts to process the bits on the priority bus and in PRIORITY, starting with the most significant bit, as indicated by the eight squares 34. Simultaneouslythe interpolator 32 starts to process the least significant fractional bits of RED and RED DX, etc. as indicated by eight dotted squares 35forthe RED bus only. At to which is eight bit intervals after0, priority is resolved and the non fractional bits 36,37, forthe RED, GREEN and BLUE buses startto appear, working from the least to the most significant bits.It is these bits which are output as R, G and B (Fig 2) for insertion on the colour buses, conditional upon the presence of ENABLE which is available attl.

The groups of squares in Fig 3 are shown as staircases because they are generated by pipelined elements, one per bit of each relevant bus. If single line buses were to be employed, the bit rate would have to increase from PXCLK up to 8 x PXCLK and all eight bits forthe RED bus line (for example) would appear serially as a packet occupying the duration of one little square (four pixels) in Fig 3.

The four units of Fig 2 will now be described in more detail, commencing with the contour control unit 30, shown in Fig 4. This unit has an X ON counter 40 and an X EXTENT counter 41 forthe current (nth) line and buffer registers 42 and 43 forthevalues to be used in the next, (n+l )th line. Atthestartofeach line, HSYNC transfers the contents of the buffer registers 42,43 to the counters40,41 and the buffer registers are then reloaded from the data bus 31. The counters are clocked by PXCLKto count down but initially only the X ON counter is enabled (EN).When the left hand edge ofthe polygon is reached,the X ON counter40 is empty and provides a signal TC (terminal count) which disablestheX ON countervia an inverter44, enables the X EXTENT counter 41 and sets a flip-flop 45 providing the aforementioned signal ACTIVE. The counter 41 counts down until the right hand edge of the polygon, whereupon its signal TC resets the flip flop 45through an OR gate 46.ln case the right hand edge should be off-screen, HSYNC also resets the flip-flop via the OR gate. The third bit ofthe X EXTENT counter 41 is also taken off as the interpolation bit rate clock CLKI4which is accordingly phase locked to the left hand edge of the polygon, i.e. phase locked to the start of ACTIVE. This marks the time to in Fig. 3.

So long as ACTIVE is false itforcesthe priority resolution unit34to provide ENABLE also false (eight bits latersincethis unit is also pipelined). As soon as ACTIVE goes true the priority contest starts and ENABLE either stays false or goes true depending upon whetherthe priority bus or PRIORITYwins the contest. The priority resolution unit34 is shown in Fig.

5.

If the number input on the priority bus is A, the number PRIORITY is B andthe output number on the priority bus is Z, the bits of numbers A, B and Zwill be denoted as follows: A=a1...aj...as B=b1...bj...bs Z = z1 . z. . Z8 where the subscripts 1 and 8denote the most and least significant bits respective and j denotes a general bit.

The priority resolution unit 34 comprises eight bit logic units T1 to Ts. Considering the general unitT, it receives the bits aj and bj and outputs zi. The unitTj also receives inputs cj-1 and di-1 from the next more significant unitT1 and outputs cj and djto the next less significant unit. The signal ci indicates whether or not priority has been resolved at the u nit Tj or at a unit of higher significance and dj indicates, when priority has been resolved, in whose favour. The final bit d8 constitutesthe ENABLE signal. zj becomes aiforthe priority resolution unit ofthe next pixel rate unit 20.

One set of equations defining the structure for Tj in the case of minimum priority resolution is as follows: cj =0.-i + (aj#bj) (1) dj=c'1 dj-1 + aj c;~ (2) Zi = ai. bj + cj-1 (bj.di-7 + aj. di-1) (3) The convention assumed is that 0-i = 0 means "not resolved" while ci-i = 1 means "resolved". If cj~ = 0 the value of di-1 is without significance.If ci-1=1,then dj1 = 1 means the device has won the priority contest whereas dii = 0 means the bus has won the priority contest.

The provision ofthe initial values c0 and d0 will now be considered. c0 is the signal ACTIVE while do is tied to logical 0. This cases ENABLE to be forced false by ACTIVE false, whereas during ACTIVE true, ENABLE is true only if PRIORITY has higherprioritythan the bus priority n u m ber A, (save that the state of ENABLE is delayed eight bits relative to the state ofthe ACTIVE).

Afullerexplanation ofthe priority resolution unit, and an example which resolves in favour of the maximum priority number, will be found in our copending application of even date, entitled "Priority Resolution System".

Fig 6 shows part of the R G B interpolator 32, namely the partfor one colour, which may be assumed to be RED. Fig 6 is replicated for the other colours. The interpolator handles sixteen bits, namely eightfractional bits and eight integer bits, in eight DFUs (dual function units) 50forthefractional bits and eight DFUs 51 forthe integer bits. All sixteen DFUs are pipelined and receive input bits from an initial colourvalue register 53 into which RED is written at the start of each line and an incremental colourvalue register 54 into which RED DX is similarlywritten.RED which does not provide any inputs to the fractional DFUs; their RED inputs may be tied to 0. The incremental value RED DX provides inputs to the DFUs occupying both integer and fractional positions in the colour word. Onlythe outputs from the integers DFUs 51 are employed. They are denoted P1 (MSB) to P8 (LSB) (only P1 to P4 show) and togetherform the R bus of Fig.2 The basic action of each DFU 50 or 51 is as fallows.

When asignal on an iput Fl (function input) isfalse, the DFU latches its I input which is the corresponding bit of RED. When Fl is true, it adds the latched value to its D inputwhich isthecorresponding bit of RED DX, providing an output bit P and a carry bitto the next more significant DFU on Cl. Moreover Fl is pipelined on to the next DFU. The least significant DFU 50 has ACTIVE appliedto its Fl input. All DFUs are clocked CLK/4 so that pipelined bitwise additions takes place at quarter pixel rate.

This is illustrated in Fig 8in which the abscissa represents CLK/4 which starts at Oat the start of ACTIVE. At CLK/4 = 8 ENABLE goes true or stays false, depending upon who has won the priority contest and the integer DFUs 51 start to produce RED (latched in when ACTIVE was false) which appears in bit-skewed fashion on the R BUS, as indicated by the diagonal line 55. At CLK/4 = 9, RED + (RED DX) starts to appear (diagonal line 56) and so on.

Fig 7 shows the contruction of one DFU 50 or handling one bit. The registers 53 and 54 of Fig 6 are represented by one bit latches l(n) 60 and D(n) 61 for the current line, linen. These are loaded by HSYNC from buffers l(n+l) 62 and D(n+1) 63 which then receive the new bits of RED and RED DX respectively fromthedata bus 31.

The latches 60 and 61 are connected to a 1-bit multiplexer64which is controlled by Fl to output when Fl isfalseand Dwhen Fl is true. The selected input is applied to an inputAofa 1-bit adder unit 65 which receives inputs Fl, Cl = carry in and A and provides outputs FO -function out (to the next DFU), CO = carry out and P = result. The unit 65 is clocked by CLKI4 and has the following properties. At each clock pulse, FO latches Fl. If Fl is false, P latches A. If Fl is true, one bit addition of A, P and Cl is effected to generate the new P and CO. Fig. 9 is a block diagram ofthe unit 65, which comprises a function flip-flop 66, a P flip-flop 67 and a carry flip-flop 68 which are set-reset flip-flops clocked by CLK/4. The flip4lop 66 simply latches Fl to provide FO. An adder 69 adds A, P and Cl to produce Q.

A multiplexer 70 selects either A (false) or Q (Fl true) to be latched in the P flip-flop 67. The carry produced by the adder 69 is latched by the carry flip4lop 68 to provide CO. It will be appreciated that the phases at which the various items are clocked will need correct adjustment to ensure correct operations i.e. multiph ase clock signals may be used. This design detail is not illustrated in Fig 9.

Fig 10 shows the pixel insertion unit 33, again just for RED. The lines forthe input red bus 22, RED IN, are denoted R1 (MS) to R8 (LS)whilethecorresponding lines ofthe red bus 39from the interpolator32 are denoted S1 to S8. The insertion unit is essentially an eight-channel multiplexer controlled by ENABLE but, because of the pipelined operation of the interpolator 32 and the corresponding skew of the bits on the buses 22 and 39, ENABLE hasto bepipelinedthrougheight multiplexer stages, one per bit. Each stage comprises a a 1-bit multiplexer71 and each, otherthan the last comprises a flip-flop 72 clocked by CLK.The flip-flops are cascaded, leastto mostsignificant bit and the least significant copies ENABLE. it will be noted that, although the interpolator 32 is pipelined at CLKI4 rate, the pixel insertion unit 33 treats RGB as ifthey were pipelined at CLK rate.

It will also be noted that the interpolation effected by the R G B interpolator 32 carries on regardless ofthe state of ENABLE. This is because each processor 17 deals with one triangle (or clipped triangle) and the colourvalue of each pixel is produced by incremental calculation. Therefore, even if part ofthe object is hidden, the interpolation must still continue to ensure that the correct colour value is present if and when the surface emerges from hidding.

The interpolator has been somewhat simplified in Figs 6 and 7. In practice, the two's complement fixed point number representation is preferably used in the interpolarutilising a sign bit as well as an 8-bit integer portion and fraction bits. The colour values RED etc must always be positive but the incremental values RED DX etc may be positive or negative. The result of the difference accumulation is always positive and the sign bit may therefore be ignored. It is merely required to determine whether the DFUs add or usbtractthe incremental values. In two's complement arithmetic, the sign bit ofthe difference value cannot influence the result at less significant bit positions, therefore, the sign bit need not have any physical representation within the colour interpolator.

The number of fraction bits is determined by the minimum colourgradientwhich has to be represented. Eight fractional bits have been assumed above.The number required is one more than that required to represent the minimum colour gradient.

The extra bit is required to prevent an error in the least significant bit position from propogating into the integerpartofthecolourvalue. If the horizontal resolution is 1024 pixels and the colour is interpolated everyfourth pixel, then the m inimum colour gradient is one in 256. Eightfractional bits are required to represent this quantity. A one it error will propogate 8-bit positions towards the most significant bit after 256 successive accumulations. Therefore nine fraction ; bits are required for a system with a minimum horizontal colour gradient of one in 256.

It is convenient to have the same number of fractional bits as there are bits on the priority bus.

However, if there is a discrepancy, it can be compensated for by a corresponding delay element. For example, ACTIVE can be delayed attheinputtothe interpolator32ortheinputtothepriorityresolution unit 34, as maybe required to generate ENABLE synchronously with interpolation of the leastsignifi- cant integer bit.

The reasons for accepting a fixed priority value for each surface have been explained above. This restriction could be avoided if the priority resolution was effected in a pipelined manner, least significant bit first. A most significant bit first difference adder would allowthe same resuitto be achieved in conjunction with most significant bitfirst priority resolution.

As described above, inserted pixels completely overwrite the colour buses, i.e. overlying surfaces are assumed to be opaque. The effect of overlaying a transparentsurface could be achieved by positioning transparentsurfaces last along the linear array of polygon processing sections 17. If the priority comparison for such a surface succeeded, the colour values on the corresponding buses 39 would not overwrite the valuesonthe buses 22 but would modify these by pipelined subtraction.

In the above description, although interpolation is effected once every four pixels, the scanline algorithm is assumed to be performed every line. However, the division operations required to calculate the incremental colour quantities are expensive in comput ing time. The scanline algorithm mayaccordinglybe implemented less than every scan line, say every third scanline (or on any scanline which contains a cusp).

There is then some risk of colour interpolators overflowing or underflowing which will produce dramatic and unacceptable visual results. Accordingly, guard bands may be established at the extremes of thecolourvaluesso that black is equal to 16 and saturated colour is equal to 235,forexample.

SHADED SURFACE GENERATIONAL GORITHM Version RECALCULATE PARAMETERS ON EVERY SCANLINE RECALCULATE COLOUR VALUES FOR EACH GROUP OF PIXELS ALONG SCANLINE SCANLINEALGORITHM INPUTS From Polygon Frame Buffer: LEFT, RIGHT: cusp lists Y TOP,Y BOTTOM: integer PRIORITY: positive integer The following parameters are definedforeach cusp in the cusp lists; X, Y, RED, GREEN, BLUE, d(x)/dy, d(RED)/dy, d(GREEN)/dy, d(BLUE)/dy.

OUTPUTS X~ON : integer; X EXTENT, PRIORITY: positive integer; RED, GREEN, BLUE : positive integer; d(RED)/dx, d(GREEN)/dx, d(BLUE)/dx : fixed point; ALGORITHM Set the current left, and current right, cusps to the first left, and first right, cusps respectively.

For each scanline in turn from first scanline to the last scanline BEGIN If scanline intersects the polygon.

(e.g. if scanline is between Y TOP and Y BOT- TOM) then BEGIN If a leftcuspisonthisscanline then InitialiseX~LEFT,RED~LEFT,GREEN~LEFT BLU E LEFT with the values in the current left cusp.

Make the next cusp in the left cusp list the current cusp.

else Add the dy increments from the previous cusp to X LEFT, RED LEFT, GREEN~LEFT, and BLUE LEFT.

If a rightcusp isonthisscanline then InitialiseX~RIGHT,RED~RIGHT,GREEN~ RIGHT, BLUE RIGHTWITH THE VALUES IN THE CURRENT RIGHT CUSP.

MAKETHE NEXT CUSP IN THE RIGHT CUSP LIST THE CURRENT CUSP.

else Add the dy increments from the previous right cusp to X~RED~LEFT,GREEN~LEFT, and BLUE LEFT.

Calculate the extent, in pixels, ofthe intersection ofthe scanline and the polygon. Partially in tersected pixels are included.

Calculate the extent, in pixel groups, ofthe intersection ofthe scanline and the polygon.

Partially intersected pixel groups are included.

Calculate the red, green, and blue colour gra dients, per pixel group.

Pass parameterstothe pixel rate process.

END; (scanline intersects polygon) END; (for each scanline in turn} PIXEL RA TEALGORITHM INPUTS From Scanline Algorithm: X ON: integer X~EXTENT,I PRIORITY: positive integer; RED, GREEN, BLUE: : positive integer; d(RED)/dx, d(GREEN)/dx, d(BLUE)/dx : fixed point; From previous object processor: RED GREEN~BUSJN,BLUE~BUS~IN: positive integer; PRIORITY BUS : positive integer; OUTPUTS RED BUS OUT, GREEN~BUS OUT, BLUE BUS OUT: positive integer; PRIORITY BUS OUT: positive integer; ALGORITHM Initialise group counter.

SetRED,GREEN and BLUEtotheinputvalues.

For each pixel in turn along the scanline from the first pixel to the last pixel.

BEGIN If pixel is inside, or on the edge of the polygon (e.g. if pixel is between X~ON and (X~ON+X~ EXTENT) inclusive) then BEGIN If priority is greater than PRIORITY~BUS IN then Transferthecolourvalues RED, GREEN, BLUE to their respective output colour busses.

Transferthe priorityvalue to the priority output bus else Transferthe colourvalues on the input colour busses to the out put colour busses.

Transferthe priority value on the input priority bus to the output priority bus.

END Increment group counter If start of a pixel group then Add dx increments to the colourvalues, RED, GREEN, and BLUE.

END PROGRAM SHADED SURFACE GENERATION ALGORITHM; CONST DX~CLR~Step = 4; GUARD~BITS=1; SIGN~BlT-=l; X~INTEGER~BITS=9; X~DY~FRAC~BITS=9 X DYBITS=SLGN BIT+X INTEGER BITS+ X~DY~FRAC~BITS; CLR~INTEGER~BITS=8; CLR~DX~FRAC~BITS=7+GUARD BITS;{quarter resolution or a 512 display} CLR DX BITS=SIGN BIT-I-CLR INTEGER BITS + CLR~DX~FRAC~BITS; CLR~DY~FRAC~BITS=9+GUARD~BITS;{CLR~ DY~FRAC~BITS > = CLR DX~FRACBITS) CLR DY BITS=SIGN BIT3-CLR INTEGER BITS +CLR~DY~FRAC~BITS; MAX~NUM~OF~CUSPS=7; FIRST~SCAN LINE = 255; LAST~SCANLINE =-256; FIRST~PIXEL=256; LAST~PIXEL=255; TYPE POS~INTEGER=..MAXINT; Y~RANGE=LAST~SCANLINE..FIRST~SCAN LINE;; X RANGE = [ BlT(XlNTEGER~BITS) ] FIRST PIXEL.. LAST PIXEL; DELTA~X~RANGE = [ BIT(XlNTEGER~BITS) ] 0..

(LAST~PlXEL-FlRSTPlXEL); X~DY~RANGE = [ BlT(X~DY~BITS) ] FIXED POINT; CLR~RANGE=[BIT(CLR~INTEGER~BITS)]=..

(2**CLR~INTEGER~BITS)-1; CLR~DX~RANGE = [ BlT(CLRDX~BITS) ] FIXED POINT; CLR~DY~RANGE=[BIT(CLR~DY~BITS)]FIXED~ POINT; CUSP=RECORD Y:Y~RANGE; X:X~RANGE; RED:CLR~RANGE; GREEN:CLRRANGE; BLUE:CLR~RANGE; X~dy:X~DY~RANGE; RED~dy:CLR~DY~RANGE; GREEN dy: CLR DY RANGE; BLUEdy: dy:CLR DY RANGE; end; CUSP~PTR=0..MAX~NUM~OF~CUSPS; CUSP~LIST=ARRAY[CUSP~PTR] OF CUSP; FUNCTION TRUNC~TO~INTEGER (X:FIXED~POINT) :INTEGER; BEGIN (This function performs a type conversion from a fixed point representation to an integer representation. The integer part of the fixed point number is returned as the result.The fractional part of the fixed point number is disregarded.) END; FUNCTION FLOAT~TO~FXP(X: INTEGER) : FIXED~ POINT; BEGIN {This function performs a type conversion from an integer representation of a numberto a fixed point representation ofthesame number.) END; PROCEDURE PIXEL PROCESS (X~ON: X~RANGE; X EXTENT: DELTABX RANGE; PRIORITY: POS~INTEGER; RED~LEFT, GREEN~LEFT, BLUE~LEFT: CLR~ RANGE; RED DX GREEN DX BLUE~DX:CLR DX RANGE); VAR RED, GREEN, BLUE: CLR DX RANGE; RED~BUS~OUT, GREEN~BUS~OUT, BLUE~ BUS~OUT:CLR~RANGE' PRIORITY~BUS~OUT: POS~INTEGER; X~DISPLAY: X~RANGE; G~COUNTER:DELTA~X~RANGE; BEGIN RED:=FLOAT~TO~FXP(RED~LEFT); GREEN:=FLOAT~TO~FXP(GREEN~LEFT); BLUE:=FLOAT~TO~FXP(BLUE~LEFT); G~COUNTER:=0; FOR X~DISPLAY:=FIRST~PIXEL TO LAST~DO IF (X ON < = X~DISPLAY) AND (X DISPLAY < = (X ON + X EXTENT) ) THEN BEGIN IF PRIORITY > PRIORITY~BUS IN THEN BEGIN RED~BUS~OUT:=TRUNC~TO~IN- TEGER(RED); GREEN~BUS~OUT:=TRUNC TO IN TEGER(GREEN); BLUE~BUS~OUT:=TRUNC~TO~IN- TEGER(BLUE); PRIORITY BUS OUT: = PRIORITY; END ELSE BEGIN RED~BUS~OUT:=RED~BUS~IN; GREEN~BUS~OUT:=GREEN~BUS~IN; BLUE~BUS~OUT:=BLUE~BUS~IN; PRIORITY~BUS~OUT:=PRIORITY~BUS~ IN; END; G~COUNTER:=G~COUNTER+l; IF (G~COUNTERMODDX~CLR STEP)=0 {simulates divided down pixel clock) THEN BEGIN RED: = RED + RED dx; GREEN : = GREEN + GREEN~dx; BLUE: = BLUE + BLUE dx; END; END; END; PROCEDURE SCANLINE~PROCESS (LEFT, RIGHT: CUSP LIST; YTOP,Y~BOTTOM INTEGER; PRIORITY: POS INTEGER); VAR X~LEFT, X~RIGHT: X~DY~RANGE; {fixed point) RED~LEFT, GREEN~LEFT, BLUE~LEFT: CLR~DY~ RANGE; (fixed point) RED~RIGHT, GREEN~RIGHT, BLUR~RIGHT: CLR~ DY~RANGE; (fixed point) Y~DISPLAY: Y~RANGE; {subrange of INTEGER} LEFT~PTR, RIGHT~PTR: CUSP~PTR; {subrange of INTEGER} X~EXTENT, X~CLR~GROUP: DELTA~X~RANGE; (subrange of INTEGER) RED~DX, GREEN~DX, BLUE~DX: CLR~DX RANGE; (fixed point) PROCEDURE DY~STEP(SIDE: CUSP~LIST; VAR SIDE CUSP CUSP~PTR; VAR X~SIDE:X~DY RANGE; VAR RED SIDE, GREEN SIDE, BLUE~SIDE: :CLR~ DY~RANGE); BEGIN {procedure dy~sep} IF Y~DISPLAY=SIDE[SIDE~PTR].Y THEN WITH SlDE [ SIDEPTR ] -DO BEGIN X~SIDE:=FLOAT~TO~FXP(X); RED SIDE: = FLOAT TO~FXP(RED); GREEN~SIDE: = FLOAT TO~FXP(GREEN); BLUE SIDE: = FLOAT~TO~FXP(BLUE); SIDE~PTR:=SIDE~PTR+1; END ELSE BEGIN WITH SIDE[SIDE~PTR-1]DO BEGIN X~SIDE:=X~SIDE+X~dy; RED SIDE: = RED SIDE + RED dy; GREEN~SIDE: = GREEN SIDE + GREEN dy; BLUE SIDE: = BLUE SIDE + BLUE~dy; END; END; END; {procedure dy~step} BEGIN (procedure line rate *) LEFT PTR: = 0; RIGHT PTR: = 0; FOR Y~DISPLAY:=FIRST~SCANLINE DOWNTO LAST~SCANLINE DO BEGIN IF BOTTOM < = Y~DISPLAY) AN D (Y DISPLAY < =Y~TOP) THEN BEGIN DY~STEP(LEFT, LEFT~PTR, X~LEFT, RED~LEFT, GREEN~LEFT, BLUE~LEFT); DY~STEP(RIGHT, RIGHT~PTR, RED~ RIGHT,GREEN~RIGHI, BLUE RIGHT); X~EXTENT:=TRUNC~TO~lNTEGER(X~RIGHT X LEFT) + 1; X CLR GROUP: = (X EXTENT DIV DX CLR~ STEP) + 1; RED dx: TR U TRUNC~TOJNTEGER(REDight RED~left)DlVX~CLR~GROUP; GREEN dx: =TRUNC TO INTEGER(GREEN~ rightGREEN ieft) DIVX CLR~GROUP); BLUE = TRUNC TOgNTEGER(BLUE right BLUE ieft) DIVX CLR~GROUP; PIXEL PROCESS (TRUNC TO INTEGER(X LEFT),X EX- TENT, PRIORITY, TRUNC~TO~lNThGER(REDLEFT), TRUNC~TO~lNThGER(GREENLEFT), TRU N CTO NTEG E R(B LU E~LE FT), RED~DX, GREEN~DX, BLUE~DX); END; END; END; (procedurescanline Drocess)

Claims (15)

1. CLAIMS 1. Agraphicssystem for display of shaded polygons, comprising a polygon frame buffer, means forcomputing and storing in the polygonframe buffer sets of parameters defining cusps of polygons and corresponding incremental quantities which define the shading ofthe polygons, scanline processing means operative in real time synchronously with respect to a raster-scan display to provide from each set of parameters, a set of parameter signals including signals marking the beginning and end of the part of each scanline crossing a polygon and first and second plural-bit signals defining an initial colour for the said part of the scan line and an incremental colour quantity, a plurality of pixel processing units operative on respective ones of the sets of parameter signals, a colour bus comprising at least one colour line, and a source of clock pulses, each pixel processing unit being responsivetothesetof parameter signals supplied thereto and to the clock pulses to perform bit-serial incrementing, at a bit rate established by the clock pulses, of the said firstsignal in accordance with the said second signal, and to reiterate such incrementing over an interval determined by the signals marking the beginning and end ofthe part of a scanline crossing a polygon, thereby to provide a plurality of bits forthe colour bus in respect of each pixel or small group of pixels.
2. 2. Agraphicssystem according to claim 1, wherein the clock pulses are at a submutiple of the pixel rate.
3. 3. A graphics system according to claim 2, wherein each pixel processing unit comprises pixel insertion means operable at pixel rate to introduce respective bits from the said plurality of bits on to respective lines ofthe colour bus.
4. 4. Agraphicssystem according to claim 1, wherein the clock pulses are at pixel rate and each pixel processing unit comprises pixel insertion means operable at pixel rate to introduce respective bits from the said plurality of bits on to respective lines ofthe colour bus.
5. 5. Agraphicssystem accordingtoclaim 1, wherein the clock pulses are at an integral multiple of pixel rate and each pixel processing unit comprises pixel insertion means operable at clock rate to introduce packets of bits per pixel on to the or each line ofthecolour bus.
6. 6. A graphics system according to claim 3,4 or 5, wherein the pixel insertion means are pipelined.
7. 7. A graphics system according to any of claims 1 to 6, wherein the said bit-serial incrementing is pipelined.
8. 8. A graphics system according to claim 7, wherein each pixel processing unit comprises first and second registers for storing the first and second plural-bit signals, means for updating each register fromthescanlineprocessing meansatscanline rate orasubmultiplethereof,andapluralityoffunction units, one per bit ofthe registers, pipelined in order of increasing significance to transferfrom unit to unit, at the said clock rate, an active signal which is asserted during the said part of reach scanline crossing a polygon, each function unit comprising a 1-bit adder with an output register and being operative to latch the corresponding bit of the first plural bit signal in the output register when the active signal is not asserted, a nd, wh en the active signal is asserted, to form in the output register the sum bit from the bit in the output register, the corresponding bit of the second plural bit signal and a carry-in bit from the preceding function unit, and to provide a carry-out bit to the succeeding function unit.
9. 9. A graphics system according to claim 8, wherein the plurality of bits for the colour bus are taken from a most significant subset only of the function units.
10. 10. A graphics system according to any of claims 1 to 9, wherein each pixel processing unit includes a priority resolution unit and wherein a priority bus is routed through the priority resolution units in parallel with the colour bus.
11. 11. A graphics system according to claim 10, wherein the sets of parameters include priority numbers individual to the pixel processing units and each priority resolution unit is adapted to compare with the processing unit priority number the incoming bus priority number on the bus, to pass on to the priority bus whichever number pertains to the higher priority and to control introduction of bits on to the colour bus in dependence upon the sense of the priority resolution.
12. 12. A graphics system according to claim 11, wherein each pixel processing unit includes insertion unitwhich passes the colour bus unchanged if the priority resolution is in favour of the priority bus bit substitutes the bits provided by the pixel processing means forthe bits on the colour bus if the priority resolution is in favour of the pixel processing unit.
13. 13. A graphics system according to claim 12, wherein each priority resolution unit comprises pipelined stages in order of decreasing significance which pass on a bit signaling the sense of the priority resolution from the first stage whereat corresponding bits of the processing unit priority number and the bus priority number disagree, the output of the last such stage signalling the sense ofthe priority resolution to the pixel insertion unit.
14. 14. A graphics system according to claim 13, wherein the stages of the priority resolution unit are pipelined at pixel rate.
15. 15. Agraphics system according to claim 13 or 14, insofar as dependent upon claim 8, wherein the active signal also controls the fi rst stage ofthe priority resolution unit so asto indicate resolution infavourof the priority bus if the active signal is not asserted.