1.1 Basic concept in line drawing :Line drawing algorithm:-DDA digital differential analyzer algorithm,Bresenham’s algorithm.

2.2 Circle generation Algorithms:- Symmetry of circle,Bresenham’s circle drawing algorithm

2.3 Polygon: Types of polygon,inside and outside test,polygon filling:seed fill algorithm:flood fill ,boundary fill,scan line algorithms.
2.4 Scan conversion,frame buffers.
2.5 .Character Generation methods:Stoke,Starburst,bitmap

1.1 Basic Concepts in line drawing

1.Line is Straight object with no curves,no thickness and it extends in both directions without end.if it doesn't end it is called a line
segment.
2.A vector is a quantity having direction as well as magnitude, especially as determining the position of one point in space relative to
another.
3.The process of ‘turning on’ the pixel for a line segment is called Vector generation or line generation and the algorithms or line drawing
algorithm.

Problems of vector generation

1.The 45 Degree line is straight but its width is not constant.
2.The line with any other orientation is neither straight nor has the same width.Such cases are due to the finite resolution of display.
3.The brightness of the line is dependent on the orientation of the line.
4.we can observe that the effective spacing between pixels for the 45 degree line is greater than for the vertical and horizontal lines
appear brighter than the 45 degree line.
4.Complex calculations are required to provide equal brightness along lines of varying length and orientation .
5.Therefore, to draw line rapidly some compromises are made such as.
1.calculate only an approximation line length.
2.Reduce the calculation using simple integer arithmetic.
3.implement result in hardware and firmware.
1.Line Generation.

DDA Line generation Algorithm in Computer Graphics

1.In computer graphics, a digital differential analyzer (DDA) is hardware or software used for
interpolation of variables over an interval between start and end point. DDAs are used for
rasterization of lines, triangles and polygons
2.In any 2-Dimensional plane if we connect two points (x0, y0) and (x1, y1), we get a line
segment.
3.In the case of computer graphics we can not directly join any two coordinate points, for that
we should calculate intermediate points coordinate and put a pixel for each intermediate
point, of the desired color
4.With the help of functions like putpixel(x, y, K) in C, where (x,y) is our co-ordinate and K denotes some color.
5.For using graphics functions, our system output screen is treated as a coordinate system where the coordinates of the top-left corner is
(0, 0) and as we move down our y-ordinate increases and as we move right our x-ordinate increases for any point (x, y).
6.Now, for generating any line segment we need intermediate points and for calculating them we can use a basic algorithm called
DDA(Digital differential analyzer) line generating algorithm.

DDA Algorithm:
1 Step : Consider one point of the line as (X0,Y0) and the second point of the line as (X1,Y1).

2 step:// calculate dx , dy
dx = X1 - X0;
dy = Y1 - Y0;

3 Step // Depending upon absolute value of dx & dy

// choose number of steps to put pixel as
// steps = abs(dx) > abs(dy) ? abs(dx) : abs(dy)
steps = abs(dx) > abs(dy) ? abs(dx) : abs(dy);

4 Step: // calculate increment in x & y for each step

Xinc = dx / (float) steps;
Yinc = dy / (float) steps;
5 Step: // Put pixel for each step
X = X0;
Y = Y0;
for (int i = 0; i <= steps; i++)
{
putpixel (X,Y,WHITE);
X += Xinc;
Y += Yinc;
}

// C program for DDA line generation

#include<stdio.h>
#include<graphics.h>

//Function for finding absolute value

int abs (int n)
{
return ( (n>0) ? n : ( n * (-1)));
}

//DDA Function for line generation

void DDA(int X0, int Y0, int X1, int Y1)
{
// calculate dx & dy
int dx = X1 - X0;
int dy = Y1 - Y0;

// calculate steps required for generating pixels

int steps = abs(dx) > abs(dy) ? abs(dx) : abs(dy);

// calculate increment in x & y for each step

float Xinc = dx / (float) steps;
float Yinc = dy / (float) steps;

// Put pixel for each step

float X = X0;
float Y = Y0;
for (int i = 0; i <= steps; i++)
{
putpixel (X,Y,RED); // put pixel at (X,Y)
X += Xinc; // increment in x at each step
Y += Yinc; // increment in y at each step
delay(100); // for visualization of line-
// generation step by step
}
}

// Driver program
int main()
{
int gd = DETECT, gm;

// Initialize graphics function

initgraph (&gd, &gm, "");

int X0 = 2, Y0 = 2, X1 = 14, Y1 = 16;

DDA(2, 2, 14, 16);
return 0;
}

1st Problem:

Explain DDA line drawing algorithm. For line segment between (2, 2) and (6, 6) :
we need (3, 3) (4, 4) and (5, 5) as our intermediate Points.
Answer:
Step1: suppose we want to draw a line from (2,2) to (6,6) So
x1=2, y1=2,
X2=6, y2=6
Step2:Therefore
Dx=(x2-x1)=6-2=4
Dy=(y2-y1)=6-2=4
Step3:As |Dx|=|Dy| the line is of gentle slope category
steps=abs(Dx) =4

Step4: Xinc = Dx/steps=4/4=1

Yinc= Dy/steps=4/4=1
Step 5:First point we know i.e. x1,y1, so plot it

Therefor Xnew= Xold + Xinc= 2+1= 3

Ynew= Yold + Yinc = 2+1= 3

Chapter 02 Computer Graphics Compiled by Dashrath Kale 1

 Second point we know i.e. x2,y2 ,so plot it

