Computer Graphics
Dr.S.Sivakumar,Principal
C.P.A College, Bodinayakanur
*
1
Circle drawing algorithms
Where do we draw a circle???
Properties of a circle:
(x – xc)2 + (y – yc) 2 = r2
y = yc +(- ) (r2 – (xc –x )2)1/2
Circle Generation
But, how many lines do
we need for an acceptable
representation?
How do we determine end
points of lines?
Polar co-ordinates for a circle
x = xc + r cosθ y = yc + r sinθ
A Simple Circle Drawing Algorithm
A Simple Circle Drawing Algorithm (cont…)
A Simple Circle Drawing Algorithm (cont…)
Eight-Way Symmetry
(x, y)
(y, x)
(y, -x)
(x, -y)
(-x, -y)
(-y, -x)
(-y, x)
(-x, y)
Mid-Point Circle Algorithm
The mid-point circle algorithm was developed by Jack Bresenham, who we heard about earlier. Bresenham’s patent for the algorithm can be viewed here.
Mid-Point Circle Algorithm (cont…)
(xk+1, yk)
(xk+1, yk-1)
(xk, yk)
Mid-Point Circle Algorithm (cont…)
Mid-Point Circle Algorithm (cont…)
Midpoint Circle Drawing Algorithm
Midpoint Circle Drawing Algorithm
Midpoint Circle Drawing Algorithm
fcircle (x,y) = x2 + y2 –r2
> 0, (x,y) outside the circle
< 0, (x,y) inside the circle
= 0, (x,y) is on the circle boundary
{
fcircle (x,y) =
The Mid-Point Circle Algorithm
The Mid-Point Circle Algorithm (cont…)
Midpoint Circle Drawing Algorithm
Example:
Given a circle radius = 10, determine the circle octant in the first octant from x=0 to x=y.
Solution:
f0 = 5 – r
4
= 5 – 10
4
= -8.75
≈ –9
Midpoint Circle Drawing Algorithm
k | Fk | x | y | 2xk+1 | 2yk+1 |
0 | -9 | 1 | 10 | 2 | 20 |
1 | -9+2+1=-6 | 2 | 10 | 4 | 20 |
2 | -6+4+1=-1 | 3 | 10 | 6 | 20 |
3 | -1+6+1=6 | 4 | 9 | 8 | 18 |
4 | 6+8+1-18=-3 | 5 | 9 | 10 | 18 |
5 | -3+10+1=8 | 6 | 8 | 12 | 16 |
6 | 8+12+1-16=5 | 7 | 7 | 14 | 14 |
Initial (x0, y0) = (1,10)
Decision parameters are: 2x0 = 2, 2y0 = 20
Midpoint Circle Drawing Algorithm
void circleMidpoint(int xCenter, int yCenter, int radius)
{
int x = 0;
Int y = radius;
int f = 1 – radius;
circlePlotPoints(xCenter, yCenter, x, y);
while (x < y) {
x++;
if (f < 0)
f += 2*x + 1;
else {
y--;
f += 2*(x-y)+1;
}
circlePlotPoints(xCenter, yCenter, x, y);
}
}
Midpoint Circle Drawing Algorithm
void circlePlotPoints( int xCenter, int yCenter,
int x, int y)
{
setPixel (xCenter + x, yCenter + y);
setPixel (xCenter – x, yCenter + y);
setPixel (xCenter + x, yCenter – y);
setPixel (xCenter – x, yCenter – y);
setPixel (xCenter + y, yCenter + x);
setPixel (xCenter – y, yCenter + x);
setPixel (xCenter + y, yCenter – x);
setPixel (xCenter – y, yCenter – x);
}
Mid-Point Circle Algorithm Example
Mid-Point Circle Algorithm Example (cont…)
9
7
6
5
4
3
2
1
0
8
9
7
6
5
4
3
2
1
0
8
10
10
k | pk | (xk+1,yk+1) | 2xk+1 | 2yk+1 |
0 1 2 3 4 5 6 | | | | |
Mid-Point Circle Algorithm Exercise
Mid-Point Circle Algorithm Summary
(x,y)
(x,-y)
(-x,-y)
(-x,y)
(-y,-x)
(y,-x)
(y,x)
(-y,x)
Midpoint Circle Algorithm
�� select which of 2 pixels, (xk+1,yk) or (xk+1,yk-1)� are closer to the circle� by evaluating the circle function at the midpoint.
x
y
where yk+1 is either yk or yk–1 depending on the sign of pk.
if pk < 0 pk+1 = pk+ 2xk + 3
if pk ≥ 0 pk+1 = pk+ 2xk – 2yk + 5
computing p0 at (x0,y0) = (0,r)
if r is integer p0 = 1–r
Midpoint Circle Algorithm
Input: radius r and circle center (xc,yc)
draw(0+xc,r+yc) (add xc and yc before plotting)
pk←1–r; xk←0; yk←r;
while xk<yk
if pk < 0 choose yk
yk+1←yk; pk+1←pk+2xk+3
else choose yk –1
yk+1←yk–1; pk+1←pk + 2xk – 2yk + 5
xk+1←xk+1
draw (xk+1+xc,yk+1+yc)
xk←xk+1; yk←yk+1;
pk←pk+1
if pk < 0 choose yk
yk+1←yk; pk+1←pk+2xk+3
else choose yk –1
yk+1←yk–1; pk+1←pk + 2xk – 2yk + 5
Bresenham's to Midpoint
Midpoint Circle Algorithm
fcircle(x,y) = x2 + y2 – r2
Midpoint Circle Algorithm
yk
Yk-1
xk
xk+1
Xk+3
Midpoint
X2+y2-r2=0
Midpoint between candidate pixels at sampling position xk+1 along a circular path
Midpoint Circle Algorithm
pk = fcircle (xk +1, yk-1/2) = (xk +1)2 + (yk -1/2)2 – r2
If pk < 0 , this midpoint is inside the circle and the pixel on the scan line yk is closer to the circle boundary. Otherwise, the
mid position is outside or on the circle boundary, and we select the pixel on the scan line yk-1
Midpoint Circle Algorithm
Pk+1 = fcircle(xk+1+1, yk+1-1/2)
= [(xk+1)+1]2 + (yk+1 -1/2)2 –r2
OR
Pk+1 = Pk+2(xK+1) + (yK+12 – yk2) – (yk+1- yk)+1
Where yk+1 is either yk or yk-1, depending on the sign of pk
2xk+1+1 if pk is negative
2xk+1+1-2yk+1 otherwise
Midpoint circle algorithm
2xk+1 = 2xk +2
2 yk+1 = 2yk – 2
p0 = fcircle(1, r-1/2) = 1+ (r-1/2)2-r2
OR
P0 = 5/4 -r
p0 = 1-r
The actual algorithm
1: Input radius r and circle center (xc,yc) and obtain the first point on the circumference of the circle centered on the origin as
(x0,y0) = (0,r)
2: Calculate the initial value of the decision parameter as
P0 = 5/4 - r
3: At each xk position starting at k = 0 , perform the following test:
If pk < 0 , the next point along the circle centered on (0,0) is (xk+1, yk) and
pk+1 = pk + 2xk+1 + 1
The algorithm
Otherwise the next point along the circle is (xk+1, yk-1) and
pk+1 = pk + 2xk+1 +1 -2yk+1
Where 2xk+1 = 2xk+2 and 2yk+1 = 2yk-2
4: Determine symmetry points in the other seven octants
5: Move each calculated pixel position (x,y) onto the circular path centered on (x,yc) and plot the coordinate values
x = x+ xc , y= y+ yc
6: Repeat steps 3 through 5 until x >= y
Circle Algorithms
Circle Algorithms
Circle Algorithms
Curve Functions
Midpoint Ellipse
Midpoint Ellipse Algorithm
Midpoint Ellipse..
with
and continue until
Midpoint Ellipse Contd.
where is the last position calculated in region 1
Midpoint Ellipse