  In this article, we will now look into the line drawing algortihms in graphics system used in CAD/CAM systems. This is useful for people preparing for GATE Mechanical Engineering, UPSC exams. The purpose of a graphics system is to make programming easier for the user. In this article, we will mainly discuss about the raster scan technology behind computer graphics which makes use of special procedures to generate the display.

The most common type of computer output device which is capable of displaying a graphical output is the raster scan cathode ray tube (CRT). The CRT raster display is considered a matrix of discrete finite area cells (pixels) each of which can be made bright. These pixels cannot be used to draw a straight line from one point to another as these pixels do not represent a mathematical point. The process of determining which pixels provide the best approximation to achieve the desired line is called rasterisation. When rasterisation is combined with the process of generating the picture in scan line order, the process is called scan conversion. Scan conversion of a point involves illuminating the pixel that contains the point.

Refer the figure below for illustration. The device coordinate points (2.5, 2.75) and (2.75, 2.25) would both be represented by pixel (3, 3). In general the pixel is represented by [INY(x), INT(y)]. The process of turning on the pixels for a line segment is called vector generation. If the end points of the line segment are known then there are many methods to select the pixels between the endpoints.

Line Drawing Algorithms

The main design criteria for line drawing displays are as follows:

1. Lines should appear straight.
2. Lines should start and end accurately.
3. Lines should have constant brightness along their length.
4. Displayed lines should be independent of the line length and orientation.
5. Lines should be drawn rapidly.

We will now discuss the two line drawing algorithms:

1) DDA Algorithm

The digital differential analyser generates lines from their differential equations. The DDA works on the principle that x and y are simultaneously incremented by small steps proportional to the first derivates of x and y. The governing differential equation for a straight line shown in the figure above is or The solution of the finite difference approximation can be written as,  Where and are the end points of the required straight line and is the initial value for any given step along the line.

For simple DDA algorithm, either dx or dy, which ever is larger, is chosen as one raster unit. Check out the DDA algorithm below which works everywhere:

digital differential algorithm (DDA)

// The line end points are and assume not equal //

Integer is the integer function.
// For example (-6.5) = -7 rather than -6 //

Sign returns -1, 0, 1 for arguments < 0, =0, >0, respectively

//Approximate the line length//

if abs (x2-x1)>abs (y2-y1) then

length = abs (x2-x1)

else

length = abs (y2-y1)

end if

// Select the larger of or to be one raster unit//  // round the values rather than truncate, so that centre pixel addressin is handles correctly//  begin main loop

i=1

while (if length()

setpixel (integer (x), integer (y))   end while

finish

with the above algorithm try the below given question.

Example: The end points of a line are (0,0) and (4,4). Use the DDA algorithm to rasterize the line.

2) Bresenham's Algorithm

This is an efficient method for scan converting a straight line which uses only integer addition, subtraction and multiplication by 2. The computer can perform the operations of integer addition and subtraction very rapidly. The computer is also time-efficient when performing integer multiplication and division by powers of 2.

The algorithm seeks to select the optimum raster locations that reprsent a straight line. The algorithm increments by one unit in either x or y depending on the slope of the line. The increment in the other variable, is either zero or one and is determined by examining the distance between the actual line and the nearest grid location.

This algorithm identifies a decision algorithm:  when , the closest pixel in the raster will be the pixel below the true line. Conversely when the , the pixel immediately above the true line is the closest.

Continuing the short notes series for Mechanical engineers, in the next article we will look at Mid Point circle algorithm.