Computer Graphics Subject Notes | Gate Vidyalay

Tag: Computer Graphics Subject Notes

2D Translation in Computer Graphics | Definition | Examples

Computer Graphics

2D Transformation in Computer Graphics-

In Computer graphics,

Transformation is a process of modifying and re-positioning the existing graphics.

2D Transformations take place in a two dimensional plane.
Transformations are helpful in changing the position, size, orientation, shape etc of the object.

Transformation Techniques-

In computer graphics, various transformation techniques are-

In this article, we will discuss about 2D Translation in Computer Graphics.

2D Translation in Computer Graphics-

In Computer graphics,

2D Translation is a process of moving an object from one position to another in a two dimensional plane.

Consider a point object O has to be moved from one position to another in a 2D plane.

Let-

Initial coordinates of the object O = (X_old, Y_old)
New coordinates of the object O after translation = (X_new, Y_new)
Translation vector or Shift vector = (T_x, T_y)

Given a Translation vector (T_x, T_y)-

T_x defines the distance the X_old coordinate has to be moved.
T_y defines the distance the Y_old coordinate has to be moved.

This translation is achieved by adding the translation coordinates to the old coordinates of the object as-

X_new = X_old + T_x (This denotes translation towards X axis)
Y_new = Y_old + T_y (This denotes translation towards Y axis)

In Matrix form, the above translation equations may be represented as-

The homogeneous coordinates representation of (X, Y) is (X, Y, 1).
Through this representation, all the transformations can be performed using matrix / vector multiplications.

The above translation matrix may be represented as a 3 x 3 matrix as-

PRACTICE PROBLEMS BASED ON 2D TRANSLATION IN COMPUTER GRAPHICS-

Problem-01:

Given a circle C with radius 10 and center coordinates (1, 4). Apply the translation with distance 5 towards X axis and 1 towards Y axis. Obtain the new coordinates of C without changing its radius.

Solution-

Given-

Old center coordinates of C = (X_old, Y_old) = (1, 4)
Translation vector = (T_x, T_y) = (5, 1)

Let the new center coordinates of C = (X_new, Y_new).

Applying the translation equations, we have-

X_new = X_old + T_x = 1 + 5 = 6
Y_new = Y_old + T_y = 4 + 1 = 5

Thus, New center coordinates of C = (6, 5).

Alternatively,

In matrix form, the new center coordinates of C after translation may be obtained as-

Thus, New center coordinates of C = (6, 5).

Problem-02:

Given a square with coordinate points A(0, 3), B(3, 3), C(3, 0), D(0, 0). Apply the translation with distance 1 towards X axis and 1 towards Y axis. Obtain the new coordinates of the square.

Solution-

Given-

Old coordinates of the square = A (0, 3), B(3, 3), C(3, 0), D(0, 0)
Translation vector = (T_x, T_y) = (1, 1)

For Coordinates A(0, 3)

Let the new coordinates of corner A = (X_new, Y_new).

Applying the translation equations, we have-

X_new = X_old + T_x = 0 + 1 = 1
Y_new = Y_old + T_y = 3 + 1 = 4

Thus, New coordinates of corner A = (1, 4).

For Coordinates B(3, 3)

Let the new coordinates of corner B = (X_new, Y_new).

Applying the translation equations, we have-

X_new = X_old + T_x = 3 + 1 = 4
Y_new = Y_old + T_y = 3 + 1 = 4

Thus, New coordinates of corner B = (4, 4).

For Coordinates C(3, 0)

Let the new coordinates of corner C = (X_new, Y_new).

Applying the translation equations, we have-

X_new = X_old + T_x = 3 + 1 = 4
Y_new = Y_old + T_y = 0 + 1 = 1

Thus, New coordinates of corner C = (4, 1).

For Coordinates D(0, 0)

Let the new coordinates of corner D = (X_new, Y_new).

Applying the translation equations, we have-

X_new = X_old + T_x = 0 + 1 = 1
Y_new = Y_old + T_y = 0 + 1 = 1

