GB2187368A - Graphics display processors - Google Patents

Abstract

A display processor for processing polygon and vector data in a computer graphics system. In the polygon mode, data defining the edges of each polygon to be processed is provided to the display processor, and a series of "spans" are created by the processor, each of which defines the condition of each pixel within the polygon along a raster line of a display screen. Computations of color, intensity, and depth are made in parallel and the results stored in frame (22) and Z (23) buffers. In the vector mode, the condition of each pixel along the vector to be drawn is determined by the processor, with calculations of intensity and depth being carried out in parallel. Hidden surface and line removal is accomplished by the Z buffer (23). <IMAGE>

Description

SPECIFICATION Graphics display processors The synthesis of visual scenes through the use of computers (computer graphics) is a growing area of computer science. There are innumerable applications of computer graphics including Computer Aided Design (CAD), the synthesis of demonstrative charts, creation of titles and other graphic displays for television use, and the simulation physical events.

In order to facilitate the generation of a scene including an object or objects by computer, normally the first step is to create three dimensional descriptions of the objects to be displayed and to store them in mathematical form in a database. The data is then processed and manipulated so that the scene can be displayed on a view screen.

The processing of information from the database can be thought of as involving five basic functions: 1. Breaking the objects down (mathematically) into small sections which can be conveniently handled. These sections are commonly plane polygons, each representing a portion of the surface of an object to be displayed.

2. Extracting data corresponding to a section of an object from the database; 3. Transforming the three dimensional description to a two dimensional description in "screen" coordinates; 4. Selecting the pixels of a viewscreen which must be activated to display the section, and defining their color and intensity; and 5. Determining which areas of the section are visible in the scene and displaying those areas.

Repetition of this process for all of the sections of all objects in the scene will result in a display depicting the desired scene.

The present invention is concerned with the latter two processes. In addition, the present invention is concerned with the drawing of vectors, or line segments, on a view screen which may or may not display other objects.

Prior art display processors have been limited in the speed with which data is processed and displayed. The limitation has been due, in some measure, to the tendency in the prior art to use general purpose computers, controlled by software which includes the algorithms for performing the required operations. This has of necessity required that computations be performed serially so that the final result may not be achieved as rapidly as might be desired.

Accordingly, there is described herein an improved display processor for a graphics processing system which is capable of significantly improved speed of operation with respect to the prior art.

In the improved display processor, dedicated hardware and pipelining is provided so that many of the needed calculations are performed in parallel, resulting in a significant increase in speed of operation. In addition, unique efficient algorithms are utilized, further improving speed.

The described processor uses a raster scan display as opposed to a random scan or point plotting display. It is intended for use in connection with an external database and geometry processor which supply data in the form of packets of data, each of which describes a plane polygon or a line segment in a three dimensional coordinate system. The origin of the coordinate system in the presently preferred embodiment of the system is the upper left hand corner of the screen but other locations could be used, if desired. Integer values of X refer to pixel positions to the right of the origin, and integer values of Y refer to raster line numbers down from the top. Depth [Z] values refer to relative distance behind the screen.

As is common in the computer graphics field, each object in the scene to be displayed is broken up into a series of small, not necessarily regular, plane polygons. In the case of complex objects, such as a human face for example, the polygons are made small enough and of such shape and color that together they make a satisfactory representation of the desired object.

Simpler objects, such as flat surfaces with-flat lighting, may be represented satisfactorily by larger polygons. The improved display processor is intended to reproduce representations of both complex and simple objects.

There are two basic modes of operation of the display processor. In one mode (called polygon fill), polygons are reproduced on the view screen positioned so that the effect of all the polygons together is a representation of the objects or scene desired. In this mode, each polygon is reproduced on the screen as an area of color not bounded by a contrasting outline.

Each polygon is characterized by a uniform color over its area, the intensity of which may vary, depending on the shading desired. Shading is controlled by intensity gradient information supplied by an external geometry processor. The shading of a polygon can be flat (uniform) or it can vary linearly over the surface of the polygon in either the X direction, the Y direction, or both.

In a presently preferred embodiment of the invention color and intensity information for each pixel on the screen are combined in a single 12 bit binary number stored in a frame buffer. The more significant bits are used to designate color, and the lesser significant bits are used to designate intensity. The user is free to determine how much of the word is used to define color, and how much is used to define intensity. To form the combined word, the results of intensity calculations are "right shifted" by the number of bits necessary to place them in the desired position in the word, and then the shifted intensity value is added to the binary number designating color, where the color designating bits occupy the most significant positions.

In the polygon fill mode, the display processor utilizes data defining each edge of a polygon in order to create "spans" containing color and intensity information, each "span" containing information relating to one raster line to be displayed. After comparing the depth location of the polygon at each pixel address with the depth of any previously processed polygons (by use of a "Z" or depth buffer), the color and intensity information is entered into the frame buffer at the pixel address only if the comparison shows that the new polygon is closer to the screen at that pixel location than any of the previously processed polygons. In this manner, hidden surfaces of polygons are removed and not displayed. The polygons used in the polyon fill mode are not necessarily solid, but may have internal openings.In accordance with the principles of the present invention, polygons having such openings or cutouts need not be processed specially, but are handled in the same manner as are normal polygons. More than one span will be created for each raster line which intersects a polygon opening, but system operation will remain the same.

In the second mode, called "vector draw", straight line segments can be drawn on the screen at desired locations. The vector draw mode is also used for "edge highlighting", i.e., bounding a polygon (or group of polygons) with a line of color different from the polygon itself.

