Page 52 - DCAP504_Computer Graphics

Unit 4: Scan Conversion I

If Δ < 0, then the diagonal point is inside the circle, i.e. select one of the two point (X k+1, Y k) or (X k+1, Y
k-1), the one which is closer to the circle boundary. For this, the midpoint between these two points is
checked i.e.
Pk = (Xk + 1) 2 + (Y k — 1/2) 2 - R2
If Pk > 0, this midpoint is outside the circle and the pixel on the scan line Yk-1 is closer to the circle
boundary. If not the mid position is inside or on the circle boundary (Pk ≤ 0) and we select the pixel on
scan line Yk.
Similarly, If Δ > 0, then the diagonal point is outside the circle, i.e. we have to select one of the two point
(Xk+1, Y k-1) and (Xk, Y k-1), the one which is closer to the circle boundary. For this, once again we
check for the midpoint between these two points, i.e.,
Pk = (Xk + 1/2) 2 + (Y k-1) 2 - R2
If Pk > 0, this midpoint is outside the circle and the pixel (Xk, Y k-1) is selected. Otherwise the mid-
position is inside or on the circle boundary (Pk < 0) and we select the pixel (Xk, Y k-1).

If Δ = 0
Pixel (Xk+1, Y k-1) is selected.
Bresenham’s Midpoint Circle Algorithm for the First Quadrant is as follows:
Initialize the variables, Xk = 0 and Yk = R. Also, D = (Xk +1)2 + (Yk – 1)2 - R2
1. setpixel (Xk , Yk)
If Yk ≤ 0 then step 7

If D < 0 then step 2
If D > 0 then step 3
If D = 0 then step 5
2. Pk = (Xk +1)2 + (Yk – 1/2)2 - R2
If Pk ≤ 0 then step 4
If Pk > 0 then step 5

3. Pk = (Xk +1/2)2 + (Yk – 1)2 - R2
If Pk ≤ 0 then step 5
If Pk > 0 then step 6
4. Xk = Xk +1
D = D + 2 Xk + 1
goto step 1
5. Xk = Xk +1
Yk = Yk +1

D = D + 2 Xk - 2 Yk + 2
goto step 1
6. Yk = Yk - 1
D = D - 2 Yk + 1
goto step 1
7. Finish

LOVELY PROFESSIONAL UNIVERSITY 45