Bresenham’s Circle drawing algorithm: Bresenham’s Circle drawing algorithm
Midpoint Circle Algorithm: Midpoint Circle Algorithm We will first calculate pixel positions for a circle centered around the origin (0,0). Then, each calculated position (x,y) is moved to its proper screen position by adding xc to x and yc to y Note that along the circle section from x=0 to x=y in the first octant, the slope of the curve varies from 0 to -1 Circle function around the origin is given by fcircle(x,y) = x 2 + y 2 – r 2 Any point (x,y) on the boundary of the circle satisfies the equation and circle function is zero
Midpoint Circle Algorithm: Midpoint Circle Algorithm For a point in the interior of the circle, the circle function is negative and for a point outside the circle, the function is positive Thus, f circle (x,y) < 0 if (x,y) is inside the circle boundary f circle (x,y) = 0 if (x,y) is on the circle boundary f circle (x,y) > 0 if (x,y) is outside the circle boundary yk Yk-1 xk xk+1 Xk+2 Midpoint X 2 +y 2 -r 2 =0 Midpoint between candidate pixels at sampling position x k +1 along a circular path
Midpoint Circle Algorithm: Midpoint Circle Algorithm Assuming we have just plotted the pixel at (x k ,y k ) , we next need to determine whether the pixel at position ( x k + 1, y k -1) is closer to the circle Our decision parameter is the circle function evaluated at the midpoint between these two pixels p k = f circle (x k +1, y k -1/2) = (x k +1) 2 + (y k -1/2) 2 – r 2 If p k < 0 , this midpoint is inside the circle and the pixel on the scan line y k is closer to the circle boundary. Otherwise, the mid position is outside or on the circle boundary, and we select the pixel on the scan line y k -1
Midpoint Circle Algorithm: Midpoint Circle Algorithm Successive decision parameters are obtained using incremental calculations P k+1 = f circle (x k+1 +1, y k+1 -1/2) = [(x k+1 )+1] 2 + (y k+1 -1/2) 2 –r 2 OR P k+1 = P k +2(x K +1) + (y K+1 2 – y k 2 ) – (y k +1- y k )+1 Where y k+1 is either y k or y k-1 , depending on the sign of p k Increments for obtaining P k+1 : 2x k+1 +1 if p k is negative 2x k+1 +1-2y k+1 otherwise
Midpoint circle algorithm: Midpoint circle algorithm Note that following can also be done incrementally: 2x k+1 = 2x k +2 2 y k+1 = 2y k – 2 At the start position (0,r) , these two terms have the values 2 and 2r-2 respectively Initial decision parameter is obtained by evaluating the circle function at the start position (x0,y0) = (0,r) p 0 = f circle (1, r-1/2) = 1+ (r-1/2) 2 -r 2 OR P 0 = 5/4 -r If radius r is specified as an integer, we can round p 0 to p 0 = 1-r
The Midpoint Circle algorithm: The Midpoint Circle algorithm 1: Input radius r and circle center (x c ,y c ) and obtain the first point on the circumference of the circle centered on the origin as (x 0 ,y 0 ) = (0,r) 2: Calculate the initial value of the decision parameter as P 0 = 5/4 - r 3: At each x k position starting at k = 0 , perform the following test: If p k < 0 , the next point along the circle centered on (0,0) is (x k+1 , y k ) and p k+1 = p k + 2x k+1 + 1
Continuation…: Continuation… Otherwise the next point along the circle is (x k+1 , y k-1 ) and p k+1 = p k + 2x k+1 +1 -2y k+1 Where 2x k+1 = 2x k+2 and 2y k+1 = 2y k -2 4: Determine symmetry points in the other seven octants 5: Move each calculated pixel position (x,y) onto the circular path centered on (xc,yc) and plot the coordinate values x = x+ x c , y= y+ y c 6: Repeat steps 3 through 5 until x >= y
PowerPoint Presentation: Void circlemidpoint(int Xcenter , int YCenter, int radius) { int x=0; int y=radius; int p=1-radius; Void circleplotpoints (int , int , int, int ); }
PowerPoint Presentation: /* plot first set of points*/ circleplotpoints ( XCenter , Ycenter, x, y); while(x<y) { X++; If(p<0) P+=2*x+1;
PowerPoint Presentation: Else { Y--; P+=2*(x-y)+1; } Circleplotpoints (XCenter , Ycenter, x, y); } }
PowerPoint Presentation: Void circleplotpoints (int Xcenter, int Ycenter, int x, int y ) { Setpixel(Xcenter+x,Ycenter+y); Setpixel(Xcenter-x,Ycenter+y); Setpixel(Xcenter+x,Ycenter-y); Setpixel(Xcenter-x,Ycenter-y); Setpixel(Xcenter+y,Ycenter+x); Setpixel(Xcenter-y,Ycenter+x); Setpixel(Xcenter+y,Ycenter-x); Setpixel(Xcenter-y,Ycenter-x); }
Circle: Circle Given a circle with radius r=10, use mid-point circle algorithm and find the circle octant in the first quadrant from x=0 to x=y.
PowerPoint Presentation: K Pk (X,Y) 0 -9 ( 1,10 ) 1 -6 ( 2,10 ) 2 -1 ( 3, 10) 3 6 ( 4, 9) 4 -3 ( 5, 9) 5 8 ( 6, 8) 6 5 (7 , 7)