Therefore Xnew=Xold + Xinc = 3+1= 4

Ynew=Yold + Yinc = 3+1= 4

Third point we know i.e x3,y3 ,so plot it.

Xnew =Xold+Xinc=4+1=5
Ynew= Yold+ Yinc=4+1=5

Fourth point we know i.e x4,y4 ,so plot it.

Xnew =Xold+Xinc=5+1=6
Ynew= Yold+ Yinc=5+1=6
DDA Line Problem 1 Plot table Graph on problem 1 DDA

2.Problem :-
Draw DDA line algorithm. For the following segments (1,1) to (5,3) for rasterize this line.
Answer: suppose we want to draw a line from (1,1) to (5,3)
Step1:
So x1=1,y1=1,
x2=5,y2=3

Step2:Therefore Dx= (x2-x1)=5-1=4

Dy= (y2-y1)=3-1=2

Step3:As |Dx|>|Dy| the line is of gentle slope category

Steps = abs(Dx) =4
Step4:
Xinc = Dx/steps=4/4=1
Yinc= Dy/steps=2/4=0.5
Step5: First point we known i.e. x1,y1, so plot it

Therefor Xnew= Xold + Xinc = 1+1=2

Ynew=Yold + Yinc = 1+0.5=1.5

Second point we known i.e. x2,y2 ,so plot it

Therefore Xnew=Xold+Xinc = 2+1=3
Ynew =Yold+Yinc = 1.5+0.5=2

Third point we known i.e x3,y3 ,so plot it.

Xnew =Xold+ Xinc = 3+1=4
Ynew=Yold + Yinc = 2+0.5=2.5

Fourth point we known i.e x4,y4 so plot it,

Xnew=Xold+Xinc = 4+1=5
Ynew=Yold+Yinc = 2.5+0.5=3

Problem 2 Plot table ​ Graph on DDA Problem 2

Chapter 02 Computer Graphics Compiled by Dashrath Kale 2

Problem 3.
Explain DDA line drawing algorithm. Consider the line from (1,1) to (5,6) Use DDA line drawing algorithm to rasterize this line.
Answer :

Given
Step 1: x1=1 , y1=1 ,x2=5, y2=6

Step 2: Dx=x1-x2=5-1=4
Dy=y1-y2=6-1=5

Step 3:
Since |Dy|>|Dx| the line is of steep slope category
∴ Steps= abs(Dy)=5

Step 4:
Xinc = Dx/steps=4/5=0.8
Yinc =Dy/steps=5/5=1
Step 5:
As we know the first point, let’s plot it as(1,1)
Xnew=Xold+Xinc= 1+0.8 =1.8
Ynew=Yold+Yinc= 1+1 =2

As we know the 2nd point, let’s plot it as(1.8,2)

Xnew=Xold+Xinc= 1.8+0.8 =2.6
Ynew=Yold+Yinc= 2+1 =3

As we know the 3nd point, let’s plot it as (3,3)

Xnew=Xold+Xinc= 2.6+0.8 =3.4
Ynew=Yold+Yinc= 3+1 =4

As we know the 4th point, let’s plot it as(3.4,4)

Xnew=Xold+Xinc = 3.4+0.8 =4.2
Ynew=Yold+Yinc = 4+1 =5

As we know the 5th point, let’s plot it as(4.2,5)

Xnew=Xold+Xinc= 4.2+0.8 =5
Ynew=Yold+Yinc= 5+1 =6
Problem 3 Plot table ​ Graph on Problem 3

Bresenham’s Line Algorithm

2.Bresenham’s Line Algorithm:-

1.Bresenham’s line algorithm uses only integer addition and subtraction and multiplication by 2 .
2.The computer is also time-efficient when performing integer multiplication by powers of 2.
3.Therefore,it is an efficient method for scan-converting straight lines.
4.The basic principle of Bresenham’s line algorithm is to select the optimum raster locations to represent a straight line.
5.To accomplish this the algorithm always increments either x or y by one unit depending on the slope of the line.
6.The increment in the other variables is determined by examining the distance between the actual line location and the nearest pixel. This
distance is called decision variable or error .

7.​Decision Variable or Error ​ this is illustrated in the figure below.

1.The line does not pass through all raster points (pixel).It passes through raster point(0,0) and subsequently crosses three pixels.

2.It is seen that the intercept of line with the line x=1 is closer to the line y=0 ,i.e. pixel(1,0) than to the line y=1 i.e. pixel(1,1).
Chapter 02 Computer Graphics Compiled by Dashrath Kale 3
 3.Hence ,in this case,the raster point at (1,0) better
represents the path line than that at(1,1).

4.The intercept of line with the line x=2 is closer to the line
y=1, i.e. pixel(2,1) than to the line y =0,i.e. Pixel (2,0).Hence
the raster point at(2,1) better represents the path of line as
shown in the above figure.
5.in the mathematical terms error or decision variables is
defined as
E= DB - DA or DA - DB
6.Let us define e=DB-DA.now if e>0 , then it implies that DB
> DA i.e. the pixel above the line closer to the true line.
7.If DB < DA (i.e.e<0) then we can say that the pixel below
the line is closer to the true line.
Thus by checking only the sign of error term it is possible to determine the better pixel to represent the line path.
8.The error term is initially set as
e= 2Δy - Δx
Where Δy= y2 - y1 ,and Δx= x2 - x1
9.Then according to value of e following actions are taken
if (e ≥ 0)
{
y=y+1
e=e-2*Δx
}
x=x+1
e=e+2 * Δy
10. When e ≥ 0 error is initialized with e= e-2 Δx. This is continued till error is negative.in each iteration y is incremented by 1.
When e<0, error is initialized to e= e+2 Δy. In both cases x is incremented by 1.

