DDA Line Drawing Algorithm - Computer Graphics

hi the topic is DD a line drawing algorithm that is digital differential analyzer algorithm that is useful during a line this topic is from computer graphics and this is the basic algorithm for drawing a line in this video I am going to cover these topics C for understanding the algorithm we need to know few things so quickly I will cover those things so what is the line we'll understand then what are line equations and what is it mean by slope of a line and the examples for drawing a line that will help us to understand DDA then finally I will show you DDA algorithm so let us start I'll take two dimensional coordinate system this is x axis and this is y axis and this is origin in two dimensional coordinate system if I draw a lines now line is usually a in finite in dimension but if we want a part of a line then let us say I want a line from here to here then this piece of line we call it as line segment this is line segment so a line segment we have to confine points that is x1 y1 and x2 y2 so when we say a line we actually mean a line segment that is confined between two end points now the next thing C Line is said to be a collection of points so if I take just a segment think that this segment is a set of points or collection of points so line as a define as set of points over a path so that part that line is defined by using line equations so a commonly known line equation is y is equals to MX plus C where m is the slope of a line and see is the intersecting point of this line over y so this is called as y-intercept and this point if you take this is called as x-intercept over an x axis wherever it is intersecting so if you know slope and the y intercept of a line then you can know any point on the line suppose revolved within this segment then you put any x value you can get the y value suppose I want to know this is suppose X is 20 for example then at 20 what should be the Y value you can find out so Y is equals to and into 20 plus if you know the y-intercept so if you know these two things then you can find out the value of line so this line equation is useful for knowing all the points over line for radius X values or various y values and there are more line equations also like you may be knowing if two endpoints are given then Y minus y1 is equal to y2 minus y1 by x2 minus x1 into X minus x1 this is also a line equation and there is one more line equation that is X by ay that is x intercept and Y by B that is y intercept equal to one so this is first one second one third one in computer graphics will be using this line equation for drawing lines now next we will see the slope of a line in a coordinate system if we have a line segment then these are the two end points so this is X 1 and this is X 2 and this is y 1 and this is y 2 so this distance the difference between X 2 and X 1 I can show it here with a dotted line so this is the difference in X DX or we can also say Delta X difference in X and this distance between two points of a line that I will plot it here and this distances distance in Y that is dy or we can also call it as Delta Y so this is Delta X and this is Delta Y so it is forming a right angle triangle with a line so if I take difference in X and difference in Y then it forms some angle here theta so difference in Y and difference in X so what is the slope slope is equals to difference in Y by difference in X actually this is opposite and this is adjacent with respect to this triangle for this angle theta so that is nothing but tan theta that is opposite by adjacent so slope is nothing but tan theta so M is equals to tan theta so we can find the slope of a line if you know difference in X and difference in Y so the slope is a dy by DX now let us see few examples see in a coordinate system if I have a line like this these are the two end points then the difference in X is this much and difference in Y is this one so difference in Y is less than a difference in X so this numerator is smaller than denominator so we get the values that are less than one so suppose this is a line segment then this is difference in X this is difference in X and this is difference in Y for this particular line so dy is grater and DX is smaller so dy is grater and DX is smaller so then we get the values that are greater than one so slope will be greater than 1 so the lines which are having angle greater than 45 degrees they are having slope greater than one who those who are having less than 45 degrees then their slope is less than one if I take this line so this is looks like 45 degrees so this is difference in X and this difference in Y so they both look equal so when the DX and dy they are same then slope will be 1 so that's it so the lines with slope equal to 1 will be at 45 degrees in the coordinate system less than 45 degrees their slope is less than 1 and this is greater than 1 whose angle is greater than 45 degrees so here angle is theta is 45 degrees and this here theta is less than 45 degrees and here theta is greater than 45 degrees this is the first line which is having degree greater and this is the second line whose degree is less than 45 and this is the third line whose degree is exactly 45 then next let us see how to draw a line I will take an example of coordinate system and explain you then also I will show you how it happens on computer screen in computer graphics now here is an example of a coordinate system I have taken origin here and the x-axis is going in this direction and the y axis is going upwards but actually on the screen it will be the x-axis will be going in this direction only but the y-axis will be coming downwards and this will be the origin here will be the origin so just as a change of origin so we can understand the algorithms based on the world coordinate system these are called as world coordinate system so based on this we can understand it and then we can plot it on the screen but remember on the screen the origin starts from here now we have to understand D D algorithm so for that I will take some example lines I will draw them then from that we will understand D D algorithm so first I will draw a line from 2 comma 2 9 comma 2 this is the line I will take so these are the two end points of a line so x1 y1 x2 and y2 that is 2 comma 2 is x1 y1 and 9 comma 2 is x2 y2 now I have to draw a line so you can observe that it's a straight line and it's a horizontal line for a horizontal lines I should just fill up these boxes that's on so total how many boxes including this points 1 2 3 4 5 6 7 8 so if I start from here 7 steps I have to take from 2 comma 2 I should take 7 steps to reach this one so I will be getting seven boxes or in terms of screen if you say seven pixels so total eight pixels so now how to get those points let us see so for finding there all the points on the line we have to find out a difference in X differences X is what 9 minus 2 that is 7 and difference in Y that is 2 minus 2 that is 0 then what is slope M as difference in Y by difference in X that is 0 by 7 it is 0 so from the starting point how many steps I have to take steps that is verbs in X is greater see the number of pixels that indicating depends on x value so the steps are 7 then each time how much I should increment in X how much I should increment in X difference in X is 7 and the steps are 7 so I should increment by 1 then how much I should increment in by every time difference in Y is 0 and the steps are 7 0 divided by anything that is 0 only so I should not increment at all in Y then what are the points that I will get x and y if I take the points let us start the first point is 2 comma 2 then X increment is 1 every time and why increment is 0 so don't change Y at all so it will be 3 comma 2 4 comma 2 8 2 and finally it is 9 to see these are the points I am getting on the line so 2 - 3 - 4 - 5 - let us check here - 2 3 2 & 4 2 5 - 8 - 9 - so I got a line so I got all the points on a line so in that visualize it was increasing by 1 every time x value was increasing here 1 by x value was increasing by 1 every time and the Y value was not increasing at all now I will take one more line I will show you 2 comma 5 2 - comma 12c and taking a vertical line so for this vertical line X 1 y 1 R 2 comma 5 and X 2 y 2 R 2 comma 2 and these are the two points now let us find out all the points on that line so if you directly see how many points will be getting 1 2 3 4 5 6 7 8 total eight points are there including both the end points so let us see difference in X is how much 2 minus 2 that is 0 and difference in Y as 12 minus 5 that is 7 so 7 I am getting because excluding the first point so remaining seven points so what is slope slope is dy by D X so that is seven by zero so this is infinity slope is infinity because it's a vertical line so it's greater than 1 and how many steps I should take for plotting all the points so excluding the first point I should take seven steps so that is dy see if you observe now here the steps were obtained by a difference in X and here the steps are obtained by difference in Y now how much I should increment in X every time so what is the difference in X zero and what are the number of steps 7 that is zero then then how much I should increment in my every time difference in Y is the 7 and the number of steps are also 7 so this is 1 so this means that now Y will be increasing by 1 every time an X will not be increasing at all so let us take the points x and y so the starting point is 2 comma 5 and the next step is if I take the next point then X nothing is increase and the y one is increased so 2 comma 6 then 2 comma 7 11 and 12 see these are the points I got so 2 6 - 7 to 11 and 2 12 so I got a vertical line now I will take a more examples of lines one with slope less than one and greater than and equal to one so to that you can't really understand what our DD algorithm is then also I will show you the code for DD and God let us look at the examples so the first example is our line between 5 comma 4 to 12 comma 7 so here are the two coordinates x1 y1 x2 y2 5 comma 4 to 12 comma 7 now let us find out quickly all those things difference in X's 12 minus 5 that is 7 difference in Y is 7 minus 4 that is equal to 3 then what is slope difference in Y by difference in X that is 3 by 7 this is the slope now on this line if you see how many points you will get see from first point to the last point which difference is greater X difference is greater than Y difference so we will get the number of points equal to X difference so how many steps will be there steps will be equal to 7 difference in X then how much X should increment every time difference in X bias steps that is 1 then how much Y should increment every time difference in Y divided by 7 so this is so 3 by 7 is point 4 2 something but I will take only 4 so you can see the difference in Y is smaller so the number the amount of increment is in decimal point for less than 1 and difference in X is greater so it will be 1 so this line is having the slope less than 1 slope less than 1 so M this is less than 1 so let us see x and y values what we get starting point is 5 comma 4 then in X every time I should add one in why I should add point 4 so this is 6 and this is 4 point 4 and this is 7 and this is 4 point 8 and this is 8 this is 5 point 2 I'm adding point for every time this is 9 this is 5 point 6 and this is a 10 this is six and eleven six point four and twelve is a six point eight see the last point he did not get seven because we have not taken exact decimal value we have taken just point four now do we have these decimal pixels there no then I should round these values so this is for only this four point four is also four four point eight is five and five point two is five only five point six I should take six this is greater than 0.5 so this is six and this is six point four is also six and six point eight is seven so these are the points we got five four six four seven five eight five nine six so on I will plot these points there five comma four five comma four is already there 6 comma 4 6 comma 4 only then 7 5 8 5 then 9 610 611 6 9 11 6 and 2 and 7 so I am getting a line like this it's a little coke the line so it will not be a smooth line so this is a line with a slope less than 1 in this example we can observe one thing like from any XK how we were getting the next x value by adding one we were getting the next x value that is XK plus 1 so from any XK like suppose six is XK then next value home we were getting this is XK plus 1 so by adding 1 6 plus 1 7 then for any YK how we are getting the next value of y that is YK plus 1 YK plus 1 we are getting by adding this point 4 that is 3 by 7 3 by 7 is nothing but slope so plus M so this means if the slope of a line is less than 1 then X increment will be by 1 and the y will you buy slope now let me take another example of a line and show you with the slope greater than one second example slope is greater than one I have two points 5 comma 7 and 10 comma 15 so these are the two end points I have taken now let us find out all those things that is how much is difference in X difference in X is 10 minus 5 that is 5 difference in Y is 15 minus 7 that is 8 so whose difference is greater Y difference is greater so it means how many points I can plot on this line so total 8 points excluding the first point so if you include total 9 points will be there so I'll be adding 8 steps so slope is how much M is how much the difference in Y by difference in X 8 by 5 this is the slope so you can see that 8 by 5 will be greater than 1 so slope is greater than 1 then how many steps will be there steps will be what 8 whichever is greater out of these 2 that many pixels will get will not get 5 6 pixels if I plot only 5 pixels then there will be gaps in between the lines so to fill the complete line I should take the number of steps whichever is greater DX or dy then how much X will be incremented every time X will be incremented by difference in X by steps 8 so this will be zero point 6 so you can observe that this X increment is inverse of slope slope is 8 by 5 this is 5 by 8 then what is y increment Y increment does difference in Y is 8 how many steps we are taking 8 so this will be 1 it means every time I should add point 6 in X and 1 in Y so let us take these coordinates x and y so first point is 5 comma 7 then next point I can get by adding 1 to Y so this will be 8 but in X how much this is point 6 over this is 5 point 6 then again every time I will add point 6 to this one so this will be 6 point 2 and this will be 98.6 and this is 13 nine point two 14 a 9 point 8 is 15 so we are not getting exactly that is a 10 the reason is we have not taken exact fractions just we have taken point 6 now the problem is do we have these pixels there the points there now we have only integral point but the answer we are getting in slope point actually this is the problem with the DD algorithm so now I will take round of values so this is 5 only and this is 5 point 6 so this is more than 0.5 so I will make it as 6 and this is 6 point 2 I will take it 6 in this is 9 and this is 9 point 8 is 10 now we plot these points they then 6 8 & 6 9 the next is 7 10 7 Levin then 8 12 12 then 9 13 9 14 so this is 9 13 and 9 14 and the last one is 10 15 so I got a line like this so this is the line I got now in this one if you observe how I was increasing every time if the current value of y is YK then how we were getting the next value that is YK plus 1 we were getting by adding 1 every time so this was one was added every time then how about XK plus 1 however getting next x value from xk we were adding 5 by 8 that is nothing but inverse of slope so we were adding 1 by M so as for the derivation of DDA algorithm if the slope is greater than 1 this is how the changes in x and y values will be done last one and the quickly we will see that slope is equal to 1 now here I have an example with the line slope equal to 1 I have taken two coordinates those two coordinates are here in the coordinate system so let us quickly find out what is difference in X that is 17 minus 12 is 5 and difference in Weyers 14 minus 9 that's also 5 so what is slope 5 by 5 that is equal to 1 and how many steps C steps are both are equal only so we can take anything so that is five only then how much I should increment in X difference in X by a number of steps that is 1 and how much I should increment in Y that is a difference in Y by 5 that steps 1 only so both are incrementing by 1 1 every time so let us start taking the points x and y so what are the starting points to L comma 9 so now every time I should add 1 to X and 1 to Y so this will be 13 10 17 14 so this is the last point so I got excluding this 1 1 2 3 4 5 five steps or 5 points I got so I will plot those points here so I have three examples here slope less than 1 greater than 1 and equal to 1 and these are actually this is the working of DDA algorithm only now one more important thing I'll show you see instructor welcome online if I write 17 comma 14 here and this is 2 l comma 9 then what happens see it means the starting point first x1 y1 I made it as x2 y2 and that is x1 y1 so the smaller point is x2 y2 and the greater point is x1 y1 then what happens let us see if I take this then - well - 17 so this will be 2 L minus 17 and this will be minus 5 and this will be minus 9 minus 14 so 9 minus 14 this will also be minus 5 slope will be what minus minus cancel its 1 and the step will be absolute of this that is 5 only so the number of steps will be 5 only but what is X increment minus 5 by 5 s minus 1 and minus 5 by 5 is this is also minus 1 so we will be starting from 1715 and by decreasing will be reaching at to welcome a 9 so it's not a problem if you give the coordinates the other way also so if you even get the values in negative also it works the starting will be this one and it will be decreasing and we'll be getting this one so I don't want to change this so you can understand with this one so this will be the starting point and the last point will be this one and that we get by decreasing both of so didi algorithm works even if you give the points in other way now I will remove these two animals right on DDL garden so I'll write D D algorithm D D algorithm is taking two points x1 y1 x2 y2 first of all we'll find out difference in X DX is x2 minus x1 then dy difference in Y is y2 minus y1 then next is I have to find out steps steps so whichever is greater we will take that one so if absolute of a difference in X is greater than absolute of difference in Y then we will take step equal to absolute of difference in X otherwise we will take step equal to absolute of difference in Y step is taken now we have to calculate X increment and y increment so how much is X increment X increment is difference in X divided by step and Y increment is difference in Y divided by step we have to generate the points so how many points we have to generate for I assign one I is less than or equal to step and I plus plus and we can plot the pixels or we can say put pixels x1 y1 and every time in x1 will be adding X 1 plus X increment so I am taking the starting point from there only and y1 that is y 1 plus y increment so this has to be repeated in a loop that's all this the algorithm so whatever the steps I have shown you those same steps are there in the cell world so this is a DDA algorithm lumber the DDA algorithm is the values that are X increment and buying three mentees has to be taken flawed because of one of the value may be in decimal point so there there are no decimal points on the screen or in coordinate system so the problem is algorithm will be generating floating numbers and the calculation of float takes extra time compared to integer so the algorithm is slower and the points that we are getting are not accurate points we are taking round up so the line will not be smooth line so the two problems of DD algorithm line will not be a smooth one and it uses floating point which takes extra time so for this reason there is another algorithm called bresenham's algorithm so if you like I will prepare a video on bresenham's and quarter that's it

Channel: Abdul Bari

Views: 297,454

Rating: 4.9172783 out of 5

Keywords: DDA, Line Drawing, Line Drawing algorithm, dda algorithm, digital differential analyzer, digital differential analyser, computer graphics, abdul bari, bari

Id: W5P8GlaEOSI

Length: 26min 48sec (1608 seconds)

Published: Thu Apr 12 2018