 |
Description  |
|
|
TECHNICAL FIELD OF THE INVENTION
This invention relates in general to computer graphics, and more
particularly to a Bresenham run slice line draw engine.
BACKGROUND OF THE INVENTION
In order to communicate with a user, a computer must be able to output
information to a display. In a graphics system, the display is defined by
an array of pixels. For example, in a standard-mode VGA (Video Graphics
Adapter) system, the screen is addressed as an array of 640.times.480
pixels. Each pixel on the display may be set to a desired color. The color
of each pixel on the screen is stored in a frame buffer. The colors may be
directly specified in the frame buffer or specified by reference to a
palette which stores color information for a predetermined number of
colors. Typically palettes are used for color depths of 16 or 256 colors.
When larger color depths are used, such as 32K or 16.7M (true color) color
depths, each pixel location in the frame buffer stores data for the RGB
(Red, Blue Green) components of each pixel. The number of pixels which may
be displayed is defined by the graphic subsystem. Typical VGA modes
support 640.times.480, 800.times.600, and 1024.times.768 resolutions. VGA
modes with resolution greater than 640.times.480 are generally referred to
as "Super VGA". The size of the frame buffer is therefore dependent upon
the resolution and color depth of the display.
The speed at which a personal computer operates is dependent upon a number
of factors. Naturally, the speed of the microprocessor has a significant
influence on the speed of operation of the overall computer system. Next
to processor speed, in many cases, the video graphics subsystem has the
most influence on the performance of the overall computer system. This is
particularly true when a graphical user interface, such as MICROSOFT
WINDOWS (by Microsoft Corporation of Redmond, Wash.) is used. In order to
boost performance, most modem day personal computers use either a local
video bus (which has a higher data bandwidth than the main peripheral bus)
and an accelerated graphics card which increases the speed of certain
operations. An accelerated graphics card allows the graphics card to
perform selected graphics operations at high speed, rather than using the
CPU to perform the operation. Hardware acceleration improves the operation
of the computer system in two ways: (1) the CPU no longer needs to perform
low-level graphics operations handled by the graphics card and (2) the
data bandwidth for certain operations is greatly reduced, resulting in
less bus traffic.
In order for acceleration to increase the responsiveness of the system, the
operating environment, such as WINDOWS, must know the capabilities of the
accelerated graphics subsystem. When the operating environment is loaded,
it initiates the loading of a graphics driver, which is a program which
acts as an intermediary between the operating environment and accelerated
graphics hardware (similarly, application software may have their own
drivers to take advantage of acceleration features found in an accelerated
video card). The driver passes parameters to the operating environment
which specify the accelerated capabilities of the graphics subsystem.
Thereafter, when the operating environment (or application) needs to
perform a graphics operation which could benefit from one of the
accelerated capabilities, it passes the necessary data to the driver. The
driver interprets the information from the operating environment,
processes the information and passes data via the bus to the graphics
subsystem. The graphics subsystem then performs the graphics operation by
writing data to its frame buffer.
Many of today's application programs are graphics intensive. For example, a
computer-aided design program, such as AUTOCAD by AutoDesk, Inc.,
Sauseleto, Calif., may spend a substantial amount of time drawing a figure
to the screen. In some cases, even a small change in the drawing will
require the entire drawing to be redrawn. In this case, the ability of the
graphics processor to draw lines quickly becomes of critical importance.
In addition to the use of line drawing by applications, a graphics card's
ability to draw lines may directly affect its other accelerated functions,
such as block transfer of data, since the BLT (Bit Block Transfer) engine
may use the line draw engine to perform the block transfer.
With regard to line drawing, many problems are addressed in an article
"Ambiguity in Incremental Line Rastering", by Jack E. Bresenham, IEEE
CG&A, May, 1987, which is incorporated by reference herein. The Bresenham
article describes problems in drawing a line using an array of pixels,
since lines having real values between two discrete pixels will have to be
approximated using one pixel or the other. A speed improvement on this
technique involves processing a Bresenham line as a number of segments.
This technique is referred to as "run-slice" processing and is described
in Jack E. Bresenham, "Run Length Slices for Incremental Lines", IBM
Technical Disclosure Bulletin 22-8B, January 1980.
In other applications, manipulation of color information is very important.
For example, some applications generate a continuum of colors between two
color values (for a line) or three color values (for a triangular region).
This operation is commonly referred to as "shading." Typically, the
intermediate color values are computed by the CPU, which can significantly
affect the responsiveness of the computer system. On the other hand,
delegating responsibility of shading functions to the graphics card, while
freeing the CPU, can seriously degrade the graphics card's ability to
perform other functions.
Further, many programs, including game software, now make use of "three
dimensional" (3D) graphics, where color manipulation of objects is used to
provide the effect of a three dimensional object on the screen.
Calculation of the 3D color information is processor intensive and
therefore can significantly affect the responsiveness of the computer
system.
While the speed and functionality of graphics cards has been steadily
increasing, the demands of software requires even more graphics power.
Accordingly, a need has arisen in the industry for a graphics processor
which increases the speed at which information is displayed, particularly
in connections with line draws, and performs complex graphical operations
without requiring additional expensive hardware.
SUMMARY OF THE INVENTION
In the present invention, Bresenham lines defined by a plurality of points
each related to neighboring points by either a axial or a diagonal step.
The lines may be drawn in a defined region where a portion of the line
lies outside of the defined region of a display. The line draw engin
receives line information defining the coordinates of first and second
endpoints of the line and determines a point of intersection between the
line and the defined region. Starting at an endpoint outside of the
defined region, the line draw engine generates coordinate information,
responsive to an error term and first and second constants, for points of
the line on a point by point basis until a step is taken in a
predetermined direction inside the defined region. The error term and the
first and second constants are recalculated to generate the remaining
points of the line within the defined region as one or more slices, each
slice formed of a plurality of points.
The present invention provides significant advantages over the prior art.
When drawing a line through a defined region, such as a window, the data
at the edge of the defined region to start the generation of the run slice
line can be quickly generated.
BRIEF DESCRIPTION OF THE DRAWINGS
For a more complete understanding of the present invention, and the
advantages thereof, reference is now made to the following descriptions
taken in conjunction with the accompanying drawings, in which:
FIG. 1 illustrates a block diagram of a computer system;
FIG. 2 illustrates an output of a run-slice line on a computer display;
FIG. 3 illustrates a chart showing the octants used to classify a line;
FIG. 4 illustrates a chart showing the half-octants and classifications for
a line;
FIGS. 5a, 5b and 5c illustate normal Bresenham, Full First and Points First
lines used in the preferred embodiment of the present invention;
FIG. 6 illustrates a flow chart describing overall operation of the line
draw engine with respect to drawing lines using a run slice technique;
FIG. 7 illustrates a line formed of groups of slices;
FIG. 8 illustrates a block diagram of the video controller of FIG. 1;
FIG. 9 illustrates a block diagram of a graphics bank shown in FIG. 8;
FIG. 10 illustrates use of the line draw engine to perform a polygon fill;
FIGS. 11a, 11b and 11c illustrate lines comprising all points, leftmost
points and rightmost points, respectively;
FIG. 12 illustrate a polygon fill using lines with the SKIPFIRST and
SKIPLAST options for the scan lines;
FIG. 13 illustrate a polygon fill using lines with the SKIPFIRST and
SKIPLAST options for the edge lines;
FIG. 14 illustrates a block diagram of the slicer shown in FIG. 8;
FIGS. 15 and 16 illustrate state diagrams describing operation of the
slicer;
FIG. 17 illustrates a line clipped by a window;
FIG. 18 illustrates a flow chart describing drawing of clipped lines using
a combination of normal Bresenham and run-slice techniques;
FIG. 19 illustrates a flow chart describing concurrent generation run-slice
parameters and output from the line draw engine;
FIG. 20 illustrates a flow chart describing concurrent generation repeat
count parameters and output from the line draw engine;
FIG. 21 illustrates a chart showing operation of the serial divider to
calculate partial repeat counts.
FIG. 22a illustrates an exemplary source line;
FIG. 22b illustrates an exemplary destination for a stretch operation using
the colors of the source line of FIG. 22a;
FIG. 22c illustrates an exemplary destination for a replicated stretch
operation using the colors of the source line of FIG. 22a;
FIG. 22d illustrates an exemplary destination for a shrink operation using
the colors of the source line of FIG. 22a;
FIG. 23 illustrates an exemplary stretch line used in the stretching of the
source line of FIG. 22a to the destination line of FIG. 22b;
FIGS. 24a and 24b illustrate stretch and destination lines, respectively,
illustrating a stretch operation in conjunction with the source line of
FIG. 22a;
FIG. 25 illustrates a stretch line used in a replicated stretch operation
from the source line of FIG. 22a to the destination line of FIG. 22c;
FIGS. 26a and 26b illustrate stretch and destination lines, respectively,
illustrating a replicated stretch operation in conjunction with the source
line of FIG. 22a;
FIG. 27a-27c illustrate exemplary source, destination and stretch lines
used in a shrink operation;
FIGS. 27d-27e illustrate exemplary destination and stretch lines used in a
second shrink operation;
FIG. 28 illustrates a flow chart describing the steps of a stretch or
shrink operation;
FIG. 29a-29c illustrate of R, G and B color lines used for shading;
FIG. 30 illustrates a flow chart describing a shade operation;
FIG. 31 illustrates exemplary R, G, B, and Y lines used in a shade
operation;
FIG. 32 is a flow chart describing a shade operation; and
FIGS. 33a-33c illustrate the processing YRGB lines for shading.
DETAILED DESCRIPTION OF THE INVENTION
SYSTEM OVERVIEW
FIG. 1 illustrates a block diagram of a computer system 20. The computer
system 20 includes a microprocessor (or central processing unit) 22,
coupled to memory 24, a local bus 26 and a main peripheral bus 28. A
graphics controller 30 and I/O circuitry 32 are coupled to the local bus
26. A display 34 is coupled to the graphics controller 30. A hard disk 36
and floppy disk 38 are coupled to the I/O circuitry 32. A plurality of
peripherals 40 are coupled to the main bus 28. A keyboard 42 is coupled to
the CPU 22 through keyboard interface 45. A printer 43 is also coupled to
I/O circuitry 32. The computer system 20 of FIG. 2 is an exemplary
embodiment for a high performance computer system. Many computer systems
vary from the architecture shown in FIG. 1, and the invention described
herein would apply to various architectures. Further, the architecture
shown in FIG. 1 is a basic architecture and many of the details have been
removed for illustrative purposes.
VIDEO CONTROLLER OPERATION
Bresenham Lines
Importantly, the graphics controller 30 uses a run-slice line draw engine
to greatly improve the performance of certain graphics functions,
described in greater detail below. A run-slice line draw engine draws
Bresenham lines at high speed. The method of drawing a Bresenham line is
described in detail in J. E. Bresenham, "Algorithm for Computer Control of
Digital Plotter," IBM Systems Journal, Vol. 4, No. 1 (1965), pp. 25-30,
which is incorporated by reference herein. The technique for drawing a
Bresenham line on a point-by-point basis (i.e., not using run-slice
techniques) is widely used throughout the industry. FIG. 2 illustrates a
Bresenham line drawn between arbitrary endpoints X.sub.0, Y.sub.0 and
X.sub.1, Y.sub.1. Given the endpoints of a line, five variables are
computed:
DX=X.sub.1 -X.sub.0
DY=Y.sub.1 -Y.sub.0
K1=2*DY-2*DX
K2=2*DY
E.sub.0 =2*DY-DX
The following pseudo-code describes the process for selecting points
between the endpoints to display the line:
##EQU1##
The above technique is described for line having a slope which falls in the
first octant (see FIG. 3). By convention, the definition is described for
first octant lines and the technique can be applied to lines in the other
octants as is well known in the art (and described in the Bresenham
article cited above).
As can be see from FIG. 2 and the pseudo-code above, the Bresenham
technique makes a decision at each point as to whether the next point of
the line will be axial (i.e., along the major axis) or diagonal (i.e.,
incremented along both the major and minor axes). It should be noted that
the pseudo-code described above results in an axial step if E=0.
Alternatively, a diagonal step could be taken when E=0.
For an arbitrary point (XY), the true error between the point (X,Y) and a
line between (X.sub.0, Y.sub.0) to (X.sub.1, Y.sub.1) can be given by the
expression:
F(X,Y)=2DY*(X-X.sub.0)-2DX*(Y-Y.sub.0).
True error is proportional to the distance between (X,Y) and the line and
has positive values on one side of the line and negative values on the
other side of the line. True error is exactly zero when the point X,Y is
on the line. The Bresenham error, E, at point (X,Y) is equal to the true
error at point (X+1, Y+1/2). When Bresenham error is zero, the next axial
and diagonal points are equally distanced from the line and the true error
is at its maximum. By adding either K1 or K2 to the previously accumulated
error, the error term indicates which move (axial or diagonal) is
appropriate.
RUN SLICE GENERAL OPERATION
While the Bresenham technique described above is popular because a line can
be defined at high speed using only addition and substraction to determine
the Bresenham error, it is known that the Bresenham line can be computed
by reference to constant direction slices of either solely axial or solely
diagonal moves. See J. E. Bresenham, D. C. Grice and S. C. Pi, "Run Length
Slices For Incremental Lines," IBM Systems Journal, Vol. 22, No. 8B
(January 1980), which is incorporated by reference herein. As shown in
FIG. 2, two full slices 50 are shown. In this case, the slices 50 are
axial slices, i.e., all points in the slice are along the major axis, and
diagonal corrections 52 are made between the slices 50.
Accordingly, a line can be classified using one of sixteen codes, depending
upon the half octant in which the slope of the line lies, as shown in FIG.
4. A line in the first half-octant (labeled "0000") has axial slices 50
aligned with the positive X axis, with diagonal corrections. A line in the
second half-octant (labeled "1000") has diagonal slices 50 at a 45.degree.
angle with corrections along the positive X axis. A line in the third
half-octant (labeled "1100") has diagonal slices at a 45.degree. angle
with corrections along the positive Y axis. A line in the fourth
half-octant (labeled "0100") has slices along the positive Y axis with
diagonal corrections at a 45.degree. angle, and so on. Each of the sixteen
line codes describe a line which is unique in the direction of the slices
50 and the direction of the corrections 52. In the preferred embodiment,
line is assigned a half octant code as shown in Table I.
TABLE I
______________________________________
Half Octant Code
______________________________________
Bit 0 = 0 if (DX>=0) and = 1 otherwise
Bit 1 = 0 if (DY>=0) and = 1 otherwise
Bit 2 = 0 if .vertline.DX.vertline.>=.vertline.DY.vertline. and = 1
otherwise
Bit 3 = 0 if (2.vertline.DY.vertline.<=.vertline.DX.vertline.) or
(2.vertline.DX.vertline.<=.vertline.DY.vertline.) =
1 otherwise
______________________________________
Also in the preferred embodiment, all lines are transformed into the first
half octant (code ="0000"). The transformation generates DX and DY for the
line in the first half octant. These lines retain their original octant
code and original endpoints as described in greater detail hereinbelow.
Also in the preferred embodiment, the video controller 30 is operable to
draw three types of Bresenham lines using run-slice technique. The first
line type, shown in FIG. 5a, is the normal Bresenham line. The second line
type is a "Full First" line, shown in FIG. 5b. The third type of line, a
"Points First" line, is shown in FIG. 5c.
The normal Bresenham line shown in FIG. 5a uses the normal Bresenham
run-slice algorithm to draw lines with pixels closest to the ideal line.
The Full First line shown in FIG. 5b draws a line between the endpoints in
which all pixels are either on the line or to the right of the line (for
lines in the first half octant). In a Points First line, all pixels are
either on or to the left of the ideal line (for a first half octant line).
FIG. 6 illustrates a flow chart describing the overall operation of the
video controller 30 with regard to run-slice line drawing. In block 60,
the endpoints of the line are received. Alteratively, other information,
such as starting point, DX and DY could be used to define the ideal line.
In block 62, the line is transformed to the first half octant. In block
64, the slice lengths are generated for the first slice, intermediate
slices, and last slice, based on the endpoints and line type (i.e.,
Bresenham, Full First or Points First). In block 66, the coordinates for
each slice, and optionally, all points of the slice, are generated based
on the starting point of the line and the slice length of each line. A
more detailed explanation of the generation of the run-slice line
information is set forth below.
Many display operations can be simplified into multiple lines. For example,
to draw a solid polygon, lines representing the perimeter of the polygon
can be calculated to determine the endpoints of a plurality horizontal
lines which are drawn to create the filled polygon. Only the horizontal
lines are actually written to the frame buffer.
RUN SLICE CALCULATIONS
Tables II, III and IV set forth the determination of the number of pixels
of the slices for Bresenham, Full First and Points First lines,
respectively. In these Tables, Q=(DX/DY) and R=MOD(DX,DY), i.e., R is the
integer remainder of the DX/DY division.
NORMAL BRESENHAM LINES
For a normal Bresenham run-slice, the number of pixels and errors shown in
TABLE II can be determined as follows:
TABLE II
__________________________________________________________________________
RUN-SLICE COMPUTATIONS
NORMAL BRESENHAM LINE
Slice Slice Length Error
__________________________________________________________________________
Axial When E = 0
First Run-Slice
Int(Q/2) + 1 E.sub.0 = 2DY - 3R if Q even
E.sub.0 = DY - 3R if Q odd
Mid Run-Slices
Q if E < 0 E = E + 2R
Q + 1 if E > = 0 E = E + 2R - 2DY
Last Run-Slice
Int(Q/2) if Q even and R = 0
N/A
Int(Q/2) + 1 if Q odd or R <> 0
Diagonal When E = 0
First Run-Slice
Int(Q/2) if Q even and R = 0
E.sub.0 = 0
Int(Q/2) if Q odd or R <> 0
E.sub.0 = 2DY - 3R if Q even and
R <> 0
E.sub.0 = DY - 3R if Q odd
Mid Run-Slice
Q if E < = 0.sub.1
E = E + 2R
Q + 1 if E > 0 E = E + 2R - 2DY
Last Run Slice
Int (Q/2) + 1 N/A
__________________________________________________________________________
First Slice
Assuming a normal Bresenham line, stepping axially when the Bresenham error
equals zero, the number of pixels of the first segment can be found at the
smallest integer end where the error switches from negative or "0" to a
positive number, since the Bresenham error is negative or "0" for all
points in the first slice, except the last point.
##EQU2##
R/2DY-1 has values from -1 to -0.5 (excluding -0.5). In either case,
smallest integer n is
n=Q/2
Including the first pixel, the number of pixels for the first segment is
L.sub.0 =Q/2+1
Alternatively, if for a Bresenham line in which a diagonal step is taken
when the Bresenham error equals zero, the number of pixels for the first
slice can be computed as follows:
##EQU3##
Mid Slices
To determine the number of pixels of the mid run-slices, suppose E is the
Bresenham error term at the last point on a segment, the next segment
length is the smallest n satisfying
E.sub.i+1 =E.sub.i +2nDY-2DX.gtoreq.0 (one diagonal step and (n-1) axial
steps) n.gtoreq.(2DX-E.sub.i)/2DY
Since DX=Q*DY+R
n.gtoreq.Q+(2R-E.sub.i)/2DY
Minimum integer n or length of the next segment is
Q when 2R-E.sub.i <0
Q=1 when 2R-E.sub.i .gtoreq.0
Assuming the next segment length is Q and calculating the error at last
pixel of next segment, if it is positive, it is indeed the last pixel, if
it is negative, it is not the last pixel, and the next segment length is
Q+1.
##EQU4##
If E.sub.i+1 >0, the next segment length is Q and the Bresenham error of
the last pixel of the next segment is
E.sub.i+2 =E.sub.i+1 -2R if E.sub.i+1 >0
If E.sub.i+1 .ltoreq.0, the next segment length is Q+1 and the Bresenham
error at the last pixel of the next segment is adjusted to be
E.sub.i+2 =E.sub.i+1 2DY
Hence the Bresenham error of the last pixel of the next segment is
E.sub.i+2 =E.sub.i+1 +2DY-2R if E.sub.i+1 .ltoreq.0
Last Slice
To find the last run-slice length, the largest integer n is found which
satisfies
##EQU5##
Since DX=Q*DY+R
n<1+Q/2+R/2DY
The last segment length is
##EQU6##
The length of the last run-slice when a diagonal step is taken when the
Bresenham error equals zero can be determined as follows
n.ltoreq.1+Q/2+R/2DY
L=Int(Q/2)+1
Initial run-slice estimated Bresenham error at last pixel of the 2nd
segment can be computed as follows:
##EQU7##
For Bresenham lines with a diagonal step when the Bresenham error equals
zero, the initial run-slice error is determined as follows:
When R=0, Q even
##EQU8##
When R<>0 or Q odd
##EQU9##
FULL FIRST LINES
For Full First lines, the line lengths and errors can be computed as
follows:
TABLE III
______________________________________
RUN SLICE CALCULATIONS
FULL FIRST LINE
Slice Slice Length Error
______________________________________
First Run Slice
Q if R = 0 E.sub.0 = 0
Q + 1 if R <> 0
E.sub.0 = 4R - 2DY
Mid Run-Slices
Q if E <= 0 E = E + 2R
Q + 1 if E > 0
E = E + 2R - 2DY
Last Run Slice
1 N/A
______________________________________
First Slice
Since the starting point is on the line, it is the start of a slice n axial
steps are taken until the true error of the point diagonally above (this
point is the start of the next slice) is positive or zero (crossing the
ideal line).
##EQU10##
Initial slice length is (including first pixel)
##EQU11##
Initial error is the true error of the diagonal point above the last point
of the 2nd slice (or beginning of the 3rd slice)
##EQU12##
Mid slices
E.sub.i is the true error at the beginning of a slice, Q-1 axial steps is
taken, the error at the diagonal point from this point is
E.sub.i+1 =E.sub.i +2*(Q-1)*DY-2DX+2DY
E.sub.i+1 =E.sub.i +2*(Q-1)*DY-2*Q*DY-2R+2DY
E.sub.i+1 =E.sub.i -2R
If E.sub.i+1 .gtoreq.0, the diagonal point crosses the ideal line and the
slice length is
L=Q
E.sub.i+1 =E.sub.i -2R
If E.sub.i+1 <0, the diagonal point has not crossed the ideal line and the
slice length is
L=Q+1
E.sub.i+1 =E.sub.i -2R+2DY
Note that the special initial slice is not necessary if the first error
term is calculated as
E.sub.0 =-2R
and the subsequent slice formula is used.
This would give the initial length of Q if R=0 and the next error of E=0,
initial length of Q+1 if R<>0 and next error of E=2DY-4R.
Last slice
Since the ending point is exactly on the line, it is the start of the last
slice and also the end and hence the length is
L=1
POINTS FIRST LINES
For Points First lines, the lengths and errors can be computed as follows:
TABLE IV
______________________________________
RUN SLICE CALCULATIONS
POINTS FIRST LINE
Slice Slice Length Error
______________________________________
First Run Slice
1 E.sub.0 = 2R - 2DY
Mid Run Slices
Q if <0 E = E+2R
Q+1 if E>=0 E = E+2R-2DY
Last Run Slice
Q N/A
______________________________________
First slice
The starting point is exactly on the line, hence it is the last point of
the slice, so the first slice length is
L.sub.0 =1
Initial error is the true error of the axial point next to the last point
of the 2nd slice (or point below the beginning of the 3rd slice)
##EQU13##
Mid Slices
E.sub.i is the true error at the axial point next to the last point of a
slice, a minor step and Q subsequent axial steps is taken, the error at
the point is
E.sub.i+1 =E.sub.i -2DX+2*Q*DY
E.sub.i+1 =E.sub.i -2*Q*DY-2R+2*Q*DY
E.sub.i+1 =E.sub.i -2R
If E.sub.i+1 >0, this point is the axial point next to the last point of
the next slice and hence the next slice length is
L=Q
E.sub.i+1 =E.sub.i -2R
If E.sub.i+1 .ltoreq.0, this point is the last point of the next slice and
hence the next slice length is
L=Q+1
E.sub.i+1 =E.sub.i -2R+2DY
Last Slice
Since the ending point is exactly on the line, it is the end point of the
last slice, and the formula for subsequent slices above should apply for
the last slice (the error of the axial point next to the ending point is
2DY, so the last slice length should be Q).
REPEAT COUNTS
As shown in FIG. 7, each line can be defined as a first slice 68, and last
slice 70 and one or more groups 72 of mid slices 50 followed by a single
slice 73. Each group 72 of mid slices 50 comprises either (1) one or more
slices of length Q, followed by a single slice of length Q+1 or (2) one or
more slices of length Q+1, followed by a single slice of length Q. The
number of liked-size slices in a group is defined herein as RC. As shown
in FIG. 7, RC=4, since each group 72 has four slices of length Q followed
by a single slice of length Q+1.
The like-size slices will have a length as defined above. For example, with
reference to Table II for normal Bresenham lines, if E<0, the group 72
will include one or more slices of length Q, followed by a slice of length
Q+1. If E>0, the group 72 will include one or more slices of length Q+1,
followed by a slice of length Q. If E=0, the slice length of the slices in
group 72 is Q if a diagonal is step is taken when E=0 or Q+1 if an axial
step is taken when E=0.
To determine the repeat count, the error at the last pixel of the previous
slice, E, is divided by either K1 (if E<0) or K2 (if E>0), where K1 is set
to 2*R and K2 is set to 2*R-2*DY to determine the point at which E will
change signs. Hence, to compute the repeat count, RC=abs(int(E/K))+1,
where K=K1 if E<0 and K=K2 if E>0, except in the following cases. If E=0,
RC is set to one. In the event that mod(E/K)=0 (i.e., the division E/K has
a remainder of zero), then RC=abs(int(E/K)) if E<0 and the line is being
drawn with an axial step when E=0 or if E>0 and the line is being drawn
with a diagonal step when E=0.
After the group 72 of RC slices, the error, E, is updated to E=E+RC*K,
where K=K1 if E<0 and K=K2 if E>0. If E=0, K=K1 if an axial step is taken
when E=0 or K=K2 if a diagonal step is taken when E=0. The new error
forces the next slice to have a repeat count of one and a length as
described above.
The use of repeat counts can greatly increase the speed in generating a
line. After calculating Q and RC and updating E, the slice information for
a plurality of slices may be known without further calculations.
GRAPHICS CONTROLLER HARDWARE OVERVIEW
Referring now to FIG. 8, a block diagram illustrates the major units of
graphics controller 30. In graphics controller 30, line draw engine 100 is
connected to host interface 102 and frame buffer 104.
In operation, the line draw engine 100 communicates with the system of FIG.
1 through host interface 102. The host interface sends drawing commands
and data, such as data to define a line, to command controller 106. The
command controller 106 decodes instructions and data received from the
host interface to draw lines. As described below, the command controller
includes a polygon decomposer which decomposes a polygon into edge lines
for determining endpoints for fill lines. In the preferred embodiment, the
command controller 106 also has the capability of decomposing text to
lines.
Command controller 106 may receive (1) the coordinates of the endpoints of
a line or (2) the coordinates of one endpoint and DX and DY to define a
line. The line information may also come from other units in line draw
engine 100, such as the dicer 122. Once received, the command controller
106 generates configuration information which indicates how to process
each line, where the line's endpoints are located and whether the line is
"active" (ready for an operation). The configurations are programmable to
ensure that the line draw engine architecture is flexible. In the
preferred embodiment, the line draw engine separately stores configuration
data for a plurality of lines which it processes concurrently. For
example, configuration information for sixteen lines could be stored in
various locations throughout the line draw engine 100. Each unit then
arbitrates between the available lines to determine which is ready for
processing, typically in a round-robin fashion.
During an operation, the points of a line are stored in the points
controllers points table. When another unit of the line draw engine 100
needs a point, the unit requests the point from the points controller 110.
The points controller arbitrates requests using a round-robin scheme and
collects the points from the other units, such as the command points
memory 108 and the command controller 106. When the requested data is
available, the points controller delivers the data and acknowledges the
associated requester. If points controller 110 is accessing data for a
request, and a new request for the same data is made, points controller
110 answers the first request, but refuses the second request in order to
keep proper track of point transactions.
The line draw engine 100 further includes at least one graphics bank 112
and optionally comprises multiple graphics banks 112 shown in FIG. 7 as
bank0, bank1, . . . bankn. To reduce hardware, only a certain number of
banks are implemented and are shared to service all lines. The number of
banks is selected to provide sufficient performance for frequently used
operations. Each bank is identical and has one slicer and one or more
dicers (two dicers are shown in the embodiment of FIG. 9) that output
points for slices. One of the graphics banks 112 is described in further
detail below with reference to FIG. 8. For ease of description, the
illustrated implementation uses a single graphics bank. At the completion
of an operation, graphics bank 112 either indicates that the points of a
slice are to be drawn by marking a data register or indicates that the
points of the slice are to be used in another operation (e.g., as
endpoints for fill lines).
Scanner 114 constantly scans graphics bank 112 for the slices to be drawn.
The scanner retrieves the points of the slices and writes the address of
the points in frame buffer 104. Scanner 114 also retrieves necessary data
to facilitate a scan operation corresponding to the point such as RGB
values, scan length and pitch. In the present embodiment, the scanner can
perform operations on four simultaneous slices by allocating each slice to
a memory channel buffer. The necessary data to facilitate a memory scan
operation are also allocated to the memory channel buffer. As the memory
channels become ready to be executed, Scanner 114 arbitrates these
channels in a round robin fashion. The scanner can store one slice from a
multiple number of slices of a line before the other slices are calculated
or, in another embodiment, store a partial slice while the length of the
slice is being calculated. Thus, information on partial slices can be
stored in the frame buffer 104 and displayed during calculation of a slice
length to increase the speed of the line draw engine 100.
The memory controller 115 takes the address and pixel data from the scanner
and generates the signal to read and write to the frame buffer 104.
The line draw engine 100 also includes VMC Interface 116 and VGA/CTRC 118.
VMC Interface 116 allows other subsystems, such as a full-motion video
subsystem to access the frame buffer 104. VGA/CTRC handles VGA commands
for DOS and text mode.
FIG. 9 illustrates graphics bank 112 in more detail. Each of the multiple
graphics banks 112 can be identical to the one depicted in FIG. 9.
Graphics bank 112 comprises a slicer 120 and a dicer 122.
The slicer 120 generates slice lengths and slice length repeat counts for a
line, as described above. The slicer 120 is illustrated in more detail
with reference to | | |