Bresenham’ line algorithm

1.Read the line end points (x1,y1) and (x2,y2) such that they are not equal.[if equal then plot that point and exit]
2. Δx = |x2 - x1| and Δy = |y2-y1|
3. [initialize starting point]
x=x1
y=y1
4.e= 2 * Δy - Δx
[Initialize value of decision variable or error to compensate for nonzero intercepts]
5.i= 1 [Initialization counter]
6. Plot (x,y)
7. if (e ≥ 0)
{
y=y+1
e=e-2* Δx
}
else
{
e=e+2*Δy
}
x= x+1

8. i= i+1
9.if (i ≤ Δx) then go to step 6.
10. Stop.

Write a Program generate Bresenham line algorithm.

#include<stdio.h>
//#include<conio.h>
#include<graphics.h>
#include<math.h>
int main()
{
int x,y,dx,dy ,x1=100,y1=100,x2=200,y2=200,e;
int gd=DETECT,gm;
int i;
//clrscr();
initgraph(&gd,&gm,NULL);
//Read Two end point
/*printf("Enter the value of x1:\t");

Chapter 02 Computer Graphics Compiled by Dashrath Kale 4

 scanf("%f",&x1);
printf("Enter the value of y1:\t");
scanf("%f",&y1);
printf("Enter the value of x2:\t");
scanf("%f",&x2);
printf("Enter the value of y2:\t");
scanf("%f",&y2);
cleardevice();*/
// calculate dx and dy
dx=abs(x2-x1);
dy=abs(y2-y1);
//Initialize the starting points
x=x1;
y=y1;
//initialize decision variable or error
e=2*dy-dx;
//initialize loop counter as i
i=1;
do
{
putpixel(x,y,10);

delay(200);
if(e>=0)
{
y=y+1;
e=e-2*dy;
}
else{

e=e+2*dy;
}
x=x+1;
i=i+1;
}while (i<=dx);
getch();
closegraph();
}

Advantage:

1. It involves only ​integer arithmetic, so it is simple.

2. It ​avoids the generation of duplicate points.
3. It can be implemented using hardware because it does not use multiplication and division.
4. It is faster as compared to DDA (Digital Differential Analyzer) because it does not involve floating point calculations like DDA Algorithm.

Disadvantage:

1. This algorithm is meant for basic line drawing only Initializing is not a part of Bresenham's line algorithm. So to draw smooth lines, you
should want to look into a different algorithm.

1.Problem: - Consider the line from (5, 5) to (13, 9). Use Bresenham's algorithm to rasterize the line.
Solution :-
Evaluating steps 1 through 4 in the Bresenham’s algorithm we have,
Given: -
step 1 :- x1 = 5 , y1 = 5 and x2 = 13 , y2 = 9 .
step 2 :- Δx = | 13 - 5| =8 Δy = | 9 - 5 | = 4
step 3 :- x = 5 , y = 5
step 4 :- e = 2 * Δy - Δx = 2 * 4 - 8 = 0.
Tabulating the results of each iteration in the step 5 through 10.
Step5:
When e ≥ 0 error is initialized with e= e-2 Δy. This is continued till error is negative.in each iteration y is incremented
by 1. When e<0, error is initialized to e= e+2 Δy. In both case x is incremented by 1

1st point x0,y0=5,5 then calculate value of e

e= 2 * Δy - Δx = 2 * 4 - 8 = 0. take reference of step 5

2nd Therefor e=0,x,y incremented by 1

Chapter 02 Computer Graphics Compiled by Dashrath Kale 5

 x=x+1=6,y=y+1=6 , e=2* Δy - Δx = 2*3-7
e=e-2 Δy=0- 2*4=-8

3rd point e=-8,x,y=6,6 only x2 get incremented..

x=x+1=7 ,y=6
e=e+2 Δy=-8-2*4=0

4th Therefor e=0 then both x and y get incremented

x=x+1=8 ,y=y+1=7
e=e-2 Δy= 0-2*4=-8

5th point e=-8 then only x get incremented.

x=x+1 =9 ,y=7
e=e+2 Δy=-8+24=0

6th point e=0 , x and y get incremented by 1

X=10,y=8
e=e-2Δy=-8

7 point e=-8 x get incremented by 1

X=11,y=8
e=e+2Δy=-8+8=0

8.point e=0 therefore both get incremented

X=12,y=9
e=e-2Δy=0-8=-8

9 point e=-8 therefor only x8 get incremented

X=13 y=9
e=e+2Δy=0

Problem 1 Problem 1 plotting

2..Plot a line by using Bresenham's line generating algorithm from (1, 1) to (5, 3).
Solution:-
Step1 :x0,y0 = 1,1 and x1,y1= 5,3

Step2:calculate Δx and Δy
Δx=x2-x1 & Δy=y2-y1
Δx=5-1=4 & Δy=3-1=2

Step 3: Total no of step is 4 ..

Step 4:Calculating Decision Variable or error..

e = 2*Δy-Δx , e = 2*2-4=0

