More info

Tuesday, 18 February 2014

Computer Graphics Notes - Lab 13 - Bresenham's Circle Drawing Algorithm

BRESENHAWTS CIRCLE DRAWING ALGORITHM

The Bresenham's circle drawing algorithm considers the eight-way symmetry of the circle to generate. It plots 1/8th part of the circle, i.e. 90° to 45°, a shown in the figure below. As circle is drawn from 90° to 45°, the x moves in positive direction and y moves in the negative direction.



To achieve best approximation to the true circle we have to select those pixels in the raster that fall the least distance from the true circle.








Let us observe the 90° to 45° portion of the circle. It can be noticed that if points are generated from 90° to 45°, each new point closest to the true circle can be found by applying either of the two options:

     Increment in positive x direction by one unit or
     Increment in positive x direction and negative y direction both by one unit

Let us assume point P (xk, yk) in the above fig as a last converted pixel. Now we have two options either to choose pixel A (xk + 1, yk) or pixel B (xk+ 1, yk-1). The closer pixel amongst these two can be determined as follows:

The distances of pixels A and B from the origin are given as DA = √((xk+1)2 + yk2)
DB= √ (xk+1)2 + (yk-1)2)
Now, the distances of pixels A and B from the true circle are given as

δA = DA - r
δB = -(r -DB) =  DB - r

However, to avoid square root term in derivation of decision variable, i.e. to simplify the computation and make algorithm more efficient the δA and δB are defined as
δA = DA2 - r2
δB = DB2 - r2

We can observe from the figure that δA is always positive and δB always negative. Therefore, we can define decision variable dk as
dk = δA + δB
    = 2(xk+1)2+yk2+(yk-1)2 -2r2
and we can say that, if dk < 0. i.e., δA < δB then only x is incremented by 1 unit: otherwise x is incremented by 1 unit and y is decremented by 1 unit.
For dk < 0, xk+1 = xk + 1 and yk+1 = yk
For dk ≥ 0, xk+1 = xk + 1 and yk+1 = yk -1
dk+1 = 2(xk+1 + 1)2 + yk+12+ (yk+1 - 1)2 - 2r2
dk+1 - dk = 2(xk+1 + 1)2+ yk+12+ (yk+1- 1)2 -2(xk+ 1)2- yk2- (yk- 1)2
xk+i = xk + 1 in all cases
dk+1 = dk + 2(xk +2)2 + yk+12 + (yk+1 -1)2 - 2(xk +1)2 - yk2 - (yk-1)2
= dk + 2xk2 + 8xk + 8 + yk+12 + (yk+1 – 1)2 - 2xk2 - 4xk - 2 - yk2 -(yk - 1)2
= dk + 4xk + 6 + yk+12 + (yk+1 - 1 )2 - yk2 - (yk- 1 )2
= dk + 4xk + 6 + yk+12 + y2 k+1 - 2yk+1 +1 - yk2 - yk2 + 2yk - 1
= dk+ 4xk + 6 +2(yk+12- yk2) - 2(yk+1 - yk)

For dk < 0, dk+1 = dk + 4xk + 6

For dk ≥ 0, dk+1 = dk + 4xk + 6+ 2((yk -1 )2- yk2)) - 2(yk -1 - yk) = dk + 4xk + 6+ 2(yk2 -2yk +1 - yk2)) + 2
= dk + 4xk + 8 - 4yk + 2
= dk + 4xk - 4yk + 10
= dk + 4(xk-yk) +10

The equation for dk at starting point i.e. at x = 0 and y = r can be simplified as follows
d0 = 2(0+1)2 + r2 + (r-1)2 - 2r2
= 2 + r2 + r2 - 2r + 1 – 2r2
= 3 - 2r
Algorithm to plot 1/8th of the circle
1.     Read the radius (r) of the circle.
2.     d = 3-2r
3.     x = 0, y = r
4.     do
{
plot(x, y) if(d<0)then
{
d = d + 4x + 6
}
else
{
d = d + 4(x-y) + 10 y = y-1
}
x = x+ 1
} while (x < y)

5.     Stop

No comments:

Post a Comment