CAD Lab Manual Department of Mechanical Engineering, SVPCET, Nagpur

Experiment No.6

Title: Write and study Bresenham’s mid point ellipse generation algorithm and it’s c program.

1. Bresenham’s Mid Point Ellipse Generation Algorithm

Mathematical Analysis

Ellipse is another important geometric entity. It is a symmetric entity about its major axis and
minor axis. Figure 1 shows an origin centered ellipse divided into 4 parts. This property of
ellipse (symmetric about its major axis and minor axis) can be used in generation of ellipse with
minimum codes. Out of the four parts shown in Fig. 1, only first part is to be generated,
remaining three fourth part is generated by using the symmetry of ellipse. Generation starts from
point (0, Ry) where Ry is semi-minor axis of the ellipse.

Fig.1 Use of symmetry of ellipse for ellipse generation

Figure 2 shows two parts of a quarter ellipse. If a tangent is drawn to part 1 then the absolute
slope of the tangent would be less than one. Similarly if a tangent is drawn to the part 2, then the
absolute slope of the tangent would be greater than one. This indicates that the arc of part 1 is
more horizontal than part 2 whereas arc of part 2 is more vertical than part 1. But slope of
tangent would be equal to one at point where part 1 and part 2 meets (point m). Hence generation
of ellipse starts from point (0, Ry) and ends at point m. The condition at point m is derived in
equation (2.39a).

BEME703P CAD Laboratory | 1

 CAD Lab Manual Department of Mechanical Engineering, SVPCET, Nagpur

Fig. 2 Slope of the tangents to the two parts of ellipse

or

Differentiate Eq. (2.39) w. r. t. x and y, we get

BEME703P CAD Laboratory | 2

 CAD Lab Manual Department of Mechanical Engineering, SVPCET, Nagpur

Mathematical Analysis for generation of ellipse in part (1)

Figure 3 shows part 1 of a quarter ellipse. As discussed in previous topic, that if a tangent is
drawn to part 1 then the absolute slope of the tangent would be less than one or the arc of part 1
is more horizontal. So, the value of x coordinate will be incremented by one in every step and y
coordinate needs to be calculated. The value of Y coordinate is calculated depending upon the
position of midpoint of two successive vertical points. Two cases are discussed below from
which Fig.4 shows position of mid point is outside the ellipse and Fig. 5 shows position of mid
point is inside the ellipse.

Fig. 3 Position of the arc of ellipse on grid

Fig. 4 Mid point outside the ellipse

BEME703P CAD Laboratory | 3

 CAD Lab Manual Department of Mechanical Engineering, SVPCET, Nagpur

Fig. 5 Mid point inside the ellipse

Equation of ellipse

if then point is inside the ellipse

else then point is outside the ellipse

Let be the decision parameter of ith point

Coordinates of the mid point

Put the values in Eq. (2.40)

Decision parameter of (i+1)thpixel is given by

Finding difference of decision parameters by Eq. (2.42) – Eq. (2.31)

BEME703P CAD Laboratory | 4

 CAD Lab Manual Department of Mechanical Engineering, SVPCET, Nagpur

If mid point is inside the ellipse then

Put these values in Eq. (2.43)

Else mid point is outside the circle then

Put these values in Eq. (2.43)

For finding the start point decision parameter

Coordinates of start point , put these values in Eq

BEME703P CAD Laboratory | 5

 CAD Lab Manual Department of Mechanical Engineering, SVPCET, Nagpur

Mathematical Analysis for the generation of ellipse in part (2)

Figure 6 shows part 2 of a quarter ellipse. As discussed in previous topic, that if a tangent is
drawn to part 2 then the absolute slope of the tangent would be greater than one or the arc of
part 2 is more vertical. So, the value of y coordinate will be incremented by one in every step and
x coordinate needs to be calculated. The value of x coordinate is calculated depending upon the
position of midpoint of two successive horizontal points. Two cases are discussed below from
which Fig. 7 shows position of mid point is inside the ellipse and Fig. 8 shows position of mid
point is outside the ellipse.

Fig. 6 Position of the arc of ellipse on grid

Fig.7 Mid point inside the ellipse

BEME703P CAD Laboratory | 6

 CAD Lab Manual Department of Mechanical Engineering, SVPCET, Nagpur

Fig. 8 Mid point outside the ellipse