Step 5:- When e ≥ 0 error is initialized with e= e-2 Δy. This is continued till error is negative.in each iteration y is incremented by 1. When
e<0, error is initialized to e= e+2 Δy. In both case x is incremented by 1

1st point e=0 and x,y both get incremented...

x=x+1 = 1+1=2 and y=1+1= 2
e=e-2*Δy or e=0-2*2 =-4

2nd point e=-4 hence x get incremented..

X=2+1=3 and y=2,
e=e+2Δy= -4+2*2=0

3rd point e=0 hence x and y get incremented..

Chapter 02 Computer Graphics Compiled by Dashrath Kale 6
X=3+1=4 and y=3,
e=e-2Δy= 0-2*2=-4

4th point e=-4 hence only x get incremented...

X=4+1=5 ,y=3 therefore
e=e+2Δy=-4+4=0
Problem 2 Problem 2 plotting.

2.2 Circle generation Algorithms:-

Bresenham’s circle drawing algorithm

Note- This is octet 2 so here x can never be decremented as per properties of

a circle but y either needs to be decremented or to be kept the same. y is
needed to be decided.
Derivation Steps of Bresenham algorithm..
1.Let's say our circle is at some random pixel P whose coordinates are (x​k​, y​k​).
Now we need to find out our next pixel.
2.Here it needs to decide whether to go with N or S.
3.For this bresenham's circle drawing algorithm will help us to decide by
calculating the difference between radius and the coordinates of the next
pixels.
4.The shortest of d1 and d2 will help us Decide our next pixel.
note- x​k+1​ = x​k​ +1 ( As x​k+1​ is the next consecutive pixel of x​k​)
similarly y​k-1​ = y​k​ -1
5.Equation of Circle with Radius r
(x– h)​2​ + (y – k)​2​ = r​2
When coordinates of centre are at Origin i.e., (h=0, k=0)
x​2​ + y​2​ = r​2​ (Pythagoras theorem)
6.Function of Circle Equation
F(C) = x​ 2 + y2 - r2
7.Function of Circle at N
F(N) = (x​k+1​)​2 + (y​k​)​2 – r​2 (Positive) Here the value of F(N) will be positive because N is out-side the circle that makes (x​k+1)​2 +
(y​k​)​ Greater than r​2
2​

8.Function of Circle at S
F(S) = (x​k+1​)​2 + (y​k-1​)​2 – r​2 (Negative) Here the value of F(S) will be Negative because S is in-side the circle that makes (x​k+1​)​2 +
2​ 2
(y​k-1​)​ Less than r​
9.Now we need a decision parameter which help us decide the next pixel
Say D​k​ And , D​k​ = ​F(N)+F(S)
Here either we will get the positive or negative value of Dk
10.So if D​k <​ 0 :-
That means the negative F(S) is bigger than the positive F(N), that implies Point N is closer to the circle than point S. So we will
select pixel N as our next pixel.
Chapter 02 Computer Graphics Compiled by Dashrath Kale 7
11.if Dk > 0:-
That means positive F(N) is bigger and S is more closer as F(S) is smaller. So we will Select S as our next pixel.
12.Now lets find D​k
D​k​ = (x​k+1​)​2​ + (y​k​)​2​ – r​2​ + (x​k+1​)​2​ + (y​k-1​)​2​ – r​2
(replacing x​k+1​ with x​k ​+ 1 and y​k-1​ with y​k​ -1)
= (x​k​ + 1)​ + (y​k​)​ – r​ + (x​k​ + 1)​2​ + (y​k​ -1)​2​ – r​2
2​ 2​ 2​

= 2(x​k​ + 1)​2​ + (y​k​)​2​ + (y​k​ -1)​2​ – 2r​2​ ----- (​i)

13.Now to find initial decision parameter means starting point that is (0,r) ,value of y is r
Putting (0,r) in ​(​i)
D​k​ = 2(x​k​ + 1)​2​ + (y​k​)​2​ + (y​k​ -1)​2​ – 2r​2
D0 = 2(0 + 1)​2​ + r​2​ + (r -1)​2​ – 2r​2
D0 = 2 + r​2​ +r​2​ + 1 – 2r – 2r​2
Initial decision parameter (Do) = 3-2r
14.Now lets find D​k+1
D​k+1 ​= 2(x​k+1​ + 1)​2​ +(y​k+1​)​2​ + (y​k+1​ -1)​2​ – 2r​2 ​(Replacing every k with k+1)
= 2(x​k+1​ + 1)​2​ + (y​k+1​)​2​ + (y​k+1​ -1)​2​ – 2r​2
(Replacing x​k+1​ with x​k​ + 1 but now we can’t replace y​k+1 ​because we don’t know the exact value of y​k​ )
2(x​k​+1+ 1)​2​ + (y​k+1​)​2​ + (y​k+1 -1)​
​
2​
– 2r​2
2​ 2​ 2​ 2​
= 2(x​k​+2)​ + (y​k+1​)​ + (y​k+1 -1)​ ​ – 2r​ ----- (​ii)

