As in the raster line algorithm, we sample at unit intervals and determine the closest pixel position to the specified circle path at each step.
For a given radius r and screen center position ( x , y,), we can first set up our algorithm to calculatepixel positions around a circle path centered at the coordinate origin (0,0)Theneach calculated position (x, y) is moved to its proper screen position by adding x,to x and y, toy.
Along the circle section from x = 0 to x = y in the first quadrant,the slope of the curve varies from 0 to -1.
Therefore, we can take unit steps in the positive x direction over this octant and use a decision parameter to determine which of the two possible y positions is closer to the circle path at each step.
Positions of the other seven octants are then obtained by symmetry.
To apply the midpoint method, we define a circle function:
$f_{circle}(x,y) = x^2 + y^2 - r^2$
Any point (x, y) on the boundary of the circle with radius r satisfies the equation $f_{circle}(x, y) = 0$. If the point is in the interior of the circle, the circle function is negative.
And if the point is outside the circle, the circle function is positive. To summarize, the relative position of any point (x. v) can be determined by checking the sign of the circle function:
The circle-function tests are performed for the mid-positions between pixels near the circle path at each sampling step.
Thus, the circle function is the decision parameter in the midpoint algorithm, and we can set up incremental calculations for this function as we did in the line algorithm.
If p_k<0, this mid-point is inside the circle and the pixel on scan line $y_b$ is closer to the circle boundary.
Otherwise, the mid-position is outside or on the circle boundary, and we select the pixel on scan line $y_b - 1$.
Successive decision parameters are obtained using incremental calculations.
We obtain a recursive expression for the next decision parameter by evaluating the circle function at sampling position $x_{k+1}+1 = x, + 2:$
$$P_{k + 1} = f_{circle}(x_{k + 1} + 1 , y_{k + 1} - \frac{1}{2})$$
$$ = [(x_k +1) + 1]^2 + (y_{k +1} - \frac{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}$ are either $2x_{k+1} + 1$ or $2x_{k+1} + 1 - 2y_{k+1}$.
Evaluation of the terms $2x_{k+1}$ and $2y_{k+1}$ can also bedone incrementallyas
$$2x_{k + 1} = 2x_k + 2$$
$$2y_{k + 1} = 2y_k - 2$$
At the start position (0, T), these two terms have the values 0 and 2r, respectively.
Each successive value is obtained by adding 2 to the previous value of 2x and subtracting 2 from the previous value of 5.
The initial decision parameter is obtained by evaluating the circle function at the start position $(x_0,y_0) = (0, r):$
$$P_0 = f_{circle} (1 , r - \frac{1}{2})$$
$$ = 1 + (r - \frac{1}{2})^2 - r^2$$
If the radius r is specified as an integer, we can simply round $p_0$ to
$$P_0 = 1 - r $$ (for r an integer)
Since all increments are integers.
As in Bresenham's line algorithm, the midpoint method calculates pixel positions along the circumference of a circle using integer additions and subtractions, assuming that the circle parameters are specified in integer screen coordinate.
We can summarize the steps in the midpoint circle algorithm as follows
Midpoint Circle Algorithm:
Input radius r and circle center (x, y,), and obtain the first point on the circumference of a circle centered on the origin as
$(x_0,y_0) = (0, r):$
Calculate the initial value of the decision parameter as
$P_0 = \frac{5}{4} - r$
At each $x_k$ position, starting at k = 0, perform the following test: If $p_k \lt 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$
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}$
Determine symmetry points in the other seven octants. Move each calculated pixel position (x, y) onto the circular path centered on $(x_c,yc)$ and plot the coordinate values:
$ x = x + x_c , y = y + y_c$
Repeat steps 3 through 5 until x r y.
and 4 others joined a min ago.
teamques10
★ 68k