WO1981002487A1 - Graphics display system and method - Google Patents

Abstract

Graphics display system (15) including a memory circuit (52) for storing vector data representing a graphics image, a raster memory circuit (54) for rasterizing the vector data into a second memory (81) for storage, and a processor (50) for controlling the operation of the vector memory (52) and raster memory (54) circuits. The raster data can be displayed on a suitable cathode ray tube monitor (20), thereby displaying the graphics image on the monitor (20).

Description

GRAPHICS DISPLAY SYSTEM AND METHOD

The present invention relates to a graphics display system and method.

Some prior art systems utilizing graphics displays have used a direct view storage tube display, which stores a graphic image directly on the face of a cathode ray tube, so that the image does not have to be continuously refreshed. This approach results in a high-resolution, flicker-free image. In addition to the stored image, a graphics cursor is con- tinuously displayed in a write-through mode, so that it does not become a part of the stored image. By using a graphics tablet or digitizer as an input device, a user can point the 'cursor at objects on a screen and issue editing commands to the system to alter these objects or add new ones. This type of display has proved adequate for the vast majority of applications in such areas as integrated circuit and printed circuit design, cartography and three-dimensional drafting designing and manufacturing.

A problem with direct view storage tube displays is that an image cannot be selectively erased, since to alter a graphics image requires the erasing of the entire old image and redrawing an entire new one. To overcome this problem, some prior art systems have employed calligraphic, or vector-stroking, displays con¬ tinuously refreshed from a list of graphic vectors stored in a vector memory. In such a vector-stroking display, the display reads X-Y coordinate data and intensity information from the memory and strokes the indicated line segments ont the screen in connect-the-dot fashion. When vector data representing a graphic image is altered in the memory from which the display is refreshed, its image on the screen^" rapidly disappears and the altered portion of the image simultaneously appears, while the remainder of the image remains unchanged.

A problem with such a vector-stroking display is that the complexity of the image which can be displayed without per- ceptible flickering is fundamentally limited by how far the display tube's^' electron beam has to travel, how rapidly the beam can be deflected and modulated, and how rapidly the image disappears from the screen.

A display which refreshes the image from a raster memory (also known as dot matrix) avoids such problems of vector stroking. Flicker-free images can easily be generated regardless of the complexity because the electron beam al- ^' ways ^"travels the same path, namely a top to bottom sequence of closely spaced left to right lines, as in a commercial television set. The raster memory is used only to modulate the intensity of the beam.

A problem with raster memories is that once data has been rasterized, there is no good way to deal with the resulting dots in the raster memory. If it is desired to remove only the dots corresponding to a given vector, one could raster- ize the vector again and use the resulting sets of dots to erase the raster memory selectively, which would generally remove too many dots. It is desirable to remove only those dots which a particular vector was solely responsible for inserting, and to leave alone those dots which were also inserted by intersecting vectors, which is difficult if not impossible, since in a raster memory all dots look alike.

As a result, after a particular vector is removed, all conceivable intersecting vectors are rewritten into the memory. In a worst case this amounts to re-rasterizing of the entire vector image, which runs the risk of nullifying the reason for going to a refreshed display in the first place, namely the ability to alter the image rapidly. In view of the above background, there is a need for an im- proved graphics display system and method which provides both vector memory and raster memory capabilities without the above-mentioned limitations.

Summary of the Invention

The present invention relates to a graphics display system and method.

The system and method includes vector memory means for managing or processing vector data representing a graphics ^'image to be displayed, transformation means for transform¬ ing the vector - ata, raster memory means for rasterizing and displaying the data, and processor means for controll¬ ing the operation of the system.

The vector memory means include means for storing the vector data, memory update means (MUDS) for performing appropriate insert, modify, delete, and selection opera¬ tions on the data, and preclipper means for performing geometric selection operations on the data.

The vector data from the vector memory means is transformed by the transformation means, which include a clipper means and a sealer means. The clipper means determines which vectors and parts of vectors are to be displayed and is further used to perform the computations involved in iden¬ tify functions. The sealer means translates and scales the clipped vector data.

The raster memory means includes means for storing raster data, write means for rasterizing the vector data provided by the transformation means, and read means for displaying the raster data on a suitable cathode ray tube monitor.

In accordance with the above summary, the present inven¬ tion achieves the objective of providing an improved graphics display system incorporating the advantages of both vector and raster memories.

Other objects and features of the present invention will become apparent from the following description when taken in conjunction with the drawings.

Description Of The Drawings

Figure 1 depicts a block diagram of a graphics data system.

Figure 2 depiGTS a block diagram of a graphics display system, which forms a portion of Figure 1.

Figures 3-6 depict the word format of a polygon entity which is one form of data utilized by the system.

Figures 7-9 depict various command formats utilized by the system.

Figures 10 and 11 depict representation of a drawing space and a screen space, respectively, which are utilized by the system. Figures 12-20 depict further formats of command functions utilized by the system-.

Figure 21 depicts a block diagram of a command processor, which forms a portion of Figure 2.

Figures 21A and 21B depict system timing diagrams.

Figure 22 depicts a block diagram of a memory update sys¬ tem which forms a portion of Figure 2.

Figure 23 depicts a timing diagram for the memory update system of Figure 22. _*

Figure 24 depicts a block diagram of a vector memory, which forms a portion of Figure 2.

Figure 25 depicts a block diagram of a memory chip of the vector memory of Figure 24.

-Figure 26 depicts a timing diagram for the memory of Figure 24.

Figure 27 depicts a block diagram of a preclipper circuit, ^"which forms a portion of Figure 2.

Figure 27A depicts a circumscribed polygon outside of a window.

Figure 28 depicts a timing diagram for the preclipper circuit of Figure 27.

Figure 29 depicts a timing diagram for the preclipper circuit of Figure 27.

Figure 30 depicts a block diagram of a clipper circuit, which forms a portion of Figure 2. Figure 31 depicts a timing diagram for the clipper circuit of Figure 30.

Figure 32 depicts a portion of a data path for the clipper circuit of Figure 30.

Figure 33 depicts a block diagram of a clipper processor, which forms a portion of Figure 30.

Figure 34 depicts a block diagram of a sealer circuit, whic forms a portion of Figure 2.

Figure 35 depicts a timing diagram for the sealer circuit of Figure 34.

Figure 36 depicts a block diagram of a write circuit, which forms a portion of Figure 2.

Figure 37 depicts a block diagram of a read circuit, which forms a portion of Figure 2.

Figure 38 depicts a block diagram of a refresh memory, whic forms a portion of Figure 2.

.Figures 39-41 depict timing diagrams for the refresh memory of Figure 38.

Detailed Description Of The Invention

In order to understand the basic operation of the present invention, a system overview will be given in conjunction with the block diagram of a graphics display system depicted in Figures 1 and 2.

Referring to Figure 1, a block diagram of a graphic data system is depicted for use in interactive graphics display systems needed in such .areas as integrated circuit and printed circuit design, cartography, and three-dimensional drafting, designing and manufacturing.

In Figure 1, a central processing unit (CPU) 10 controls the operation of the system and is connected to receive in¬ put information from console 13, disc unit 11, and magnetic tape unit (MTU) 12 by well known techniques.

CPU 10 is also connected to one or more graphics display systems (GDS) 15 via bus 56 and to one or more graphics station 17 via bus 91. GDS 15 is connected to one or more graphic stations 17 via bus 90 and provides display data on bus 90 for video monitor 20 under control of CPU 10. The subject matter of the present invention is directed toward the GDS 15, which is shown in more detail in Figure 2.

In Figure 1, graphics station 17 also includes X-Y display circuit 21 for displaying particular X-Y coordinates. Keyboard 23 and tablet 22, which are units known in the art, are connected to CPU 10 via bus 91, and provide means for communicating with CPU 10.

The system treats all data as polygons. If the beginning point and ending point of a polygon are identical, the polygon is considered closed; otherwise, it is open. The system gives the user, as will be described, the ability to define and manipulate both types.

Tablet 22 produces a pair of digital X-Y coordinate values corresponding continuously to the position of a writing stylus upon the surface of the tablet. The tablet can be placed on a table in front of the display screen, provid- ing a natural writing position for the user. In Figure 2, a command processor (CP) 50 serves as a comman center during data transfers between the host processor (CP 10) of Figure 1 via bus 56 and the remainder of the system, processes data blocks before they are transferred to the remainder of the system, and generates appropriate timing and handshake signals on system bus 57.

The system also includes a vector memory subsystem (VMS) 52 which includes a vector memory 61, memory update system (MUDS) 60, and preclipper (PC) 62. The vector memory 61 could be a random access memory (RAM), magnetic bubble memory (MBM), or charge coupled device (CCD) .

The MUDS 60 inserts vector data via bus 57 from the CP 50 into the vector memory 61 via bus 65, associatively searche and modifies items in memory 61 specified by CP 50, and selectively passes data from memory 61 via bus 64 to the PC 62 for the set view and^* identify functions, as to be des¬ cribed.

Memory 61 can be viewed as a 16 x 64K bit shift register operating at a 300 ns rate. 16-bit words are input to memory 61 on bus 65 and output on bus 64. Data output from memory 61 are processed through ring buffers in the MUDS 60 before they are re-input to memory 61.

Data from the VMS 52 are in vector data format and are sent via PC 62 to the transformation subsystem 53, which include _a clipper (C) 70 and sealer (S) 71 circuits. PC 62 accu¬ mulates data via bus 67 from MUDS 60 in relative coordinate and processes them to make the data absolute, compares line segment deltas with the censoring value received for the current set view to determine whether the current point needs to be retained for the clipper 70. PC 62 also per¬ forms a preliminary check on each polygon to determine whether it might intersect the window and sends to the transformation subsystem 53 only those polygons which pass this test. The clipper 70 receives data from PC 62, performs clip func¬ tions, and delivers the processed data to the sealer circuit 71. Other system functions include, as will be described, identify point, identify segment, identify window partial and identify window full. The clipper 70 also delivers data upon command to the CP 50 via system bus 57. The sealer 71 circuit provides during a set view operation the magnify, translate, scale and buffer functions.

The processed data from the transformation system 53 is sent to the raster memory subsystem (RMS) 54, which includes write (W) circuit 80, refresh memory (RM) circuit 81 and read (R) circuit 82.

_*

Write circuit 80 performs the function of rapidly generating points in a 512 x 512 matrix field to approximate the location of two-dimensional straight line vectors, which are subsequently transferred to 256K-bit refresh memory 81, which is used to refresh a standard raster-scan CRT monitor via bus 90 under control of* read circuit 82. -Refresh memory 81 receives the appropriate data from write circuit 80, and read circuit 82 generates the intensity and synchronization signals necessary to display a graphics image on a typical CRT monitor such as CRT 20 in Figure 1 via bus 90. Other, 'functions of the read circuit 82 are to erase refresh memory 81, display the cursors, and display the grid.

In the present embodiment, the data representing a graphi¬ cal image is characterized in the form of polygons, as pre¬ viously described.

Display Entities

Vector data representing one or more graphics images to be displayed, for example, on a conventional cathode ray tube (CRT) are stored in a vector memory subsystem 52, as depicted in Figure 2. A graphics image to be displayed is represented by a serie of vectors, which form a pattern or figure representing an image to be displayed by a series of straight lines or vectors interconnected via their respective vertices. The vector data can be in the form of open or closed figures, and for convenience purposes will be described in terms of polygons.

In Figure 3, the word format of a polygon is depicted and includes, in one embodiment, between four and 126 16-bit words. Words 0-6 represent header information which des¬ cribe and identify a particular polygon to the system.

Word 0 of Figure 3 is depicted in Figure 4, and includes three pieces of information used by the system to recogniz the boundaries and sub-boundaries of polygon entities, and to initiate/terminate selected operations on the entities.

In Figure 4, bits 0-7 indicate the size N, where N is the total number of words in the entity. One entity in genera describes one polygon. The mark bit (bit 8) is set to indicate the beginning of an operation on the entities, as will be described within the command section. The mark bi is reset on completion of such an operation. In the forma ^'section of word 0 (bits 9-15), the descriptor length is a 2-bit field indicating the number of descriptor words in the header portion of Figure 3. Bit 12 is a short bit which is set to indicate that coordinate data are given as 8-bit integers (short form), rather than 16-bit integers (long form). Bits 13-15 are short form exponent bits describing the exponent applied in the event of short form coordinate data.

Word 1 of Figure 3 is depicted in Figure 5 and is a process word which describes the manner in which the entity is to be presented or displayed. The process word is a 16-bit field, formatted specifically for a given display mechanis For a vector memory used to refresh the refresh memory of a black and white raster monitor, a process word might in¬ clude the visible/invisible bit, drawing space/screen space bit, and polygon type (2 bits).

For a color raster monitor, the process word could include visible/invisible bit, drawing space/screen space bit, polygon type (2 bits), and polygon color bits (3 bits).

The _n and Y- bits in words 2 and 3, respectively, of the header of Figure 3, describe the first coordinate point in a polygon and each coordinate is represented by a 16-bit entry.

In Figure 3, descriptor words 4-6 are a field of zero to three words in length incorporating the attributes of the corresponding system entity. An example of a descriptor might include layer number (5 bits), line type/font (8 bits), ID1 (3 bits), ID2 (16 bits) and ID3 (16 bits). Bits in the process field that are not interpreted directly by the display hardware are available for use as additional descriptor bits and hence in the case of black and white raster monitor, the process word might be allocated to include a visible/invisible bit, drawing space/ screen space bit, steady/blink bit, polygon type (2 bits), layer number (5 bits), line type (3 bits), and IDl (3 bits).

In Figure 3, the coordinate data includes zero or more coordinate pairs - (X,, Y-,), ••• (X_Nr *_N) - defining suc¬ cessive vertices of a polygon. X and Y are relative coor¬ dinates and each is represented by a 16-bit entry (long form) or an 8-bit entry (short form). In the short form, the 8 bits represent the mantissa while the exponent is given by the short exponent bits, in word zero.

For illustration purposes as depicted in Figure 6, if a one word descriptor in the header is adequate, and the drawing to be displayed comprises polygons only, and assuming the average number of vectors per polygon is five, and 90% of the vectors can be described in a short form, then the average number of words/polygon is about 10.5. Approxi¬ mately 64K words equal 6K polygons or approximately 30K vectors. Schematics typically contain from 10,000-40,000 vectors, the majority of which could be described in the short form. Printed circuit boards typically contain between 20,000 and 80,000 vectors, the majority of which could be described as short form. IC's typically contain from 40,000 to 320,000 vectors, the majority of which could be described in short form.