15.Now to find out the decision parameter of next pixel i.e. D​k+1
We need to find
D​k+1​ - D​k​ = (​ii) - (i)
= 2(x​k​+2)​2​ + (y​k+1​)​2​ + (y​k+1 ​-1)​2​ – 2r​2​ - [2(x​k​ + 1)​2​ + (y​k​)​2​ + (y​k​ -1)​2​ – 2r​2​]
= 2(x​k​)​2​ + 8x​k​ + 8 + (y​k+1​)​2​ + (y​k+1​)​2​ - 2y​k+1​ + 1 - 2r​2 ​-​ [2(x​k​ )​2​ - 4x​k​ – 2 - (y​k​)​2​ - (y​k​)​2​ + 2y​k​ - 1 + 2r​2​]
= 4x​k​ + 2(y​k+1​)​2​ - 2y​k+1​ - 2(y​k​)​2​ - 2y​k​ + 6
D​k+1​ = D​k​ + 4x​k​ + 2(y​k+1​)​2​ - 2y​k+1​ - 2(y​k​)​2​ - 2y​k​ + 6 ----- (​iii)
16.If (D​k​ < 0) then we will choose the N point as discussed.
i.e. (x​k+1​, y​k​) that means our next x coordinate is x​k+1​ and next y coordinate is y​k​ i.e. y​k+1​ = y​k​, putting y​k​ in (​iii) ​in replace of y​k+1
Now, D​k+1​ = D​k​ + 4x​k​ + 2(yk)​2​ - 2y​k​ - 2(yk)​2​ - 2y​k​ + 6
​= Dk + 4xk + 6
17.If (D​k​ > 0) then we will choose S point. i.e. (x​k+1​, y​k-1​)
that means our next x coordinate is x​k+1​ and next y coordinate is y​k​ i.e. y​k+1​ = y​k-1​ putting y​k-1​ in (​iii) i​ n replace of y​k+1
now,
D​k+1​ = D​k​ + 4x​k​ + 2(y​k-1​)​2​ - 2y​k-1​ - 2(y​k​)​2​ - 2y​k​ + 6
Now we know
y​k-1​ = y​k​ – 1
Therefore,
D​k+1 =​ D​k​ + 4x​k​ + 2(y​k​ -1)​2​ - 2(y​k​ -1) - 2(y​k​)​2​ - 2y​k​ + 6
= D​k​ + 4x​k​ + 2(y​k​)​ 2​ + 2 - 4y​k​ - 2y​k​ +2 - 2(y​k​)​2​ - 2y​k​ + 6
= D​k​ + 4x​k​ - 4y​k​ + 10
= D​k​ + 4(x​k​ - y​k​) + 10

Bresenham's Circle Drawing Algorithm

Algorithm to plot ⅛ of the circle using bresenham’s algorithm.

1.Read the radius (r) of the circle.
2.d= 3-2r
[Initialize the decision variable]
3.x=0 ,y=r
[Initialize starting points]
4.do
{
plot(x,y)
If (d<0) then
{
d=d+4x+6
}
Else
{
d=d+4(x-y)+10
y=y-1
Chapter 02 Computer Graphics Compiled by Dashrath Kale 8
 }
x=x+1
}while(x<y)
5.Stop.

Example.

1.calculate the pixel position along the circle path with radius r= 10 centered on the origin using

Bresenham’s circle drawing algorithm from point(0,10) to point x=y.

Answer:-

Step 1: Read the radius of circle r=10

Step 2:Initialize the decision variable
Decision variable:- d=3-2r =3-20=-17
Step 3: x=0 ,y=r [Initialize starting points ]
Step 4:

Plot first point i.e x=0,y=10, [d=-17] then if(d<0) then

d= d+4x+6= -17+0+6=-11
x=x+1= 1
Plot 2nd point i.e x=1,y=10 and [d=-11] then if(d<0)
d= d+4x+6= -11+4+6=-1
x=x+1= 2
Plot 3rd point i.e x=2 ,y=10 and here[d=1] then if (d<0 )
d= d+4x+6= -1+8+6=13
x=x+1= 3
Plot 4th point i.e x=3 ,y=10 and [d=13] then if (d>0)
d=d+4(x-y)+10=13+4(3-10)+10= -5
x=x+1=4
y=y-1=9
Plot 5th point i.e y=9 ,x=4 and [d=-5] therefor if(d<0)
d= d+4x+6= -5+16+6=17
x=x+1= 5
Plot 6th point i.e y=9 ,x=5 and [d=17] therefor if (d>0)
d=d+4(x-y)+10=17+4(5-9)+10= 11
x=x+1=6
y=y-1=8
Plot 7th point x=6 and y=8 and [d=11] then therefor,if (d>0)
d=d+4(x-y)+10=11+4(6-8)+10= 13
x=x+1=7
y=y-1=7
Plot 8th point x=7 and y=7 therefor,if(d>0) [d=13]

2. Plot a circle using Bresenham’s algorithm for r= 3 and center at(0,0)

Ans:
Step 1: Read the radius of circle r=3
Step 2:Initialize the decision variable
Decision variable:- d=3-2r =3-6=-3
Step 3: x=0 ,y=r [Initialize starting points ]
Chapter 02 Computer Graphics Compiled by Dashrath Kale 9
Step 4:
Plot first point i.e x=0,y=3, [d=-3] if(d<0) therefor
d= d+4x+6= -3+0+6=3
x=x+1= 1
Plot 2nd pixel position x=1,y=3,[d=3] then if (d>0) therefor,
d=d+4(x-y)+10=3+4(1-3)+10=5
x=x+1=2 ,y=y-1=2
Plot 3rd pixel position x=2,y=2 ,d=5

What is a Polygon?​:

