Page 53 - DCAP504_Computer Graphics

Computer Graphics

Midpoint Circle Drawing Algorithm
The midpoint circle drawing algorithm also uses the eight-way symmetry of the circle. An implicit
representation of a function is used for the comparable elements of Bresenham’s midpoint algorithm for
circles. The function is as follows:
F(x, y) = x2 +y2 −R2 = 0
Note that the function is positive for the points outside the circle (or above the arc) and is negative for
the points inside the circle (or under the arc).
Assume that we have drawn pixel ((xp, yp), and we must select the next pixel to draw (drawing
−
clockwise around the boundary). Since the slope of the circular arc is between 0 and 1, our choice at
each step is between the neighbor to the east E and the neighbor to the southeast SE. If the circle passes
above the midpoint M, then either we go to E next or go to SE.

Figure 4.5: Midpoint Algorithm for Circle

Next, we need a decision variable. We take this to be the value of F (M), which is

D = F (M) = F (xp + 1, yp −1/2)
D = (xp+ 1)2 + (yp −1/2)2 −R2
If D < 0, then M is below the arc. Hence, the E pixel is closer to the line. On the other hand, if D _ 0 then
M is above the arc, so the SE pixel is closer to the line.
Again, the new value of D will depend on our choice.

We go to E next: Then the next midpoint would have the coordinates (xp+2, yp (1=2)) and hence the
−
new D value would be:
Dnew = F (xp + 2, yp −1/2)
Dnew = (xp+ 2) 2 + (yp −1/2)2 −R2
Dnew = (x2p+ 4xp + 4) + (yp −1/2)2 −R2

Dnew = (x2p+ 2xp + 1) + (2xp + 3) + (yp −1/2)2 −R2
Dnew = (xp+ 1) 2 + (2xp + 3) + (yp −1/2)22 −R2= D+ (2xp + 3):
Thus, the new value of D would be the current value + (2xp + 3).
We go to NE next: Then the next midpoint would have coordinates (xp + 2, Syp − 1 − (1=2)) and hence
the new D value would be:

46 LOVELY PROFESSIONAL UNIVERSITY