Straight lines are an important building block of computer images. We are familiar with the use of straight lines in graphs, bar and pie charts, engineering drawings, but straight lines are also used to approximate curves. Therein lies the importance of implementing efficient line drawing algorithms for this graphics primitive.
Defn: primitive - "a graphics object that is used so often that it is essential to the creation of images"
What information is associated with the graphics primitive SetPix?
Answer: Coordinates of the pixel (x,y) and the color if using
a color monitor
What about the straight line primitive?
Before discussing the graphics primitives any further, let's take a look at the hardware used in computer graphics. The CRT (cathode ray tube) is the most essential device for computer graphics. Let's consider a black and white CRT as follows:
Phosphors are typically chosen for their color and persistence. Since the display screen is made up of a certain number of pixels, a picture can be achieved by having the beam excite (turn on) a pixel at a particular location or skip this process.
The image of what is being shown on the display screen is held in a structure called the "frame buffer". The frame buffer distinguishes which pixels are to be turned on and which are to be turned off. In the case of a color monitor, color information must also be stored in the frame buffer. Since we will be writing graphics primitive drivers, information about the frame buffer specific to the IBM must be known.
Where are the frame buffers located in the IBM?
Answer: monochrome frame buffer is at location: 0B0000H and the
color frame buffer is at 0B8000H.
Pictorially we then have the following scenario:
The above circuitry works in the following manner:
(1) One byte of frame buffer information contains information
on eight consecutive pixels
(2) At a given byte, the contents of that byte are shifted into
the shift register (in parallel) by the CRT controller
(3) From there, each bit is shifted out serially to the monitor
circuitry (Note: in the above example the first five bits have
been shifted out)
For each eight pixels the frame buffer must be accessed which results in a bottleneck because the main CPU is also accessing this frame buffer to create these pictures. Suppose 256 bits (32 bytes) could be shifted in parallel into a long shift register. This would dramatically reduce the contention problems. This idea has lead to the development of VRAM chips which have long shift registers and are used in conjunction with high resolution graphic displays.
It is important to note that the image must be passed 30 times/second
to maintain a flicker free picture; therefore, animation on a
graphics CRT monitor means producing new frame buffer contents
at very high speed. Several techniques can be used to produce
animation, two of which are:
(1) Work with multiple frame buffers
(2) Use additional memory areas besides the frame buffer to hold
parts of the image such as sprites, cursors, or related objects.
What is the major difference between a TV and a computer? How are the two the same? How are the two different?
The CRT is composed of a certain number of scan lines and the
number of pixels per scan line is fixed for each display setup.
Examples are:
(1) 640x200 B/W
(2) 800x600 color
Problem: How big of a frame buffer do we need for a 640x400 B/W display?
Feel free to read more on CRTs (pp.22-31)
Only starting and ending points are needed for absolute line generating algorithms.
Assumptions:
(1) Endpoints are integral
(2) We are using actual screen coordinates
Two methods exist for drawing straight lines:
(1) Structural - generates all the pixel addresses of the line
before any of the pixels are turned on
(2) Conditional - sets one pixel at a time before the next pixel
is known
Two Structural Methods are of interest:
(1) Bron's Method
(2) Best-Fit Method
eight-connectedness - 2 pixels in a grid that are vertically, horizontally, or diagonally adjacent are said to be eight-connected
How many eight-connected neighbors does a single pixel have and why?
chain code -individual numbers that are sequenced such that each number represents successive pixels on the display screen. Consider the following numbering scheme of a pixel to its eight-connected neighbors:
Problem: What is the chain code for the following line from A to B?
Note1: This chain coding scheme can be used to represent any digital arc, i.e. such as straight or circular
Note2: An interesting observation is that if no uneven substrings are contained in the digital arc, then this implies that the arc is a straight line. Consider two substrings that are equally long. If the sum of the values of each of these substrings differ by more than 1, then the substrings are said to be uneven.
Problem: Give an arbitrary chain code that represents a straight line. Give an arbitrary chain code that does not represent a straight line.
There are three interesting consequences of Note 2 ( in reference
to the chain code) and they are:
(1) No more than two different symbols can occur that differ by
at most 1 including wrap around (so 1 mod 8)
(2) Only the symbol that occurs less frequently is isolated.
(3) The more frequently occurring symbol occurs in runs that differ
at most by 1 lengthwise
Problem: What are examples showing each of these situations?
Note3: Our discussion of straight lines will be limited to those with slopes in the first octant. Everything else can be derived by the use of symmetry.
This particular algorithm is restricted to the first octant omitting 0 degree and 45 degree lines. You are responsible for these border cases. That is, why are there problems with 0 and 45 degrees and what is the fix?
Assume two substrings exist, s1 and s2, that have been loaded with the symbols 0 and 1 respectively . Further, assume that this line is from (0,0) to some arbitrary endpoint (x,y). (s)inv denotes the reverse of a string so (11001)inv = (10011) and + denotes concatenation so 110 + 101 = 110101.
Best fit Algorithm
x = x - y
loop: if(x>y) then
s2 = s1 + (s2)inv
x = x - y
else if(x=y) exit loop
else
s1 = s2 + (s1)inv
y = y - x
goto loop
exit: final chain code = s1 + (s2)inv
print final chain code x or y times since they will be equal
Problem: Draw the line from (0,0) to (9,6) using this algorithm
<Skip Bron's Method pp.34-41>
Several conditional methods for straight line generation exist. We are interested in methods that are computationally easy to compute and do not use expensive operations such as * and /. Remember that conditional methods set the current pixel before the next pixel is known. Once the pixel is plotted, there are a certain set of conditions that are checked to determine where the next pixel is to be set. We will begin by examining some DDA algorithms.
(1) Symmetrical DDA (digital differential analyzer) - generates lines from their differential equations. It is important to note that DDAs can also be used to generate arcs and other curves.
We know that the differential equation of a straight line is Dxf(x)=c or dy/dx=c if a variable y represents f(x). If we replace dy/dx by deltay/deltax (change in y over the change in x) the relation still holds true. The quotient of the increments must be equal to the line's slope (or its derivative). So for example if we have f(x)=3x+5, then Dxf(x)=3, which we know to be the slope of the line also. With this in mind, the DDA works on the principle that given a starting point (x,y), x and y are incremented by small steps proportional to deltax and deltay until we get to the end point in which case the DDA terminates. So in general, given a start point and end point we can generate a line by proceeding as follows:
1) Calculate the derivative
2) Chose incremental values for deltax and deltay
3) Plot the first point (start point)
4) Increment x by deltax
5) Increment y by deltay
6) Do some kind of rounding since the coordinates might not be
integral
7) Plot this pixel
Basically we proceed in this fashion. In general we have:
1) Xn+1 = Xn + deltax
2) Yn+1 = Yn + deltay
3) Plot_pixel(round(Xn+1),round(Yn+1))
Notice that the exact points are the nonrounded points but due to the noninfinite nature of the display, we plot the rounded (integral) points. In the case of an infinite precision display, we could generate a line by incrementing x by some e(deltax) and y by some e(deltay) where e is epsilon and is some small quantity. Visually, we have the following:
In general, the appearance of lines generated by the DDA depends on what value is chosen for epsilon.
(1) Symmetrical DDA: Choose epsilon = 2^n where 2^(n-1) <= max(|deltax|,|deltay|) < 2^n. This then implies that the line length estimate is 2^n.
Problem: Generate a line from point (0,0) to (4,3) using the symmetrical DDA.
(2) Simple DDA - Choose a line length estimate that is equal to the max(deltax,deltay) in such a way that e(deltax) or e(deltay) is of unit magnitude. This implies that one of the counters is simply an increment by 1. That is, if e=1/(max(deltax,deltay)) then either e(deltax)=1 or e(deltay)=1.
procedure simpledda(x1,y1,x2,y2 : integer);
var
length, {maximum line length}
i:integer; {loop counter}
x,y, {x and y coordinate}
xincr,yincr: real; {Dx and Dy}
begin
length := abs(x2-x1);
if(abs(y2-y1)>length)then
length := abs(y2-y1);
xincr := (x2-x1)/length;
yincr := (y2-y1)/length;
x := x1;
y := y1;
for i := 0 to length do
begin
plot_pixel(round(x),round(y));
x := x + xincr;
y := y + yincr;
end;
end;
Problem: Generate a line from (0,0) to (4,3) using the Simple DDA.