Scan-Converting Circles

+


Scan-Converting Circles
Since the circle is a frequently used component in pictures and graphs, a procedure for generating either full circles or circular arcs is included in most graphics packages.
A circle is defined as the set of points that are all at a given distance r from a center position (x, y) This distance relationship is expressed in Cartesian coordinates as:
x 2 + y 2 = r2
Because of the high symmetry of the circle, it is possible to scan-convert it in many ways.






Algorithm 1: Circle using Cartesian equation
Inputs: (x, y) circle center , R the radios
Begin
for x=0 to R do
y=sqrt(R*R - x*x )
plot(x,y), plot(-x,y), plot(x,-y), plot(-x,-y)
end

The method is slow, but a more important drawback is that the pixels are not uniformly distributed over the quarter circle. This is a result of the equal x increments of the loop figure below:








The next obvious method solves this problem. Another way to eliminate the unequal spacing shown in Figure above by employing the parametric equation x = Rcos ?, y = Rsin ?, which expresses the circle in terms of polar coordinates.
Algorithm 2: Circle using Polar Coordinate
Inputs: (x, y) circle , R radios
Begin
for theta=0 to 90 do
x = R*cos(theta), y = R*sin(theta)
plot(x,y), plot(-x,y)
plot(x,-y), plot(-x,-y)
end

This method is still very inefficient because of the use of trigonometric functions and also because some pixels may be set multiple times.


Bresenham Circle Method
The Bresenham circle method is based on a loop that starts at point (0,R) and ends at point (R/?2,R/?2) to create one octant of the circle. Each pixel calculated is used to determine seven more pixels, in the remaining seven octants, to create the complete circle. To move from (0,R) to (R/?2,R/?2), we need to increment x and decrement y. The loop of figure below is set such that the x coordinate is incremented in every step, but the y coordinate is only decremented in certain steps (i.e., conditionally). The results are good (i.e., the pixels are fairly uniformly distributed) because in this octant the circle is close to horizontal.

In each step (except the first), the algorithm examines two points, S and T in figure, that differ only in their y coordinates, and it selects the one that’s closer to the true circle.
For simplicity, we translate the center of circle to (0, 0).
The algorithm maintains a variable di (calculated using just additions, subtractions, and shifts) that is updated every step. The sign of di is used as an indicator, telling the program whether to decrement y at the step or not. The general form of the loop is as in figure .
x = 0, y = R
while x < y do
Plot( x , y )
…..
if d > 0 then
…..
y = y – 1
else
.....
End if
x = x + 1
end while

If a point Pi?1 = (xi?1, yi?1) has been selected in a certain step, then the next step should increment x from xi?1 to xi?1 + 1 and either set yi = yi?1 or decrement yi = yi?1 ? 1. The next step should therefore select either point Si = (xi?1 + 1, yi?1) or Ti = (xi?1 + 1, yi?1 ? 1).
The only remaining detail is the recalculation of di in each iteration. It turns out that calculating di+1 is very simple if it is done in terms of di. This, in fact, is the main advantage of the method.
If di > 0 (point T selected), then yi = yi?1 ? 1

If, however, di < 0 (point S selected), then yi = yi?1

We already know that xi always equals xi?1 + 1
Hence, updating the value of di in either case is simple and does not require any arithmetic operations beyond addition, subtraction, and shifting.
The initial value of di, namely d1, is easily found by substituting (xi?1, yi?1) = (0,R). This gives
d1 = 3? 2R.
The final algorithm is shown below:
Algorithm 3: Bresenham circle
Inputs: (x, y) circle , R radios
Begin
x=0, y=R, d= 3 – 2 * R
while x < y do
Procedure CirclePoints (xc,yc,x,y)
if d > 0 then
d = d + 4 * ( x – y ) + 10
y = y – 1
else
d = d + 4 * x + 6
end if
x = x + 1
end while
if x=y then Procedure CirclePoints (xc,yc,x,y)

end

To calculate the value of x , y in the eighth octants, we need to use the symmetry property of circle as in figure:

Figure : symmetry of a circle. Calculation of a circle point (x,y) in one octant yields the circle points shown for the other seven octants.



That will write as :
*Procedure CirclePoints (xc,yc,x,y)
{ PSet (xc + x, yc + y,color).
PSet (xc + x, yc - y,color).
PSet (xc + y, yc + x,color).
PSet (xc - y, yc + x,color).
PSet (xc - x, yc + y,color).
PSet (xc - x, yc - y,color).
PSet (xc - y, yc - x,color).
PSet (xc + y, yc - x,color).
} Finally, we must return the circle to the origin center by increase xc to x and decrease yc from y.