Graphics

Numerical of DDA Algorithm

Let us understand how DDA Algorithm works by taking some examples and solving them too. Just keep in mind two things one, Y=mx+b is the line equation. Second, If m is less than one increase X and calculate Y. If m is more than 1 then increase Y and calculate X. DDA Algorithm is explained by taking some examples.

Remember the steps:

If slope (m) is less than 1 (m<1) then increment x as x1+1 and calculate y as y1=y1+m
If slope (m) is greater than 1 (m>1) then increment y as y1+1 and calculate x1=x1+1/m
If slope is equal to 1 (m=1) then increment both x and y. x1=x1+1 , y1=y1+1.

DDA- Digital Differential Analyser – The Algorithm

S-1: Lets take the starting points of line as (x1,y1) and ending points as (x2,y2)

S-2: m=(y2-y1)/(x2-x1)

S-3: If slope (m) is less than 1 (m<1) then increment x as x1+1 and calculate y as y1=y1+m

S-4: If slope (m) is greater than 1 (m>1) then increment y as y1+1 and calculate x1=x1+1/m

S-5 : If slope is equal to 1 (m=1) then increment both x and y. x1=x1+1 , y1=y1+1

S-6 : Repeat the steps till end of line (x2,y2) is reached.

—————————————————————–

Problem Statement

Draw a line from (1,1) to (8,7) using DDA and BLA algorithms.

DDA- Digital Differential Analyser

This case is for slope (m) less than 1. Slope (m) =(7-1)/(8-1) = 6/7 .

S-1: x1=1; y1=1; x2=8; y2=7.

S-2: m=(7-1)/(8-1) = 6/7 which is less than 1.

S-3: As m (6/7) is less than 1 therefore x is increased and y is calculated.

S-4 : The step will be x1=x1+1 and y1= y1+6/7

S-5 : The points genrated would be x1=1+1 and Y1=1+(5/7) => 1+0.9=>1.9=> approx 2. So X 1=2 and Y1= ~2

S.No.	X1	Y1	Pixel Plotted
1	2	2	2,2
2	3	2+6/7 = 2.9	3,3
3	4	2.9 + 6/7 = 3.8	4,4
4	5	3.8 + 6/7 = 4.7	5,5
5	6	4.7 + 6/7 = 5.6	6,6
6	7	5.6 + 6/7 = 7.0	7,7

The algorithm will stop here as the x value has reached 7.

—————————————————————–

Lets take another example.

Draw a line using DDA Algorithm from (0,0) to (4,6)

This case is for slope (m) greater than 1. Slope (m) =(6-0)/(4-0) = 6/4 .

S-1: x1=0; y1=0; x2=4; y2=6

S-2: m=(6-0)/(4-0) = 6/4 which is more than 1.

S-3: As m (6/4) is greater than 1 therefore y is increased and x is calculated.

S-4 : Now increase the value of y and calculate value of x.

To calculate x, take line equation and find x , x2=x1+1/m

The step will be y1=y1+1 and x1 =x1+1/( 6/4) , After Simplification, Every time y1=y1+1 and x1=x1+4/6

Step	Y1	X1	Pixel Plotted
1	0	0	(0,0)
2	1	x1= (0)+4/6=0.67 =1	(1,1)
3	2	0.67+4/6 = 1.34	(1,2)
4	3	1.34+4/6=2.01	(2,3)
5	4	2.01+4/6= 2.68	(3,4)
6	5	2.68+4/6=3.35	(3,5)
7	6	3.35+4/6=4.02	(4,6)

The algorithm will stop here because the Y and X values have reached the End point (4,6).

Example -3: Draw a line from (0,0) to (7,7) using DDA Algorithm

This case is for slope (m) equals 1. Slope (m) =(7-0)/(7-0) = 7/7 .

S-1: x1=0; y1=0; x2=7; y2=7.

S-2: m=(7-0)/(7-0) = 7/7 which is equal to 1.

S-3: As m equals to 1 (m=1) therefore x will be increased by 1 and y will be incremented by m.

S-4 : The step will be x1=x1+1 and y1= y1+1. This would be a 45 degree line where x and y both have equal incremented value.

S-5 : The points generated would be x1=1+1 and Y1=1+(1) => So X 1=2 and Y1= 2

S.No.	X1	Y1	Pixel Plotted
1	2	2	2,2
2	3	2+1 = 3	3,3
3	4	3 + 1 = 4	4,4
4	5	4 + 1 =5	5,5
5	6	5 + 1 =6	6,6
6	7	6 + 1 = 7.0	7,7

The algorithm will stop here as the x and y values have reached 7. This would be a straight line dividing the first quadrant in two equal halves.

Example -4

Use DDA Algorithm to draw a line from (2,3) to (9,8).

S-1: x1=2, y1=3 and x2=9 , y2=8.

S-2: Calculate Slope m = (8-3)/(9-2) = 5/7, which is less than 1.

S-3: Since m is less than one that means we would increase x and calculate y.

S-4: So new x would be equal to old x plus 1 🙂 and calculate y as new y = old y +m(slope). — Easy to understand, We mean the following

x1=x1+1 and y1=y1+(5/7)

S.No.	X1	Y1	Pixel Plotted
1	2	3	2,3
2	3	3+5/7 => 26/7 => 26/7=>3.71	3,4
3	4	3.71 + 5/7 = 4.42	4,4
4	5	4.42 + 5/7 =5 .13	5,5
5	6	5.13 + 5/7 =5.84	6,6
6	7	5.84 + 5/7 = 6.55	7,7
7	8	6.55+5/7=7.26	8,7
8	9	7.26+5/7=7.97	9,8