The vector draw mode utilizes information defining the coordinates of each vertex, and the line slope (in the XY, XZ, and YZ planes) to sequentially address the pixels to be activated to draw the line.

Provision is made for drawing vectors having a dashed appearance. The repeat of a "font" creating any desired pattern of on and off pixels can be up to 64 pixels. This is accomplished through the use of a unique shift register with a continuously circulating combination of 1 's and O's corresponding to the desired pattern. An output of the shift register inhibits writing into the frame buffer when the register output is in the "1" condition. The fonting feature can be used in conjunction with the polygon fill mode to create a textured surface effect.

In the accompanying drawings, by way of example only: Figure 1 is a simplified block diagram of an entire graphics processing system.

Figure 2 is a block diagram of a display processor embodying the invention.

Figures 3A and 3B together are a block diagram of a video processing subsystem embodying the present invention.

Figure 4 depicts an illustrative polygon used to help explain the operation of the system in the polygon fill mode.

Figure 5 depicts an illustrative line segment used to help explain the operation of the system in the vector draw mode.

Figure 6 is a block diagram of the front pattern register and font length counter of the processor.

Fig. 1 depicts a generalized block diagram of a complete graphics processing system such as could be used in connection with the invented display processor, showing the major subsystems and their interconnections. Information describing each object or surface within the scene to be displayed is entered into the system through a user interface 10, which may, for example, include a joystick, a mouse, a graphics tablet, a dial box, a track ball, or an alphanumeric keyboard.

In order to synthesize a scene, the surface of each object in the scene is organized as a series of plane polygons which together are a close approximation of the object or objects to be displayed. Data defining these polygons are stored in a database 11. When the scene is to be displayed, packets of data, each describing one polygon, are transferred to geometry processor 13 one at a time over VME data bus 12. While the geometry processor computes on one packet of data, database 11 is preparing to transfer the next packet.

For each polygon to be displayed, the geometry processor 13 provides data to the display processor 20 in raster coordinates defining each edge of the polygon, as well as giving certain data relating to the polygon as a whole. This data is also transmitted over the VME data bus 12. Display processor 20 converts the edge and polygon data received into data specifying the color, intensity and relative depth of each pixel in the active raster, stores the data in a frame and "Z" buffers 22 and 23, and finally causes a display of a visual rendition of the scene to appear on a CRT 21.

Frame buffer 22 and Z buffer 23 are conventional devices used in the computer graphics field.

In the presently preferred embodiment of the invention, the frame buffer comprises a randomly addressable memory subsystem of 1280x 1024 addresses, each address storing 12 bits. The Z buffer has the same subsystem size, but accommodates 16 bits.

There are two basic operating modes for processing of data in the display processor, as will be described below. These modes are the rendering of polygons in color, or "polygon fill', and the drawing of line segments, or "vector draw". In addition, a "bypass" mode enables initialization commands to be directed to the frame and Z buffers 22, 23 to set X and Y addresses to be used as the starting addresses for the operating modes.

For purposes of the following disclosure, the coordinate system and the notation illustrated in Fig. 4 have been adopted. Fig. 4 shows, for purposes of illustration, a plane polygon 42, 43, 44, 45 superimposed on a coordinate grid. A triangular hole 46, 47, 48 is located in the interior of the polygon. The polygon shown may be a complete surface in and of itself, or it may be a small segment of a complex surface to be displayed. The display processor treats both situations identically.

An XY coordinate system having its origin at the upper left hand corner of the screen is used.

The raster lines are numbered consecutively downward, and pixel positions are numbered consecutively to the right of the origin. A pixel location is defined by the coordinates of the upper left hand corner of the square which includes the pixel. Thus, the pixel represented by the crosshatching at 41 is located at 7,3.

Each pixel address (e.g., Xt, Yt) is comprised of an integer represented by the most significant bits of a 12 bit binary word. The precise value of X at the intersection of an edge with a raster line, however, is usually not an integer, as illustrated by the point X, in Fig. 4. In some cases the integer value of a quantity such a Xu rather than its precise value is involved in calculations, and in such cases an underline is used (e.g., Xu) to indicate the integer value. The integer value may be obtained by simply truncating the binary word for the precise value to the number of bits representing integers.