A 2M-bit memory, with a capacity of 60K vectors, could ac- commodate most schematics and many printed circuits (PC's) in their entirety. In PC's, as in schematics, a character generator can achieve significant data compression and renders a 2M bit vector memory sufficient for these appli¬ cations.

A 2M-bit vector memory, with a capacity of 60K vectors, could accommodate a quadrant or a complex layer of many in¬ tegrated circuits (IC's). A 4M-bit memory is adequate in 'many IC design applications.

Commands

The system is controlled by the command processor 50 of

Figure 2 and the commands listed in Tables I and II are re¬ ceived from the host processor 10 of Figure 1 and take the form of a 16-bit command designator word (CDW) followed by a (possibly empty) command parameter table (CPT) . The CDW is depicted in Figure 7 where the C-bits (bits 0-5) form the particular command codes according to Tables I and II. The D-bits (bits 6-7) are the minimum descriptor length for associative addressing functions (to be described). The M-bits (bits 8-11) of Figure 7 form the memory bank selec¬ tion mask which will be described in conjunction with the MUDS subsystem. The N bits (bits 12-15) represent the num- 5 ber of the affected viewport, which in one embodiment are numbered from 1 to 6.

The present invention incorporates two basic types of commands — general commands and associative addressing commands. The general commands are illustrated in Table I 10 and the associative addressing commands are illustrated in Table II.

Commands are transmitted to the system by means of a data channel operation. Commands are batched together by plac¬ ing them in contiguous memory locations and placing the sum 15 of their lengths in a word counter. Each transmission con¬ sists of an integral, number of commands.

Following the completion of a batched set of commands, com¬ mand processor 50 signals host processor 10 via a data channel interrupt, requesting to transmit status infor a- 20 tion and the data, if any, generated by system 15 in response to the batched set of commands. When host 10 -directs a read operation to system 15, command processor 50 transmits to host 10 a command buffer completion status word, followed by data words, if any.

25 The command buffer completion status word has the follow¬ ing format of bits 0-7 being an error code bits 8-15 being an error index. If system 15 was able to complete all com¬ mands in the batched set successfully, the error code is zero; otherwise the error code indicates what kind of error ^• 30 occurred and the error index indicates which command or data item within a command caused the error. TAB E I GENERAL COMMANDS

INSERT

SET VIEW PARAMETERS SET CURSOR SET GRID

READBACK INSERT BUFFER READBACK RASTER MEMORY ^■■ LOAD AND EXECUTE

TABLE II

ASSOCIATIVE ADDRESSING COMMANDS

DELETE IF EQUAL

DELETE IF NOT EQUAL

MODIFY IF EQUAL MODIFY IF NOT EQUAL

TRANSLATE IF EQUAL _. TRANSLATE IF NOT EQUAL

SET VIEW PARAMETERS IF EQUAL

SET VIEW PARAMETERS IF NOT EQUAL IDENTIFY POINT IF EQUAL

IDENTIFY POINT IF NOT EQUAL

IDENTIFY VECTOR IF EQUAL

IDENTIFY VECTOR IF NOT EQUAL

IDENTIFY POLYGON TOUCHING OR IN WINDOW IF EQUAL IDENTIFY POLYGON TOUCHING OR IN WINDOW IF NOT EQUAL

IDENTIFY POLYGON ENTIRELY INSIDE WINDOW IF EQUAL

IDENTIFY POLYGON ENTIRELY INSIDE WINDOW IF NOT EQUAL

General Commands

Referring now to Table I, the insert command places the specified graphic entities set forth in the CPT within one or more of the selected memory modules of the vector memory subsystem. An error status indicator is set in the event the entities cannot be inserted due to lack of available space. The last entity to be inserted must have its mark bit (bit 8 of word zero) set to 1 and all the preceding entities have their mark bits set to 0.

The set view parameters command is depicted in Figure 8, which updates the parameters that control the data display in the system. Execution of this command also causes a full or partial redraw of data on the system's CRT screen. This command affects only the viewport specified by bits 12-15 in the CDW (word 0 in Figure 8). Use of this com¬ mand will in fact result in an associative set view com¬ mand being issued to the system hardware by the command^' processor 50, as will be described in conjunction with associative commands. However, the associative addressing mechanism is used only trivially, to select all entities for viewing-.

In Figure 8, the first word. of the CPT (word 1) contains parameter presence flags, erase control field, and an en- tity space selection mask in the format depicted in Figure 9.

In Figure 9, bits 0-4, when set to 1, indicate the pres¬ ence in the CPT of a new value for the respective parameter. When set to 0, the respective parameter entries in the CPT are to be ignored and their previous values retained.

The background field B (bit 11) is used to specify the background for the currently defined viewport. When bit 11 is set to zero, the vectors are shown as white lines with a black background. If bit 11 is set to one, the vectors are shown as black lines with a white background.

The erase control field EC (bits 12-13) is used to signal a total (bit 12 = 1) or a partial (bit 13 = 1) erase of the screen (i.e., raster memory) that is to precede the genera¬ tion of new display data. A partial erase affects only the

S S current rectangular viewport as defined by (X..* ^Y _T_ ^ '

(X_T U₇_R, n^~UK ) and as depicted in Figure 11. When the erase control field is zero, all erasing is inhibited and all display data generated are merged with the existing displa

The entity space selection mask SS (bits 14-15) is used to restrict the display of data to visible entities within the designated spaces. If bit 14 = 1, then the graphic repre- sentations for drawing space entities are generated. Simi¬ larly, if bit 15 = 1, then the graphic representations for screen space entities are generated. A zero setting of either bit will cause inhibiting of the display for the associated entity space.

In Figure 8, following the parameter flags word, the next two words (words 2 and 3) of the CPT are X„ and Y_c which specify the coordinates of the center in drawing space of the rectangular viewport that appears on the screen, as illustrated in Figure 10. The next two words (words 4-5) in Figure 8 specify the scale factor to be applied in map¬ ping drawing space to screen space as a 32-bit, standard format, normalized, floating-point value.

Thςe next two words of the CPT (words 6 and 7) are Xj_τ-ll_τj and

Y Inin which specify the coordinates, in screen space, of the lower left-hand vertex of the desired rectangular viewport which are followed by X_τs-_ and Ys_ττ_. which are the coord.i- nates of the upper right hand vertex of the viewport, all o which are depicted in Figure 11.

Following the viewport specifications, the censoring value in word 10 determines the minimum axial distance that a polygon must traverse before a vector representing one or more polygon sides is inked. Each polygon is represented b at least a single vector from the first to the last vertex..

c Referring to Figure 12, the set cursor command controls the display of one of the system's cursors and includes a CDW and a three word CPT. The CDW contains a 3-bit VP field which designates the viewport in which the cursor is to appear. The first word of a CPT includes a single bit D flag which determines the current display status, where zero represents cursor off and one represents cursor on. If the D flag is set to zero, then the display of the cursor is inhibited and the coordinates are ignored. When the D flag is set to one, the cursor is displayed at the specified location in screen space. A 2-bit C-field designates which of the unit's cursors is to be affected. A single bit S-flag specifies in which space the coordinates are contain- ed. When the S-flag is set to zero, the coordinates are given in terms of drawing space and the cursor is appropri¬ ately displayed within the designated viewport. When the S-flag is set to one, the coordinates are contained within screen space.

Referring now to Figure 13, the associative addressing commands that associatively address the vector memory sub¬ system include two 6-word masks within the command parameter table (CPT). The two masks, MASKO and MASKl, occupy the first 12 words of the CPT.

In Figure 13, two masks are applied to an entity header to compute a Boolean value termed "selection condition". The resulting value then determines whether the command ad¬ dresses (i.e., should operate on) a given entity. The selection condition value is determined by extending an en- • tity's header as depicted in Figure 3 to a full seven words by appending zeroes as required; ANDing the second through seventh word of the entity's headers with the six words of MASKO; testing for equality the six word result with MASKl and setting to zero the selection condition if the values are equal, or to one if the values are unequal. Two additional parameters, provided in the CDW of each associative addressing command, further affect the inter¬ pretation of the selection condition. The D field specifie the minimum number of optional descriptor words which must be present in the header of an entity as a prerequisite for being addressed. If an entity has fewer optional descrip¬ tors than the number specified in the D field of the comman then the command does not address the entity, regardless of the selection condition. The M field specifies which memor modules within vector memory subsystem 52 are to be affecte by the command. If an entity is stored in a memory module which is specified in the M field not to be affected by the command, then the command does not address the entity.

MASKO functions as a bit selection mask and MASKl functions as a qualification value. That is, an entity's selection condition will be true (0) or false (1) depending on whethe it equals or does not equal the qualification value in thos bit positions specified in the bit selection mask. Each associative addressing function can operate on all entities whose selection condition is either zero or one. All commands that associatively address memory equire a comman parameter table. The format of each respective CPT is described below in conjunction with the associative address ^'ing commands.

Figure 14 depicts the modify if equal/not equal commands of Table II, which change the contents of the headers of those entities whose computed selection condition matches that specified in the given command. The second through seventh words of an entity headers will be replaced by the corres- ponding word of the quantity (HEADER AND MASK2) XOR MASK3. Only the existing header words are modified and thus the length of an entity's header remains unchanged.

Figure 15 depicts a delete if equal/not equal command of Table II, which removes all entities from the vector memory whose computed selection condition matches that specified in the given command.

Figure 16 depicts a translate if equal/not equal command of Table II, which changes the contents of the headers of those entities whose computed selection condition matches that specified in the given command. The second through seventh words of an entity header are replaced in the corresponding word of (HEADER AND MASK2) PLUS MASK3. Only existing header words are modified and thus the length of the entity's header remains unchanged.

Figure 17 depicts a set view parameters if equal/not equal command of Table II, which causes those entities whose computed selection condition matches that specified in the given command to be displayed in accordance with the rest of the parameters in the- CPT.

Figure 18 depicts the identify point if equal/not equal com¬ mands of Table II, whose first function is to qualify those entities whose computed selection condition matches that specified in the given command. Those entities that qualify for identification are next checked to insure that at least one point falls within the drawing space viewport specified at the lower left and the upper right corner specified in words 13 through 16 of the CPT. For an entity meeting the above requirements, D is calculated such that D = maximum ( JX - XI -j or JY - Yl j), where X and Y are contained within the polygon's coordinate list) is computed. On completion of testing of all qualifying entities, the header of the entity for which D assumes a minimum value is made avail- able to the host CPU.

The identify segment if equal/not equal command has the same format as depicted in Figure 18 except that X and Y are ^'-20- computed to the point on any line segment of the entity closest to (XI, YI) before D is computed.

Figure 19 depicts the identify polygon touching or in windo if equal/not equal command, whose first function is to qualify those entities whose computed selection condition matches that specified in the given command. Those entitie that qualify for identification are next checked against th drawing space window specified in the command. The headers of the first several entities found touching or totally within the window are returned to the host computer. The identify polygon entirely within window if equal/not equal command has the same command format and functions similarly

Figure 20 depicts the contents of the system data bus 57 of Figure 2 during the time that a command designator word (CDW) is being output by the command processor, in which th OD field (bits 8-9) is an optional descriptor field used by the MUDS system only when processing associative commands, and the MD field (bits 4-7) 'specifies which memory modules of VMS 52 are to be affected by the command. The SF field (bits 0-3) is a special flag field in which bit zero is set to one during a set cursor command to designate cursor on. Bits 0, 1 and 2 are also used during any associative comman to inform the memory update system of the selection condi¬ tion for items missing optional descriptors. The appropri- ate bit set to one indicates a not equal condition. Bit $ specifies the condition for one missing descriptor, bit 1 for two missing descriptors and bit 2 for three missing des criptors. The CC field (bits 10-15) will be described sub¬ sequently.

Command Processor

The command processor (CP) 50 of Figure 2 is depicted in more detail in Figure 21. The command processor (CP) 50 serves as a command center during transfers between the hos CPU 10 of Figure 1 via bus 57 of Figure 2 and the remainder of the system, processing data blocks, generating the clocking signals and proper handshaking signals for data transfer sequences.

The command processor 50 includes a microprocessor circuit 111 which includes typically a microprocessor and memory subsection 112 having read only memory (ROM), random access memory (RAM), and general purpose peripherals 113. The system program is stored in a ROM of circuit 112.

Processor 111 may include, for example, an Intel 8085A microprocessor, together with associated peripherals, the details of which are known in the art.

In Figure 21, the direct memory access (DMA) I/O controller 101 is connected to receive address signals on bus 115 and data signals on bus 116 from the microprocessor 111. Also, controller 101 receives control signals from the host CPU via bus. 57-6 and 56-1.

Multiplexer (MUX) 103 receives address signals from pro¬ cessor 111 and system I/O controller 102. MUX 104 receives data signals from processor 111 and from the system via bus ^'58, ECL-TTL circuit 109, and bus 117.

Transceiver circuit (XCVR) 120 receives data signals from multiplexer 123, as well as data signals from the host CPU via bus 56-2. Clock generator 121 generates the appropri- ate SYNC and 40 MHz signals for the system on bus 57-5.

When the host CPU has a block of data to be transferred to the command processor, it activates the host request line (HRNK) to controller 101, which responds with an acknowledge signal (VTAK) when it is ready to accept data. The host CPU 10 inserts two 8-bit bytes, which constitutes

c-TI a 16-bit word, into the insert buffer 105, a IK x 16-bit buffer. Processor 111 waits^* until it has a 256-word block available, which constitutes a maximum length transfer, before responding to the request. The program functions include setting a counter (not shown) in controller 101 to the word count minus one, sending to controller 101 a starting address in insert buffer 105 into which it can begin loading the data from host CPU. From that point, the transfer is effected solely by the host CPU and controller 101. Data is transferred in 2-byte (16-bits) burst mode until completion of transfer. CP 50 examines newly trans¬ ferred data and determines how to process it.

Assuming that the first command in the data block is the insert command illustrated in Table I previously, the CP 50 programs system controller 102 to output the insert command and all of the header and associated coordinate data words with that command onto system bus 57-4. Appropriate pro¬ gramming operation includes sending to the system control¬ ler 102 the address of .the insert buffer 105 location that contains the insert command, loading a controller counter (not shown) with the number of words associated with the insert command, and providing the controller 102 with an address to output onto the address bus 122. The IBAC sig- -nal on bus 122 is an address which points to the location in buffer 105 where a command is stored. The EAD signal on bus 57-4 is the system address which is distributed to the system.

The first word that I/O controller outputs onto the data bu 57-4 is the insert command. At that time, the controller 102 outputs the CP-provided address (of zero or 80, hexi- decimal) onto address bus 122, which indicates that there is a CDW on the EDAT bus 57-6, which is meant for some circuits in the system. Another indication of the presence of a CDW is that it is the first word of a set of words presented on the bus at 300 ns intervals. Because the com¬ mand is an insert command, the address placed on the ad¬ dress bus 122 is recognized only by the MUDS subsystem. Consequently, only the MUDS subsystem loads the command code into its command decoder and upon decoding the command, the MUDS replies that a number of words are about to be output onto the data bus 57-4, which must be inserted into the vector memory. These words define a number of items which jointly comprise part of a drawing that is to be displayed on the system's CRT. As the words are placed onto the data bus 57-4 via the I/O controller 102, they are taken by the MUDS and inserted into the vector memory. The six most significant bits of some of the data words may be configured exactly like a command code but such words will be inter- preted as data rather than command because there will be no valid addresses on the address bus 122.

While the MUDS system is busy executing the insert command, the busy line on bus 57-1 is enabled or asserted (the busy line is enabled whenever any circuit is executing a com- and). When system controller 102 has outputted all the words it was programmed to output, it places a start signal on bus 57-4 and the MUDS interprets this signal as the end of the item transferred. When the MUDS has received the ' start signal from the I/O controller 102, and has finished processing the last word associated with an insert command, it frees the CP busy line on bus 57-1. When the CP recog¬ nizes the busy signal on 57-1 is free, it examines the next word in insert buffer 105 and starts processing the next comman .

The DMA controller 101 transfers 16-bit data words from the host processor to the insert buffer 105, performs parity generation and checking overall transfers, is capable of addressing any location in insert buffer 105, and includes a word count register (not shown) capable of handling a 256- word transfer. The word count register is capable of being loaded and read back by the CPU.

The request signal, HRNK on bus 56-3, is activated during a download operation when data is being placed on the bus b host 10. It remains until DMA controller 101 activates system acknowledge, VTAK on bus 56-1, signaling host 10 tha it is ready for the download. If DMA controller 101 detect a parity error in the transmission, it activates system negative acknowledge, VRNK on bus 56-1, rather than VTAK, which aborts the download. Error-free transmissions procee with HRNK/VTAK handshake exchanges, one for each data byte transferred, until host 10 asserts host terminal count, HTA on bus 56-3, which terminates the download.

When system 15 has data to upload to host 10, it begins by asserting system request, VRNK on bus 56-1. After host 10 returns a host acknowledge, HTAK on bus 56-3, system 15 begins the upload by placing data on the bus and reasserting VRNK. Error-free transmissions proceed with VRNK/HTAK handshake exchanges, one for each data byte transferred, until system 15 asserts system terminal-count, VTAK on bus 56-1, which terminates the upload. If host 10 detects a parity error in the data received it asserts host negative acknowledge, NRNK on bus 56-3, rather than HTAK, which aborts the upload.

The system controller 102 transfers 16-bit data words bet¬ ween the buffer 105 and the system data bus EDAT 57-6. Con¬ troller 102 includes an address register IBAC capable of ad¬ dressing any location in the buffer 105. The contents of another 8-bit counter/register within controller 102 are placed on the system address bus EAD 57-4 during certain I/O operations as commanded by the CPU. A word count register capable of handling a 256-word transfer is included. Con¬ troller 102 is programmable by the CPU to output to the system an output strobe (OSTB) signal on bus 57-4 and data and addresses on the system busses EDAT and EAD, respec¬ tively. When programmed to input data from the system data bus, the controller 102 sends an input strobe (ISTB) to the system. Sometime after ISTB has been received, the input data should be placed on the system data bus to be latched and written into insert buffer 105.

The clock generator 121 supplies the SYNC and 40 MHz sig¬ nals to the system as depicted in Figures 21A and 21B.

Figure 21A depicts timing signals from the system to CP 50, and Figure 21B depicts timing signals from CP50 to the system.

Memory Update System

The memory update system (MUDS) 60 of Fig. 2 is depicted in more detail in Figs. 22A and 22B. The primary functions of MUDS circuit 60 are to insert data from the host CPU through command processor (CP) into vector memory 61, associatively search and modify items in memory 61 specified by the command processor, and to selectively pass data from memory 61 to preclipper circuit 62 for the set view and identify functions, to be described. Timing diagrams for illustrat¬ ing the operation of MUDS 60 and memory 61 are depicted in Fig. 23.

In Fig. 22A, a command decoder 140 receives the OSTB and EAD signals and commands in the form of EDAT signals from the system on bus 57. Decoder 140 is connected to command latch and signal generator 138 which generates on bus 132 the commands, command type and busy signals.

The memory data in (MDI) bus 64 from memory 61 is connected to logic circuit 131 which waits for a command to be started. When free space or an end of item is detected, mark logic 131 sets a mark bit. The bit position in the first word o an item or free space is set and is called the mark bit. Mark logic 131 is connected to command latch 138 to inform latch 138 when a command is completed.

Item parser 141 is a logic circuit which determines the possible categories of a data word from vector memory 61 o MDI bus 64. Item parser 141 generates the FREE SPACE, IN ITEM, HEADER and END OF ITEM signals on bus 133.

MDI bus 64 is also connected to latch circuit 142 which sends unmodified items to ring buffer circuit 155 of Fig. 22B, which is a 256 X 16 bit buffer utilized for modifying, translating and deleting functions.

Polygon vector data from the command processor (CP) 50 is sent to the MUDS 60 circuit via bus 57 into buffer/inverter circuit 145 which in turn is connected to mask memory 148 (MMO) and mask memory 149 (MMl) which are 16 X 16 bit memories and which are addressed by mask memory address generator 139, which generates the necessary 4-bit address signals in response to a command type signal from command latch 138.

The 16-bit MASKO and MASK2 items from memory 148 are latche to mask and latch circuit 147, which also receives unmodi¬ fied items from the vector memory via bus 64. MASKl and MASK3 items from memory 149 are connected to ALU circuit 150. The mask and latch circuit 147 is also connected to ALU 150, which processes the data under control of ALU con¬ trol circuit 151, depending upon the type of command received from command latch 138.

Masked items from ALU 150 are connected to qualification logic circuit 162, which provides appropriate selection

C between the ring buffer circuits of Fig. 22B, depending upon the results of MASKO and MASKl.

Modified items from ALU 150 are connected to multiplexer (MUX) 154, which also receives items to be inserted via bus 57 and connects the insert or modified items to ring buffer 157 (RB2) of Fig. 22B under control insert controller 160, which receives the INSERT COMMAND, IN ITEM and END OF ITEM signals from item parser 141 and command latch 138, respec¬ tively.

Referring now to Fig. 22B, ring buffer address generator 161 receives the IN ITEM signal from item parser 141 and provides 8-bit address signals to ring buffer 155, ring buffer 157 and ring buffer 158.

The ring buffer circuits of Fig. 22B are controlled by ring buffer control 156, which receives appropriate timing sig¬ nals from clock generator circuit 130 of Fig. 22A.

Flag generation logic 166 receives the QUALIFY signal from qualification logic circuit 162 and IN ITEM, END OF ITEM and HEADER signals from item parser 141 of Fig. 22A and which effectively tells the ring buffer circuitry when to set ^' flags.

Ring buffers 155, 157 (RBI and RB2) are 256 X 16 bit ring buffers. Ring buffer 158 is a 256 X 4 bit ring buffer and ring buffers 155, 157, 158 are used for updating memory 61. Ring buffer 155 stores unmodified item(s), ring buffer 157 157 stores modified item(s), and ring buffer 158 is used to store ring buffer selection code from logic circut 166. The 2-bit selection code from ring buffer 158 is connected to select control circuit 168. One bit is an enable flag in order not to change or modify an item in process. The other flag bit tells which ring buffer 155, 157 should be selected. Multiplexer (MUX) 167 selects the data from either ring buf fer 155 or 157 and sends the 16-bit data on bus 65 back to vector memory 61.

In Fig. 22B, the error detection, used word count and statu logic circuit 144 receives the data from memory 61 together with the INSERT, DELETE, BUSY and QUALIFY signals from Fig. 22A to provide the appropriate control signals on bus 57.

Preclipper interface circuit 153 receives vector data on bu 64 together with the QUALIFY, END OF ITEM and X-COORDINATE signals. The X-COORDINATE signal on bus 66 from the pre- clipper circuit is an instruction requesting either the X or Y coordinate and in response thereto the MUDS circuit provides the appropriate coordinate on PCD bus 67.

Preclipper interface* 153 also provides to the preclipper circuit the necessary data available signal on bus 66 to¬ gether with the appropriate signals indicating end of item, short form data, header, qualify and which word of the item

In Fig. 22A, the clock generator circuit 130 receives the 40M and SYNC signals from the system together with the DS ^'(read) signal on bus 64 from the vector memory. The clock generator 130 generates the 100NS, 300NS signals and P cloc signals depicted in Fig. 23, as well as the T clock signals (not shown) .

The vector memory receives two clock inputs (differential pairs) for its basic timing from one of the MUDS 60 systems Every 300 ns, a 16-bit word is stable at output bus 65 and the data can be latched by the read clock signal (DS) of Fig. 23. At the trailing edge of the DS signal, data on bus 65 to memory 61 must be stable for writing. In one embodiment, a memory 61 cycle is 300 ns long which is the period of the DS (read clock) signal. At the end of the 32 cycles, memory 61 will go into a refresh or shift period which is 9.6 us long. During this period, the internal clocks of the MUDS are inhibited, which are designated PI, P2 and P3 of Fig. 23. All processing comes to a halt ex¬ cept that data from CP 50 can still be inserted from that time under control of the T clock signals (not shown).

In Fig. 22A, the command decode logic 140 decodes the different commands from the command processor via bus 57. The commands (depicted in Tables I and II) decoded are insert, delete if equal/not equal, modify if equal/not equal, translate if equal/not equal, identify if equal/not equal (including point, line and window identify), and set view if equal/not equal. The desired command is decoded upon the right combination of address and data signals followed by the OSTB* signal. After the command is properly decoded, parameters accompanying the command are loaded by subsequent OSTB signals. The start signal initiates the processing of a command.

The status and used word count report circuit 144 reports the busy status, error status and number of words used in ^'memory 61 to the command processor, via bus 57. MUDS 60 is busy as long as a command is in process. In the case of an insert command, the command is not done until all of the insert data is written into memory 61. If the word count of the items is less than four, a header length error is reported. If in long form, data length error is reported when the parity of the length of the item differs from that of the descriptor length. The used word counter is preset to zero during a memory 61 reset and decrements by the num¬ ber of words deleted during a delete command and increments by the number of words inserted during an insert command. The count remains intact during all other operations. In the case of modify and translate commands, the items wi modified headers are written into ring buffer 157 while un modified items are written into ring buffer 155. At corre ponding locations in ring buffer 158, where the first word are in ring buffers 155, 157 respectively, bit zero is set and bit one is set so that ring buffer 157 will be chosen for writing into memory 61 if the item satisfies the quali fication test. Ring buffer 157 is also used for data in¬ sertion into memory 61. Insert data from command processo 50 is loaded into ring buffer 157 and as soon as a word of free space or end of item from memory 61 is detected, in¬ serted data in ring buffer 157 is written into memory 61.

There are two read pointers (RP and IRP) , two write pointe (WP and IWP) and a header pointer (HP) . RP points to a location in a ring buffer where the next word from memory 61 will be stored. WP points to the location in a ring buffer from which the next word written into memory 61 is retrieved. RP and WP are used by both ring buffers 155, 157. IRP and IWP are used only during an insert command b ring buffer 157. HP is used to keep track of the first wo of the current item in ring buffers 155, 157 and is select to address ring buffer 158 for recording the first word an ring buffer selection flags. WP is selected for reading t ^'flags from ring buffer 158.

In Figure 22A, the mask memories 148, 149 are loaded with the masks during command parameter load (MASK LOAD IN PROGRESS-MLIP) . The mask memory and address assignments for the four are as follows:

ASK MASK MEMORY ADDRESS

? 0 - 0-5

1 1 0-5

2 Sf 8-D

3 1 8-D MASKO and MASK2 are stored in memory 148 in one's complement form so that an effective ANDing function is performed on the latched data. The following functions are performed:

(1) (MASK0 ^* DATA Θ MASKl (2) Record above result and do qualification test.

(3) RB2 (MASK2) ' DATA Φ (or PLUS) MASK3.

(4) Select RB2 output for memory input data if the item passes qualification test. Otherwise RBI is selected. (RBI DATA is done every cycle).

The preclipper interface circuit 153 provides the input data

- for the preclipper along with various timing and state signals. A 16-bit word is sent to the preclipper circuit

62 if the word just received by the MUDS from memory 61 is part of an item. For coordinate data, the word can be sent in three ways, which are:

(1) Unmodified if data is in long form.

(2) Lower eight bits shifted left with sign extension by the value in short exponent, if data is in short form and XSEL is low. (3) Upper eight bits shifted left with sign extension by the value in short exponent, if data is in short form and XSEL is high.

The fact that insert data is sent to the vector memory 61 when free space or the end of an item is detected allows the MUDS circuit to handle its own "garbage collection" without imposing an overhead penalty. New data is inserted into the vector memory in place of unused or free space or in between existing items. Thus, new data can be inserted into the vector memory regardless of the distribution of items throughout the memory as long as the total number of words inserted does not exceed the capacity of the vector memory. The significance of the read pointer and write pointer is that it allows the ring* buffers to act as FIFO (first in first out) registers, with an important advantage. When a FIFO register is filled, its internal address is incremente from a zero (empty) to some maximum count (full). As data is read out, the internal address is decremented until zero is reached again. Therefore, a FIFO requires special logic to keep from counting below zero or above the maximum value However, the ring buffers overcome this problem by limiting the size of items going into the ring buffer to less than the maximum ring buffer size. The ring buffers are also arranged so that the data will be read out of the ring buffers fast enough so that they will never be completely filled. Consequently, MUDS 60 needs only to detect when the buffers are empty. Instead of using address zero to indicate "empty," the ring buffer address is allowed to tak any value and two pointers are used.

When data is written into the ring buffers, the read pointe is incremented by one to the address into which the data will be written and as data is being read out of the ring buffers, the write pointer is incremented by one to the address from which data will be read. When the two pointer are equal to each other, the ring buffer is empty.

If both pointers are incremented enough, the ring buffer address eventually will return to where it started, hence the name ring buffer. Since the ring buffer logic need onl detect the case of the two pointers being equal, the contro logic is simplified over the FIFO type of register.

In the MUDS circuit, the items in the vector memory can be inserted, associatively modified, and/or passed to the preclipper circuit regardless of their distribution or relative position in the vector memory. As long as the number of items inserted into the vector memory do not exceed the capacity of the vector memory, the MUDS circuit will find spaces to insert new items, process existing items and perform the "garbage collection" technique described above as the items serially circulate through the MUDS circuit.

Vector Memory

In one embodiment, vector memory 61 is a 64K-word x 16-bit charge coupled device (CCD) memory. The memory storage area includes 64 serial memory devices arranged in four banks. The memory is addressed sequentially and operates in an in¬ terleaved mode, with a read operation performed in one bank while a write operation is performed on another bank. The sequencing of the operation thereby allows a read-modify- write operation to be performed at each memory location in turn. The memory has a sequentially interleaved average data rate of 300 nanoseconds (ns). However, it is to be understood that other types of known memories can be in¬ cluded within the scope of the present invention. For ex¬ ample, magnetic bubble memories (MBM) or random access memories (RAM) could be utilized for vector memory 61.

In one embodiment the CCD memory devices include 64 256-bit chip registers which are addressed serially under control of a four-phase clock input. The data in the chip register is shifted every 32 cycles (i.e., every 10 microseconds) to refresh data, and to bring data into an access position. The memory has a 900 ns data gap during a shift operation. Since the memory has 64K data locations, the maximum period required to read and write the entire memory is 24 ms.

Memory 61 receives clock inputs from the MUDS and from these inputs generates required control and mode signals. All address bits are internally generated. In Figure 24, there are 16 write data lines forming bus 65 from the MUDS to latches 208, 209 to memory 61 and 16 read data lines from the memory 61 to MUDS 60 via drivers 210, 211 and bus 64.

The memory storage area includes 64 16K-word by 1-bit charge-coupled (CCD) serial memory chips, such as Intel's model 2416.' The chips are arranged in four banks 201-204, as depicted in Figure 24, in which each bank stores 16K 16- bit words.

In the interleaved mode, a read-modify-write operation is performed at each memory location in turn. In Figure 24, a read operation is performed in one bank of memory such as bank 201 (bank A) while a write operation is performed at another bank such as bank 204 (bank D) . A write operation is then performed in the bank from which data has just been read out, at the same address, to complete the read-modify- write operation at that location. While this write opera¬ tion is going on, a read operation is being formed at another bank. A basic cycle time for memory 61 is 300 ns, which in effect allows a. read-modify-w.rite operation to be completed every 300 ns.

For a first functional cycle, bank 201 is enabled by the -CEA signal, for a read operation, while a write operation is going on in bank 204 (enabled by -CED) . At the next cycle, bank 202 is enabled for a read operation by -CEB. -CEA is still active and a write operation is performed in bank 201, at the same address as the read operation. 300 n later, a read operation is initiated in bank 203, when -CEC goes low, while a write operation is then performed in bank 204, while a write operation is going on in bank 203. -The timing requirements for these operations are depicted in Figure 26.

These procedures are repeated until a read-modify-write operation has been performed in all 64K chip locations. A 1.2 us refresh operation occurs at the end of every 32nd cycle which provides a refresh cycle time of 9.6 us.

Figure 25 depicts a block diagram of 64 recirculating shift registers 220 of 256 bits each. Address bits for banks 201 and 203 and for banks 202 and 204 are internally decoded to select one of those 64 registers. The chip registers 220 are grouped in blocks of 8 (0-7, 8-15, 16-23, 24-31, 32-39, 40-47, 48-55, and 56-63). Decode signals A3 A5 into buffer 215 are decoded by decoder 221 to select one of these eight blocks and address signals A0-A2 are decoded to select one individual register out of the eight in the block.

One bit out of 256 in the selected register is addressed by shifting the data in register 220 to bring the required bit into the access position in buffer 313. Data are input to a selected register via buffer 214. Shifting is controlled by four phase clock inputs 1-4. Timing generator 216 con¬ trols internal timing. With interleaving, one bit is accessed in each of the 32 chips during each cycle, thereby allowing one 16-bit word to be read out. from and one 16-bit word to be written into the desired locations.

Preclipper

^"The preclipper circuit 62 of Figure 2 is depicted in more detail in Figure 27, and includes a command decode circuit 226 for receiving status and control signals from the com¬ mand processor via system bus 57. The preclipper includes two coordinate control units 227, 228 (which are control units for the X and Y coordinates, respectively) and two co¬ ordinate processor units 229, 230 (which are processor units for the X and Y coordinates, respectively).

Each control unit 227, 228 includes a next address logic cir- cuit 232, control storage (PROM) 233 and a pipeline register 234. Each processor unit 229, 230 includes a four to one (16-bit) MUX 240, an 8 x 16 register file 241 and a 16-bit ALU 242. Each register file 241 has one input port from M 240 and two output ports. One of the two output ports of register file 241 is connected directly or indirectly (through MUX 240) to a IK x 32 bit output buffer (RAM) 243.

X-control signals on bus 235 and Y-control signals on bus 236 from control units 227, 228, respectively, are input t the respective processor units 229, 230. Data from the MU circuit via 16-bit bus 67 are also input through status latch 245 into intersect and censoring value test circuit 246, which also has inputs from control units 227, 228 and from processor units 229, 230. Outputs from test circuit and clock generator 246 are input to header pointer (HP) circuit 250, write pointer (WP) circuit 251 and read point (RP) circuit 252.

The HP 250 output is input to ALU circuit 255 and into WP circuit 251, MUX 257, and. RP 252. The WP 251 output is input to ALU circuit 257 and also input to HP 250, ALU 255 and MUX 257. The output of RP 252 is input to comparator (COMP) 258, ALU 256 and MUX 257.

_The output of ALU 255 is input to MUX 260 which also re¬ ceives 8-bits from register file 241. The output of MUX 26 forms an input to RAM 243. The output of MUX 257 forms an input to RAM 243 and an output of test circuit 246 is inpu to RAM 243.

The preclipper 62 functions are to accumulate the relative coordinates received from the MUDS 60 to make them absolute to compare line segment deltas with the censoring value received for the current set view to determine whether the current point needs to be retained in output buffer 243, an to determine whether a particular polygon intersects a viewport or window. The intersection test in circuit 246 works in the following manner:

Let the window be defined by (XL, YL) and (XH, YH). Let the smallest rectangle that circumscribes the polygon be defined by (XMIN, YMIN) and (XMAX, YMAX) . If XMAX < XL or XMIN > XH or YMAX < YL or YMIN > YH, then the polygon is outside of the window.

Figure 27A depicts an illustration of a circumscribed poly- gon, in which polygon 270, formed by a series of vectors, is circumscribed by a rectangle 271 defined by (XMIN, YMIN) and (XMAX, YMAX). Window 272 is defined by (XL, YL) and (XH, YH). Although it can be seen that polygon 270 does not intersect window 272, its circumscribed rectangle 271 does intersect window 272, so polygon 270 is passed to clipper ■circuit 70. Clipper circuit 70 subsequently determines that no segment of polygon 270 is visible. Note that, while preclipper 62 may pass polygons to clipper 70 which do not intersect the window, preclipper 62 never fails to pass a ,polygon to clipper 70 which does intersect the window.

Preclipper 62 receives polygon data from^' MUDS 60 at a rate of either one or two words per 300 us cycle. Specifically, two words per cycle are received if the data represents an X-Y coordinate pair which was originally encoded in short form within vector memory 61; otherwise, one word per cycle is received. A central processing section for the preclip¬ per, as previously mentioned, includes control units 227, 228 and processor units 229, 230. Buffer 243 is addressed by the three pointers HP 250, WP 251, RP 252 via MUX 257. The header pointer (HP) points to the first word of the polygon under consideration being accumulated in the output buffer 243 and going through the intersection test by test circuit 246. The read pointer (RP) points to the location in output buffer 243 where the next word is to be retrieve by the clipper circuit 70. The write pointer (WP) points to the location in the output buffer 243 where the next 32 bit word is written by the preclipper circuit 62.

The 300 ns between successive words from MUDS circuit 60 i divided into three 100 ns periods called PI, P2 and P3 as depicted in Figure 28. Data is stable for the preclipper ns after the leading edge of P2. The three pointers HP, W and RP are time multiplexed in MUX 257 for addressing the output buffer 243 by P3 for HP, PI for RP, and P2 for WP. When RP = HP, the data available (DA) signal would be low, which indicates that output buffer 243 is empty. Otherwis the DA signal is high. When (RP - WP) ^ 32 a pause signal from circuit 256 on bus 66 will be raised to initiate the CCD pause cycle previously described.

The preclipper circuit 62 decodes two command classes, whi are set view and identify. Data from MUDS 60 is processed differently according to whether the word received belongs to the header or is a coordinate as described in conjuncti with the polygon format.

In case of an identify function, the whole header is sent t buffer 243. For a set view function, only the first two words of the header are stored in output buffer 243 with th actual number of 32-bit words stored in the word count fiel of the header.

The micro-instruction cycle is 50 ns. In Figure 27, the X-processing unit 229 runs for six cycles (300 ns) and the y-processing unit 230 runs for six cycles. In the case of short form data, the X and Y units 229, 230 run in parallel with a skew of 50 ns. The pipeline registers in units 227, 228 are used to allow overlap of the execution and instruc¬ tion fetch cycle, as depicted in Figure 28, in which E sig¬ nifies execution of an instruction fetched during the last fetch cycle and F signifies instruction fetch. During the course of processing coordinate data for a set view com- mand, the arithmetic operations involved for X (and ana¬ logously for Y) are as follows:

1) I input from MUDS

2) X X + I

4) Compare |Δ XP| with CN

5) Compare X with XL

