Page 53 - DCAP313_LAB_ON_COMPUTER_GRAPHICS

Unit 3: Implementing Line Algorithm

3.3 DDA Line Algorithm Notes

Digital Differential Analyzer (DDA) is a scan alteration line algorithm stand on calculating
either dy or dx. We sample the line at unit gaps in one coordinate and decide corresponding
integer values neighboring to the line path for the other coordinate. The DDA method is not
very proficient by reason of the need for division and rounding. Bresenham's line algorithm is
a more efficient method to draw lines because it uses only addition, subtraction and bit shifting.
The algorithm accepts as input the two endpoint pixel positions. Horizontal and vertical
differences between the endpoint positions are allocated to parameters dx and dy. The difference
with the greater magnitude concludes the increase of the parameter steps. Starting with the
pixel position (x a , y a ), 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 d y and x a is less that x b , the values of the increments in the x
and y directions are i and 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.

This algorithm is also a scan conversion algorithm now as Bresenham’s algorithm. This works as
well by selecting which pixels to put on between two points, but instead of calculating the next
point by looking at the errors between the possible choices, this algorithm always increments
the value along one axis and calculates the value of the other co-ordinate. The decision to which
coordinate to move at a constant step is by finding which of the two have a greater gradient,
i.e., if dy< dx, then co-ordinate x will move in steps, and co-ordinate y will be calculated.
Current = (x, y)
calculate dy and dx
if (dy > dx) then
steps = dx
else
steps = dy
x inc = dx /steps
y inc = dy /steps
repeat until current = (x end , y end )
Plot (Current)
xCurrent = xCurrent + xinc

yCurrent = (xCurrent + l, yCurrent + y inc

LOVELY PROFESSIONAL UNIVERSITY 47