Equation of ellipse

if then point is inside the ellipse

else then point is outside the ellipse

Let be the decision parameter of ith point

Coordinates of the mid point

Put the values in Eq. (2.47)

Decision parameter of (i+1)thpixel is given by

Finding difference of decision parameters by Eq. (2.49) – Eq. (2.48)

BEME703P CAD Laboratory | 7

 CAD Lab Manual Department of Mechanical Engineering, SVPCET, Nagpur

If mid point is inside the ellipse then

Put these values in Eq (2.50)

Else mid point is outside the circle then

Put these values in eq. (2.50)

For finding the start point decision parameter

Coordinates of start point , put these values in Eq

BEME703P CAD Laboratory | 8

 CAD Lab Manual Department of Mechanical Engineering, SVPCET, Nagpur

Mid pointellipse generation algorithm

STEP 1: [DECLARATION OF VARIABLES]

int center point coordinates of ellipse

int (x,y) coordinates of current pixel representing line
int semi-major and semi-minor axis of ellipse
int p decision parameter

STEP 2: [INITIALIZATION]

Read
Read

STEP 3: [PLOTTING PIXEL FOR ELLIPSE]

Plotting part (1) of ellipse (m<1)

x=0
y=

loop,
put pixel ( x, y)
if

else

BEME703P CAD Laboratory | 9

 CAD Lab Manual Department of Mechanical Engineering, SVPCET, Nagpur

Continue loop till ( )

Plotting part (2) of ellipse (m>=1)

x=
y=0

loop,
put pixel ( x, y)

if

else

Continue loop till ( )

STEP 3: [PLOT CIRCLE FUNCTION]

plot ellipse (x, y, )

put pixel
put pixel
put pixel
put pixel

STEP 4: [STOP]

BEME703P CAD Laboratory | 10

 CAD Lab Manual Department of Mechanical Engineering, SVPCET, Nagpur

/* PROGRAM FOR ELLIPSE GENERATION USING BRESENHAM’S MID POINT

ELLIPSE GENERATION ALGORITHM */

#include<graphics.h>
#include<math.h>
#include<stdio.h>
#include<conio.h>
void main()
{
int rx,ry,xc,yc,x1,y1,x2,y2,p1,p2,i,j;
int gd=DETECT,gm;
initgraph(&gd,&gm,"c:\\tc\\bgi");
printf("enter the center of the ellipse");
scanf("%d%d",&xc,&yc);
printf("enter semi_major and semi_minor axis");
scanf("%d%d",&rx,&ry);
x1=0;
y1=ry;
p1=(ry^2-ry*rx^2);
for(i=0;x1*ry^2<y1*rx^2;i++)
{
if(p1<0)
{
x1=x1+1;
y1=y1;
p1=p1+(2*x1+3)*ry^2;
}
else
{
x1=x1+1;
y1=y1-1;
p1=p1+(2*x1+3)*ry^2+(2-2*y1)*rx^2;
}
putpixel(x1+xc,y1+yc,1);
putpixel(-x1+xc,y1+yc,1);
putpixel(x1+xc,-y1+yc,1);
putpixel(-x1+xc,-y1+yc,1);
}
x2=rx;
y2=0;

BEME703P CAD Laboratory | 11

 CAD Lab Manual Department of Mechanical Engineering, SVPCET, Nagpur

p2=rx^2-rx*ry^2;
for(j=0;x2*ry^2>y2*rx^2;j++)
{
if(p2<0)
{
x2=x2;
y2=y2+1;
p2=p2+(2*y2+3)*rx^2;
}
else
{
x2=x2-1;
y2=y2+1;
p2=p2+(2*y2+3)*rx^2-(2*x2-2)*ry^2;
}
putpixel(x2+xc,y2+yc,1);
putpixel(-x2+xc,y2+yc,1);
putpixel(x2+xc,-y2+yc,1);
putpixel(-x2+xc,-y2+yc,1);
}
getch();
}

4. Problem

Generate ellipse using Bresenham’smid point algorithm with center of ellipse (15, 17)
& .

SOLUTION:

BEME703P CAD Laboratory | 12

 CAD Lab Manual Department of Mechanical Engineering, SVPCET, Nagpur

Raster Screen:

Result: Thus Bresenham’s mid point ellipse generation technique and its c program is studied.

BEME703P CAD Laboratory | 13