Thus, New coordinates of corner D = (1, 1).

Thus, New coordinates of the square = A (1, 4), B(4, 4), C(4, 1), D(1, 1).

To gain better understanding about 2D Translation in Computer Graphics,

Watch this Video Lecture

Next Article- 2D Rotation in Computer Graphics

Get more notes and other study material of Computer Graphics.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Bresenham Circle Drawing Algorithm

Computer Graphics

Circle Drawing Algorithms-

In computer graphics, popular algorithms used to generate circle are-

Mid Point Circle Drawing Algorithm
Bresenham Circle Drawing Algorithm

In this article, we will discuss about Bresenham Circle Drawing Algorithm.

Bresenham Circle Drawing Algorithm-

Given the centre point and radius of circle,

Bresenham Circle Drawing Algorithm attempts to generate the points of one octant.

The points for other octacts are generated using the eight symmetry property.

Also Read- Mid Point Circle Drawing Algorithm

Procedure-

Given-

Centre point of Circle = (X₀, Y₀)
Radius of Circle = R

The points generation using Bresenham Circle Drawing Algorithm involves the following steps-

Step-01:

Assign the starting point coordinates (X₀, Y₀) as-

X₀ = 0
Y₀ = R

Step-02:

Calculate the value of initial decision parameter P₀ as-

P₀ = 3 – 2 x R

Step-03:

Suppose the current point is (X_k, Y_k) and the next point is (X_k+1, Y_k+1).

Find the next point of the first octant depending on the value of decision parameter P_k.

Follow the below two cases-

Step-04:

If the given centre point (X₀, Y₀) is not (0, 0), then do the following and plot the point-

X_plot = X_c + X₀
Y_plot = Y_c + Y₀

Here, (X_c, Y_c) denotes the current value of X and Y coordinates.

Step-05:

Keep repeating Step-03 and Step-04 until X_plot => Y_plot.

Step-06:

Step-05 generates all the points for one octant.

To find the points for other seven octants, follow the eight symmetry property of circle.

This is depicted by the following figure-

PRACTICE PROBLEMS BASED ON BRESENHAM CIRCLE DRAWING ALGORITHM-

Problem-01:

Given the centre point coordinates (0, 0) and radius as 8, generate all the points to form a circle.

Solution-

Given-

Centre Coordinates of Circle (X₀, Y₀) = (0, 0)
Radius of Circle = 8

Step-01:

Assign the starting point coordinates (X₀, Y₀) as-

X₀ = 0
Y₀ = R = 8

Step-02:

Calculate the value of initial decision parameter P₀ as-

P₀ = 3 – 2 x R

P₀ = 3 – 2 x 8

P₀ = -13

Step-03:

As P_initial < 0, so case-01 is satisfied.

Thus,

X_k+1 = X_k + 1 = 0 + 1 = 1
Y_k+1 = Y_k = 8
P_k+1= P_k + 4 x X_k+1 + 6 = -13 + (4 x 1) + 6 = -3

Step-04:

This step is not applicable here as the given centre point coordinates is (0, 0).

Step-05:

Step-03 is executed similarly until X_k+1 >= Y_k+1 as follows-

P_k	P_k+1	(X_k+1, Y_k+1)
		(0, 8)
-13	-3	(1, 8)
-3	11	(2, 8)
11	5	(3, 7)
5	7	(4, 6)
7		(5, 5)
Algorithm Terminates These are all points for Octant-1.

Algorithm calculates all the points of octant-1 and terminates.

Now, the points of octant-2 are obtained using the mirror effect by swapping X and Y coordinates.

Octant-1 Points	Octant-2 Points
(0, 8)	(5, 5)
(1, 8)	(6, 4)
(2, 8)	(7, 3)
(3, 7)	(8, 2)
(4, 6)	(8, 1)
(5, 5)	(8, 0)
These are all points for Quadrant-1.

Now, the points for rest of the part are generated by following the signs of other quadrants.

The other points can also be generated by calculating each octant separately.