6) Compare X with XH

Variable Names Description I Input data from MUDS

X Current X coordinate

|ΔXP| Absolute value of X-XP

XP Previous X coordinate

CN Censoring value X X low limit

XH X high limit

Y Current Y coordinate

|ΔYP| Absolute value of Y-YP

YP Previous Y coordinate YL Y low limit

YH Y high limit

In addition to the operations described above, preclipper 62 loads the XP and YP registers with the contents of X and Y, respectively, on the last 50 us cycle used to process a co- ordinate pair, if X differs from XP or Y differs from YP by at least the censoring value CN.

The processing performed for identify commands is similar to -O- that for set view commands, except that all operations per¬ taining to censoring value CN are omitted.

Figure 29 depicts the timing considerations and sequence of operation for the preclipper circuit according to the arithmetic operations involved. During time P2, the write pointer WP is selected for the address in output buffer 243. If either |ΔXP| or IΔY I is greater than the censoring value, the current pair of coordinates is written into the buffer. During time P3, the header pointer is selected. I intersection is detected, then after the end item (El) sig¬ nal or the pen up (PU) signal is received, the word count i the header will be updated and the header pointer will be

_* set to the write pointer, thus making the data pertaining t the currently processed entity available to the transforma- tion subsystem 53; otherwise the write pointer will be set to the header pointer, thus discarding this data.

