Sem 4‎ > ‎CG LAB‎ > ‎0 Algorithms‎ > ‎

### 2 Bresenham's Line Algo

posted Jan 8, 2012, 4:48 AM by Neil Mathew   [ updated Jan 8, 2012, 5:26 AM ]
 [Normal]Explanation:  Here, Normal means when the slope is less than 1 ( 0 < m < 1 ). That means, dx is greater than dy. Therefore, x has a regular increase. And with every regular increase of x, y is determined by the the closest pixel. Unlike DDA Algo, the values of x and y are chosen rather than a repeated addition. Algo (Normal) :1. Input the starting and ending points and store the starting points in (x0,y0) .2. Load (x0,y0) into frame buffer and plot the first print.3. Calculate the constants Δx, Δy, 2Δy, 2Δy-2Δx and obtain starting value of decision parameter.Δx = x2- x1Δy = y2-y1dT= 2(Δy- Δx)dS= 2(Δy)d= 2Δy -   Δx4. At each xi along the starting i=0 perform if di < 0 the next point is (xi+1,yi)di+1= di +2Δy //+dSotherwisethe next point is (xi+1,yi +1)                                                                          di+1= di +2Δy-2Δx //+dT 5. Repeat step 4 Δx times.My Notes:1. T is used to represent the the upper pixel while    S is used to represent the lower pixel.2. d is the decision variable which tells me which pixel should be chosen, T or S.    if d < 0, Negative, it is LOWER, S. (Y=y as X inc by 1)    if d >=0, Positive, it is UPPER, T.  (Y=y+1 as X inc by 1)3. Accordingly, if d<0, d+=dS                        d>=0, d+=dT    to determine the next decision variable. 4. Usually, dT is negative as it is the upper One, and dS is positive, S being the Lower one.[General]Explanation:  This uses the same concept however,  General means it works for any slope.Steps:1. Initialize:x=x0;y=x0;dx=abs(x2-x1)dy=abs(y2-y1)Sx=sign(x2-x1)Sy=sign(y2-y1)2. Determine IF dy > dx then, // Slope > 1steps=dy;flag=1;//Swap values of dx and dy - To save code rather than create everything again just for specific dx dyt=dx; dx=dy; dy=t;elsesteps=dx;flag=0;             //flag=0, dx > dy (same as Normal)END IFPk= 2dy-dx;   //Pk decision variablesetpixel(x,y);for(i=1 to steps)while ( Pk>0 )IF flag=1 thenXi+1=Xi+Sxelse                  // You should understand and KNOW flag=0Yi+1=Yi + Sy    // When Pk>0 +dT X=X+1 Y=Y+1 (Conditional Inc one) END IFPk=Pk-2dx       // + dT is 2dy-2dx, So, the remaining +2dy (+dS) is given below in parts. (dT=dS-dx)END WHILEIF flag=1 thenYi+1=Yi+1elseXi+1=Xi+1        // if the Pk<=0, while not included. if flag=0, +dS & Y=Y X=X+1 (Regular Inc one)END IFPk=Pk+2dySetpixel(x,y);NEXT(i);FINISH          // used in Algos for end of For loop   The Reason behind Decision Variable, dS, dTBased on above diagram:If (BlueLine < Midpoint)   Plot_East_Pixel();Else   Plot_Northeast_Pixel();What if we came up with an equation, given a line and a point, that will tell us if the line is above or below that line?  Let's play with the line equation.y= dy/dx x + Bdx *y = dy* x + B *dx                (rewritten)0 = dy* x - dx* y + B*dx                     (rewritten again)Notice that the left side of this equation equals zero on the line.  It can be shown that for any point x, y above the line, the right side of the equation becomes a negative number, and any point x,y below the line becomes positive.  Or, in other words, if we define a line function F:F( x, y) = 2 * dy* x - 2 * dx * y + 2 * B * dxThen for any point (x,y) that represents a midpoint between the next East or Northeast pixel, F(x,y) < 0,    when     BlueLine < MidpointF(x,y) > 0,    when     BlueLine > MidpointNote also that I changed the equation to include a factor of 2.  This will be explained in a moment; but realize for now that this factor does not change the results of the equation; positive numbers remain positive, and negative numbers remain negative.Using The Line FunctionFor the first midpoint, given by (x1+1, y1+1/2), we can use our equation F(x,y) to determine if the second pixel (after x1,y1) to light up should be (x1+1, y1) or (x1+1, y1+1). Next, look at the line function on (x1, y1):F(x1, y1) = 2* dy * x1- 2 * dx* y1+ 2* B* dx = 0thereforeF(x1+1, y1+1/2) = 2*dy*x1 + 2*dy – 2*dx*y1 – dx + 2*B*dxd0 = F(x1+1, y1+1/2) = 2*dy – dxWe call this value d0 (for "decision variable – initial value")Now, for the next midpoint, we either evaluate F(x1+2, y1+1/2) or F(x1+2, y1+3/2), depending on whether we chose the East or Northeast pixel for the first midpoint, respectively.  As it turns out, we can exploit the nature of our Line Function F(x,y) because of the relationship between successive midpoints. Let's calculate the difference in the Line Function between midpoints, depending on our previous pixel choice:incE = F(Mx+1, My) – F(Mx,My)   = 2*dy                  (E pixel) (dS)incNE = F(Mx+1, My+1) – F(Mx, My) = 2*dy – 2*dx   (NE pixel)  (dT)To clarify; each time we make a decision on the choice of East or Northeast, we must make a new calculation based on the new midpoint.  As shown above, an East choice means the x-component of the midpoint increases but the y component does not.  So now, all we really have to do is calculate the initial value of d0 and loop through the pixels, recalculating the value of F(x,y).   The beauty of this is that all of the values incE, incNE, and d0 are constant integers.Speaking of which, remember that factor of two we introduced to F(x,y)?  That was added because each midpoint falls halfway between two pixels, and simply by multiplying both sides of that equation by 2, we can get an equation that usesonly integers.  How sweet.