Here, all the points have been generated with respect to quadrant-1-

Quadrant-1 (X,Y)	Quadrant-2 (-X,Y)	Quadrant-3 (-X,-Y)	Quadrant-4 (X,-Y)
(0, 8)	(0, 8)	(0, -8)	(0, -8)
(1, 8)	(-1, 8)	(-1, -8)	(1, -8)
(2, 8)	(-2, 8)	(-2, -8)	(2, -8)
(3, 7)	(-3, 7)	(-3, -7)	(3, -7)
(4, 6)	(-4, 6)	(-4, -6)	(4, -6)
(5, 5)	(-5, 5)	(-5, -5)	(5, -5)
(6, 4)	(-6, 4)	(-6, -4)	(6, -4)
(7, 3)	(-7, 3)	(-7, -3)	(7, -3)
(8, 2)	(-8, 2)	(-8, -2)	(8, -2)
(8, 1)	(-8, 1)	(-8, -1)	(8, -1)
(8, 0)	(-8, 0)	(-8, 0)	(8, 0)
These are all points of the Circle.

Problem-02:

Given the centre point coordinates (10, 10) and radius as 10, generate all the points to form a circle.

Solution-

Given-

Centre Coordinates of Circle (X₀, Y₀) = (10, 10)
Radius of Circle = 10

Step-01:

Assign the starting point coordinates (X₀, Y₀) as-

X₀ = 0
Y₀ = R = 10

Step-02:

Calculate the value of initial decision parameter P₀ as-

P₀ = 3 – 2 x R

P₀ = 3 – 2 x 10

P₀ = -17

Step-03:

As P_initial < 0, so case-01 is satisfied.

Thus,

X_k+1 = X_k + 1 = 0 + 1 = 1
Y_k+1 = Y_k = 10
P_k+1= P_k + 4 x X_k+1 + 6 = -17 + (4 x 1) + 6 = -7

Step-04:

This step is applicable here as the given centre point coordinates is (10, 10).

X_plot = X_c + X₀ = 1 + 10 = 11

Y_plot = Y_c + Y₀ = 10 + 10 = 20

Step-05:

Step-03 and Step-04 are executed similarly until X_plot => Y_plot as follows-

P_k	P_k+1	(X_k+1, Y_k+1)	(X_plot, Y_plot)
		(0, 10)	(10, 20)
-17	-7	(1, 10)	(11, 20)
-7	7	(2, 10)	(12, 20)
7	-7	(3, 9)	(13, 19)
-7	15	(4, 9)	(14, 19)
15	13	(5, 8)	(15, 18)
13	19	(6, 7)	(16, 17)
Algorithm Terminates These are all points for Octant-1.

Algorithm calculates all the points of octant-1 and terminates.

Now, the points of octant-2 are obtained using the mirror effect by swapping X and Y coordinates.

Octant-1 Points	Octant-2 Points
(10, 20)	(17, 16)
(11, 20)	(18, 15)
(12, 20)	(19, 14)
(13, 19)	(19, 13)
(14, 19)	(20, 12)
(15, 18)	(20, 11)
(16, 17)	(20, 10)
These are all points for Quadrant-1.

Now, the points for rest of the part are generated by following the signs of other quadrants.

The other points can also be generated by calculating each octant separately.

Here, all the points have been generated with respect to quadrant-1-

Quadrant-1 (X,Y)	Quadrant-2 (-X,Y)	Quadrant-3 (-X,-Y)	Quadrant-4 (X,-Y)
(10, 20)	(10, 20)	(10, 0)	(10, 0)
(11, 20)	(9, 20)	(9, 0)	(11, 0)
(12, 20)	(8, 20)	(8, 0)	(12, 0)
(13, 19)	(7, 19)	(7, 1)	(13, 1)
(14, 19)	(6, 19)	(6, 1)	(14, 1)
(15, 18)	(5, 18)	(5, 2)	(15, 2)
(16, 17)	(4, 17)	(4, 3)	(16, 3)
(17, 16)	(3, 16)	(3, 4)	(17, 4)
(18, 15)	(2, 15)	(2, 5)	(18, 5)
(19, 14)	(1, 14)	(1, 6)	(19, 6)
(19, 13)	(1, 13)	(1, 7)	(19, 7)
(20, 12)	(0, 12)	(0, 8)	(20, 8)
(20, 11)	(0, 11)	(0, 9)	(20, 9)
(20, 10)	(0, 10)	(0, 10)	(20, 10)
These are all points of the Circle.

