Page 48 - DCAP504_Computer Graphics

Unit 4: Scan Conversion I

Direct Use of the Line Equation
A line can be scan converted by following the steps given below:

1. Scan-convert the endpoints P1 and P2 to pixel coordinates (x1, y1) and (x2, y2) respectively
2. Set m = (y2-y1)/ (x2- x1) and b= y1-m x1
3. If |m|≤1, calculate the corresponding value of y using the equation and scan-convert (x, y) for
every integer value of x between and excluding x1 and x2
4. If |m|>1, calculate corresponding value of x using the equation and scan-convert (x, y) for every
integer value of y between and excluding y1 and y2
DDA Algorithm
The Digital Differential Analyzer (DDA) algorithm is one of the incremental scan-conversion methods.
This approach is characterized by calculating at each step using the results obtained in the previous
step.
Assume that in step 1, (x i , y i ) has been calculated to be a point on line. As the next point, (x i+1 , yi+1 )
must satisfy ∆y/ ∆x where ∆y=y i+1 -y i and ∆x=x i+1 -x i. H ence we have:

Y i +1=y i +m∆x…………………...Eq (1)
X i +1=x i +∆y/m……………...….Eq (2)
Equations (1) and (2) are used in DDA algorithms as follows:

1. When |m||≤1, assuming x1 < x2 start with x=x1 and y =y1 and set ∆x=1. Calculate the y -
coordinate of each point using yi+1= yi+m.
2. When|m|≥1, assuming y1<y2 start with x=x1 and y=y1 and set ∆y=1. Calculate the x-coordinate
of each point using xi+1=xi+1/m.

The above process is continued until x reaches x 2 or y reaches y 2 and all points are scan-converted to
pixel coordinates.

The DDA algorithm is faster than the direct use of the line equation. This is because DDA

algorithms calculate points on the line without any floating-point multiplication.

Bresenham’s Line Algorithm
Bresenham’s line algorithm is one of the highly efficient incremental methods for scan-converting lines.
It is an algorithm that determines which points in an n-dimensional raster should be plotted in order to
form a close approximation to a straight line between two given points. It is an accurate and efficient
raster line-generating algorithm that uses only incremental integer calculations.
Bresenham’s algorithm can be used to display lines, circles and other curves. The vertical axes show
scan-line positions, and the horizontal axes identify pixel columns, that is, Bresenham’s algorithm can
be successfully used for drawing lines on a computer screen, subtracting, and bit shifting.

Bresenham’s line algorithm works as follows. Assume that you want to scan-convert the line shown in
figure 4.2, where 0<m<1. For this, start with pixel p i (x 1 , y 1 ), then select the subsequent pixels. After
the pixels are chosen at any step, the next pixel is either the one to its right and down or one to its right
and up due to the limit on m.

LOVELY PROFESSIONAL UNIVERSITY 41