Note: Descriptions are shown in the official language in which they were submitted.
~.2fi3775
GRAPHICS VECTOR GENERATOR SETUP TECHNIQUE
BACKGROUND OF THE INVENTION
1. Field of the In~ention
The present invention relates to information
handling systems and more particularly to information
handling systems including method and apparatus for
reducing set up overhead in a vector generator of a
graphics display system.
2. Description of the Prior Art
The following is 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-30J 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
describes 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 required
either four or five clock cycles. Thus the present
* Registered trade mark
KI986-001 - 1 -
~,Zfi377~i
invention saves at least fifty percent of the setup
time.
SU~ ARY OF THE INVENTION
Therefore, it is an object of the present
invention to setup a graphics vector generator by
apparatus and method including 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 functions; means for
storing a sign of said difference functions for
controlling X, Y, swap and multiplex operations; X, Y,
swap means for swapping X values and Y values in
response to said sign storage 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.
It is a further object of the present invention to
setup a graphics vector generator as above by apparatus
and method further including means for determining an
absolute value for each of said delta X and delta Y
values.
It is yet another object of the present invention
to setup a graphics vector generator as above by
apparatus and method further including means for
RI986-001 - 2 -
1;~63~7S
multiplying said absolute values by a predetermined
factor.
The foregoing and other objects, features and
advantages of the invent~on will be apparent from the
S more particular description of the preferred
embodiments of the invention, as illustrated in the
accompanying drawing.
BRIEF DESCRIPTION OF TB DRAWING
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.
FIG. 3 is a state diagram of a vector generator
set up technique in accordance with the present
invention.
In the drawing, like elements are designated with
similar reference numbers, and identical elements in
different specific embodiments are designated by
identical reference numbers.
KI986-001 - 3 -
1263775
DESCRIPTION OF PREFERRED ENBODI?~NTS OF THE INVE~TION
A RASTER GRAPHICS SYSTEM
Consider the raster graphics system in Fig. 1.
It consists of the following major compone~lts:
'1. System Control Processor
2. Host Communication Interface Processor
3. Display Processor
4. Hardware Rasterizer - Vector Generator
5. Hardware Character Generator
6. Video Pixel Memory
7. System Memory
KI986-001 - 4 -
lZfi377.~i
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 S080 Graphics System.
l. System Control Processor
The System Control Processor is a general
~ purpose processor that has master controi of
the System. The System Control Processor is
- responsible for servicing all attached Graphics
1 I/0 devices
Coordinating the associated processing with the
Display Processor
the System Control Processor interfaces with
the host via Host Communication Interface
2; Host Communication Interface
the ~ost Communication Interface provides the
serial interface of the System to the host.
3. Display Processor
KI986-001 . - 5 ~ `~ ~`
.
. , , -. .;
12fi3775
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 Video Pixel Memory
4. Vector generator
Vector generator is a Hardware Implementation of
the Brssenham 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.
RI986-001 - 6 -
12fi377.~;
5. Video Pixel Memory
Video Pixel Memory consists of 8 1~ by lk bit
planes, which supports 256 colors simultaneously
via color look-up tables. The image stored here
will be displayed in the ~lonitor.
PREFERRED E~IBODI~JENT OF THE INV~:NTION
The present invention is in a technique for
efficiently performing Vector Generator set up and
will be described in more detail with reference to
FIG.s 2 and 3.
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
of delta Y appearing on bus 102 at any period of
time. A sign bit output of multiplexer 122 is also
KI986-001 - 7 -
S3775
fed to inputs to X sign flip flop 126 and Y sign
flip flop 128. The appropriate sign flip flop to
be activated by the sign bit output from
multiplexer 122 is ~nabled by the sequencer not
S 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 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 a~d the output of
multiplier 144 represents 2 delta Y.
During vector generator setup, X less than Y
of flip flop 150 is initialized so that X less than
KI986-001 - 8 -
1 ~fi37~5
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 initia~ 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
r 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 1;6 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
KI986-001 - 9 -
~.2q~3775
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
iO 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
i 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 lOB 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
KI986-001 - 10 -
1263775
performs only subtraction operations in each of the
two cycles of setup.
OPERATION
The operation ~f the setup technique according
to the present invention, will now be described
with reference to the state diagram shown in Fig.
3.
The vector generator is in the idle condition
state O until a start signal is received at which
~ point the system moves to state l.
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
ths 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 l and 2 as shown in Fig. 3 complete the
vector generator setup procedure in accordance with
KI986-001 - 11 -
~3775
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 (~um 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.
KI986-001 - 12 -
3~ZÇi3775
If the next pixel also indicates a sum less
than æero 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 dlrectly f~om
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.
Thus, while the invention has been described
with reference to preferred embodiments thereof, it
will be understood by those skilled in the art that
KI986-001 - 13 -
i3775
various changes in form and details may be made
without departing from the scope of the invention.
KI986-001 - 14 -