Advantages of Bresenham Circle Drawing Algorithm-

The advantages of Bresenham Circle Drawing Algorithm are-

The entire algorithm is based on the simple equation of circle X² + Y² = R².
It is easy to implement.

Disadvantages of Bresenham Circle Drawing Algorithm-

The disadvantages of Bresenham Circle Drawing Algorithm are-

Like Mid Point Algorithm, accuracy of the generating points is an issue in this algorithm.
This algorithm suffers when used to generate complex and high graphical images.
There is no significant enhancement with respect to performance.

To gain better understanding about Bresenham Circle Drawing Algorithm,

Watch this Video Lecture

Get more notes and other study material of Computer Graphics.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Mid Point Circle Drawing Algorithm

Computer Graphics

Circle Drawing Algorithms-

In computer graphics, popular algorithms used to generate circle are-

Mid Point Circle Drawing Algorithm
Bresenham’s Circle Drawing Algorithm

In this article, we will discuss about Mid Point Circle Drawing Algorithm.

Mid Point Circle Drawing Algorithm-

Given the centre point and radius of circle,

Mid Point Circle Drawing Algorithm attempts to generate the points of one octant.

The points for other octacts are generated using the eight symmetry property.

Procedure-

Given-

Centre point of Circle = (X₀, Y₀)
Radius of Circle = R

The points generation using Mid Point Circle Drawing Algorithm involves the following steps-

Step-01:

Assign the starting point coordinates (X₀, Y₀) as-

X₀ = 0
Y₀ = R

Step-02:

Calculate the value of initial decision parameter P₀ as-

P₀ = 1 – R

Step-03:

Suppose the current point is (X_k, Y_k) and the next point is (X_k+1, Y_k+1).

Find the next point of the first octant depending on the value of decision parameter P_k.

Follow the below two cases-

Step-04:

If the given centre point (X₀, Y₀) is not (0, 0), then do the following and plot the point-

X_plot = X_c + X₀
Y_plot = Y_c + Y₀

Here, (X_c, Y_c) denotes the current value of X and Y coordinates.

Step-05:

Keep repeating Step-03 and Step-04 until X_plot >= Y_plot.

Step-06:

Step-05 generates all the points for one octant.

To find the points for other seven octants, follow the eight symmetry property of circle.

This is depicted by the following figure-

Also Read- Line Drawing Algorithms

PRACTICE PROBLEMS BASED ON MID POINT CIRCLE DRAWING ALGORITHM-

Problem-01:

Given the centre point coordinates (0, 0) and radius as 10, generate all the points to form a circle.

Solution-

Given-

Centre Coordinates of Circle (X₀, Y₀) = (0, 0)
Radius of Circle = 10

Step-01:

Assign the starting point coordinates (X₀, Y₀) as-

X₀ = 0
Y₀ = R = 10

Step-02:

Calculate the value of initial decision parameter P₀ as-

P₀ = 1 – R

P₀ = 1 – 10

P₀ = -9

Step-03:

As P_initial < 0, so case-01 is satisfied.

Thus,

X_k+1 = X_k + 1 = 0 + 1 = 1
Y_k+1 = Y_k = 10
P_k+1= P_k + 2 x X_k+1 + 1 = -9 + (2 x 1) + 1 = -6

Step-04:

This step is not applicable here as the given centre point coordinates is (0, 0).

Step-05:

Step-03 is executed similarly until X_k+1 >= Y_k+1 as follows-