1.​Polygons​ can be regular or irregular. They can be simple or complex, convex or concave.
2.The word ​"​polygon"​ means ​"many-angled," from Greek. To be a polygon, a flat, closed shape must use only line segments to create its
sides. So a circle or any shape that has a curve is ​not a​ polygon.
3.​The three identifying properties of any polygon are that the polygon is:
1. A two-dimensional shape
2. Closing in a space (having an interior and exterior)
3. Made with straight sides
4.Types of Polygons
Let's take a look at the vast array of shapes that are polygons and go into detail.

Sr.no Type of polygon Diagram

1 Regular polygons have congruent sides and interior

angles. Every side is equal in length to every other side,
and every interior angle is equal to all other interior
angles. The number of regular polygons is limitless.

Chapter 02 Computer Graphics Compiled by Dashrath Kale 10

 2 Irregular polygons do ​not have congruent sides and
angles. Home plate on a softball or baseball field is an
irregular pentagon, because it has five sides with two
90° angles.

3 Convex :-​A ​convex polygon closes in an interior area

without looking "dented." None of its interior angles
point inward. In geometry, you could have a four-sided
polygon that points outward in all directions, like a ​kite​,

4 Concave polygon: ​It has at least one angle greater than

180°. Think of a bowtie-shaped simple hexagon (6 sides).
It will have two interior angles greater than 180°.

5 5.Simple Complex Polygons:-​Simple polygons have no

self-intersecting sides.

Chapter 02 Computer Graphics Compiled by Dashrath Kale 11

 6 6.​Complex polygons​, also called self-intersecting
polygons, have sides that cross over each other.

Inside-outside Test
This method is also known as counting number method. While filling an object, we often need to identify whether a particular point is
inside the object or outside it. There are two methods by which we can identify whether a particular point is inside an object or outside.
Odd-Even Rule
Nonzero winding number rule

1.Odd-Even Rule
In this technique, we will count the edge crossing along the line from any point x,y to infinity. If
the number of interactions is odd, then the point x,y is an interior point; and if the number of
interactions is even, then the point x,y is an exterior point. The following example depicts this
concept.
From the above figure, we can see that from the point x,y the number of interaction points on the
left side is 5 and on the right side is 3. From both ends, the number of interaction points is odd, so
the point is considered within the object.

2.Nonzero Winding Number Rule:-

1.In another alternative method, give directions to all the edges of the polygon. Draw a scan line from the point to be tested towards the
left most of X direction.
2.Give the value 1 to all the edges which are going to upward direction and all other -1 as direction
values.
3.Check the edge direction values from which the scan line is passing and sum them up.
4.if the total sum of this direction value is non-zero, then this point to be tested is an interior point,
otherwise it is an exterior point.
5.In the above figure, we sum up the direction values from which the scan line is passing then the total
is 1 – 1 + 1 = 1; which is non-zero. So the point is said to be an interior point.

Boundary Fill Algorithm

1.The boundary fill algorithm works as its name.
2.This algorithm picks a point inside an object and starts to fill until it hits the boundary of the object.
3.The color of the boundary and the color that we fill should be different for this algorithm to work.
4.In this algorithm, we assume that the color of the boundary is the same for the entire object.
5.The boundary fill algorithm can be implemented by 4-connected pixels or 8-connected pixels.
4-Connected Polygon

Chapter 02 Computer Graphics Compiled by Dashrath Kale 12

 Four connected Four connected points
In this technique 4-connected pixels are used as shown in the figure. We are putting the pixels above, below, to the right, and to the left
side of the current pixels and this process will continue until we find a boundary with different color.
There is a problem with this technique. Consider the case as shown below where we tried to fill the entire region. Here, the image is filled
only partially. In such cases, 4-connected pixels technique cannot be used.

Algorithm :
void boundaryFill4(int x, int y, int fill_color,int boundary_color)
{
if(getpixel(x, y) != boundary_color &&
getpixel(x, y) != fill_color)
{
putpixel(x, y, fill_color);
boundaryFill4(x + 1, y, fill_color, boundary_color);
boundaryFill4(x, y + 1, fill_color, boundary_color);
boundaryFill4(x - 1, y, fill_color, boundary_color);
boundaryFill4(x, y - 1, fill_color, boundary_color);
}
}
// C Implementation for Boundary Filling Algorithm Function for 4 connected Pixels
#include <graphics.h>
void boundaryFill4(int x, int y, int fill_color,int boundary_color)
{
if(getpixel(x, y) != boundary_color &&
getpixel(x, y) != fill_color)
{
putpixel(x, y, fill_color);
boundaryFill4(x + 1, y, fill_color, boundary_color);
boundaryFill4(x, y + 1, fill_color, boundary_color);
boundaryFill4(x - 1, y, fill_color, boundary_color);
boundaryFill4(x, y - 1, fill_color, boundary_color);
} }
int main()
{
int gd = DETECT, gm;

Chapter 02 Computer Graphics Compiled by Dashrath Kale 13

 initgraph(&gd, &gm, "");
int x = 250, y = 200, radius = 50;
// circle function
circle(x, y, radius);
// Function calling
boundaryFill4(x, y, 6, 14);
delay(10000);
getch()
closegraph();
return 0;
}
8-Connected Polygon
In this technique 8-connected pixels are used as shown in the figure. We are putting pixels above, below, right and left side of the current

Fig. 8 point position Fig.8 connected pixel

pixels as we were doing in 4-connected technique.
In addition to this, we are also putting pixels in diagonals so that the entire area of the current pixel is covered. This process will continue
until we find a boundary with different color.

