0 Algorithms
CG Algos
2 Bresenham's Line Algo
 [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. |
3 Bresenham's Circle Algo
Explanation: 
The program should make use of basic concept of circle generation algorithm. This algorithm does only integer arithmetic which makes it faster than floating point. We are creating only one octant i.e. from 90 to 45 degree. We derive other seven octants of circle by symmetry property. The circle is generated by considering center point as origin with radius ‘r’. The algorithm calculates one new pixel per step. One Octant (1/8 circle): (x,y) symmetry points: (-x,y) (x,-y) (-x,-y) (y,x) (-y,x) (y,-x) (-y,-x)  (Plotting need not be counterclockwise in what I've done) The above is assuming the origin is at centre. (0+x,0+y) When a centre (xc,yc) is provided by the user, the points are: (xc+x, yc+y) (xc-x, yc+y)
( xc+x , yc-y )
( xc-x , yc-y ) ( xc+ y , yc+x )
( xc+ y , y c+x )
( xc+ y , yc-x)
( xc+ y , yc-x )Caution: The xc,yc being centre coordinates, they should not be rearranged such that the x and ys are together. (yc+y,xc+x) = WRONG (xc+Y, yc+X) = RIGHT Algo: 1. Input the radius of circle and store end points in (x0,y0) = (0,r). 2. Load (x0,y0) into frame buffer and plot the first point. 3. Calculate the starting value for decision variable d=3-2r 4. At each xi along the circle starting i=0, perform: if (di < 0) the next point is (xi+1,y) di+1=di + 4xi + 6 // another way to write: di+1=di + (4xi + 4) + 2 else the next point is (xi+1, yi-1) di+1=di + 4(xi-yi) + 10 // another way to write: di+1=di + (4xi + 4) + 2 + ( - 4yi + 4) 5. repeat 4 while x<=y //or write it as repeat until x>y My Notes: 1. when decision variable d < 0, it means the next point is getting inside the circle. Therefore Y=y; when decision variable d > 0, it means the next point is getting outside the circle/ There fore Y=y-1; 2. As compared to last time - Bresenham's Normal Line Algo, (but slightly different) the X is the regular inc one, while Y is the conditional dec one. 3. Also, in the algo, only one octant is made. Add symmetry points for the others too. Reason behind the decision Variables ... |
1 DDA Line Algo
 ( DDA uses repeated addition ) ( Use of floating point operations makes it slightly slower than Bresenham's Algo ) Explanation: The program should make use of basic concept of DDA’s line generation algorithm. The DDA is a scan conversion line algorithm based on calculating Dy and Dx. We sample the line at unit intervals in one co-ordinate and determine corresponding integer values nearest the line path for the other co-ordinate.1. We will consider a line with positive slope. >>If the slope is less than or equal to 1,we sample it at unit x intervals (Dx = 1) and compute each successive y value as yk+1 = yk + m (Subscript k takes integer values starting from 1 for the first point and increases by 1 until the final end point is reached. The value of m can be any real number between 0 and 1.2) >>For lines with positive slope greater than 1, we reverse the roles of x and y. We sample at unit y intervals and calculate each succeeding x value as xk+1= xk + 1/m >> For the above equation we are processing the line equation from the left end point to right end point. If this processing is reversed , (negative Slope) so either we have Dx = -1 and
yk+1 = yk - m Or Dy = -1 and xk+1= xk - 1/m Program:
|
1-3 of 3
