EP0229694B1

EP0229694B1 - Vector graphics generator set-up

Info

Publication number: EP0229694B1
Application number: EP19870300126
Authority: EP
Inventors: James Corona; Terence Wallace Lindgren
Original assignee: International Business Machines Corp
Current assignee: International Business Machines Corp
Priority date: 1986-01-17
Filing date: 1987-01-08
Publication date: 1993-07-07
Anticipated expiration: 2007-01-08
Also published as: JPS62165280A; DE3786408T2; CA1263775A; DE3786408D1; EP0229694A2; EP0229694A3

Description

The present invention relates to vector graphics generator set-up.
As an example of a prior art vector generator set up technique, in the Bresenham vector generation, described in J. E. Bresenham, "Algorithm for Computer Control of Digital Plotter", IBM Systems Journal, Volume 4, No. 1, 1965, Pages 25-30, and "Fundamentals of Interactive Computer Graphics, J. T. Foley and Andries Van Dam, Addison Wesley Publishing Company, 1982 at pages 433 to 436, a number of computations are required prior to the start of line generation. This process is called vector generator setup. The present invention provides an improved implementation of a Bresenham vector generator which requires only two clock cycles to perform the setup operation. The prior art Bresenham vector generator setup normally requires either four or five clock cycles. Thus the present invention saves at least fifty percent of the setup time.
According to the present invention, there is provided a graphics vector generator including apparatus for setting-up the generator comprising means for computing values representative of difference functions between Delta Y values and Delta X values for a vector to be drawn, means for storing such computed values, means for storing a sign for each of the difference functions for controlling X Y swap and multiplex operations, swap means for swapping X values and Y values in response to the store sign to present a larger of an X function or a Y function to a control means for controlling a number of iterations in generation of a vector and iteration counter means for controlling a number of iterations in generation of a vector.
From another aspect, the present invention provides a method for setting up a graphics vector generator, comprising: the steps of:
computing values representative of difference functions between Delta Y values and Delta X values for a vector to be drawn;
storing the difference function values;
storing a sign for each of the difference functions for controlling X Y swap and multiplex operations;
swapping X values and Y values in response to the store sign to present a larger of an X function or a Y function to a control means for controlling a number of iterations in generation of a vector; and
controlling a number of iterations in generation of a vector.
The present invention will be described further by way of example with reference to an embodiment thereof as illustrated in the accompanying drawings in which:-

Fig. 1 is a block diagram of a raster graphic system embodying a vector generator according to the present invention;
Fig. 2 is a block diagram of a vector generator employing the set up technique according to the present invention; and
FIG. 3 is a state diagram of a vector generator set up technique in accordance with the present invention.

Consider the raster graphics system in Fig. 1. It consists of the following major components:-

1. System Control Processor;
2. Host Communication Interface Processor;
3. Display Processor;
4. Hardware Rasteriser - Vector Generator;
5. Hardware Character Generator;
6. Video Pixel Memory; and
7. System Memory.

Functions of Major Components

Each of the major components to be described may be implemented by elements of commercially available display systems such as the IBM 5080.

1. System Control Processor

The System Control Processor is a general purpose processor that has master control of the System. The System Control Processor is responsible for servicing all attached Graphics I/O devices
Coordinating the associated processing with the Display Processor
the System Control Processor interfaces with the host via the Host Communication Interface.

2. Host Communication Interface

the Host Communication Interface provides the serial interface of the System to the host.

3. Display Processor

The DP is responsible for executing graphics orders in the Display Storage Program, residing in the system memory and is concerned mainly with the generation of the image that will appear on the Display Monitor. It has the following functions:

Decoding graphics orders and executing non-drawing orders; e.g. book keeping and control.
Performing the transformation and clipping function to the geometric primitives: lines, characters, polygons, etc.
Preparing the following geometric objects for display: lines, characters, markers, filled polygons, by preprocessing and feeding the data to the Vector Generator and the Video Pixel Memory.

4. Vector Generator