In Figure 27, data from the preclipper buffer 243 is output on 32-bit bus 73 to the clipper circuit 70, and includes 16 bits of X-coordinate data and 16 bits of Y-coordiήate data.

Clipper Circuit

The clipper circuit 70 of Figure 2 is depicted in more de¬ tail in Figure 30, in which preclipper vector data via bus 73 are input to data selector and accumulator 301. Control signals are input on bus 57 into command processor interfac 302 and into clocking, timing and reset circuit 303, which provides appropriate timing signals for the clipper circuit. Preclipper control signals via bus 72 are input to pre¬ clipper interface circuit 304. The clipper 70 provides the clip and identify functions.

Clipper processor 310 contains a program register, a 256- word X 48-bit PROM and other control logic for supervising clipper activities during the processing of data. Data selector and accumulator 301 receives preclipper data via bus 73 and from other sources to be described, and stores data in the accumulator portion.

Arithmetic unit 311 is used to manipulate and compare data 5 words, and the results are passed to the processor 310 via bus 312. Memory 313 holds parameters received from command processor 50 of Figure 1, data currently being processed, and other words used in computations and all the header words to be sent to the command processor.

.0 Figure 31 depicts the basic timing signals utilized in Fig¬ ure 30. The SYNC, 40 MHz, and 25 ns timing designations have been previously described. The CKQTR and timing sig¬ nals are utilized by some of the logic for timing purposes. The remaining signals are not necessarily periodic and are

15 shown for explanatory purposes.

The PARENB. signal is used to enable the loading of .command processor parameters in the clipper and sealer circuits. The LOSTB signal is a 100 ns synchronous image of the OSTB signal. The QSTRT signal is a 100 ns synchronous image of 20 the CP's start signal. The FETSTB signal is a strobe sent to the preclipper to fetch data. The SLDSTB signal is a sealer data strobe enable signal. The DOEN signal is a strobe used to load header words onto the EDAT data lines.

In Figure 30, the command processor interface 302 receives 25 and interprets commands on bus 57 from the command processor 50, supervises the loading of command processor parameters for both the clipper and sealer. It turns the processor 310 on via bus 314 in response to an appropriate start pulse from CP and turns processor 310 off in the case of a suc- 30 ceeding command occurring while processor 310 is still pro¬ cessing data, and specifies which of the five functions of processor 310 is to carry out. The preclipper interface 304 monitors the data available signals from a preclipper circuit via bus 72 and selects one from which the clipper circuit will receive data for a given system. When the processor in 310 is about to finish processing a given entity, it sends the search signal on bu 316 to interface 304, informing it to select another pre¬ clipper.

Since the clipper circuit includes a path for X-coordinate data and for Y-coordinate data. Figure 32 depicts one half of the clipper circuit data path. Data is selected from one of four sources in Figure 32, which are the command pro cessor via bus 57 and buffer 327, the preclipper via bus 73 and buffer 328, the other accumulator. data path via bus 331 and buffer 329, and the ALU circuit 326 and inverter circui 325.

Command processor data from buffer 327 are selected from th interface 302 circuit of Figure 30 before the processor 310 is turned on. Preclipper data from buffer.328 are selected whenever a fetch strobe to a preclipper is issued. Data from the other accumulator via buffer 329 or from the ALU 326 and inverter 325 are selected by control signals from „proce-ssor 310.

In Figure 32, the ALU 326 and inverter 325 perform the off (unselected) , increment accumulator, add memory to accumu- lator, subtract memory from accumulator, invert result if negative, select memory, and select accumulator functions.

Selected data are fed to the accumulator 330. X-selected data are also fed to a process bits register (not shown) which also holds the screen space bit. Y-selected data are also fed to word counters (not shown), which monitor header and all words in an entity. The contents of the process bits register form part of the data sent to the sealer cir¬ cuit 71. Accumulator 330, in addition to holding data, can be right shifted one bit. A right-shift immediately follow¬ ing an ALU summing provides the SUM/2 function.

In Figure 32, each comparator 335, 337 has an accompanying one-word register 334, 336 loaded from memory 333. Regis- ters 334, 336 contents are compared to the accumulator 330 contents and the results are sent to logic in the arithmetic unit where they are analyzed and compared with previous such results. Processor 310 circuit of Figure 30 makes decisions on the results of such testing.

The X-memory of a clipper data path has a capacity of 16 words. The Y-memory, which is also used to store header - words, has a capacity of 256 words. In addition to feeding the items already mentioned, the memory is the source for coordinates sent to the sealer circuit. The Y-memory, in addition, must feed the EDAT data lines in order to flush the buffers. During* the storing and flushing of header words, the X-accumulator addresses the Y-memory via bus 339, controlling where in the Y-memory the headers are stored.. Two address pointers are maintained in the X-memory.

Figure 33 depicts the processor 310 circuit of Figure 30 in further detail. Processor 310 includes an 8-bit P-register

^'345 which feeds a 256-word X 48-bit PROM. Five of the PROM

346 bits select one of up to 32 signals, the state of which will select between two possible next addresses. Each processor state generates a series of commands which are summarized below.

COMMAND # BITS COMMENTS

MEMORY 6 Provides four bits of Memory addressing and separate enables for writing the X and Y Memories. -44-

COMMAND # BITS COMMENTS ACCUMULATOR 8 Directs separately the loading & ALU of the X and Y Accumulators. Provides for selecting the other Accumulator for data input. Supervises ALU opera¬ tion. Provides for shifting the Accumulators.

SPECIAL COMMANDS Selects one of 32 mutually ex¬ clusive special commands. These among other duties operate various Processor status flip- flops, load registers in the data path, and terminate Pro¬ cessor operation.

MISC BITS Generates six signals, which among other duties, generate the PRECLIPPER fetch strobe and the SCALER data strobe enable and load registers in the data path.