Edge 42 of polygon 42, 43, 44 and 45 terminates at two vertices 40 and 49. A set of coordinates Xt, Y , and Z, are defined by the pixel in which the top vertex (40) is located, Zt representing the distance behind the screen of the point Xt, Y. A value called Xu is also defined as the value of X (with high precision) at the intersection of the edge with the first raster line it intersects, line (i.e., raster line Yt+ 1, called Yj.

Similarly, Xd can be seen to be the precise X coordinate of the intersection of the edge 42 with the raster line just above vertex 49. Xb, Yb, and Zb are the coordinates of the pixel containing vertex 49. The slopes of the edge with respect to the three axes are denoted by the functions dX/dY, dZ/dX, and dZ/dY.

Another variable involved in the display is intensity, denoted by the letter S. Depending on the desired shading of the polygon, S may vary with respect to any or all of the axes as represented by the function dS/dX, dS/dY, and dS/dZ.

In a presently preferred embodiment of the invention, intensity calculations are carried out with 27 bit precision in order that roundoff errors not affect the display. This precision is much higher than is necessary for display purposes however, and fewer bits are used to set pixel intensity of the CRT. Color and intensity information for each pixel are both contained in a single 12 bit word formed during processing and stored in frame buffer 22 at the pixel address. Color is specified by the most significant bits, the user selecting the number of bits needed to specify the number of colors desired. Intensity is specified by the least significant bits.In order to generate a 12 bit word including both kinds of information, first a 12 bit color word is generated (by the geometry processor) wherein the color information occupies the user assigned number of most significant bits, the remaining bits being zeros. The 27 bit intensity word is truncated and clipped to 12 bits and then right shifted by the number of bits necessary to avoid the color bits. The color word and the intensity word are then added to obtain a composite word containing both quantities. A limiting circuit 98 is provided to prevent the intensity word from overflowing into the color bit area of the word.

A simplified block diagram of a presently preferred embodiment of the invented display processor 20 may be seen in Fig. 2 where the major blocks of the processor are depicted and the predominant data and instructional paths are shown. The processor is under the direct control of microsequencer 26, which receives commands over VME data bus 12 from the geometry processor, the user interface, or other portions of the system as appropriate. Within microsequencer 26 is a writeable control store (a randomly addressable memory subsystem) which, in the presently preferred system, can accommodate 8 K words60 bits. Upon initialization, the micro program to control the display processor is downloaded into the writeable control store portion of the microsequencer 26 via VME data bus 12.In operation the microsequencer produces a sequence of addresses, and program instructions are issued to those addresses by the writeable control store. instructions to the microprocessor 27 are conducted over bus 39 and to the video processing means over bus 34. References to the microsequencer 26 herein are intended to refer to both the microsequencer and writeable control store.

As noted above, the display processor 20 accepts data from the geometry processor 13 and manipulates it so as to result in the desired display. Data arriving from the geometry processor is fed to one of two identical input memories 24, 25. Each of the input memories 24, 25 consists of bus gating, input and output registers, an address counter/register, and a random access memory subsystem. At any given time, one of these memories is coupled to the VME data bus 12 and the other to the Y & D busses of the display processor. Thus one memory can be receiving input data via the external interface while previously received data stored in the other memory is being operated on. Instructions from writeable control store 26 provide the control for input memory function selection.

Addressing of the memories can be either sequential or random under micro program control.

When a read operation is performed, the data is loaded into the output register of the memory and at the appropriate time applied to the D Bus. For write operations, data from the Y Bus is loaded into the memory input register and then into the memory subsystem itself under micro program control. During the processing of a block of input data, the input memory can be utilized to store immediate results.

The arithmetic processing elements and data buffers (microprocessor 27, multiplier 28, and associated registers) provide for 16 bit parallel arithmetic and logic operations. Arithmetic operations consist of addition, subtraction, multiplication, division, increment, decrement, sum, single and multiple shifts and compare. All common logic functions can be performed including and, or, exclusive or, logical inversions and others.

Multiplication is accomplished in high speed multiplier 28 which accepts two 16 bit operands from the Y bus and outputs a 32 bit product on the D bus (in two cycles). By passing one of the operands through a reciprocal table, which for purposes of this disclosure can be considered to be within multiplier 28, division is accomplished.

All arithmetic operations other than multiplication and division and all logic operations are accomplished in the micro programmable micro processor 27, which in a presently preferred embodiment, consists of a full 16 bit parallel arithmetic/logic unit, 16 bit barrel shifter, thirty-two 16 bit registers and associated logic. Output data and/or intermediate data can be temporarily stored in the input memories 24, 25 or the scratch memory 31.

The output of the processing function is normally fed to a 64 word by 18 bit first-in-first out (FIFO) memory 29 which provides for loose data coupling to the video processing subsystem ("VPS") 30.

The information fed to display processor 20 depends upon which mode of operation is desired, polygon fill or vector draw. Whichever mode is selected, the information is supplied in packets, a packet in the polygon fill mode describing one polygon, and in the vector draw mode, one line segment.

In the polygon fill mode, a packet includes information defining each edge of the polygon, and information relating to the polygon as a whole. For each edge, the following data (called an "edge packet") is provided: PTR an identification pointer which allows access to the polygon related data; HOR-a flag indicating whether or not the edge is horizontal; SSF-a start/stop flag indicating whether the polygon interior is to the left or to the right of the edge; X,; Y Z,; x.

S'.; Yb; dX/dY; and dS/dY.

For the polygon as a whole, the following is provided: Color of the polygon surface; dZ/dX; and dZ/dY.

After the above information for a complete polygon is received at one of the input memories 24, 25, micro sequencer 26 couples that memory to the D and Y busses and initiates computation to determine which pixels in the raster are to be activated to display the polygon. For purposes of explanation, the operation of the system will be described with reference to the illustrative polygon of Fig. 4. It should be noted that the pixel size illustrated in Fig. 4 is very large in relation to the polygon size so that the displayed representation of the polygon of Fig. 4 would be substantially distorted. For purposes of explanation, however, the principles of the present invention are more evident when reference is had to relatively large pixels.

In general terms, microprocessor 27 and multiplier 28, and associated components, take the edge and polygon data fed into the input memories 24, 25 and, for each active raster line of the polygon, supply data to the video processing subsystem ("VPS") 30 which identifies the starting and stopping pixels on the line, and the Z and S values for the starting pixels. VPS 3Q takes this data, together with gradient data passed through to it, and calculates the intensity and Z values for each pixel between the start and stop pixels. The Z values are used for hidden surface removal and are stored in Z buffer 23, while the intensity values for surfaces which are not hidden are stored in the frame buffer 22 for later display by CRT 21.

When computation is initiated, a list of input memory addresses (called the "ordered Yt list") is formed and stored in scratch memory 31. The addresses in the list refer to locations in the active input memory (24 or 25) which contain the edge packet data relating to the respective edges of the polygon being processed. The list is maintained in order of the raster line which includes the top vertex of each edge, i.e. Yt. A given entry in the ordered Yt list may include the addresses of more than one set of edge packet data. The ordered Yt list for the simple polygon illustrated in Fig. 4 would contain addresses for locating the edge packet data in the following order: Entry No. Edge packet address 1 42, 43 2 46, 47 3 44 4 45 It may be noted that edge 48 does not appear in the above list.This is because edge 48 is a horizontal edge and thus does not bound any internal pixels. The horizontal edge flag, HOR, prevents horizontal edges from being processed. Use of the ordered Yt list increases the speed of the display processor since it allows sequential processing of the raster lines which intersect each edge, without the need to process raster lines above or below the end points of the edges. In other words, using the polygon illustrated in Fig. 4 as an example, the ordered Yt list permits processing of the data to begin with the raster line assocaited with the top vertex of the edge packet associated with edges 42 and 43, i.e., line 1, and not line 0.As will appear later, because of the way the data is processed, raster line Y,+ 1, i.e., Yu (or raster line 2, in the case of edges 42 and 43) will in actuality be the first raster line having active pixels.

After the ordered Y, list is completed, computation by the display processor proceeds to create a series of "spans", which together will cause a polygon having the desired coloring to appear on the CRT screen. A "span" is the data which defines the condition of each pixel along a raster line bounded by two edges of the polygon. In the case of some polygons there may be more than one span on a raster line. For example, in Fig. 4, raster line 6 will include two spans.

Spans are created one at a time starting with the span involving the lowest numbered raster line intersected by the polygon (as is determined by reference to the ordered Y, list). To facilitate processing, an "active edge list" is created and maintained. The active edge list includes the addresses of the edge packet data corresponding to each edge which intersects the raster line currently being processed.

The creation of the spans will be described in two steps, first the calculations performed by microprocessor 27 and multiplier 28, and associated components, and second, the operations performed in the VPS 30.

Referring to the ordered Y, list for the illustrative polygon of Fig. 4 reveals that the active edges corresponding to the first raster line to be processed are edges 42 and 43. The active edge list will then contain the edge packet addresses for edges 42 and 43. The edge packet for edge 42 will contain a start flag, while the edge packet for edge 43 will contain a stop flag.

An arbitrary rule has been adopted in connection with the presently preferred embodiment of the invention which specifies that a pixel will not be considered to be a part of a polygon unless the coordinates of the pixel (the upper left hand corner of the pixel space) is within the bounds of the polygon. Thus, according to the rule, the first active pixel in the polygon of Fig. 4 is pixel 5, 2. The start and stop pixels along a raster line may be determined by the following equations: for a start edge: xl=x,+ 1; and for a stop edge: x2=-x, where X, is the X coordinate of the starting pixel of the span, X2 is the X coordinate of the last pixel of the span, and X is the integer value of the actual intersection of the edge and the Y coordinate of the span.

For the first span (Y=2), #X, for edge 42 is Xu, i.e. 4; for edge 43, X is 6.

As will be realized, prior to making the above calculations, the X coordinates of the start and stop edges for the raster line must be ordered and paired. In connection with the pairing computation, a test is made to exclude any apparent spans wherein the stop pixel has a lower address than the start pixel. Such an anomaly can occur when a portion of a polygon subtends less than one pixel, or when a computational roundoff error projects the edges slightly out of order. In either event, such data is not processed. The pairing and ordering is accomplished by microprocessor 27 under control of the program in the writeable control store 26.A consequence of the ordering of the start/stop coordinates and not processing pairs wherein the stop pixel has a lower address than the start pixel is that holes in a surface automatically appear as holes, and no special processing is required to accomodate them.

The value of Z, (the Z coordinate of the first active pixel) for the first raster line (Yu) is computed from Zi and the Z gradients supplied by geometry processor 13 as follows: Z, =Zi+(#Xu#Xt)(dZ/dX)+dZ/dY where X is the integer value of Xu.

For raster lines following YuS the equation is: Z1=Z1(prev)+(#,-X(prev)(dZ/dX)+dZ/dY where Z1(prev) is Z1 of the previous raster line, y is the integer value of the actual intersection of the edge and the Y coordinate on the current raster line, and #X,(prev) is #X, of the previous raster line.

The data provided by geometry processor 13 includes Sot , the intensity of the first active pixel of raster line Yu (i.e., X,r+ 1). For subsequent raster lines, the following equation is used: S1 = S1 (prev) + dS/dY where Sl(prev) is S1 of the previous raster line.

The ending intensity for each raster line (S2) is also calculated in a similar manner using the starting S value and gradient for the stop edge of the span. the gradient dS/dX for the span is then computed: dS S2-S1 dX X2-X1+1 The additional 1 in the denominator accounts for the fact that S2, as computed, does not really relate to the last pixel in the span, but to the pixel beyond the last one.

There may be more than one span on a given raster line as, for example, in the region of the polygon of Fig. 4 which includes a hole. Each edge of the hole is treated as a polygon edge and when the edges are being paired it will be found that the stop flag accompanying edge 46 precedes the start flag accompanying edge 47. The region of the raster line between the edges 46 and 47 are thus not processed. The above computations must be made with respect to each pair of active edges. Upon completion of all the span calculations for a raster line, Y" for all active edges is compared with the current raster line address. If Y" has been reached for any edge, that edge is no longer processed.Also, the edge packet corresponding to the next entry on the ordered Yt list is accessed to determine if Y, has been reached for a new edge. If either has occured, the edge pairings are appropriately adjusted. When the last Y" is passed, calculations for that polygon are terminated and calculations for the next polygon initiated.

For the polygon illustrated in Fig. 4, for example, the active edge list initially includes the addresses for the edge packets describing edges 42 and 43. After raster line 3 has been processed, edges 46 and 47 will be added to the active edge list and the edge pairings will be updated to: 42, 46, and 47, 43. After raster line 4, since Y,, for edge 43 and Y, for edge 44 have been reached, edge 43 is deleted and edge 44 is added to the active edge list. The pairings are appropriately adjusted.

As the span calculations are completed, the results are loaded into FIFO register 29 and they then flow into the appropriate registers of VPS 30 through buffer register 33 when required by VPS 30. FIFO 29 allows VPS 30 to be operating on one set of span data while another set of data is being loaded into the FIFO. In order to allow for this overlap, it is preferred that FIFO 29 be "deep" enough to hold at least two complete sets of span data.

The data transmitted to VPS 30 in the polygon fill mode is as follows: (The reference to a number of bits following each entry refers to the number of bits transmitted in the presently preferred embodiment of the invention, included herein for purposes of example. It may be noted that the data bus used can accommodate only 16 bits so that some data values require two machine cycles to be completely transferred.) Polygon Data: dZ/dX-30 bits Y1- 1 (the address of the raster line above the first Yu of the polygon)~12 bits Color~12 bits Intensity shift~4 bits Font pattern~64 bits (all zeros) Font length~6 bits (all ones) Span Data:: X1 -12 bits, X2 -12 bits, Z1 -30 bits; S, --27 bits; Yinc 1 bit In addition to the above, the gradient dS/dX is transmitted. Depending on the type of shading desired, dS/dX may be a polygon related quantity or a span related quantity. The flag Yinc is sent with the first span on a given raster line as a signal to VPS 30 to increment the Y register in VPS 30 and the frame and Z buffers to the next raster line prior to processing span data.

The significance of the font signals will be explained below in connection with the vector draw mode.

As described in connection with the polygon fill mode (all zeros in the font pattern register and all ones in the font length register) the fonting function is inactive. However, as will be evident to those skilled in the art after reading the explanation of fonting in the vector draw mode, the fonting function can be utilized in the polygon fill mode to achieve texturing of the surface displayed.

Figs. 3A and 3B comprise a block diagram of VPS 30 (the video processing subsystem), 30A being the data handling elements and 30B the controller which controls the data processing functions of the VPS. The arrows to "C" in Fig. 3A refer to a connection to controller 30B. The control lines from controller 30B to the various registers, multiplexers, adders, and comparators are not shown for clarity.

Upon receipt of a command over line 34, VPS 30 initiates loading data into its data registers over line 35. Data is loaded into the following registers in a predetermined sequence under control of microsequencer 26 through Y bus register 31 and buffer register 32 over line 35: Quantity Register dZ/dX dZ/dX, 52 Y1 Frame Buffer, 22 and Z Buffer 23 color Color, 54 Intensity shift Intensity Shift, 55 Font pattern Shift Register 56 (all zeros) Font length Font length, 57 (all ones) After the foregoing polygon related quantities are loaded, the following span related quantities are loaded from FIFO 29 through buffer register 33 over line 35:: Quantity Register X1 X1, 58 X2 X2, 59 S1 S, 61 Z, Z, 60 Y,nc Frame Buffer, 22 and Z Buffer, 23 As X1 is loaded in X1 register 58, the X address registers of frame buffer 22 and Z buffer 23 are also set to X,. Yinc accompanies only the first span on a raster line.

The presently preferred embodiment of the invention operates at a clock rate of 10 MHz so that each quantity having 16 bits or less can be loaded in one machine cycle of 100 nanoseconds while those having more than 16 bits are loaded in two machine cycles. After loading is complete, processing of the span data for the first span is started. Calculations of the various parameters are done in parallel at the 100 nanosecond clock rate. It may be noted that Z and S calculations are made with high precision (30 and 27 bits respectively) but only 16 and 12 bits respectively are retained in the Z and frame buffers. This is done to prevent a buildup of roundoff errors from affecting the operation of the system.Truncation to 16 and 12 bits respectively is indicated in the block diagram of Fig. 3 by the legend "TRUNC". The magnitude of the data is also limited so as to be within permissible ranges. Such limiting is indicated on Fig. 3A by the legend "LIMIT".

As the calculations for the first span are started, Yinc causes the Y address registers of the frame and Z buffers 22, 23 to be incremented by 1, bringing the addresses to the value Yu for the first raster line of the polygon.

At the same time, the Z value in Z buffer 23 at location X1, Y1 is coupled through register 62 to comparator 63 where it is compared with the contents of Z register 60 (truncated to 16 bits). If the value from register 60 is equal to or less than the value in the Z buffer, the truncated value in Z register 60 is coupled through multiplexers 64 and 66 to the Z buffer and written in place of the old Z value. If the contents of register 60 is greater than the old Z buffer value, the old value is rewritten into the Z buffer. In this way, the Z buffer keeps a record of the Z value of the object closest to the screen at each address. The results of the comparison in comparator 63 together with a signal from font pattern register 56, through AND gate 65, signals controller 30B whether to enable writing into the frame buffer at that address.For purposes of this explanation it is assumed that the output of font pattern register 56 is such as to enable AND gate 65 so that it is the Z value comparison only that determines whether a new value will be written into frame buffer 22. The fonting features will be discussed below. It can be seen that the Z value comparison accomplishes hidden surface removal by causing the frame buffer to contain only information relating to the nearest object.

At the same time, the contents of dZ/dX register 52 is added to the contents of Z register 60 in adder 67 and the result coupled back to Z register 60 through multiplexer 68. The new contents of Z register 60 is the Z value corresponding to pixel location X1+ 1 (Zl+dZ/dX).

In parallel with the aforementioned calculations, the contents of intensity shift register 55 acts on shift unit 75 to shift the truncated contents of S register 61 some predetermined number of bits to the right, the resulting value being added to the contents of color register 54 in adder 76. Limit circuit 98 is provided to assure that the intensity value added to the contents of color register 54 does not intrude on the color bits. The sum so formed defines a color and intensity as previously described. The output of adder 76 is coupled through multiplexer 77 and frame data register 78 to the frame buffer 22. If the Z comparison determines that the polygon being processed is closer to the screen at this address than previously processed polygons, writing of this value into the frame buffer is enabled, as discussed above.

Also, at the same time, the contents of dS/dX register 85 is added to the contents of the S register 61 in adder 86, resulting in a new intensity value which is coupled back to S register 61 through multiplexer 87. This will be the value of S used for pixel X1+ 1 (Sl+dS/dX).

Finally a comparison of X1 register 58 and X2 register 59 is made in comparator 90. If they are not equal, the X1 register and the X address registers in frame buffers 22 and Z buffer 23 are all incremented by 1 and the above calculations repeated for pixel X1 + 1. Incrementing of the XT register is accomplished by adding one to the contents of the register in adder 93 and writing the result back into the register. This process continues until the contents of X1 register 58 equals the contents of X2 register 59 at which time comparator 90 causes controller 30B to emit a "done" signal.of one bit over line 36 to the microsequencer 26.Upon receipt of the "done" signal, which signifies that VPS 30 has completed calculations for one span, microsequencer 26 causes FIFO 29 to begin filling the registers of VPS 30 with data for the next span.

This process continues until all spans for a given polygon are completed, after which either another polygon can be started or a line segment can be drawn in the vector draw mode.

If the next function to be performed is the drawing of a vector, or the drawing the edge of a polygon in a shade other than the face shade (edge highlighting) the frame and Z buffers are filled using a different processing algorithm than described above. The information received at the input memories 24, 25 in the vector draw mode is similar but slightly different from that received in the polygon fill mode. For purposes of example, the following explanation of drawing a line segment in the vector draw mode will refer to the line segment illustrated in Fig. 5. This line segment has an upper vertex within the pixel space 9,1 and a lower vertex in the space 1,5. The notation is the same as used in connection with the polygon fill mode. For purposes of illustration, the pixel areas which will be activated when the postulated line segment is drawn are shown crosshatched (assuming that the line segment drawn is the closest object to the view screen).

For each vector, the following quantities are sent by the geometry processor 13 over VME data bus 12: X (X1) Y (Y1) Xb (X2) Yb (Y2) Z, or alternately Zb; Xu or alternately Xv; dX/dY; dZ/dX; dZ/dY; Color (including intensity); Font pattern; Font length; The order in which Xt, #t and Xb,Yb are sent determines whether the line segment will be drawn from the top down or from the bottom up. The order in the foregoing list will result in a downward draw. By sending Xb,Yb in the X1,Y, positions, Xt,Yt in the X2,Y2 positions, and sending the alternate quantities, Zb and Xv, the draw will be upward. The following explanation applies to a downward draw.

The direction of draw is established by two flags SBX and SBY. These flags are generated by microprocessor 26 as a result of comparing X1 with X2 and Y, with Y2. If X, is greater than X2, SBX= 1, and if Y, is greater than Y2, SBY=1. These flags determine whether the X, and/or Y, registers (58 and 95) in VPS 30 are to be incremented or decremented during the draw sequence. If an SB flag is set (1), the associated register is set to be decremented, while if the flag is not set (0), it will be incremented. If X, register 58 is decremented (SBX=1) and Y, register 95 is incremented (SBY=0), the vector will be drawn downward and to the left. If SBX is set to 0, X, register will be incremented and the vector will proceed to the right. If SBY is 1, the vector will be drawn upwards.Incrementing or decrementing of the X1 and Y, registers is accomplished by adders 93 and 94 which add or subtract one from the contents of the related register and rewrite the results back into the register.

As in the polygon fill mode, the data required to draw a line segment is coupled to VPS 30 through one of two paths: through FIFO 29 and buffer register 33, or through Y bus register 31 and buffer register 32. The following registers are loaded: Data Register X1 X, (58) Y, Y1 (95) Z, Z (60) Xu Xu (61) Xb X2 (59) Y Y2 (96) dX/dY dX/dY (85) dZ/dX dZ/dX (52) dZ/dY dZ/dY (97) Color Color (54) Font pattern font pattern (56) Font length font length (57) HOR controller 30B SBX controller 30B SBY controller 30B The address registers of frame buffer 22 and Z buffer 23 are set to X1, Y, over lines 70 and 71 respectively.

After the data has been loaded into the VPS 30 registers, the draw sequence is started by command from microsequencer 26. A comparison of the contents of Z register 60 (truncated to the same number of bits as in the Z buffer (16)) with the previous contents of the Z buffer are made in a manner similar to that described for the polygon fill mode, except that after each calculation Z register 60 is not only incremented by dZ/dX each time the X address is incremented, but is also incremented by dZ/dY from dZ/dY register 97 each time the Y address is incremented.If the truncated contents of the Z register 60 at any comparison is equal to or less than the contents of Z buffer 23 at that address, the new value of Z is written into the Z buffer and the contents of color register 54 is coupled through multiplexer 77 and frame data register 78 to the frame buffer 22 in the same manner as previously described.

The initial pixel address is Xl, Y, as noted above. Using the vector illustrated in Fig. 5 for purposes of illustration, it can be seen that X, Y, is at coordinates 9, 1. Since X, is greater than X2 and Y2 is greater than Y1, SBX= 1 and SBY=0. X1 register 58 will therefore be decremented and Y, register 95 will be incremented as the vector draw proceeds.

Before any register is incremented or decremented, Y1 is compared with Y2 (comparator 91), X1 is compared with X2 (comparator 92), and X1 is compared with X, (the contents of Xu register 61 truncated to 12 bits (comparator 90). In the specific example of the line segment illustrated in Fig. 5, Y1=1, Y2=5, X1=9, X2=1 and ~u=8. If none of the comparisons result in equality, and, in the example chosen they will not, X1 register 58 is decremented by one pixel space as are the X address registers of the frame and Z buffers. The Z comparison and write into the Z and frame buffers operation is then repeated for the pixel now addressed: 8, 1.

When the X and Y comparisons are made this time, it will be noted that X will equal the contents of X, register 58. When this occurs, comparator 92 enables controller 30B to increment register Y1 and the Y address registers of the frame and Z buffers (22, 23). At the same time the contents of dX/dY register 85 is added to the contents of X,, register 61. The contents of Xu register 61 will then be the exact coordinate of the intersection of the vector with Y=3. It may be noted that the intersections of the vector with the Y pixel coordinates are calculated with 27 bit precision and the values are later truncated to represent integral X coordinate addresses.The reason for this is so when the vector is being drawn for the purpose of providing edge highlighting, the vector will appear precisely at the edge of the polygon, and there will not be pixels of polygon color extending beyond the highlighted edge.

After a repetition of the Z compare and write operation at the addresses of pixel 8, 3, the three X comparisons are made, resulting in no equalities. This causes X, register 58 and the X address registers of the Z and frame buffers to be decremented one address. This procedure is repeated every clock cycle until there is an equality between the X1 register 58 and the X2 register 59, or the Y, register 95 and the Y2 register 96, or both. After X1 (58) equals X2 (59), the X registers are not longer decremented, and after Y1 (95) equals Y2 (96), the Y registers are no longer incremented. When both equalities occur, the vector has been completed and controller 30B sends a "done" signal to microsequencer 26 over line 36.

As will be realized, any regions of the vector wherein the Z value stored in the Z buffer 23 is less than the Z value of the vector at that address will not be drawn, but the object previously entered in that region will remain in the buffers and be displayed in the final scene. Similarly, subsequent polygons or lines whose Z values indicate that they are closer to the face of the scene than the drawn vector at any pixel address will displace the vector at that address.

The foregoing explanation of drawing a line segment was presented without consideration of the "fonting" capability of the system.

The term "fonting" as used herein refers to the ability of the system to produce intermittent lines such as dashed lines. A wide variety of combinations or font patterns are possible using font pattern register 56 and font length register 57 to control whether a particular pixel of a vector will be activated.

Font pattern register 56 is a 64 bit parallel in, serial out, recirculating shift register which is loaded by four sequential 16 bit words at the time the vector draw data is being loaded into VPS 30. In addition, a 6 bit word is loaded into font length counter 57. The 6 bit word in font length register 57 controls the operating length of font pattern register 56 so that although a maximum of 64 stages are available, the register can operate as a shorter register, depending on the contents of font length counter 57. Thus if the repeat of the font pattern is 40 pixels, font length register 57 would be set to cause font pattern register 56 to operate as a 40 stage recirculating shift register.

The 64-bit programmable length font pattern register 56 has been designed in a unique manner to minimize gate count and area. A typical shift register is designed with a flip-flop memory element and a multiplexer for each cell. A 2 to 1 multiplexer selects either the previous cell's value or the bus value, depending on the Shift/Load signal. Additional complexity is added to the multiplexer and the select logic by requiring the shift register to be of programmable length from 1 to 64. The multiplexer in this case becomes a 3 to 1 selecter. The three inputs are the preset or loadable value, the nearest neighbor in the shift mode, and the wrap-around bit for selecting the programmable length.

The unique implementation of font pattern register 56 in the present invention has reduced the gate count from that in a typical design requiring over 600 2-input equivalent gates to about 400 gates. In order to accomplish this, first, the memory cells have been changed to D-type latches, reducing the gate count from 6 to 3.5 gates per cell. This is possible since the register does not shift the data from cell to cell but rather the output connection is multiplexed. Shifting of the output is performed by a three stage 4 to 1 multiplexer. The first stage reduces the 64 bits to 16, the second stage selects 4 from 16, and the third stage selects a single bit from the 4 remaining. The sequencing through the 64 latches via the three stages of multiplexers, is performed by 6-bit font length counter 57. The counter outputs control the multiplexer select lines. After reaching the programmed length, the counter resets and begins counting again. In toto, the number of gates are reduced by a factor of one-third with comparable performance and flexibility as compared with the prior art.

A block diagram of the font length counter 57 and font pattern register 56 is shown in Fig. 6.

Sixty-four D-type latches 101 are shown coupled to 4-16 bit input registers 105. The input data defining the font pattern arriving on line 35 is fed in four sequential 16 bit words through input registers 105-1, -2, -3, and -4 to the 64 D-type registers 105-1 through 105-64. The Q output of each latch in groups of four is fed to 16 multiplexers 102-1 through 102-16. Similarly, the output of each group of four multiplexers 102 is fed to one of four multiplexers 103-1 through 103-4. Finally the outputs of the four multiplexers 103 are fed to the last multiplexer 104.

Font length counter 57 receives a 6-bit signal over line 35 which sets it to count up to the number of the repeat in the font pattern and then to start over. The output of font length counter 57 selects one out of the 64 latches 101 to be coupled to the output of font pattern register 56 via multiplexers 102, 103, and 104 depending on the count in the counter. As the count of font length counter 57 changes, the output of multiplexer 104 scans the latches 101 in sequence. In this manner font pattern register 56 is made to operate as a programmable length parallel in serial out shift register.

To illustrate the operation of the fonting feature of the invention in the vector write mode, assume for example, that it is desired to draw a vector with a dashed effect of 15 pixels on, 5 pixels off, 5 pixels on, 5 pixels off, 5 pixels on and finally 5 pixels off. In other words a longer dash followed by two short dashes. The font length would be set to 40 pixels by font length counter 57 since that is the total number of pixels in the repeat. Font pattern register 56 would then operate as though it was a shift register of 40 stages, with the output of the 40th stage recirculated to stage 1. Negative logic is used in the font control system (0 out of register 56 resulting in an active pixel) so that the loading of register 56 should be 15-Os, 5-1s, 5-Os, 5-1s, 5-Os, and 5-1s.The output of font pattern register 56 is coupled to AND gate 65 which (depending on an appropriate Z comparison) signals controller 30B to inhibit writing data into the frame buffer whenever font register 56 has an output of 1.

At the conclusion of the processing of all polygons and line segments in the scene, frame buffer 22 will contain a 12 bit word corresponding to each pixel on the screen of CRT 21. Each word will contain information as to the color and intensity required of each pixel to be illuminated. In order to display the scene, the addresses of the frame buffer are scanned in raster fashion and the contents of each address is passed through a color "look-up" table 36 and D/A converter 37 to CRT 21. For each frame buffer address, three digital words are produced by the lookup table 36 which, after being converted to a voltage amplitude in D/A converter 37, drive the red, green, and blue guns of CRT 21 to produce the desired color and intensity at each pixel.

Claims (8)

1. A display processor for a raster scan computer graphics system which comprises a) an input memory for receiving and storing data related to at least a portion of a scene to be displayed; b) a control store for storing a processing program; c) an arithmetic processing unit for performing arithmetic and logical operations on data in said memory under control of said program; d) a video processing subsystem which accepts data both from said input memory and said arithmetic unit, said video processing subsystem providing parallel computation of relative depth in said scene and intensity for each pixel forming a part of said portion of a scene to be displayed; e) means for storing data defining the color and intensity of each pixel forming a part of said scene to be displayed;; f) means for comparing the relative depth at each pixel location in said portion of said scene to be displayed with the relative depth at each said pixel location of portions of said scene previously processed; and g) means preventing the storage of color and intensity data for any pixel forming part of said portion of said scene to be displayed, if the relative depth of previously processed portions of said scene to be displayed is less than the relative depth of said portion of said scene to be displayed at said pixel location.

