Bresenham’s Line Algorithm

Bresenham’s Line Algorithm

Bresenham's line-drawing algorithm uses an iterative scheme. A pixel is plotted at the starting coordinate of the line, and each iteration of the algorithm increments the pixel one unit along the major, or x-axis. The pixel is incremented along the minor, or y-axis, only when a decision variable (based on the slope of the line) changes sign. A key feature of the algorithm is that it requires only integer data and simple arithmetic. This makes the algorithm very efficient and fast.

Bresenham's algorithm determines which of these two pixel locations is nearer to the actual line by calculating the distance from each pixel to the line, and plotting that pixel with the smaller distance. Using the familiar equation of a straight line, y = mx + b, the y value corresponding to xi + 1 is y=m(xi+1) + b

The two distances are then calculated as:

d1 = y- yi

d1= m(xi + 1) + b- yi

d2 = (yi+ 1)- y

d2 = (yi+ 1) - m(xi + 1)- b

and,

d1 - d2 = m(xi+ 1) + b - yi - (yi + 1) + m(xi + 1) + b

d1 - d2 = 2m(xi + 1) - 2yi + 2b - 1

Multiplying this result by the constant dx, defined by the slope of the line m = dy/dx, the equation becomes:

dx(d1-d2)= 2dy(xi)- 2dx(yi) + c

where c is the constant 2dy + 2dxb - dx. Of course, if d2 > d1, then (d1-d2) < 0, or conversely if d1 > d2, then (d1-d2) >0. Therefore, a parameter pi can be defined such that

pi = dx(d1-d2)

                                                             Figure

pi = 2dy(xi) - 2dx(yi) + c

If pi > 0, then d1 > d2 and yi + 1 is chosen such that the next plotted pixel is (xi + 1, yi). Otherwise, if pi < 0, then d2 > d1 and (xi + 1, yi + 1) is plotted. (See Figure3.5 .) Similarly, for the next iteration, pi + 1 can be calculated and compared with zero to determine the next pixel to plot. If pi +1 < 0, then the next plotted pixel is at (xi + 1 + 1, Yi+1); if pi + 1< 0, then the next point is (xi + 1 + 1, yi + 1 + 1). Note that in the equation for

pi + 1, xi + 1 = xi + 1.

pi + 1 = 2dy(xi + 1) - 2dx(yi + 1) + c.

Subtracting pi from pi + 1, we get the recursive equation: pi + 1 = pi + 2dy - 2dx(yi + 1 - yi)

Note that the constant c has conveniently dropped out of the formula. And, if pi < 0 then

yi + 1= yi in the above equation, so that:

pi + 1 = pi + 2dy

or, if pi > 0 then yi + 1 = yi + 1, and

pi + 1 = pi + 2(dy-dx)

To further simplify the iterative algorithm, constants c1 and c2 can be initialized at the beginning of the program such that c1 = 2dy and c2 = 2(dy-dx). Thus, the actual meat of the algorithm is a loop of length dx, containing only a few integer additions and two compares.

Steps for bresenham’s line drawing algorithm

1. Input the two line endpoint & store the left endpoint in (Xo, Yo)

2. Load (Xo, Yo) into the frame buffer that is plotting of first point.

3. Calculate constants dx, dy, 2dy & 2dy – 2dx, & obtain the starting value for the decision parameter as:

P k+1 = Pk + 2dy

Otherwise, the next point to plot is (xk+1, yk +1) & Pk+1 = Pk + 2dy –2dx

4. Repeat step 4 dx times.

DDA Algorithm

DDA Algorithm

Digital Differential Analyzer is a scan conversion line algorithm based on calculating either dy or dx. We sample the line at unit intervals in one coordinate & determine corresponding integer values nearest to the line path for the other coordinate. The algorithm accepts as input the two endpoint pixel positions. Horizontal & vertical differences between the endpoint positions are assigned to parameters dx &dy. The difference with the greater magnitude determines the increment of the parameter steps. Starting with the pixel position (Xa , Ya), we determine the offset needed at each step to generate the next pixel position along the line path. We loop through this process ‘steps’ times. If the magnitude of dx is greater that the magnitude of dy & Xa is less that X_b, the values of the increments in the x & y directions are i & m. It is a faster method of calculating pixel positions. However, the accumulation of round off error in successive additions can cause the calculated pixel positions to draft away from the true line path for long line segments.

Example:  let us consider the algorithm in two cases depending on the slope of the line whether it is > 1 or < 1.