Referring again to Figure 30, the functions ol the clipper will be described in more detail. The clipper lies in the data path between the preclipper circuit 62 and the sealer circuit 71. The clipper performs five functions which are set view (CLIP), identify point, identify segment, identify window partial, and identify window full.

During the CLIP function, the clipper receives data pre¬ selected and modified by the preclipper circuit. For each data entity delivered to the clipper, a special single 32- bit header word is received followed by a number of 32-bit coordinate-pair of words. The special header contains the following items sensed by the clipper of Figure 30, which are:

ITEM # BITS COMMENTS SIZE 8 Specifies the number of 32 bit words, including the header, to be sent to the CLIPPER for that entity.

SCREEN SPACE Differentiates between Screen Space and Drawing Space.

PROCESS BITS Auxiliary data passed to the WRITE BOARD via the SCALER.

Prior to the execution of the CLIP or set view command, the command processor 50 of Figure 1 issues a series of para¬ meters of which the following are sensed by the clipper:

PARAMETER COMMENTS XL X coordinates defining left boundary of CLIP window.

YL Y coordinates defining lower boundary of CLIP window.

XH X coordinate defining right boundary of CLIP window.

YH Y coordinates defining upper boundary of CLIP window.

XMT, YMT, SCALER parameters. The CLIPPER detects MULTIPLY & SHIFT the issuance of these and via appropri¬ ate control signals directs the sealer to strobe these into the appropriate registers. During the set view execution, ^"for all entities with the screen space bit true, each coordinate-pair is passed on to the sealer circuit unmodified. PEN is UP for the first pai of each such entity and DOWN for the remaining.

For all entities with the screen space bit false, each coor dinatepair is considered in relationship to the previous coordinate-pair (if any) and to the window. A series of coordinate-pairs and PEN commands is generated and sent to the sealer so that that portion of the entity line on or within the window can be reproduced on the screen.

During the point-identify function, the clipper receives data preselected and modified by the preclippers. For each data entity delivered to the clipper circuit, the unmodifie group of header words are received, each 16-bit word one by one, on the Y portion of bus 73. A size byte with the same format as in set view is received via the X portion of bus 73 at the same time as the first header word is received. Also, the X_n coordinate is received via the X portion of bu 73 at the same time as the Y_Q coordinate is received. These are followed by the coordinate pairs received as 32- bit words, as in the set view function, beginning with the -coordinate pair X, , Y, . This scheme applies to both short and long form data.

Just prior to the execution of the point-identify command, the command processor issues a series of parameters of whic the following three are sensed and used by the clipper:

PARAMETER COMMENT

XID X coordinate defining identify origin.

YID Y coordinate defining identify origin. FFFFH First delta (= 2¹⁶ - 1).

During point identify execution, the following actions are taken by the clipper circuit:

1. The complete header of the entity being received is stored in the Clipper memory.