P_k	P_k+1	(X_k+1, Y_k+1)
		(0, 10)
-9	-6	(1, 10)
-6	-1	(2, 10)
-1	6	(3, 10)
6	-3	(4, 9)
-3	8	(5, 9)
8	5	(6, 8)
Algorithm Terminates These are all points for Octant-1.

Algorithm calculates all the points of octant-1 and terminates.

Now, the points of octant-2 are obtained using the mirror effect by swapping X and Y coordinates.

Octant-1 Points	Octant-2 Points
(0, 10)	(8, 6)
(1, 10)	(9, 5)
(2, 10)	(9, 4)
(3, 10)	(10, 3)
(4, 9)	(10, 2)
(5, 9)	(10, 1)
(6, 8)	(10, 0)
These are all points for Quadrant-1.

Now, the points for rest of the part are generated by following the signs of other quadrants.

The other points can also be generated by calculating each octant separately.

Here, all the points have been generated with respect to quadrant-1-

Quadrant-1 (X,Y)	Quadrant-2 (-X,Y)	Quadrant-3 (-X,-Y)	Quadrant-4 (X,-Y)
(0, 10)	(0, 10)	(0, -10)	(0, -10)
(1, 10)	(-1, 10)	(-1, -10)	(1, -10)
(2, 10)	(-2, 10)	(-2, -10)	(2, -10)
(3, 10)	(-3, 10)	(-3, -10)	(3, -10)
(4, 9)	(-4, 9)	(-4, -9)	(4, -9)
(5, 9)	(-5, 9)	(-5, -9)	(5, -9)
(6, 8)	(-6, 8)	(-6, -8)	(6, -8)
(8, 6)	(-8, 6)	(-8, -6)	(8, -6)
(9, 5)	(-9, 5)	(-9, -5)	(9, -5)
(9, 4)	(-9, 4)	(-9, -4)	(9, -4)
(10, 3)	(-10, 3)	(-10, -3)	(10, -3)
(10, 2)	(-10, 2)	(-10, -2)	(10, -2)
(10, 1)	(-10, 1)	(-10, -1)	(10, -1)
(10, 0)	(-10, 0)	(-10, 0)	(10, 0)
These are all points of the Circle.

Problem-02:

Given the centre point coordinates (4, -4) and radius as 10, generate all the points to form a circle.

Solution-

Given-

Centre Coordinates of Circle (X₀, Y₀) = (4, -4)
Radius of Circle = 10

As stated in the algorithm,

We first calculate the points assuming the centre coordinates is (0, 0).
At the end, we translate the circle.

Step-01, Step-02 and Step-03 are already completed in Problem-01.

Now, we find the values of X_plot and Y_plot using the formula given in Step-04 of the main algorithm.

The following table shows the generation of points for Quadrant-1-

X_plot = X_c + X₀= 4 + X₀
Y_plot = Y_c + Y₀ = 4 + Y₀

(X_k+1, Y_k+1)	(X_plot, Y_plot)
(0, 10)	(4, 14)
(1, 10)	(5, 14)
(2, 10)	(6, 14)
(3, 10)	(7, 14)
(4, 9)	(8, 13)
(5, 9)	(9, 13)
(6, 8)	(10, 12)
(8, 6)	(12, 10)
(9, 5)	(13, 9)
(9, 4)	(13, 8)
(10, 3)	(14, 7)
(10, 2)	(14, 6)
(10, 1)	(14, 5)
(10, 0)	(14, 4)
These are all points for Quadrant-1.

The following table shows the points for all the quadrants-

