Bresenham’s Circle drawing algorithm

33 %
67 %
Information about Bresenham’s Circle drawing algorithm

Published on May 18, 2012

Author: sanuphilip


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)

Add a comment

Related presentations

Related pages

Midpoint circle algorithm - Wikipedia, the free encyclopedia

In computer graphics, the midpoint circle algorithm is an algorithm used to determine the points needed for rasterizing a circle. Bresenham's circle ...
Read more

Bresenham's line algorithm - Wikipedia, the free encyclopedia

Bresenham's line algorithm is an algorithm that ... as either Bresenham's circle algorithm or ... Bresenham line drawing algorithm to ...
Read more

Bresenham Line and Circle Drawing - WR Franklin (WRF)

Bresenham Line and Circle Drawing W. Randolph Franklin (WRF) Bresenham Algorithm ... Here are several versions, ending with Bresenham's algorithm.
Read more

An efficient circle drawing algorithm - Linköping University

An efficient circle drawing algorithm ... The problem of drawing a ... sents the Bresenham circle algorithm along with a plethora of other circle algorithms.
Read more

Computer Graphics Circle Generation Algorithm - Tutorialspoint

Drawing a circle on the screen is a little complex than drawing a line. There are two popular algorithms for generating a circle − Bresenham’s ...
Read more

A Fast Bresenham Type Algorithm For Drawing Circles

A Fast Bresenham Type Algorithm For Drawing Circles by John Kennedy Mathematics Department Santa Monica College ... Fast Circle Drawing 4 @AB2CDE ( !/*% ().
Read more

Bresenham’s Circle Algorithm

The purpose of Bresenham’s circle algorithm is to generate the set of points that approximate a circle on ... When drawing the first octant of a circle, ...
Read more

Bresenham's Line and Circle Algorithms -

Above all remember that these optimizations will only significantly speed up the line drawing algorithm ... Bresenham's circle algorithm ... ...
Read more

Bresenham's Line Algorithm - RogueBasin

Bresenham's Line Algorithm is a way of drawing a line segment onto a ... """Bresenham's Line Algorithm Produces a list of tuples from start and end ...
Read more

Bresenham-Algorithmus – Wikipedia

Der originale Ansatz nach Bresenham (s. u.) geht übrigens mehr geometrisch vor, ... Bresenham’s algorithm (NIST Dictionary of Algorithms and Data ...
Read more