Algorithm:-
void boundaryFill8(int x, int y, int fill_color,int boundary_color)
{
if(getpixel(x, y) != boundary_color &&
getpixel(x, y) != fill_color)
{
putpixel(x, y, fill_color);
boundaryFill8(x + 1, y, fill_color, boundary_color);
boundaryFill8(x, y + 1, fill_color, boundary_color);
boundaryFill8(x - 1, y, fill_color, boundary_color);
boundaryFill8(x, y - 1, fill_color, boundary_color);
boundaryFill8(x - 1, y - 1, fill_color, boundary_color);
boundaryFill8(x - 1, y + 1, fill_color, boundary_color);
boundaryFill8(x + 1, y - 1, fill_color, boundary_color);
boundaryFill8(x + 1, y + 1, fill_color, boundary_color);
}
}
// C Implementation for Boundary Filling Algorithm Function for 8 connected Pixels

Chapter 02 Computer Graphics Compiled by Dashrath Kale 14

#include <graphics.h>
void boundaryFill8(int x, int y, int fill_color,int boundary_color)
{
if(getpixel(x, y) != boundary_color &&
getpixel(x, y) != fill_color)
{
putpixel(x, y, fill_color);
boundaryFill8(x + 1, y, fill_color, boundary_color);
boundaryFill8(x, y + 1, fill_color, boundary_color);
boundaryFill8(x - 1, y, fill_color, boundary_color);
boundaryFill8(x, y - 1, fill_color, boundary_color);
boundaryFill8(x - 1, y - 1, fill_color, boundary_color);
boundaryFill8(x - 1, y + 1, fill_color, boundary_color);
boundaryFill8(x + 1, y - 1, fill_color, boundary_color);
boundaryFill8(x + 1, y + 1, fill_color, boundary_color);
}
}
int main()
{
int gd = DETECT, gm;
initgraph(&gd, &gm, "");
// Rectangle function
rectangle(200, 200, 100, 100);
// Function calling
boundaryFill8(150, 150, 9, 15);
delay(200);
getch();
closegraph();
return 0;
}

Flood Fill Algorithm:

1.In this method, a point or seed which is inside the region is selected. This point is called a seed
point.
2.Then four connected approaches or eight connected approaches are used to fill with specified
color.
3.The flood fill algorithm has many characters similar to boundary fill. But this method is more
suitable for filling multiple colors.
4.When boundary is of many colors and interior is to be filled with one color we use this algorithm.
5.n fill algorithm, we start from a specified interior point (x, y) and reassign all pixel values that are
currently set to a given interior color with the desired color.
6.Using either a 4-connected or 8-connected approaches, we then step through pixel positions until all interior points have been
repainted.
Algorithm:
Procedure floodfill (x, y,fill_ color, old_color: integer)

Chapter 02 Computer Graphics Compiled by Dashrath Kale 15

 If (getpixel (x, y)=old_color)
{
setpixel (x, y, fill_color);
fill (x+1, y, fill_color, old_color);
fill (x-1, y, fill_color, old_color);
fill (x, y+1, fill_color, old_color);
fill (x, y-1, fill_color, old_color);
}
}
Write a Program to implement flood fill algorithms.
#include<stdio.h>
#include<conio.h>
#include<graphics.h>
#include<dos.h>
void flood(int,int,int,int);
void main()
{
int gd=DETECT,gm;
initgraph(&gd,&gm,"C:/TURBOC3/bgi");
rectangle(50,50,250,250);
flood(55,55,10,0);
getch();
}
void flood(int x,int y,int fillColor, int defaultColor)
{
if(getpixel(x,y)==defaultColor)
{
delay(1);
putpixel(x,y,fillColor);
flood(x+1,y,fillColor,defaultColor);
flood(x-1,y,fillColor,defaultColor);
flood(x,y+1,fillColor,defaultColor);
flood(x,y-1,fillColor,defaultColor);
}
}

Sr.No Flood Fill Algorithm Boundary Fill Algorithm

1 Flood fill colors an entire area in an enclosed Here area gets colored with pixels of a chosen color as
figure through interconnected pixels using a boundary this giving the technique its name
single color

2 So, Flood Fill is one in which all connected Boundary Fill is very similar with the difference being the
pixels of a selected color get replaced by a fill program stopping when a given color boundary is found.
color.

3 A flood fill may use an unpredictable amount Boundary fill is usually more complicated but it is a linear
of memory to finish because it isn't known algorithm and doesn't require recursion
how many sub-fills will be spawned
Chapter 02 Computer Graphics Compiled by Dashrath Kale 16
 4 Time Consuming It is less time Consuming

1.Advantages of Boundary-Fill over Flood-Fill:-

1.Flood-fill regions are defined by the whole of the region. All pixels in the region must be made the same colour when the region is being
created. The region cannot be translated, scaled or rotated.
2.4-connected boundary-fill regions can be defined by lines and arcs. By translating the line and arc endpoints we can translate, scale and
rotate the whole boundary-fill region. Therefore 4-connected boundary-fill regions are better suited to modelling.
1.Disadvantages of Boundary-Fill over Flood-Fill:-
1.In boundary-fill algorithms each pixel must be compared against both the new colour and the boundary colour. In flood-fill algorithms
each pixel need only be compared against the new colour. Therefore flood-fill algorithms are slightly faster.
2.Boundary-fill algorithms can leak. There can be no leakage in flood-fill algorithms.

2.Adavantage of Flood Fill Algorithm :-