Quadrant-1 (X,Y)	Quadrant-2 (-X,Y)	Quadrant-3 (-X,-Y)	Quadrant-4 (X,-Y)
(4, 14)	(4, 14)	(4, -6)	(4, -6)
(5, 14)	(3, 14)	(3, -6)	(5, -6)
(6, 14)	(2, 14)	(2, -6)	(6, -6)
(7, 14)	(1, 14)	(1, -6)	(7, -6)
(8, 13)	(0, 13)	(0, -5)	(8, -5)
(9, 13)	(-1, 13)	(-1, -5)	(9, -5)
(10, 12)	(-2, 12)	(-2, -4)	(10, -4)
(12, 10)	(-4, 10)	(-4, -2)	(12, -2)
(13, 9)	(-5, 9)	(-5, -1)	(13, -1)
(13, 8)	(-5, 8)	(-5, 0)	(13, 0)
(14, 7)	(-6, 7)	(-6, 1)	(14, 1)
(14, 6)	(-6, 6)	(-6, 2)	(14, 2)
(14, 5)	(-6, 5)	(-6, 3)	(14, 3)
(14, 4)	(-6, 4)	(-6, 4)	(14, 4)
These are all points of the Circle.

Advantages of Mid Point Circle Drawing Algorithm-

The advantages of Mid Point Circle Drawing Algorithm are-

It is a powerful and efficient algorithm.
The entire algorithm is based on the simple equation of circle X² + Y² = R².
It is easy to implement from the programmer’s perspective.
This algorithm is used to generate curves on raster displays.

Disadvantages of Mid Point Circle Drawing Algorithm-

The disadvantages of Mid Point Circle Drawing Algorithm are-

Accuracy of the generating points is an issue in this algorithm.
The circle generated by this algorithm is not smooth.
This algorithm is time consuming.

Important Points

Circle drawing algorithms take the advantage of 8 symmetry property of circle.
Every circle has 8 octants and the circle drawing algorithm generates all the points for one octant.
The points for other 7 octants are generated by changing the sign towards X and Y coordinates.
To take the advantage of 8 symmetry property, the circle must be formed assuming that the centre point coordinates is (0, 0).
If the centre coordinates are other than (0, 0), then we add the X and Y coordinate values with each point of circle with the coordinate values generated by assuming (0, 0) as centre point.

To gain better understanding about Mid Point Circle Drawing Algorithm,

Watch this Video Lecture

Next Article- Bresenham Circle Drawing Algorithm

Get more notes and other study material of Computer Graphics.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Mid Point Line Drawing Algorithm

Computer Graphics

Line Drawing Algorithms-

In computer graphics, popular algorithms used to generate lines are-

Digital Differential Analyzer (DDA) Line Drawing Algorithm
Bresenham Line Drawing Algorithm
Mid Point Line Drawing Algorithm

In this article, we will discuss about Mid Point Line Drawing Algorithm.

Mid Point Line Drawing Algorithm-

Given the starting and ending coordinates of a line,

Mid Point Line Drawing Algorithm attempts to generate the points between the starting and ending coordinates.

Also Read- DDA Line Drawing Algorithm

Procedure-

Given-

Starting coordinates = (X₀, Y₀)
Ending coordinates = (X_n, Y_n)

The points generation using Mid Point Line Drawing Algorithm involves the following steps-

Step-01:

Calculate ΔX and ΔY from the given input.

These parameters are calculated as-

ΔX = X_n – X₀
ΔY =Y_n – Y₀

Step-02:

Calculate the value of initial decision parameter and ΔD.

These parameters are calculated as-

D_initial = 2ΔY – ΔX
ΔD = 2(ΔY – ΔX)

Step-03:

The decision whether to increment X or Y coordinate depends upon the flowing values of D_initial.

Follow the below two cases-

Step-04:

Keep repeating Step-03 until the end point is reached.

For each D_new value, follow the above cases to find the next coordinates.

PRACTICE PROBLEMS BASED ON MID POINT LINE DRAWING ALGORITHM-

Problem-01:

Calculate the points between the starting coordinates (20, 10) and ending coordinates (30, 18).

Solution-

Given-

Starting coordinates = (X₀, Y₀) = (20, 10)
Ending coordinates = (X_n, Y_n) = (30, 18)

Step-01:

Calculate ΔX and ΔY from the given input.

ΔX = X_n – X₀ = 30 – 20 = 10
ΔY =Y_n – Y₀ = 18 – 10 = 8