Case 1: slope (m) of line is < 1 (i.e., line 1): In this case to plot the line we have to move the direction of pixel in x by 1 unit every time and then hunt for the pixel value of the y direction which best suits the line and lighten that pixel in order to plot the line. So, in Case 1 i.e., 0 < m < 1 where x is to be increased then by 1 unit every time and proper y is approximated.

                                                     Figure 3.3DDA Line Generation

Case 2: slope (m) of line is > 1 (i.e., line 2) if m > 1 i.e., case of line 2, then the most appropriate strategy would be to move towards the y direction by 1 unit every time and determine the pixel in x direction which best suits the line and get that pixel lightened to plot the line.

So, in Case 2, i.e., (infinity) > m > 1 where y is to be increased by 1 unit every time and proper x is approximated.

DDA or slope method algorithm for line drawing

Step1: compute dx: dx=x2-x1;

Step2: compute dy: dy=y2-y1;

Step3 compute m:m=dy/dx;

Step 4: compute b:b=y1-m*x1;

Step 5: set(x,y) equal to lower left hand endpoint and set x’=largest value of x.if dx<0 then

x=x2,y=y2 and x’=x1.if dx>0 ,then x=x1,y=y1 and x’=x2.

Step 6: Test to determine whether the entire line has been drawn.If x> x’, stop

Step 7: Plot a point at the current(x,y) coordinates.

Step 8: Increment x:x=x+1;

Step 9: compute the next value of y from the equation y=mx+b

Step 10 goto step 6

The drawback of DDA algorithm

Digital differential Analyzer is a scan conversion algorithm based on calculating the differences between the x coordinates and y coordinates. The disadvantage of this algorithm is that the accumulation of the round-off error in successive additions of the floating point increment can cause the calculated pixel positions to drift away from the true line path for long line segments that results in a zigzag line instead of a straight one.

What are the various displays available?

What are the various displays available? Explain with example.

1. Raster scan displays: It is based on television technology. In this system an electron beam is swept across the screen, one row at a time form top to bottom. As the electron beam moves across each row, the beam intensity is turned on & off to create a pattern of illuminated spots. Picture definition is stored in a memory area called frame buffer. This memory area holds the set of intensity values for all the screen points. Stored intensity values are then retrieved from the buffer & plotted on the screen one row at a time. e.g. printers
2. Random Scan displays: Here a CRT has the electron beam directed only to the parts of the screen where a picture is to be drawn Random scan monitors draw a picture one line at a time. e.g.: pen plotter.
3. Color CRT monitors: They display color pictures by using a combination of phosphors that emit different colored light. By combining the emitted light form the different phosphors, a range of colors can be generated.
4. A direct view storage tube stores picture information as a charge distribution just behind the phosphor created screen. Two electron guns are used in a DVST. One, the primary gun, is used to store the picture pattern, the second, the flood gun, maintains the picture display.
5. Flat-panel displays: It refers to a class of video devices that have reduced volume, weighty & power requirements compared to a CRT. They are divided into two categories:

1. Emissive displays: are devices that convert electrical energy into light. e.g. Plasma panels.
2. Non-emissive displays: are devices that convert sunlight or light from some other source into graphics patterns. E.g.: LCD.

Hard Copy Devices

Hard Copy Devices

Hard-copy devices for graphics workstations include standard printers and plotters, in addition to devices for producing slides, transparencies, and film output. Printing methods include dot matrix, laser, ink jet, electrostatic, and electro thermal. Plotter methods include pen plotting and combination printer-plotter devices.

The major factors which control the quality of a printer are individual dot size on the paper and the number of dots per inch. Printers produce output by either impact or nonimpact methods. Impact printer’s press formed character faces against an inked ribbon onto the paper. A line printer is an example of an impact device, with the typefaces mounted on bands, chains, drums, or wheels. Nonimpact printers and plotters use laser techniques, ink-jet sprays, xerographic processes (as used in photocopying machines), electrostatic methods, and electro thermal methods to get images onto paper.

In a laser device, a laser beam creates a charge distribution on a rotating drum coated with a photoelectric material, such as selenium. Toner is applied to the drum and then transferred to paper. Figure 2.10 shows examples of desktop laser printers with a resolution of 360 dots per inch.

Ink-jet methods produce output by squirting ink in horizontal rows across a roll of paper wrapped on a drum. The electrically charged ink stream is deflected by an electric field to produce dot-matrix patterns.