2. A display processor as recited in claim 1 and further including a path for program instructions, from said control store to said arithmetic processing means and to said video processing subsystem independent of the data path between said input memory, said arithmetic processing means and said video processing subsystem.

3. A display processor as recited in claim 1 and further including a first in first out memory for coupling data from said arithmetic processing means to said video processing subsystem.

4. A display processor as recited in claim 1 wherein said input memory is comprised of two sections, said sections alternating between being coupled to an input bus for receiving data and being coupled to said arithmetic processing means in such manner that data previously received can be utilized within said display processor.

5. A video processing subsystem for producing data defining the desired intensity of each pixel on at least a portion of a raster line of a display screen in a system for displaying a representation of three dimensional objects on a two dimensional raster which comprises: a) a first data register for storing data defining a desired pixel intensity of a predetermined first pixel on a raster; b) a second data register for storing data defining an incremental value of intensity; c) means for repeatedly forming the sum of the contents of said first and second data registers, and for replacing the contents of said first data register with said sum; and d) a third data register for receiving and storing each of said sums at predetermined addresses.

6. A video processing subsystem as recited in claim 5 and further including: a) a fourth data register for storing data defining the color of the pixels in said portion of a raster line; b) means for adding the contents of said fourth data register to each of said sums forming a plurality of digital words in such manner that the data defining said color is represented by a first group of digits in said digital words and the data defining intensity is represented by a second group of digits in said digital words, said digital words being stored in said third data register instead of said sums.

7. A video processing subsystem as recited in claim 6 wherein said means for adding the contents of said fourth data register to each of said sums includes means for repositioning the digits of each said sums so as to create a binary number including only zeros in the digit positions occupied by color data in the contents of said fourth data register.

8. A video processing subsystem as recited in claim 5, and further including: a) a fourth data register for storing data defining the relative depth in the scene to be displayed of the point on an object in said scene corresponding to each pixel in said predetermined pixel; b) a fifth data register for storing data defining an incremental value of depth; c) means for repeatedly forming totals of the contents of said fourth and fifth data registers; d) a sixth data register for receiving and storing said totals at predetermined addresses; e) means for comparing each of said totals with previously obtained totals stored at corresponding addresses in said sixth data register and inhibiting the storage of any of said totals and the corresponding ones of said sums wherein said total exceeds the previously obtained total stored at the corresponding address.