The Vector Generator is a Hardware Implementation of the Bresenham Line Generating algorithm, which takes the end points of a vector (line) as input, and generates pixels in the Video Pixel Memory as output for display.

5. Video Pixel Memory

The Video Pixel Memory consists of 8 1k by 1k bit planes, which supports 256 colours simultaneously via colour look-up tables. The image stored here will be displayed in the Monitor.
As shown in Fig. 2, at the heart of vector generator 100 is ALU 110 having bus inputs 106 (left) and 108 (right) from multiplexers 112 and 114 respectively and having a bus output 116 and a sign bit 120 at N indicating SUM<0 when active.
Delta X and delta Y values are input to vector generator 100 on bus 102 which provides a first input to multiplexer 122. During a first time period, multiplexer 122 is enabled by sequence logic of a display controller such as IBM 5080 (not shown) so that the data on bus 102 is fed through absolute magnitude logic 124 which determines the absolute magnitude of the value of either delta X or delta Y, whichever is on bus 102 at that period of time. A sign bit output of multiplexer 122 is also fed to inputs to X sign flip flop 126 or Y sign flip flop 128. The appropriate sign flip flop to be activated by the sign bit output from multiplexer 122 is enabled by the sequencer not shown. The output of absolute magnitude logic 124 is fed on bus 130 to inputs to delta X register 132, delta Y register 134 and left ALU multiplexer 112.
Next, a value for delta Y is placed on bus 102 and is fed through multiplexer 122 where the sign bit is identified and used to activate Y sign flip flop 128. The magnitude of delta Y is then determined by magnitude logic 124 and the absolute magnitude of delta Y is loaded into delta Y register 134.
The delta X output from delta X register 132 is fed on bus 136 to multiplexer 140 and to hard wired two times multiplier 142. The magnitude of delta Y output of delta Y register 134 is fed on bus 138 to a second input of multiplexer 140 and to hard wired two times multiplier 144.
During a first pass, the output of multiplier 142 now represents 2 delta X and the output of multiplier 144 represents 2 delta Y.
During vector generator setup, X less than Y of flip flop 150 is initialised so that X less than Y output 158 is zero, which assumes that delta X is greater than or equal to delta Y. X less than Y line 158 controls swap logic 146 and multiplexer 140. In the initial state, with line 158 equal to zero, there is no swap performed thus the output of multiplier 142 is fed through to a left-most input of multiplexer 114 which is the right-hand multiplexer for ALU 110 and the output of multiplier 144 is fed through swap logic 146 to a right-input of multiplexer 112 which is the left-hand input to ALU 110.
Similarly, the output of multiplexer 140, representing at this time the absolute magnitude of delta X, on bus 152 is fed to a second input of multiplexer 114 and into an input of iteration counter 154. A first computation to be performed by ALU 110 is the operation 2 delta Y minus 2 delta X. The subtraction is controlled by ALU control line 104 from the graphics processor sequencer. The output of the ALU on bus 116 is inputted to RB register 156 which now stores the quantity 2 delta Y minus 2 delta X. Also, as a result this computation, the sign bit of the result which appears at line 120 is stored in the X less than Y flip flop 150 which provides the active control line 158 to swap logic 146 and multiplexer 140.
Line 158 controls the inputs to multiplexer 112 and 114 respectively such that if line 158 is active, 2 delta X is fed to multiplexer 112 and 2 delta Y is fed to multiplexer 114 resulting in an actual computation of 2 delta X minus 2 delta Y rather than 2 delta Y minus 2 delta X.
Of course, the ALU merely subtracts the inputs presented on lines 108 from the inputs presented on lines 106 to achieve the desired result.
In the next cycle, 2 delta Y appearing on lines 106 is fed to the left side of ALU 110 and delta X from multiplexer 140 through multiplexer 114 under the control of the graphics processor sequencer is fed on lines 108 the right side of ALU 110 so that the output on bus 116 is the quantity 2 delta Y minus delta X.
This quantity is fed to RC register 162 where it is stored.
The output 164 of RC register 162 is a third input to multiplexer 114 which feds the right side of ALU 110.
Vector generator setup is complete at this point. During vector generator setup, ALU 110 performs only subtraction operations in each of the two cycles of setup.
The vector generator is in the idle condition state 0 until a start signal is received at which point the system moves to state 1. In state 1, the quantity 2 delta Y minus 2 delta X is calculated by ALU 100 based upon inputs received as described above with reference to Fig. 2 and the value is stored in RB register 156. Also, in state 1 the X less than Y flip flop 150 is set based upon the value of (sum less than zero) line 120. Next, the system unconditionally moves to state 2 at which point a second setup step takes the quantity two delta Y through multiplexer 112 and delta X through multiplexers 140 and 114 and ALU 110 calculates the quantity 2 delta Y minus delta X which is then stored in RC register 162 as the error term. At this point, the iteration counter 154 is set to the value of delta X.
States 1 and 2 as shown in Fig. 3 complete the vector generator setup procedure in accordance with the present invention. States 3 and 4 to be discussed below describe the "normal" Bresenham line generation technique that is known in the prior art. If the (sum less than zero) line is active, the system moves from state 2 to state 3 and the next value of 2 delta Y is added to the error term stored in RC register 162 and the result is put back into RC register 162. Iteration counter 154 is decremented by one and the system may continue to generate pixels in state 3 as long as the sum less than zero line is active and the iteration counter is greater than or equal to zero which indicates that there are more pixels to be drawn along the X axis of the line being drawn with no Y increment.
If the (sum less than zero) line becomes zero for any particular pixel to be drawn, and the iteration counter is not less than zero, the system moves from state 3 to state 4 at which point the absolute value of the quantity stored in RB register 156 is subtracted from the value of the error stored in RC register 162 with the result being stored back in RC register 162. The Y value is incremented and the iteration counter is decreased by one.
If the next pixel also indicates a sum less than zero in active, indicating a further Y coordinate increment, the system loops in state 4 until such Y steps have been completed. When the (sum less than zero) line becomes active again, the system returns control to state 3 and additional pixels are drawn as described above until the iteration counter becomes less than zero at which time the process is terminated and control returns to the idle state zero.
If after the second setup state, state 2, the (sum less zero) line is inactive, indicating a Y increment, then control is passed directly from state 2 to state 4 and the first pixel to be drawn is controlled by state 4 rather than state 2 and the process continues as described above.
The method of the present invention provides a more efficient method for setting up a vector generator by reducing the number of setup states from 4 or 5 in the prior art to the two setup states required by the method and apparatus of the present invention.

Claims

A graphics vector generator including apparatus for setting-up the generator comprising means for computing values representative of difference functions between Delta Y values and Delta X values for a vector to be drawn, means for storing such computed values, means for storing a sign for each of the difference functions for controlling X Y swap and multiplex operations, swap means for swapping X values and Y values in response to the stored sign to present a larger of an X function or a Y function to a control means for controlling a number of iterations in generation of a vector and iteration counter means for controlling a number of iterations in generation of a vector.
A generator as claimed in claim 1, further including means for determining an absolute value for each of the delta X and delta Y values.
A generator as claimed in claim 2, further including means for multiplying the absolute values by a predetermined factor.
A method for setting up a graphics vector generator, comprising: the steps of:
computing values representative of difference functions between Delta Y values and Delta X values for a vector to be drawn;
storing the difference function values;
storing a sign for each of the difference functions for controlling X Y swap and multiplex operations;
swapping X values and Y values in response to the stored sign to present a larger of an X function or a Y function to a control means for controlling a number of iterations in generation of a vector; and
controlling a number of iterations in generation of a vector.
A method as claimed in claim 4, further comprising the step of determining an absolute value for each of the delta X and delta Y values.
A method as claimed in claim 5, further comprising the step of multiplying the absolute values by a predetermined factor.