 [Normal] 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-y1 dT= 2(Δy-
Δx) dS= 2(Δy) d= 2Δy - Δx 4. At each xi along the starting i=0 perform if di < 0 the next point is (xi+1,yi) di+1=
di +2Δy //+dS otherwise the 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 > 1 steps=dy; flag=1; //Swap values of dx and dy - To save code rather than create everything again just for specific dx dy t=dx; dx=dy; dy=t; else steps=dx; flag=0; //flag=0, dx > dy (same as Normal) END IF Pk= 2dy-dx; //Pk decision variable setpixel(x,y); for(i=1 to steps) while ( Pk>0 ) IF flag=1 then Xi+1=Xi+Sx else // You should understand and KNOW flag=0 Yi+1=Yi + Sy // When Pk>0 +dT X=X+1 Y=Y+1 (Conditional Inc one) END IF Pk=Pk-2dx // + dT is 2dy-2dx, So, the remaining +2dy (+dS) is given below in parts. (dT=dS-dx) END WHILE IF flag=1 then Yi+1=Yi+1 else Xi+1=Xi+1 // if the Pk<=0, while not included. if flag=0, +dS & Y=Y X=X+1 (Regular Inc one) END IF Pk=Pk+2dy Setpixel(x,y); NEXT(i); FINISH // used in Algos for end of For loop The Reason behind Decision Variable, dS, dT Based 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 + B dx *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 * dx Then for any point (x,y) that represents a midpoint between the next East or Northeast pixel, F(x,y) < 0, when BlueLine < Midpoint F(x,y) > 0, when BlueLine > Midpoint Note 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 Function For 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 = 0 therefore F(x1+1, y1+1/2) = 2*dy*x1 + 2*dy – 2*dx*y1 – dx + 2*B*dx d0 = F(x1+1, y1+1/2) = 2*dy – dx We 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 uses only integers. How sweet. |
|
|
 |