​1.Flood fills colors an entire area in an enclosed figure through interconnected pixels using a single color.
2.It is an easy way to fill color in the graphics. One just takes the shape and starts flood fill.

2. Disadvantages of flood fill algorithm :-

1.Requires getpixel() system call.
2.Not efficient for large polygons - needs a large stack.
3.Requires a seed point.

Application of Concept/ Examples in real life​:

1.P​aint programs​ to fill connected, similarly-colored areas with a different color.
2.​In games such as ​Go​ and ​Minesweeper​.

1.Scan line fill

1.Scanline filling is basically filling up of polygons using horizontal lines or
scanlines. The purpose of the SLPF algorithm is to fill (color) the interior
pixels of a polygon given only the vertices.
2.In above figure polygon and a line cutting polygon is shown. First of all,
scanning is done. Scanning is done using a raster scanning concept on
the display device.
3.The beam starts scanning from the top left corner of the screen and
goes toward the bottom right corner as the endpoint. The algorithms
find points of intersection of the line with the polygon while moving
from left to right and top to bottom.
4.The various points of intersection are stored in the frame buffer. The
intensity of such points is kept high. Concept of coherence property is
used. According to this property if a pixel is inside the polygon, then its
next pixel will be inside the polygon.

Scan Line Algorithm

This algorithm works by intersecting the scanline with polygon edges and fills the
polygon between pairs of intersections. The following steps depict how this algorithm
works.
Step 1 − Find out the Ymin and Ymax from the given polygon.
Step 2 − ScanLine intersects with each edge of the polygon from Ymin to Ymax. Name
each intersection point of the polygon. As per the figure shown above, they are named
as p0, p1, p2, p3.

Step 3 − Sort the intersection point in the increasing order of X coordinate i.e. p0,p1,
p1,p2, and p2,p3.

Step 4 − Fill all those pairs of coordinates that are inside polygons and ignore the
alternate pairs.
Scan Conversion
1.It is a process of representing graphics objects as a collection of pixels.
2.The graphics objects are continuous. The pixels used are discrete. Each pixel can have either on or off state.
3.The circuitry of the video display device of the computer is capable of converting binary values (0, 1) into a pixel on and pixel off
information.
4. 0 is represented by pixel off. 1 is represented using pixel on. Using this ability, graphics computers represent pictures having discrete
dots
5.Any model of graphics can be reproduced with a dense matrix of dots or points. Most human beings think of graphics objects as points,
lines, circles, ellipses. For generating graphical objects, many algorithms have been developed.

FrameBuffer:
1.In raster scan displays a special area of memory is dedicated to graphics only. This memory area is called a frame​ buffer​.
Chapter 02 Computer Graphics Compiled by Dashrath Kale 17
2.It holds the set of intensity values for all the screen points. The stored intensity values are retrieved from the frame buffer and displayed
on the screen one row (scan line) at a time.
3.Usually, a frame buffer is implemented using rotating random access semiconductor memory.
4.However, frame buffers also can be implemented using shift registers. Conceptually, shift register is operated as first-in-first-out (FIFO)
fashion, i.e. similar to queue.
5.We know that, when the queue is full and if we want to add a new data bit then the first data bit is pushed out from the bottom and
then the new data bit is added at the top.
6.Here, the data ejected out of the queue can be interpreted as the intensity of a pixel on a scan line.
7.one shift register is required per pixel on a scan line and the length of shift register in bits is equal to the number of scan lines.
8.Here, there are 8 pixels per scan line and there are in all 5 scan lines. The synchronization between the output of the shift register and
the video scan rate is maintained; data corresponding to a particular scan line is displayed correctly.

Application of Concept/ Examples in real life​:

Examples of objects which can be scan converted

1. Point
2. Line
3. Sector
4. Arc
5. Ellipse
6. Rectangle
7. Polygon
8. Characters
9. Filled Regions

1.Advantage of developing algorithms for scan conversion

1.Algorithms can generate graphics objects at a faster rate.
2.Using algorithms memory can be used efficiently.
3.Algorithms can develop a higher level of graphical objects.

Character Generation Methods:-

1.Star bust Method:-

1.In this method a fixed pattern of line is used to generate the character.
2.In this method we use a combination of 24 bit line segments.
3.In 24 bit line segment code each bit represents a single line.
4.To highlight a line we put corresponding bit 1 in 24 bit line segment code and 0 otherwise.
5. fig. show starbus pattern for character A and Character M.
6.The patterns for particular characters are stored in the form of 24 bit code.
7.Each bit representing one line segment.
8.The bit is set one to highlight the line segment otherwise it is set to zero.

Chapter 02 Computer Graphics Compiled by Dashrath Kale 18

2.Stroke Method:
1.This method uses a small line segment to generate a character.
2. The small series of line segments are drawn like a stroke of a pen to form a character as
shown in fig.
3. We can build our own stroke method.
1.by calling a line drawing algorithm.
2.Here it is necessary to decide which line segments are
needed for each character
3. Then Drawing these segments using line drawing algo.
4.This method supports scaling of the character.it does this by changing the length of the line
segments used for character drawing.

3.Bitmap Method:
1.This is the third method of character generation.
2.Also known as dot matrix because in this method characters are represented by an array
of dots in the matrix form.
3.It’s a two dimensional array having columns and rows: 5x7 as shown in fig.
4.7x 9 and 9x 13 arrays are also used.
5.Higher resolution devices may use character array 100x100.

Chapter 02 Computer Graphics Compiled by Dashrath Kale 19