Step-02:

Calculate D_initial and ΔD as-

D_initial = 2ΔY – ΔX = 2 x 8 – 10 = 6
ΔD = 2(ΔY – ΔX) = 2 x (8 – 10) = -4

Step-03:

As D_initial >= 0, so case-02 is satisfied.

Thus,

X_k+1 = X_k + 1 = 20 + 1 = 21
Y_k+1 = Y_k + 1 = 10 + 1 = 11
D_new= D_initial + ΔD = 6 + (-4) = 2

Similarly, Step-03 is executed until the end point is reached.

D_initial	D_new	X_k+1	Y_k+1
		20	10
6	2	21	11
2	-2	22	12
-2	14	23	12
14	10	24	13
10	6	25	14
6	2	26	15
2	-2	27	16
-2	14	28	16
14	10	29	17
10		30	18

Problem-02:

Calculate the points between the starting coordinates (5, 9) and ending coordinates (12, 16).

Solution-

Given-

Starting coordinates = (X₀, Y₀) = (5, 9)
Ending coordinates = (X_n, Y_n) = (12, 16)

Step-01:

Calculate ΔX and ΔY from the given input.

ΔX = X_n – X₀ = 12 – 5 = 7
ΔY =Y_n – Y₀ = 16 – 9 = 7

Step-02:

Calculate D_initial and ΔD as-

D_initial = 2ΔY – ΔX = 2 x 7 – 7 = 7
ΔD = 2(ΔY – ΔX) = 2 x (7 – 7) = 0

Step-03:

As D_initial >= 0, so case-02 is satisfied.

Thus,

X_k+1 = X_k + 1 = 5 + 1 = 6
Y_k+1 = Y_k + 1 = 9 + 1 = 10
D_new= D_initial + ΔD = 7 + 0 = 7

Similarly, Step-03 is executed until the end point is reached.

D_initial	D_new	X_k+1	Y_k+1
		5	9
7	7	6	10
7	7	7	11
7	7	8	12
7	7	9	13
7	7	10	14
7	7	11	15
7		12	16

Advantages of Mid Point Line Drawing Algorithm-

The advantages of Mid Point Line Drawing Algorithm are-

Accuracy of finding points is a key feature of this algorithm.
It is simple to implement.
It uses basic arithmetic operations.
It takes less time for computation.
The resulted line is smooth as compared to other line drawing algorithms.

Also Read- Bresenham Line Drawing Algorithm

Disadvantages of Mid Point Line Drawing Algorithm-

The disadvantages of Mid Point Line Drawing Algorithm are-

This algorithm may not be an ideal choice for complex graphics and images.
In terms of accuracy of finding points, improvement is still needed.
There is no any remarkable improvement made by this algorithm.

To gain better understanding about Mid Point Line Drawing Algorithm,

Watch this Video Lecture

Next Article- Mid Point Circle Drawing Algorithm

Get more notes and other study material of Computer Graphics.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Bresenham Line Drawing Algorithm

Computer Graphics

Line Drawing Algorithms-

In computer graphics, popular algorithms used to generate lines are-

Digital Differential Analyzer (DDA) Line Drawing Algorithm
Bresenham Line Drawing Algorithm
Mid Point Line Drawing Algorithm

In this article, we will discuss about Bresenham Line Drawing Algorithm.

Bresenham Line Drawing Algorithm-

Given the starting and ending coordinates of a line,

Bresenham Line Drawing Algorithm attempts to generate the points between the starting and ending coordinates.

Also Read- DDA Line Drawing Algorithm

Procedure-

Given-

Starting coordinates = (X₀, Y₀)
Ending coordinates = (X_n, Y_n)

The points generation using Bresenham Line Drawing Algorithm involves the following steps-

Step-01:

Calculate ΔX and ΔY from the given input.

These parameters are calculated as-

ΔX = X_n – X₀
ΔY =Y_n – Y₀

Step-02:

Calculate the decision parameter P_k.

It is calculated as-

P_k = 2ΔY – ΔX

