Mumbai university > Comp > SEM 4 > Computer Graphics

Marks: 10M

Year: Dec 2014,Dec 2015 , May 2014

Assuming that we have just plotted the pixels at $(X_i, Y_i)$

Which is next ? $(X_i+1, Y_i)$ OR $(X_i+1, Y_i – 1)$.

The one that is closer to the circle.

The decision parameter is the circle at the midpoint between the pixels Yi and Yi – 1.

$$p_i = f_{circle}(x_i + 1 , y_i - \frac{1}{2})$$

$$ = (x_i +1)^2 + (y_i - \frac{1}{2})^2 - r^2$$

If pi< 0, the midpoint is inside the circle and the pixel Yi is closer to the circle boundary.

If pi ≥ 0, the midpoint is outside the circle and the pixel Yi - 1 is closer to the circle boundary.

Mid-point circle algorithm:

1. Accept the radius ‘r’ and circle center $(X_c, Y_c)$ from user and plot 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 = 1 - r$.

3. If we are using octant symmetry property to plot the pixels, then until (X < Y) we have to perform following steps.

If $P_k \lt 0$ then

Modify $P_k \ \ as \ \ P_k = P_k + 2X + 1$ and

Then increase X by 1

Otherwise

Modify $P_k \ \ as \ \ P_k = P_k + 2(X – Y) + 1$ and

Increase X by 1

And decrease X by 1.

1. Determine the symmetry points in other octants also and

2. Move each calculated pixel position (X, Y) on to the circular path centered on $(X_c, Y_c)$ and plot the co-ordinates values as $X = X + X_c$ and $Y = Y + Y_c$

[Note: Because we have derived all formulas by considering center point as origin i.e. (0, 0). But actually the center point may be anything, so we have to add that center co-ordinates to midpoint X and Y to plot the point.]

Example:

Plot a circle whose radius is 10.

Let center co-ordinates be (0, 0).

Therefore r = 10, $X_c$ = 0 and $Y_c$ = 0.

Now plot the 1st point as (0, r) i.e. Y = r, Therefore Plot (0, 10)

Likewise find out other points from (0, 10) by using symmetry property.

So Plot (10, 0)

Plot (0, -10)

Plot (-10, 0)

Find P = 1 – r, Therefore P = 1 – 10 = -9

Till (X < Y) we have to perform following

If (P < 0)

In this case P = -9

So we have to increase X by 1 and modify P as P = P + 2X + 1

I.e. P = -9 + 2 (0) + 1 = -8

Here we are not increasing Y. Therefore Plot (X + 1, Y)

I.e. Plot (1, 10)

Again continuing this process we will get following table. Then plot the co-ordinates of this table by using symmetry property as shown in figure 9.