advertisement

# Bresenham’s Circle drawing algorithm

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

Published on May 18, 2012

Author: sanuphilip

Source: authorstream.com

advertisement

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

 User name: Comment:

October 18, 2017

October 18, 2017

October 18, 2017

October 18, 2017

October 18, 2017

October 18, 2017

## 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 ﬁrst octant of a circle, ...
Read more

### Bresenham's Line and Circle Algorithms - GameDev.net

Above all remember that these optimizations will only significantly speed up the line drawing algorithm ... Bresenham's circle algorithm ... GameDev.net ...
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