Step-03:

Suppose the current point is (X_k, Y_k) and the next point is (X_k+1, Y_k+1).

Find the next point depending on the value of decision parameter P_k.

Follow the below two cases-

Step-04:

Keep repeating Step-03 until the end point is reached or number of iterations equals to (ΔX-1) times.

PRACTICE PROBLEMS BASED ON BRESENHAM LINE DRAWING ALGORITHM-

Problem-01:

Calculate the points between the starting coordinates (9, 18) and ending coordinates (14, 22).

Solution-

Given-

Starting coordinates = (X₀, Y₀) = (9, 18)
Ending coordinates = (X_n, Y_n) = (14, 22)

Step-01:

Calculate ΔX and ΔY from the given input.

ΔX = X_n – X₀ = 14 – 9 = 5
ΔY =Y_n – Y₀ = 22 – 18 = 4

Step-02:

Calculate the decision parameter.

P_k

= 2ΔY – ΔX

= 2 x 4 – 5

= 3

So, decision parameter P_k = 3

Step-03:

As P_k >= 0, so case-02 is satisfied.

Thus,

P_k+1 = P_k + 2ΔY – 2ΔX = 3 + (2 x 4) – (2 x 5) = 1
X_k+1 = X_k + 1 = 9 + 1 = 10
Y_k+1 = Y_k + 1 = 18 + 1 = 19

Similarly, Step-03 is executed until the end point is reached or number of iterations equals to 4 times.

(Number of iterations = ΔX – 1 = 5 – 1 = 4)

P_k	P_k+1	X_k+1	Y_k+1
		9	18
3	1	10	19
1	-1	11	20
-1	7	12	20
7	5	13	21
5	3	14	22

Problem-02:

Calculate the points between the starting coordinates (20, 10) and ending coordinates (30, 18).

Solution-

Given-

Starting coordinates = (X₀, Y₀) = (20, 10)
Ending coordinates = (X_n, Y_n) = (30, 18)

Step-01:

Calculate ΔX and ΔY from the given input.

ΔX = X_n – X₀ = 30 – 20 = 10
ΔY =Y_n – Y₀ = 18 – 10 = 8

Step-02:

Calculate the decision parameter.

P_k

= 2ΔY – ΔX

= 2 x 8 – 10

= 6

So, decision parameter P_k = 6

Step-03:

As P_k >= 0, so case-02 is satisfied.

Thus,

P_k+1 = P_k + 2ΔY – 2ΔX = 6 + (2 x 8) – (2 x 10) = 2
X_k+1 = X_k + 1 = 20 + 1 = 21
Y_k+1 = Y_k + 1 = 10 + 1 = 11

Similarly, Step-03 is executed until the end point is reached or number of iterations equals to 9 times.

(Number of iterations = ΔX – 1 = 10 – 1 = 9)

P_k	P_k+1	X_k+1	Y_k+1
		20	10
6	2	21	11
2	-2	22	12
-2	14	23	12
14	10	24	13
10	6	25	14
6	2	26	15
2	-2	27	16
-2	14	28	16
14	10	29	17
10	6	30	18

Advantages of Bresenham Line Drawing Algorithm-

The advantages of Bresenham Line Drawing Algorithm are-

It is easy to implement.
It is fast and incremental.
It executes fast but less faster than DDA Algorithm.
The points generated by this algorithm are more accurate than DDA Algorithm.
It uses fixed points only.

Disadvantages of Bresenham Line Drawing Algorithm-

The disadvantages of Bresenham Line Drawing Algorithm are-

Though it improves the accuracy of generated points but still the resulted line is not smooth.
This algorithm is for the basic line drawing.
It can not handle diminishing jaggies.

To gain better understanding about Bresenham Line Drawing Algorithm,

Watch this Video Lecture

Next Article- Mid Point Line Drawing Algorithm

Get more notes and other study material of Computer Graphics.

Watch video lectures by visiting our YouTube channel LearnVidFun.

← Older Posts

Newer Posts →