2. For each coordinate-pair received, a. ΔX(= |X - XID| and ΔY(= |Y - ΪID.j ) are formed. b. The greater of X and Y is compared with the stored delta (initially, the First Delta, 2¹⁶ - 1). c. If it is less than the stored delta, it replaces the stored delta, and the current entity is marked as a HIT.

3. After all coordinate-pairs for a given entity have been analyzed, if the entity has not been marked as a HIT, its header will be discarded. If the entity has been marked as a HIT, the header group for the previous HIT entity will be discarded.

4. When the CLIPPER detects the condition in which no more data is forthcoming, it interrupts the command pro¬ cessor,which then fetches from the CLIPPER a size word, indicating the total number of words to be sent, and the complete header of the entity last marked as a HIT.

The segment identify function is a refinement of the point identify function and the same parameters are used in the treatment and disposition of headers. Action taken on received coordinate pairs is as follows:

1. A point identify routine (equivalent to that described above) is applied to the first coordinate of each entity.

2. For each succeeding point (let P represent the previous coordinate pair, C the current, and PC the line connect¬ ing them): a. If PC crosses neither X = XID or Y = YID, a point identify is applied to C. b. If PC crosses one of the axes and is orthogonal, delta is formed equal to the magnitude of the distance between the axis intercept and the iden¬ tify origin. If this delta is less than the stored delta, it replaces the stored delta, and the current entity is marked as a HIT. c. If PC is a diagonal and, crosses X = XID only, with a slope > 1, or crosses Y = YID only, with a slope _< 1, then a point identify is applied to C. d. If PC is a diagonal and crosses X = XID with a slope < 1, the intercept on X = XID is computed. If PC is a diagonal and crosses Y = YID with a slope > 1, the intercept on Y •= YID is computed. In either case a delta is formed equal to the magnitude of the distance between the axis inter¬ cept and the identify origin. If this delta is less than the stored delta, it replaces the store delta, and the current entity is marked as a HIT. Then a point identify is applied to C.

During the identify window partial function, the clipper re ceives data preselected and modified by the preclippers and the format is the same as for the point and segment identif functions. The above described parameters XL, YL, XH and YH are received and stored prior the execution of the com¬ mand. During the partial window identify function, the following actions are taken by the clipper:

1. The complete header of the entity being received is stored in the CLIPPER memory. 2. If the first coordinate-pair lies on or within the window, the entity is marked as a HIT. 3. If any successive coordinate-pair lies on or within th window or if the line connecting any point, other than the first, with the previous point intersects the window, the entity is marked as a HIT. 4. After all coordinate-pairs for a given entity have been analyzed, if the entity has not been marked as a HIT, its header will be discarded. Otherwise, it will be retained along with the headers for any previous HIT entities.

5. Whenever the CLIPPER memory contains 224 or more header words or the CLIPPER detects the condition in which no more data is forthcoming, it interrupts the COMMAND PROCESSOR, which then fetches from the CLIPPER a size word, indicating the total number of words to be sent, and then all the header words stored.

The identify window full function differs from partial win- dow identify in that an entity is considered within a window only if all coordinate pairs lie on or within the window.

Sealer Circuit

Referring now to Figure 34, the sealer circuit 71 of Figure 2 is shown in more detail. The 40 MHz, SYNC and reset sig¬ nals on bus 57 are input to clocking, timing and reset cir¬ cuit 405, which provides appropriate timing pulses for the sealer circuit.

Clipper control interface circuit 401 receives data strobe enable and parameter strobe enable signals from the clipper on bus 77. Buffer 402 receives 16-bit system data signals on bus 57 for connection to magnifier parameter register 407, translation parameter register 410, and/or scale para¬ meter register 413. Clipper data on bus 76 from the clipper circuit 70 are input to clipper data buffers 403.

During the set view operation, the sealer provides the func¬ tions of magnify, translate, scale and buffer. Parameters from the command processor 50 of Figure 1 are loaded through buffer 402 into the registers 407, 410, 413 via bus 430. Data on bus 76 from the clipper are received and stored in the clipper data buffers 403.

Assuming a drawing space mode, the X and Y coordinates are sent in pipeline fashion (Y-coordinate following X-coordi- nate) through the magnifier 408, translator 411 and sealer 414 circuits, via bus 421-423, respectively.

In screen space mode, the X and Y coordinates are loaded directly into sealer and buffer circuit 414 via bus 421 without processing. From buffer 414, in either mode, the sealer coordinates on bus 425, together with the process and pen up bits on bus 426, are loaded into buffer memory 417. From memory 417, data are sent via bus 427 to output buffer 418, a one-word or 25-bit output buffer, and to the write circuit 80 in Figure 1 on bus 83.

The sealer circuit basic timing is depicted in Figure 35.

The LDCRD signal loads clipper, data into clipper data buf¬ fers 403 and raises PRCENB, which in turn enables the PROCESS signal, which will lead to the processed coordi¬ nates being written into buffer memory 417.

xiSEL and YISEL signals enable the loading of respective input coordinates onto a common bus 421 which feeds magni¬ fier circuit 408 and also the buffers in the sealer circuit 414.

The SELXMT and SELYMT signals select the appropriate trans- lation parameter to be fed to the translator circuit 411.

The CKMG signal clocks the magnifier buffer 408. The X and Y notations on the timing diagram in Figure 35 indicate the coordinate clocked. The CKTR signal clocks translator buffer 411. The X-coor- dinate will be clocked into translator buffer 411 at the same time the X-coordinate in the magnifier buffer 408 is being overwritten by the Y-coordinate.

The sealer buffer 414 has separate buffers for both X and Y coordinates, which are clocked by CKSX and CKSY signals, respectively. At the occurrence of these respective clocks, XISEL and YISEL in Figure 35 are off. However, in screen space mode, XISEL and YISEL will be active as required at the times in order to load the input coordinates into the sealer buffer 414.

The FETDIS signal prevents data from being read from the buffer memory 417. The LDMEM signal selects the write pointer (as opposed to the read pointer) for memory 417. WRMEM is the strobe that actually writes memory 417.

In Figure 34, the magnifier buffer 408 takes 16-bit input coordinate data on bus 421 and left-shifts the data 0 to 15 bits ignoring overflow, and filling with zeros. The result is truncated to 12 bits and stored in magnifier buffer 408. The extent of the left-shift is determined by the magnifier ^'parameter from register 407, which has been loaded via bus 430 from buffer 402.

Translator buffer 411 takes the 12-bit coordinate data from magnifier buffer 408 via bus 422 and subtracts from it the appropriate 12-bit (X or Y) translation parameter, the most significant borrow being ignored, and the result is stored in the buffer 411.

The sealer buffer 414 takes the 12-bit coordinate from translator buffer 411 vis bus 423 and multiplies it by the 8-bit scale parameter from register 413. The most signi¬ ficant bit (MSB) of the 20-bit result is discarded (it should be a zero) and the remainder is rounded back to 9 bits. The result is stored in one 9-bit buffer for X and another for the Y coordinate.

The contents (18 bits) of the sealer buffer 414 along wit six process bits and the pen up bit on bus 426 are writte into IK buffer memory 417. Process bits and pen up bit a loaded into an input register (not shown) simultaneously with the reception of the coordinates from the clipper. They are loaded by the CKSK and CKSY signals into an inte mediate register (not shown) which feeds the memory.

Output buffer 418 holds one full data word (coordinates, process bits and pen up bit) in transit from the buffer memory 417 to the write circuit 80 of Figure 1. Buffer 41 is loaded whenever it is empty and buffer memory 417 con- tains data and is not being written. When it is being loaded or already contains a word, a data available signal is sent to a write circuit data 80 via process control circuit 404 and bus 84. The write circuit 80 responds wit a data acknowledge (ACKN) which permits refilling of outpu buffer 418.

-. The data transfer rate between the sealer circuit 71 and write circuit 80 can be six words per 300 ns if buffer .memory 417 is not being written or four words per 300 ns i it is being written. The write circuit 80 can send a HOLD signal via bus 84 which will cause the sealer circuit 71 t suspend processing data and writing the buffer memory whenever the buffer memory is more than half full.

Prior to the execution of the set view operation, the seal circuit receives four parameters, in three words, from command processor via bus 57. The parameters are: Name Sy bol Range

SCALE (MULTIPLY) f 0 < f <.2^b - 1 MAGNIFY (SHIFT) e 0 <. e _< 2⁴ - 1 X TRANSLATION XMT 0 <. XMT _< 2¹² - 1 Y TRANSLATION YMT 0 < YMT < 2¹² - 1

During execution of the set view operation, the sealer cir¬ cuit receives from the clipper via bus 76 data containing the following:

NAME COMMENTS DRAWING SPACE Bit differentiating between screen space and drawing space.

PROCESS BITS Six bits stored and passed on to the

WRITE CIRCUIT without modification.

PEN UP Bit specifying Pen Up. Stored and passed on to the WRITE CIRCUIT without modification.

COORDINATE-PAIR Coordinate-pair to be operated upon.

Symbols X and Y. Range 0 to 2 - 1.

In the drawing space mode, the sealer circuit applies all four functions (magnify, translate, scale, and buffer) to ,the input coordinate pair. In screen space it applies only the buffer function.

For a magnify (shift) function, the two input coordinates are left-shifted a number of places specified by the para- meter, with overflow discarded, and with zeros shifted in. The result is then truncated to 12 bits. Consequently the magnify coordinate for X (and analogously for Y) is:

12

XM = x ^• truncated, modulo 2

16

For the translate function, from the 12-bit magnified (shifted) coordinates, XM and YM, are subtracted the cor¬ responding translation parameters stored in register 410, also each 12 bits. The subtraction is carried out modulo

12 2 in that borrow-outs are ignored. For the X-coordinate (and analogously for Y) XT = XM - XMT, modulo 2¹².

For the scale (multiply) function, the 12-bit translated coordinates on bus 423 are each multiplied by the 8-bit parameter f from register 413. The MSB of the 20-bit result, which should be a zero, is discarded. The remainin 19 bits are then truncated to 9 bits. Hence for the X coor dinate (and analogously for Y) on bus 425, the X value is

XS = — XTτ-R" f, truncated, modulo 29. '

2

For the buffer function, the 9-bit scaled coordinates on bu 425 (in the case of drawing space) or of the 16-bit inputte coordinates truncated to 9-bits (in the case of screen space) are stored in IK word buffer memory 417 along with the six process bits and the pen up bit on bus 426. A one-word output register 418 holds the data words in transi from the buffer memory to the write board.

The sealer circuit flags the clipper via bus 77 and control circuit 404 to suspend sending data when buffer memory 417 is full or if the write circuit acknowledges a hold signal on bus 84, when the buffer memory 417 is more than half full.

The sealer parameters loaded into registers 407, 410, and 413 are received from the command processor via bus 57 and buffer 402. Strobing of these parameters into the appro¬ priate sealer registers 407, 410, 413 is under control of the clipper circuit via bus 77, control interface 401 and bus 420. Write Circuit

Referring now to Figure 36, (Figures 36A, 36B, and 36C), the write circuit 80 of Figure 2 is depicted in further detail.

The write circuit 80 performs the function of rapidly generating points in a matrix field to approximate the location of two-dimensional straight line vectors. The matrix field can be any rectangular matrix such as 512 x 512, 768 x 1024, 1024 x 1024 etc. A 512 x 512 matrix is assumed in the following description of the Write circuit. The points are subsequently transferred to refresh memory 81 which is used to refresh a standard television monitor scope. The refresh memory must have a storage capacity of at least equal to the number of points in the matrix field for a black and white display or some multiple of this size for a color display. The refresh memory referred to in this circuit description has a storage capacity of 262, 144 bits to accommodate the 512 x 512 matrix field for a black and white display.

Vector data stored in refresh memory 81 is derived from vector end points stored in a data base having considerably more resolution than the refresh memory which implies that vectors stored in the refresh memory are in general approx- imations of the vectors stored in the data base. The mapping of arbitrary vector end points from the data base to the refresh memory can be considered to be exact only for a relatively small number of vectors and magnification values. In a majority of cases, where arbitrary magnification and translation values are applied to a given vector, the end points being rounded to lesser precision will produce some distortion of geometrical figures, the effect being more noticeable as the number of points comprising the figure is reduced. The rounded vector end points are input to the -56- write circuit from sealer circuit 71 along with the line format information (e.g., pen state, line type, and/or color) . The write circuit then fills in the remaining points on the vectors and transfers^' them to refresh memor 71.

Data from sealer circuit 71 are transferred via bus 83 in an input register comprising an end point latch 451, dela latch 452 and start point latch 453.

Status information from the sealer circuit are input on b 84 into data strobe control circuit 455. Data from comma processor 50 of Figure 1 are input via bus 57 providing t 40 MHz and reset signals previously described.

Vector data are transferred from the sealer circuit 71 to the write circuit 80 when the data available line (SCWDAV on bus 84 is high, signifying that data are available on data lines 83. Data are latched into the end point latch 451 by input register clock (IRC ) from data strobe contr circuit 455. Data in the end point latch 451 are trans¬ ferred to delay latch 452 during the next, clock period.

The first vector data following a set view command will b pen up vector and the coordinates of this vector are load from the delay latch 452 into X- and Y-axis chase counter 456, 457, as well as into final value latch 461 by the LO pulse. As soon as possible, another vector is transferre from the sealer circuit to end point latch 451 and the vector previously stored in this latch is transferred to start point latch 453. As soon as the previous vector ha been processed by the chase counters, the next vector wil be transferred from delay latch 452 to final value latch 461, in the case of a pen down vector, or to both final value latch 461 and the X and Y chase counters 456, 457, -57- the case of a pen up vector. Final value latch 461 can be loaded at the same time that the next vector is transferred to end point latch 451 provided that the input register al¬ ready contains an unused vector and that the chase counters εre not processing a vector. Subsequent sealer circuit to write circuit transfers can occur simultaneously with a LOAD pulse or any time after the LOAD pulse has taken the pre¬ vious vector. Subsequent LOAD pulses can occur whenever valid data exists in the input register provided that no other vector is being processed.

Final value latch 461 contains the end point coordinates of the vector being processed as well as the line type, line color, chase counter direction control lines along with signals that specify whether this vector has changed cell (to be explained), color, or both.

Final value comparator 460 separately monitors whether the state of the X and Y axis chase counters 456, 457 agree with the coordinates stored in the final value latch 461 so that the chase counters can be stopped when the end point is reached. Alternately, a counter could be loaded with the longer component of the vector being processed and this counter could then be counted down as the chase counters operate, ultimately reaching zero when the end point is reached. By monitoring the state of this counter, one could anticipate ahead of time when the last point in the vector will be reached. Write circuit 80 includes a diagonal generator which operates only on pen down lines. If an input vector has a pen down flag, then the coordinates in start point latch 453 and end point latch 451 are compared by the direction comparators 462 to determine whether the chase counters 456, 457 are to count up or down. After the proper direction has been determined, the absolute value of ^~-58- the vector component lengths along the X and Y axes are computed by ALU circuit 464. Slope comparator 465 deter¬ mines whether the X or Y component is larger and controls multiplexer (MUX) 466, which selects the smaller (A) and larger (B) components. Subtracter 467 computes the value C = A-B and D = A-B/2. The D value is used to preset the count latch 471 during a load cycle. The values of A, B, C and D are also loaded into latch 472 during a load cycl since they are needed later in the diagonalization proces The diagonal generator is not required when writing hori¬ zontal or vertical lines and can be bypassed if desired i order to eliminate the time required to calculate the A, C and D values.

Multiplexer (MUX) 473 selects either A or C = A-B and the selected value is added to the data output of count latch

471 on the next accumulation cycle. If the count output count latch 471 is low, then A is added to the data outpu of count latch 417 on the next cycle whereas if count is high then A-B is added on the next cycle.

Because count latch 471 is required to accumulate at a fa clock rate, 40 MHz in the circuit being described, insuf- ficient time is available to use the carry output from th LSB adder of adder 470 to provide the carry input to the adder of adder 470. Hence a look ahead circuit consistin of two 4-bit adders 470 (SIN, DBL) and two multiplexers

(MUX) 473 calculate the results of four possible combina¬ tions of two successive operations and the results are stored in count latch 471 and the appropriate one is sele ed by the count output on the next cycle and routed to th carry input of the MSB adder. The count output of the co latch will be high if the adder had a carry out (GDC) on previous clock cycle. A high level on the count output w eventually be used to enable one of the chase counters 45 -59- 457 and since count will generally be low for some fraction of the active clock cycles, one of the chase counters 456, 457 will count less frequently than the other. Since B represents the length of the longer component of the vector and A the length of the shorter component, one of the chase counters 456, 457 will count B times and the other will count A times. The result of any operation will be greater than or equal to A-B and less than A which leads to the inequality

A - B _< B ' A - A ^* B + I < A

where I is the initial value in the count latch. This equation can be rewritten as

B .> I - A > $

which makes it clear that there are in general a number of choices for I that will lead to the correct vector end point. However, the path taken to reach this end point is influenced by the choice of I. The path which most closely - approximates the desired line will result when I is chosen to be approximately the arithmetic average of A and A-B, so that I = A - B/2 is a good choice. Since D has been pre¬ viously defined as D = A-B/2, then I = D. *

Counters 456, 457 initially contain the beginning point of a vector as a result of either being preset to this state by a pen up operation or by being counted to this state as a result of processing a previous pen down vector. When the next pen down vector is loaded into final value latch 461, one or both of the counters 456, 457 will operate until the state of the counters match that stored in final value latch 460. The counter whose vector component is larger will be programmed by the slope comparator 465 to count continuously except when restrained from doing so by refresh memory cyc time limitations. The other counter is also subject to th cycle time restriction and in addition can only operate wh count is high.

The three least significant bits of both counters 456, 457 are decoded by one out of 64 decoder 475 to determine the location of the appropriate point in an 8 x 8 matrix (the matrix defining a cell) and this data point is stored in 64-bit memory 476, which is a one's latching memory so that data points can be accumulated without regard to pre¬ vious data.

Decoder 475 is enabled by signal INHIB, from inhibit flip flop 477, going low when a vector is loaded into final val latch 461. Decoder 475 is disabled by signal INHIB going high after the end point is reached. This prevents extran eous data from being written into memory 476 after the contents of this_, memory have been transferred to chip enab latch 478.

Memory 476 will accumulate a new data point every clock cycle as successive vectors are processed until it becomes - imminent that one or both of counters 456, 457 crosses a cell boundary on the next clock cycle or a color change occurs or until the input register empties. If any of the possibilities occurs the contents of memory 476 are trans- ferred to chip enable latch 478, the cell address, which i derived from the high order bits of the counters 456, 457, is transferred from an address delay latch 479 to memory address latch 480 and the color bits are also transferred from address delay latch 479 to color select latch 480. These three latches constitute an output latch and the dat must be maintained valid in these latches until the cycle time of refresh memory circuit 81 has been satisfied. The transfer of data to the output latches is therefore subject to the condition that the previous memory cycle has timed out. More than eight points can be transferred at one time if one or more corners of the polygon are contained in a cell. However, the statistical probability of this occur¬ ring diminishes rapidly as the number of points increases above eight.

Simultaneously with data transfer to the output latch, a WRITE pulse is output to refresh memory circuit 81 which initiates a new refresh memory cycle and a reset pulse is generated which causes memory 476 to be erased during the next clock interval. If chase counter decoder 475 is enabled when the reset pulse occurs, then the selected bit will remain set if it was previously set or it will be set during the next clock interval if it was not previously set since decoder 475 overrides the reset command.

The memory organization of this system 15 is based upon, but not limited to, an 8 x 8 matrix format which permits hori- zontal, vertical and diagonal lines to be transferred to refresh memory circuit 81 at the rate of 8 points every 200 'ns when using a 40 MHz clock. The system utilizes a refresh memory having 4096 words of data storage, each word contain¬ ing 64 bits to accommodate the 8 x 8 cell. Except for the first and last cells, a refresh memory that will cycle in 200 ns or less will suffice, however, the first and last cell may contain fewer than 8 points which means that even a .50 ns refresh memory might be slower than desired for this situation. The first and last cells will be processed more rapidly on the average as faster refresh memories are made available. A fast memory becomes more important as the proportion of short vectors or pen up vectors increases. In order to generate the intermediate points of a diagonal vector, given the end points, previous techniques have used binary rate multipliers or differential digital analyzers, which tend to waste clock cycles and generate dense lines, consuming time.

The present system utilizes a technique which permits diagonal lines to be generated at the rate of one point eac clock cycle provided that the previous memory cycle times out before a cell boundary is crossed, thereby generating a minimal density line which allows diagonal lines to be written as rapidly as the longer component could be written if it were written by itself (assuming of course that no time was lost waiting for the refresh memory cycle to time out) and thereby no wasted clock cycles.

A fast memory is quite desirable when writing diagonal line since a large fraction of the intersected cells can contain fewer than eight points. For instance, it is possible to construct situations where slightly more than half of the intersected cells contain only a single point. To facili- tate the utilization of faster refresh memory devices, as they become available, the present write circuit is designe with a memory cycle time controller that is automatically programmed by refresh memory circuit 81 to accommodate cycl times between 50 and 200 ns, in increments of 25 ns.

In summary, then, the write circuit can generate a new point on any vector every clock cycle, subject to refresh memory cycle time limitations and can accommodate refresh memories having cycle times between 50 and 200 ns.

Read Circuit

Figure 37 depicts in more detail the read circuit 82 of

Figure 2. Read circuit 82 performs the function of gener- ating the intensity and synchronization signals necessary to display a graphic image on a raster-scan CRT monitor such as monitor 20 of Figure 1. The image includes a primary image, obtained from the refresh memory circuit 81 of Figure 2, upon which are superimposed a grid and two cursors. Other functions of the read circuit 82 include selectively erasing the refresh memory 81, transmitting the contents of the refresh memory 81 to the command processor 50, controlling the activity of the write circuit 80, and interpreting the commands issued by the command processor 50 via bus 57.

Referring now to Figure 37, the read circuit 82 includes a control processor 501, which receives control and data signals via bus 57 from the command processor 50 of Figure 2, interprets these signals as commands and timing informa- tion, and generates various control signals (not shown) necessary to execute the commands intended for read circuit 82. Read circuit 82 responds to the commands set forth in Table III issued by command- processor 50:

TABLE III SET CURSOR LOAD PROGRAM

SET GRID EXAMINE PROGRAM

SET ERASE LOAD CURSOR TABLE

READ REFRESH MEMORY LOAD VIDEO TABLE QUERY REFRESH MEMORY ^' LOAD REGISTER READ STOP EXAMINE STATUS READ GO

In one embodiment, control processor 501 is a micropro¬ grammed processor having a 40-bit microword and a cycle time of 50 ns. The microprogram is PROM-resident. Following a general system reset, execution of the microprogram begins at address zero.

Read circuit 82 also includes a display processor 502, which

^~~~~ generates various control signals (not shown) under the supervision of the control processor 501. These signals control the operation of the memory cell field generator 508, write circuit control interface 509, refresh memory control interface 510, memory cell bit latch 511, memory cell address latch 512, and refresh memory data latch 513. Display processor 502 is used by control processor 501 to cooperate in executing certain commands as they are being received. The display processor may also function indepen dently, as it does, for example, in controlling the genera tion of the video image on CRT monitor 20.

Display processor 502 also generates signals XS and YS, which designate the x-y coordinates of a pixel of the graphics image.

In one embodiment, display processor 502 is a micropro¬ grammed processor having a 60-bit microword and a cycle ti of 25 ns. The microprogram is RAM-resident. Command pro¬ cessor 50 issues a LOAD PROGRAM command to load the displa processor microprogram memory and, optionally, to initiate execution of the microprogram at a specified address. An EXAMINE PROGRAM command may be issued to read back the contents of a specified word of the microprogram memory, for diagnostic purposes. Display processor 502 also includes counter registers for generating the XS and YS signals and three additional counter registers, included f timing and iteration control purposes.

Display processor operation may be halted by issuing the READ STOP command and may be resumed by issuing the READ GO command.

Read circuit 82 also includes control multiplexer 503, whi allows control processor 501 to generate certain control signals normally generated by the display processor. Cursor generators 504 output pixel data pertaining to the two cursors generated by read circuit 82. For each pixel of a given cursor, two bits are output which correspond to its column location XS and two bits are output which correspond to its row location YS. Cursor pixel information is stored in cursor generator 504 in the form of two 512 x 2-bit edge arrays, one indexed by XS and one indexed by YS. These edge arrays are loaded via bus 57 by command processor 50, using the SET CURSOR command.

Similarly, grid generator 506 outputs pixel data pertaining to the grid generated by read circuit 82. For each pixel of the grid, two bits are output which correspond to its column location XS and two bits are output which correspond to its row location YS. Grid pixel information is stored in grid generator 506 in the form of two 512 x 2-bit edge arrays.

These edge arrays are loaded via bus 57 by command processor 50, using the SET GRID command.

Cursor output generator 505 combines the pixel data pertain¬ ing to the two cursors into a three-bit value, according to an arbitrary Boolean function implemented as a 256-word look-up table. This look-up table is loaded via bus 57 by -. command processor 50, using the LOAD CURSOR TABLE command.

Similarly, video output generator 507 combines the pixel data pertaining to the grid with pixel data from the refresh memory 81 and cursor summary data from cursor output gen¬ erator 505. An eight-bit result is generated internally, according to an arbitrary Boolean function implemented as a 256-word look-up table. This look-up table is loaded via bus 57 by command processor 50, using LOAD VIDEO TABLE command. The four-bit result represents the brightness of the pixel to be produced in the graphics image. A digital- to-analog converter circuit within video output generator 507 converts the four-bit digital result to the electrical voltage required to produce the desired pixel brightness o CRT monitor 20 via bus 90. The digital-to-analog converte also generates the electrical voltages required to effect synchronization of CRT monitor's X and Y raster sweep function with the presented video image.

Memory cell field generator 508, refresh memory control interface 510, memory cell bit latch 511, memory cell address latch 512, refresh memory data latch 513, and bus constitute the interface of read circuit 82 with refresh memory 81.

Memory cell field generator 508 specifies which rows and columns within an 8 x 8 memory cell participate in the current memory read or write operation. Any single column pairs of columns on a two-column boundary, the left or rig four columns, or all eight columns may be specified, and similarly for rows. For a read operation it is typical to specify a single row and all eight columns.

Memory cell field generator 508 may be used to specify whi rows and column of an 8 x 8 cell to erase to a specified background condition. Information is stored in memory cel -- field generator 508 specifying which rows and columns of t ^•graphics image are to be erased. Erase information is stored in two 512 x 1-bit edge arrays, similar in concept the edge arrays in cursor generator 504 and grid generator 506. Memory cell field generator 508 may optionally outpu the Boolean conjunction of the erase information for a memory cell's rows/columns and the directly specified rows columns. For an erase write operation it is typical to specify a single row and all eight columns directly, and t specify the Boolean conjunction with erase edge array data in both X and Y directions. The erase edge arrays are loaded via bus 57 by command processor 50, using the SET ERASE command. Memory cell bit latch 511 generates signals specifying which individual bits of an 8 x 8 memory cell participate in the current refresh memory read or write operation, from the specification by rows and columns generated by memory cell field generator 508. A latching function is also performed.

Memory cell address latch 512 latches the upper six bits of the XS and YS signals, which constitute a specification of the particular 8 x 8 memory cell affected by the current refresh memory operation.

Refresh memory data latch 513 receives data corresponding to the columns of an 8 x 8 memory cell during a read operation. It outputs this data serially to video output generator 507 during the process of generating a graphics image on CRT monitor 20. Alternatively, during the READ RASTER MEMORY command, received data is transferred in parallel on an internal bus (not shown) to control processor 501, which in turn transmits the data via bus 57 to command processor 50. Data obtained in this way can be used for diagnostic pur¬ poses and can also be processed further for output to a dot matrix hard copy peripheral. Data received during the QUERY RASTER MEMORY command is treated in the same way. However, .the data itself, generated in the refresh memory circuit 81

_* without regard to the other signals whenever QUERY signal is asserted, is a code specifying the minimum cycle time of refresh memory 81. The data obtained in this way can be used to select a display algorithm that optimizes use of refresh memory.

Refresh memory control interface 510 determines what kind of refresh memory operation is being performed. The QUERY signal is asserted during a query raster memory operation. The STROBE signal is asserted during a read operation. The WRITE signal is asserted during a write operation, in which case the DBIN signal determines the data value written to selected bits of the selected 8 8 memory cell. The QUER STROBE, and WRITE signals are driven directly from display processor 502, while the DBIN signal is latched separately and can be set and reset by display processor 502.

5 Write circuit control interface 509 generates the WRTINH signal, which when asserted prevents write circuit 80 from accessing refresh memory 81. The state of the WRTINH sign can be set and reset by display processor 502. Whenever t WRTINH signal is unasserted, read circuit 82 must unassert 0 the CE, MA, QUERY, WRITE, and STROBE signals, to avoid conflicts with their use by write circuit 80, and must provide the correct DBIN signal, namely the complement of the background value.

The LOAD REGISTER and EXAMINE STATUS commands are included 5 in read circuit 82 for diagnostic and test purposes.

Various internal registers may be set to known values and/ examined using these commands.

Proper operation of read circuit 82 requires the initializ tion of its internal state. When command processor 50 0 asserts the RESET signal of bus 57, control processor 501 , suspends execution of its microprogram. When the reset

« signal is unasserted, control processor 501 resumes .execu¬ tion at address^' zero, placing it in a correct microprogram sequence for receiving and interpreting commands, while 5 suspending execution of the display processor 502 micro¬ program.

Next, command processor 50 issues LOAD CURSOR TABLE com¬ mands, to^' initialize the look-up table within cursor outpu generator 505, and LOAD VIDEO TABLE commands, to initializ 0 the look-up table within video output generator 507. Thes tables define the rules whereby edge array specifications the grid and cursors are merged with primary image data to form the video output signal on bus 90 to CRT monitor 20. This look-up table mechanism allows the brightness of the cursors, grid, primary image, and their combinations to be specified arbitrarily. It also affords considerable flex¬ ibility in specifying how row and column edge array data is combined to form shapes. For example, the grid may be displayed either as a rectangular matrix of points or as lines that pass through those points.

Command processor 50 also issues LOAD PROGRAM commands, to download the microprogram memory of display processor 502. Then, command processor 50 issues SET ERASE commands, to establish erase edge array data for clearing refresh memory; SET CURSOR commands, to clear the cursor edge arrays; and a

SET GRID command, to clear the grid edge arrays. Finally, command processor 50 initiates execution of the display processor microprogram, causing display processor 502 to erase refresh memory 81 and display a blank graphics image on CRT monitor 20.

The initialization sequence described above is normally performed only when graphics display system 15 is issued a reset command by CPU 50.

During normal execution of the microprogram for generating a graphics image, display processor 502- asserts the CURSUP signal of bus 57 at the end of each video frame. This signal interrupts commands, such as SET CURSOR, SET GRID, and SET ERASE, during the time between video frames, thus avoiding a disruption in the presentation of video frames. Also during normal execution of this microprogram, display processor asserts the WRTINH signal of bus 86 continuously, so that read circuit 82 has unlimited access to refresh memory 81 and write circuit 80 is denied access.

Command processor 50 issues a SET CURSOR command between video frames as described above. Command processor 50 is responsible for generating the edge array data transmitted within the SET CURSOR command via bus 57 to read circuit 8 given the parametric specification in the corresponding SE CURSOR command transmitted from host CPU 10 via bus 56 to command processor 50, as shown in Figure 12.

Similarly, command processor 50 issues a SET GRID command between video frames. Command processor 50 is responsible for generating the edge array data transmitted within the SET GRID command via bus 57 to read circuit 82. The edge array representation allows grids to be specified with considerable flexibility. For example, the spacing in X and Y can be different and even non-uniform.

»

Read circuit 82 does not respond to a SET VIEW command as such, but does respond to a SET ERASE command issued^' by command processor 50 between video frames during a set vie operation. Command processor first issues a SET VIEW command and at a later time, but before the completion of the set view operation, issues a SET ERASE command. Comma processor 50 is responsible for generating the edge array data transmitted within the SET ERASE command via bus 57 to read circuit 82, given the viewport specifications in t , corresponding SET VIEW command received by command process 50 from host CPU 10 via bus 56. In addition to loading th erase edge array data, read circuit 82 sets an internal flag, indicating that during the presentation of the next video frame the specified viewport is to be erased.

During the same inter-frame interval that command processo 50 issues a SET ERASE command, it also issues a LOAD PROGR command, which causes display processor 502 to set the DBI signal to the proper background state, as specified by the SET VIEW command received from host CPU 10.

During the subsequent video frame, read circuit 82 erases -li¬ the specified viewport to the specified background state. At the end of the frame, read circuit 82 clears the internal flag that caused the erase to occur, complements the DBIN signal, relinquishes the rest of bus 87,* and unasserts the WRTINH signal on bus 86, thus permitting write circuit 80 to write new data to refresh memory 81. Then read circuit 82 monitors the BUSY signal of bus 57 and thereby waits for the set view operation to complete. If the inter-frame interval expires before the set view operation completes, read circuit 82 generates one or more blank video frames while waiting, rather than interrupt write circuit 80 or alter the timing of video frame presentation. When set view operation completes, read circuit 82 reasserts the WRTINH signal and resumes its task of generating a graphics image on CRT monitor 20..

Refresh Memory

Figure 38 depicts in more detail the refresh memory circuit 81 of Figure 2. Refresh memory circuit 81 is used by system 15 to store raster data generated by write circuit 80 and to make this raster data available to read circuit 82 for display and other purposes. Data can also be stored into refresh memory circuit 81 by read circuit 82, typically for the purpose of erasing refresh memory circuit 81. Refresh memory circuit 81 can also be requested by write circuit 80 or read circuit 82 to output a code describing, the speed of refresh memory circuit 81, so that write circuit 80 and read circuit 82 can access refresh memory circuit 81 as rapidly as possible.

Referring now to Figure 38, refresh memory circuit 81 in- eludes a memory 607 into which raster data is stored. In one embodiment, memory 607 comprises sixty-four 4096-bit memory integrated circuits. Memory 607 ^includes logic circuits (not shown) to interface the signals of bus 87. The logic circuits are incidental to the conceptual opera¬ tion of refresh memory circuit 81 and need not be describe in detail.

Each memory integrated circuit within memory 607 has twelv address signals, one chip-enable signal, one write signal, one data-in signal and one data-out signal. The memory circuits are interconnected so that the address signals, data-in signals and write signals of the circuits are connected to logically equivalent copies of the MA, DBIN a WRITE signals of bus 87, respectively. However, the chip enable signal of each circui is connected logically to it own unique CE signal on bus 87.

Memory 607 is thus organized as 4096 64-bit words, with the MA signals of bus 87 specifying which word is accessed Moreover, since all memory integrated circuits within memo 607 are logically connected to a common WRITE signal on bu 87, a given word as a whole may be accessed for reading or accessed for writing, but may not be accessed so that part of the word is accessed for reading and another part the word is simultaneously accessed for writing. Further more, since all memory integrated circuits within memory 6 ,. are logically connected to a common data-in signal, DBIN o bus 87, a given word as a whole may be accessed for writin ones or accessed for writing zeroes, but may not be access for writing ones into part of the word and zeroes into another part of the word simultaneously.

However, since each memory integrated circuit within memor 607 is logically connected to its own unique chip enable signal within the CE portion of bus 87, the effect of a memory access on the accessed word may be controlled for each bit within the word independently. Specifically, for write access, the CE signals specify which bits within the

Refresh memory circuit 81 further includes memory type cod circuit 611 for encoding a description of the performance characteristics of refresh memory circuit 81 and multiplex 612 to allow this information to be accessed internally. Memory type code circuit outputs on bus 631 a three-bit integer, between 1 and 7, which is one fewer than the numb of 25 us clock periods required by the memory to complete read or write cycle. If the QUERY signal of bus 87 is asserted, multiplexer 612 routes the code on bus 61 to the three low-order signals of the DO portion of bus 87, but i QUERY is unasserted, multiplexer 612 routes the contents of bus 630 to the DO portion of bus 87.

Refresh memory circuit 81 has four features which parti¬ cularly suit it for use in graphics display system 15. Th first feature is that write circuit 80 can write multiple raster points into refresh memory circuit 81 within each- memory write cycle. This feature is of value because, typically, write circuit 80 is able to generate raster points much faster than refresh memory circuit 81 can perform a memory write operation. For example, in one embodiment, write circuit generates raster points at a rat of one point every 25 ns, but a memory write operation is performed in 175 ns. By writing multiple raster points pe memory cycle, it is possible in many cases for write circu 80 to generate raster points at the maximum rate, without having to wait for refresh memory circuit 81.

The second feature is that the organization of refresh memory circuit 81, into 64-bit words in one embodiment, is compatible with the interpretation imposed by write circui 80 and read circuit 82 that the bits within a word represe picture elements within a rectangular portion, or cell, of the rasterized graphics image. In the case of a 64-bit word, the following interpretations regarding cell shape a possible: 64 X 1, 32 X 2, 16 X 4, 8 X 8, 4. X 16, 2 X 32, and 1 X 64. In one embodiment, an 8 X 8 cell shape is used to facilitate equally the rasterizing of both horizontal and vertical lines.

The third feature is that the width of the data path out of refresh memory circuit 81, the DO portion of bus 87, can be designed to be any divisor of the word size, by utilizing the technique of ORing (or wire-ORing) the data outputs of multiple memory devices. The geometric interpretation of the bits which are accessed on the data out bus at one time, as is the case for the memory cell as a whole, is₍ provided by read circuit 82 and write circuit 80. In one embodiment, the DO portion of bus 87 is eight bits in width and outputs one row of an 8 X 8 cell at a time. This provides a good match between the cycle time of refresh memory circuit 81, typically 175 ns, and the raster output scan rate, typically 25 ns per picture element.

The fourth feature is that,- as write circuit 80 performs successive write operations to a given cell, using the same DBIN value in all cases to represent a raster point, refresh memory circuit 81 inherently accumulates these raster points. This is a consequence of the fact that on any given memory write cycle, the memory devices that are selected are written to the raster point value, while the memory devices that are not selected retain their previously established contents. Thus refresh memory circuit 81 functions as a ones-latching memory or zeroes-latching memory, depending on the state of the DBIN signal on bus 87. As a result, refresh memory circuit 81 can be updated by write circuit 80 using normal write cycles, rather than read-modify-write cycles, which minimizes the time required to update the memory.

Timing diagrams depicted in Figures 39-41 illustrate timing for read, write, and read/write operations, respectively, -76- assuming that the memory integrated circuits used are 214 static RAMs. Typically, read/write operations are not performed by system 15, because of the ones-latching feat of the normal write operation, but the timing for such an operation is nevertheless illustrated, as an indication o the value of the ones-latching feature.

Claims

What is Claimed is:

1. A graphics display system comprising first memory means for storing vector data representing one or more graphic images to be displayed, second memory means, and means for rasterizing said vector data into said second memory means, thereby forming rasterized data.

2. A system as in Claim 1 including processor means for controlling said first and second memory means and said rasterizing means.

3. A system as in Claim 1 further including means for reading said rasterized data from said second memory means and monitor means for displaying said rasterized data.

4. A system as in Claim 1 wherein said vector data repre¬ sents one or more polygons, and wherein the representation of each polygon includes header information specifying the format of said representation and the properties of said polygons.

5. A system as in Claim 4 wherein said first memory means include vector memory means and control means including means for inserting said vector data into said vector memory means, means for modifying said vector data within said vector memory means, and means for retrieving said vector data from said vector memory means.

6. A system as in Claim 5 wherein said control means include means for associatively addressing specified ones of said polygons according to a specified set of said properties.

7. A system as in Claim 5 wherein said control means include means for sequentially accessing said vector data within said vector memory means.

8. A system as in Claim 7 wherein said control means in¬ clude means for inserting additional vector data into sequential address locations within said vector memory means, beginning at the first-encountered location having no data.

9. A system as in Claim 7 or 8 wherein said control means include means for inserting additional vector data into sequential address locations within said vector memory means at locations immediately following the last data word of one of said polygon representations and further includi means for relocating existing vector data within said vector memory means to make room for said additional vecto data.

10. A system as in Claim 4 wherein said polygon represen- tation represents the first point of said polygon in absolute coordinates and represents subsequent points in relative coordinates, and wherein said system includes preclipper means for converting said relative coordinates into absolute coordinates.

11. A system as in Claim 5 wherein said control means include ring buffer means for modifying said vector data.

12. A system as in Claim 11 wherein said ring buffer mean^'s includes a first ring buffer for storing unmodified data, a second ring buffer for storing modified polygon data and means for determining whether said polygon data should be returned to said vector memory means in modified or unmodi¬ fied form.

13. A system as in Claim 11 wherein said preclipper means include means for circumscribing a rectangle around one of said polygons and means for determining whether the circum¬ scribed rectangle intersects a specified window.

14. A system as in Claim 13 including clipper means for clipping ones of said polygons to fit within a specified window.

15. A system as in Claim 14 wherein said clipper means include means for identifying the one of said polygons that contains the vertex which is closest to a specified point.

16. A system as in Claim 14 wherein said clipper means include means for identifying the one of said polygons that contains the segment which is closest to a specified point.

17. A system as in Claim 14 wherein said clipper means include means for identifying ones of said polygons that are partially contained within a specified window.

18. A system as in Claim 14 wherein- said clipper means include means for identifying ones of said polygons that are wholly contained within a specified window.

19. A system as in Claim 4 including sealer means for translating specified ones of said polygons thereby deter¬ mining the position of the image to be displayed.

20. A system as in Claim 19 including means for scaling specified ones of said polygons thereby determining the size of. the image to be displayed.

21. A system as in Claim 4 including writing means for rasterizing ones of said polygons into said second memory means thereby forming said rasterized data.

22. A system as in Claim 21 wherein said writing means include means for generating raster points in a matrix field thereby representing the location of two-dimensional straight line vectors. ^{• ■* " "} -80-

23. A system as in Claim 22 wherein said second memory means comprises a plurality of memory cells, each cell comprising a plurality of picture elements, and wherein said writing means .includes means for writing multiple raster points to picture elements within a memory cell in a single memory operation.

24. A system as in Claim 23 wherein said memory cell represents a two-dimensional array of picture elements, thereby facilitating rapid rasterization of horizontal, vertical and diagonal vector data.

25. A system as in Claim 24 wherein said writing means_ι includes means for writing additional raster data to ones of said memory cells without adversely affecting any raster data previously stored .within said memory cell and without first having to read said previously stored raster data from said memory cell.

26. A system as in Claim 24 wherein said writing means includes means for simultaneously determining multiple raster points within a memory cell.

27. A system as in Claim 24 including means for inclu¬ sively ORing the data outputs of said picture elements on a column by column basis and means for asserting the data outputs of said picture elements on a row by row basis thereby providing the capability of reading the raster data within said memory cell on a row by row basis.

28. A system as in Claim 3 wherein said reading means in¬ clude edge array means for storing the representation of a grid, means for updating said representation, means for generating the graphics image of said grid from said representation, and means for superimposing said grid graphics image upon the graphics image of said rasterized data.

29. A system as in Claim 28 wherein said reading means include edge array means for storing the representation of a cursor, means for updating said representation, means for generating the graphics image of said cursor from said representation, and means for superimposing said cursor graphics image upon the graphics image of said rasterized data.

30. A graphics display system comprising first memory means for storing vector data representing one or more graphics images, second memory means, means for rasterizing said vector data into said second memory means, thereby forming raster data, means for displaying said images, and processor means for controlling the operation of said first and second memory means, said means for rasterizing and said means for displaying.

31. A graphics display system comprising vector memory means for storing vector data representing one or more graphics images to be displayed, memory update means including means for inserting said vector data into said vector memory means, means for modifying said vector data within said vector memory means and means for retrieving said vector data from said vector memory means, second ^■memory means, means for rasterizing said vector data into said second memory means thereby forming rasterized data, means for displaying said images, and processor means for controlling the operation of said vector and said second memory means, said memory update means, said means for rasterizing and said means for displaying.

32. A graphics display system comprising vector memory means for storing vector data representing one or more graphics images to be displayed, where said vector data represents one or more polygons where each polygon repres¬ entation includes header information specifying the format

i

( _: -- ° --^*_ of said representation, memory update means including mean for inserting said vector data into said vector memory means, means for modifying said vector data within said vector memory means, and means for retrieving said vector data from said vector memory means, clipper means for clipping ones of said polygons and for identifying ones of said polygons by a closest point, by a closest segment, and by partial or complete containment within a window, sealer means for translating and scaling ones of said polygons thereby transforming the image to be displayed, second memory means, writing means for rasterizing the transformed vector data into said second memory means thereby forming raster data, reading means for reading sai rasterized data from said second memory means, monitor mea for displaying said graphics image and processor means for controlling the operation of said system.

33. A graphics image display system comprising vector memory means for storing vector data representing one or more graphics images to be displayed, second memory means, means for rasterizing- said vector data into said second memory means thereby forming rasterized data, said means for rasterizing including writing means for writing the rasterized data into locations into said second memory means-, said writing means including means for generating raster points in a matrix field thereby representing the location of two-dimensional straight line vectors and mean for writing raster points within an m x n memory cell within said second memory means in one operation, and processor means for controlling the operation of said vector memory means, said second memory means and said means for rasterizing.

34. In a graphics display system having vector memory means for storing vector data representing one or more graphic images to be displayed, a memory update circuit comprising means for inserting said vector data into said vector memory means, means for modifying said vector data within said vector memory means, and means for retrieving said vector data from said vector memory means.

35. A circuit as in Claim 34 wherein said. ector data represents one or more polygons and the representation of each polygon includes header information specifying the format of said representation and the properties of said polygons and wherein said control means includes means for associatively addressing specified ones of said polygons according to a specified set of said properties.

36. A circuit as in Claim 35 wherein said control means includes means for sequentially accessing said vector data within said vector memory means.

37. A circuit as in Claim 36 wherein said control means includes means for inserting additional vector data into sequential address locations within ..said vector memory means, beginning at the first encountered location having no data.

38. A circuit as in Claim 35 or 36 wherein said control means, includes means for inserting additional vector data into sequential address locations within said vector memory means at locations immediately following the last data word of said polygon representations and further including means for relocating existing vector data within said vector memory means to make room for said additional vector data.

39. A circuit as in Claim 35 wherein said polygon represen¬ tation represents the first point of said polygon in abso¬ lute coordinates and represents subsequent points in rela- tive coordinates and wherein said system includes preclipper means for converting said relative coordinates into absolute coordinates.

y

. 1

._-

40. A circuit as in Claim 35 wherein said control means in cludes ring buffer means for modifying said vector data.

41. A circuit as in Claim 40 wherein said ring buffer means includes a first ring buffer for storing unmodified data, a second ring buffer for storing modified polygon dat and means for determining whether said polygon data should be returned to said vector memory means in modified or unmodified form.

42. In a graphics display system, a rasterizing circuit comprising means connected to receive vector data represen¬ ting one or more polygons, memory means, and writing means for rasterizing ones of said polygons into said memory mean thereby forming rasterized data.

43. A circuit as in Claim 42 wherein said writing means includes means for generating raster points in a matrix field thereby representing the location of two-dimensional straight line vectors.

44. A circuit as in Claim 43 wherein said memory means comprises a plurality of memory cells, each cell comprising a plurality of picture elements and wherein said writing means includes means for writing multiple raster points to picture elements within a memory cell in a single memory operation.

45. A circuit as in Claim 44 wherein said memory cell represents a two-dimensional array of picture elements, thereby facilitating rapid rasterization of horizontal, vertical and diagonal vector data.

46. A system as in Claim 45 wherein said writing means in¬ cludes means for writing additional raster data to ones of said memory cells without adversely affecting any raster data previously stored within said memory cell and without first having to read said previously stored raster data from said memory cell.

47. A system as in Claim 45 wherein said writing means includes means for simultaneously determining multiple raster points within a memory cell.

48. A system as in Claim 45 including means for inclusive- ly-ORing the data outputs of said picture elements on a column by column basis and means for asserting the data out- puts of said picture elements on a row by row basis thereby providing the capability of reading the raster data within said memory cell on a row by row basis.

49. In a graphics display system, a reading circuit com¬ prising edge array means for storing raster data represent- ing a grid, means for updating the representation, means for generating a graphics image of said grid from said represen¬ tation, and means for superimposing said grid graphics image upon the graphics image of said rasterized data.

50. A circuit as in Claim 49 including means for storing the representation of a cursor, means for updating said representation, means for generating the graphics image of said cursor from said representation and means for super¬ imposing said cursor graphics image upon the graphics image of said rasterized data.

51. In a graphics display system having first and second memory means, the method comprising the steps of storing vector data representing one or more graphic images to be displayed in said first memory means and rasterizing said vector data into said second memory means thereby forming rasterized data.

52. A method as in Claim 51 further including the steps o reading said rasterized data from said second memory means and displaying said rasterized data.

53. A method as in Claim 51 wherein said vector data represents one or more polygons, and wherein the represent ation of each polygon includes header information specifyi the format of said representation and the properties of said polygons, further including the steps of inserting said vector data into said first memory means, modifying said vector data within said first memory means, and retrieving said vector data from said first memory means.

54. A method as in Claim 53 including the steps of assoc¬ iatively addressing specified ones of said polygons accord ing to a specified set of said properties.

55. A method as in Claim 53 including the steps of sequen tially accessing said vector data within said vector memor means.

56. A method as in Claim 55 including the steps of insert ing additional vector data into sequential address loca- tions within said vector memory means, beginning at the first-encountered location having no data.

57. A method as in- Claim 55 including the steps of insert ing additional vector data into sequential address locatio within said vector memory means at locations immediately following the last data word of one of said polygon repre¬ sentations and relocating existing vector data within said vector memory means to make room for said additional vector data.

58. A method as in Claim 53 wherein said polygon repre- sentation represents the first point of said polygon in absolute coordinates and represents subsequent points in relative coordinates, and including the step of converting said relative coordinates into absolute coordinates.

59. A method as in Claim 53 including the steps of storing unmodified data, storing modified polygon data and deter¬ mining whether said polygon data should be returned to said first memory means in modified or unmodified form.

60. A method as in Claim 58 including the steps of circum¬ scribing a rectangle around one of said polygons and deter- mining whether the circumscribed rectangle intersects a specified window.

61. A method as in Claim 60 including the step of clipping ones of said polygons to fit within a specified window.

62. A method as in Claim 61 including the step of identify- ing the one of said polygons that contains the vertex which is closest to a specified point.

63. A method as in Claim 61 including the step of identify¬ ing the one of said polygons that contains the segment which is closest to a specified point.

64. A method as in Claim 61 including the step of identify¬ ing ones of said polygons that are partially contained within a specified window.

65. A method as in Claim 61 including the step of identify¬ ing ones of said polygons that are wholly contained within a specified window.

66. A method as in Claim 53 including the step of trans¬ lating specified ones of said polygons thereby determining the position of the image to be displayed. - S- rr-

67. A method as in Claim 66 including the step of scaling specified ones of said polygons thereby determining the size of the image to be displayed.

68. A method as in Claim 53 including the step of raster- izing ones of said polygons into said second memory means thereby forming said rasterized data.

69. A method as in Claim 68 including the step of genera¬ ting raster points in a matrix field thereby representing the location of two-dimensional straight line vectors.

70. A method as in Claim 69 wherein said second memory

•» means comprises a plurality of memory cells, each cell comprising a plurality of picture elements, and including the step of writing multiple raster points to picture elements within a memory cell in a single memory operation

71. A method as in Claim 70 wherein said memory cell represents a two-dimensional array of picture elements, thereby facilitating rapid rasterization of horizontal, vertical and diagonal vector data, including the step of writing additional raster data to ones of said memory cell without adversely affecting any raster data previously stored within said memory cell and without first having to read said previously stored raster data from said memor cell.

72. A method as in Claim 71 including the step of simul- taneously determining multiple raster points within a memory cell.

73. A method as in Claim 71 including the steps of inclu¬ sively ORing the data outputs of said picture elements on column by column basis and asserting the data outputs of said picture elements on a row by row basis thereby provi-

C ding the capability of reading the raster data within said memory cell on a row by row basis.

74. A method as in Claim 72 including the steps of storing representation of a grid, means for updating said represen- tation, generating the graphics image of said grid from said representation, and superimposing said grid graphics image upon the graphics image of said rasterized data.

75. A method as in Claim 74 including the steps of storing the representation of a cursor, updating said representa- tion, generating the graphics image of said cursor from said representation, and superimposing said cursor graphics image upon the graphics image of said rasterized data.

76. In a graphics display system, the method comprising the steps _.of storing vector data representing one or more graphics images, rasterizing said vector data thereby forming raster data, and displaying said images.

77. In a graphics display system having first and second memory means, the method comprising the steps of storing vector data representing one or more graphics images to be displayed, inserting said vector data into said first 'memory means, modifying said vector data within said first memory means, retrieving said vector data from said first memory means, rasterizing said vector data into said second memory means thereby forming rasterized data, and display- ing said images.

78. In a graphics display system, the method comprising the steps of storing vector data representing one or more graphics images to be displayed, where said vector data represents one or more polygons where each polygon repres- entation includes header information specifying the format of said representation, inserting said vector data into first memory means, modifying said vector data within said first memory means, retrieving said vector data from said vector memory means for clipping ones of said polygons and identifying ones of said polygons by a closest point, by a closest segment and by partial or complete containment within a window, translating and scaling ones of said polygons thereby transforming the image to be displayed, rasterizing the transformed vector data into second memory means thereby forming raster data, reading said rasterized data from said second memory means, and displaying said graphics image.

79. In a graphics image display system, the method com¬ prising the steps of storing vector data representing one or more graphics images to be displayed, rasterizing said vector data into memory means thereby forming rasterized data, writing the rasterized data into locations into said memory means, generating raster points in a matrix field thereby representing the location of two-dimensional straight line vectors and writing raster points within an m x n memory cell within said memory means in one operatio

80. In a graphics display system having vector memory means for storing vector data representing one or more

'graphics images to be displayed, the method comprising the steps of inserting said vector data into said vector data memory means, modifying said vector data within said vecto memory means, and retrieving said vector data from said vector memory means.

81. A method as in Claim 80 wherein said vector data represents one or more polygons and the representation of each polygon includes header information specifying the format of said representation and the properties of said polygons and including the step of associatively addressin specified ones of said polygons according to a specified set of said properties.

82. A method as in Claim 81 including the step of sequen¬ tially accessing said vector data within said vector memory means.

83. A method as in Claim 82 including the step of insert- ing additional vector data into sequential address loca¬ tions within said vector memory means, beginning at the first encountered location having no data.

84. A method as in Claim 81 or 82 including the steps of inserting additional vector data into sequential address locations within said vector memory means at locations immediately following the last data word of said polygo _*n representations and relocating existing vector data within said vector memory means to make room for said additional vector data.

85. A method as in Claim 81 wherein said polygon represen¬ tation represents the first point of said polygon in absolute coordinates and represents subsequent points in relative coordinates and including the step of converting said relative coordinates into absolute coordinates.

86. A method as in Claim 81 including the steps of storing ^'unmodified data, storing modified polygon data and deter¬ mining whether said polygon data should be returned to said vector memory means in modified or unmodified form.

87. In a- graphics display system, the method comprising the steps of receiving vector data representing one or more polygons and rasterizing ones of said polygons into memory means thereby forming rasterized data.

88. A method as in Claim 87 including the step of gener¬ ating raster points in a matrix field thereby representing the location of two-dimensional straight line vectors.

89. A method as in Claim 88 wherein said memory means com prises a plurality of memory cells,, each cell comprising a plurality of picture elements and wherein the e thod includes the step of writing multiple raster points to picture elements within a memory cell in a single memory operation.

90. A method as in Claim 89 wherein said memory cell represents a two-dimensional array of picture elements, thereby facilitating rapid rasterization of horizontal, vertical and diagonal vector data, including the step of writing additional raster data to ones of said memory cell without adversely affecting any raster data previously _* stored within said memory cell and without first having to read said previously stored raster data from said memory cell.

91. A method as in Claim 90 including the step of simul¬ taneously determining multiple raster points within a memory cell.

92. A method as in Claim 90 including the steps of inclus ively ORing the data outputs of said picture elements on a column by column basis and asserting the data outputs of said picture elements on a row by row basis thereby prov¬ iding the capability of reading the raster data within said memory cell on a row by row basis.

93. In a graphics display system, the method comprising the steps of storing raster data representing a grid, updating the representation, generating a graphics image of said grid from said representation, and superimposing said grid graphics image upon the graphics .image of said rasterized data.

94. A method as in Claim 93 including the steps of storin the representation of a cursor, updating said representa¬ tion, generating the graphics image of said cursor from said representation and superimposing said cursor graphics image upon the graphics image of said rasterized data.