DDA (Digital Differential Analyzer ) Line Drawing Algorithm.pptx

DDA (Digital Differential Analyzer) is a line drawing algorithm used in computer graphics to generate a line segment between two specified endpoints. It is a simple and efficient algorithm that works by using the incremental difference between the x-coordinates and y-coordinates of the two endpoints to plot the line.

The steps involved in DDA line generation algorithm are:

Input the two endpoints of the line segment, (x1,y1) and (x2,y2).
Calculate the difference between the x-coordinates and y-coordinates of the endpoints as dx and dy respectively.
Calculate the slope of the line as m = dy/dx.
Set the initial point of the line as (x1,y1).
Loop through the x-coordinates of the line, incrementing by one each time, and calculate the corresponding y-coordinate using the equation y = y1 + m(x – x1).
Plot the pixel at the calculated (x,y) coordinate.
Repeat steps 5 and 6 until the endpoint (x2,y2) is reached.
DDA algorithm is relatively easy to implement and is computationally efficient, making it suitable for real-time applications. However, it has some limitations, such as the inability to handle vertical lines and the need for floating-point arithmetic, which can be slow on some systems. Nonetheless, it remains a popular choice for generating lines in computer graphics.

1. WELCOME

2. Presentation Topic: DDA (Digital Differential Analyzer ) Line Drawing Algorithm

3. Table of Content Introduction Understanding The Algorithm Procedure Practice Problems Based On DDA Algorithm Advantages Limitations Conclusion

4. Introduction The line (vector) generation algorithms which determine the pixels that should be turned ON are called as digital differential analyzer (DDA). It is a simple and efficient algorithm used to draw lines on a computer screen. It is one of the technique for obtaining a rasterized straight line. This algorithm can be used to draw the line in all the quadrants. 4

5. Understanding The Algorithm DDA Algorithm is the simplest line drawing algorithm. Given the starting and ending coordinates of a line, DDA Algorithm attempts to generate the points between the starting and ending coordinates. 5

6. Procedure Given- Starting coordinates = (X , Y ) Ending coordinates = ( X n , Y n ) 6

7. Procedure (Cont.) Step-01: Calculate ΔX, ΔY and M from the given input. These parameters are calculated as - ΔX = X n  – X ΔY =Y n  – Y M = ΔY / ΔX 7

8. Procedure (Cont.) Step-02: Find the number of steps or points in between the starting and ending coordinates. if (absolute (ΔX) > absolute (ΔY)) Steps = absolute (ΔX); else Steps = absolute (ΔY); 8

9. Procedure (Cont.) Step-03: Suppose the current point is ( X p , Y p ) and the next point is (X p+1 , Y p+1 ). Find the next point by following the below three cases- 9

10. Procedure (Cont.) Step-04: Keep repeating Step-03 until the end point is reached or the number of generated new points (including the starting and ending points) equals to the steps count. 10

11. Practice Problems Based On DDA Algorithm Problem-01: Calculate the points between the starting point (5, 6) and ending point (8, 12). Solution- Given- Starting coordinates = (X , Y ) = (5, 6) Ending coordinates = ( X n , Y n ) = (8, 12) 11

12. Practice Problems Based On DDA Algorithm (cont.) Step-01: Calculate ΔX, ΔY and M from the given input. ΔX = X n   – X  = 8 – 5 = 3 ΔY =Y n  – Y  = 12 – 6 = 6 M = ΔY / ΔX = 6 / 3 = 2 Step-02: Calculate the number of steps. As |ΔX| < |ΔY| = 3 < 6, so number of steps = ΔY = 6 12

13. Step-03: As M > 1, so case-03 is satisfied. Now, Step-03 is executed until Step-04 is satisfied. X p Y p X p+1 Y p+1 Round off (X p+1 , Y p+1 ) 5 6 5.5 7 (6, 7) 6 8 (6, 8) 6.5 9 (7, 9) 7 10 (7, 10) 7.5 11 (8, 11) 8 12 (8, 12) 13 Practice Problems Based On DDA Algorithm (cont.)

14. 14 Practice Problems Based On DDA Algorithm (cont.)

15. Advantages The DDA algorithm is straight-forward to implement. It only requires basic arithmetic operations like addition and division. It can be used to draw lines in both positive and negative slopes. DDA draws the line faster than drawing the line by directly using the line equation. 15

16. Limitations There is an extra overhead of using round off( ) function. Using round off( ) function increases time complexity of the algorithm. Resulted lines are not smooth because of round off( ) function. The points generated by this algorithm are not accurate. 16

17. Conclusion The DDA line drawing algorithm is a simple and widely used method to draw lines on raster displays. While it has its limitations, it remains a valuable tool for many applications. 17

18. Thank You 18