Rev.
01 Dated 10/12/2022
NETHAJI MEMORIAL ARTS AND SCIENCE COLLEGE, NEMMARA
DEPARTMENT OF COMPUTER SCIENCE
STUDY MATERIAL
Class & Year of Admission 2021-24
Course with Code BCS6B16
Semester 6th semester
Hours per week 4
Credits 3
Prepared By (Name of faculty) S.Ranjini
Syllabus
• Module 1
Introduction to Computer Graphics Definition, Application, Pixel, Frame Buer,
Rasterand Random Scan display, Display devices CRT, Color CRT Monitors,
basics of LCD &LED Monitors.
• Module 2
Scan Conversion of line DDA algorithm of line drawing, Scan conversion of circles
Bresenham's circle generating algorithm, Polygon FillingScan line polygon filling
algorithm.
• Module 3
Two Dimensional transformation, Translation, Rotation, Scaling, Homogeneous
Coordinates, Reflection, Shear.
• Module 4
Window to view port transformation, clipping, line clipping, Cohen Sutherland line
clipping, Polygon clipping, Sutherland and Gary Hodgman polygon clipping
algorithm.
• Module 5
Color Models &Color Applications Light and Color, Different color models, RGB,
CMY,YIQ. Introduction to GIMP Image Manipulation using GIMP.
UNIT 1
UNIT I
Line Drawing Algorithms-
In computer graphics, popular algorithms used to generate lines are-
1. Digital Differential Analyzer (DDA) Line Drawing Algorithm
2. Bresenham Line Drawing Algorithm
3. Mid Point Line Drawing Algorithm
DDA Algorithm-
DDA Algorithm is the simplest line drawing algorithm.
Given the starting and ending coordinates of a line,
DDA Algorithm attempts to generate the points between the starting and ending coordinates.
Procedure-
Starting coordinates = (X0, Y0)
Ending coordinates = (Xn, Yn)
The points generation using DDA Algorithm involves the following steps-
Step-01:
Calculate ΔX, ΔY and M from the given input.
These parameters are calculated as-
ΔX = Xn – X0
ΔY =Yn – Y0
M = ΔY / ΔX
Step-02:
Find the number of steps or points in between the starting and ending coordinates.
if (absolute (ΔX) > absolute (ΔY))
Steps = absolute (ΔX);
else
Steps = absolute (ΔY);
Step-03:
Suppose the current point is (Xp, Yp) and the next point is (Xp+1, Yp+1).
Find the next point by following the below three cases-
Step-04:
Keep repeating Step-03 until the end point is reached or the number of generated new points (including the starting and ending points) equals to the steps
count.
PRACTICE PROBLEMS BASED ON DDA ALGORITHM-
Problem-01:
Calculate the points between the starting point (5, 6) and ending point (8, 12).
Solution-
Given-
Starting coordinates = (X0, Y0) = (5, 6)
Ending coordinates = (Xn, Yn) = (8, 12)
Step-01:
Calculate ΔX, ΔY and M from the given input.
ΔX = Xn – X0 = 8 – 5 = 3
ΔY =Yn – Y0 = 12 – 6 = 6
M = ΔY / ΔX = 6 / 3 = 2
Step-02:
Calculate the number of steps.
As |ΔX| < |ΔY| = 3 < 6, so number of steps = ΔY = 6
Step-03:
As M > 1, so case-03 is satisfied.
Now, Step-03 is executed until Step-04 is satisfied.
Xp Yp Xp+1 Yp+1 Round off (Xp+1, Yp+1)
5 6 5.5 7 (6, 7)
6 8 (6, 8)
6.5 9 (7, 9)
7 10 (7, 10)
7.5 11 (8, 11)
8 12 (8, 12)
Advantages of DDA Algorithm-
The advantages of DDA Algorithm are-
It is a simple algorithm.
It is easy to implement.
It avoids using the multiplication operation which is costly in terms of time complexity.
Disadvantages of DDA Algorithm-
The disadvantages of DDA Algorithm are-
There is an extra overhead of using round off( ) function.
Using round off( ) function increases time complexity of the algorithm.
Resulted lines are not smooth because of round off( ) function.
The points generated by this algorithm are not accurate.
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.
Starting coordinates = (X0, Y0)
Ending coordinates = (Xn, Yn)
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 = Xn – X0
ΔY =Yn – Y0
Step-02:
Calculate the decision parameter Pk.
It is calculated as-
Pk = 2ΔY – ΔX
Step-03:
Suppose the current point is (Xk, Yk) and the next point is (Xk+1, Yk+1).
Find the next point depending on the value of decision parameter Pk.
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 = (X0, Y0) = (9, 18)
Ending coordinates = (Xn, Yn) = (14, 22)
Step-01:
Calculate ΔX and ΔY from the given input.
ΔX = Xn – X0 = 14 – 9 = 5
ΔY =Yn – Y0 = 22 – 18 = 4
Step-02:
Calculate the decision parameter.
Pk
= 2ΔY – ΔX
=2x4–5
=3
So, decision parameter Pk = 3
Step-03:
As Pk >= 0, so case-02 is satisfied.
Thus,
Pk+1 = Pk + 2ΔY – 2ΔX = 3 + (2 x 4) – (2 x 5) = 1
Xk+1 = Xk + 1 = 9 + 1 = 10
Yk+1 = Yk + 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)
Pk Pk+1 Xk+1 Yk+1
9 18
3 1 10 19
1 -1 11 20
-1 7 12 20
7 5 13 21
5 3 14 22
S.NO DDA Line Algorithm Bresenham line Algorithm
DDA stands for Digital Differential
1. While it has no full form.
Analyzer.
DDA algorithm is less efficient than While it is more efficient than DDA
2.
Bresenham line algorithm. algorithm.
The calculation speed of DDA While the calculation speed of
3. algorithm is less than Bresenham line Bresenham line algorithm is faster than
algorithm. DDA algorithm.
DDA algorithm is costlier than While Bresenham line algorithm is
4.
Bresenham line algorithm. cheaper than DDA algorithm.
S.NO DDA Line Algorithm Bresenham line Algorithm
DDA algorithm has less precision or
5. While it has more precision or accuracy.
accuracy.
In DDA algorithm, the complexity of While in this, the complexity of calculation
6.
calculation is more complex. is simple.
In DDA algorithm, optimization is not
7. While in this, optimization is provided.
provided.
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.
Procedure-
Given-
Centre point of Circle = (X0, Y0)
Radius of Circle = R
The points generation using Bresenham Circle Drawing Algorithm involves the following steps-
Step-01:
Assign the starting point coordinates (X0, Y0) as-
X0 = 0
Y0 = R
Step-02:
Calculate the value of initial decision parameter P0 as-
P0 = 3 – 2 x R
Step-03:
Suppose the current point is (Xk, Yk) and the next point is (Xk+1, Yk+1).
Find the next point of the first octant depending on the value of decision parameter Pk.
Follow the below two cases-
Step-4
If the given centre point (X0, Y0) is not (0, 0), then do the following and plot the point-
Xplot = Xc + X0
Yplot = Yc + Y0
Here, (Xc, Yc) denotes the current value of X and Y coordinates.
Step-05:
Keep repeating Step-03 and Step-04 until Xplot => Yplot.
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-
Problem-1
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 (X0, Y0) = (0, 0)
Radius of Circle = 8
Step-01:
Assign the starting point coordinates (X0, Y0) as-
X0 = 0
Y0 = R = 8
Step-02:
Calculate the value of initial decision parameter P0 as-
P0 = 3 – 2 x R
P0 = 3 – 2 x 8
P0 = -13
Step-03:
As Pinitial < 0, so case-01 is satisfied.
Thus,
Xk+1 = Xk + 1 = 0 + 1 = 1
Yk+1 = Yk = 8
Pk+1 = Pk + 4 x Xk+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 Xk+1 >= Yk+1 as follows-
(Xk+1,
Pk Pk+1
Yk+1)
(0, 8)
-
-3 (1, 8)
13
-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 Quadrant-2 (- Quadrant-3 (- Quadrant-4
(X,Y) X,Y) X,-Y) (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.
POLYGON FILLING
• Given vertices of a polygon and a colour , our aim is to fill the
polygon with the particular colour
• 2 methods
– Boundary method
• Intersect polygon with horizontal lines and fills the polygon
between pairs of intersection
• Used with simple objects
– Fill method
• Start from an interior position and paint until the boundary
condition reached
SCAN LINE FILLING
• Filling up of polygons using horizontal lines or scanlines
• Purpose is to fill the interior pixels of a polygon , given only verticesand
edges of the figure
• Algorithm works by intersecting scanline with the polygon edgesand
fill the polygon between pairs of intersection
BASIC CONCEPTS
• There are 3 steps to perform in order
– Find the intersections of the scanline with all edges of the
polygon
– Sort the intersections by increasing x coordinates, ie. from leftto right
– Make pairs of intersections and fill in colour within all the pixelsinside
the pair
Simple example
• List of intersection points 8,12,16,20
• Sorted order will be 8,12,16,20
• Make pairs of intersection (8,12),(16,20)
• Fill in all the pixels with the given colour insidethe
pixel
SPECIAL CASES
• Some scan line intersections at polygon vertices requires special
handling
• A scan line passing through vertex intersects two polygon edges atthat
position adding two points to the list of intersections for the scanline
• 2 cases
– If both lines intersecting at the vertex are on the same side ofthe
scanline , consider it as two points
– If lines intersecting at the vertex are on the opposite side of thescan line
consider it as a single point
• Scan line y’ is intersecting with 4 edges and passing through a vertex
• Here edges at vertex are on same side of the scanline . So count thevertex twice
• The pairs of intersection points are (8,12),(12,14)
Scanline y is intersecting with5 edges and also passing through a vertex
The edges are on opposite side of the vertex. So count the vertex as
single intersection point
The pairs of intersection points are (6,16),(20,22)
UNIT III
Old point
New Point
HOMOGENOUS COORDINATE
1. (0,0)
2. (0,1)->1+2*0=1
(0,1)
3. (2,0)->0+2*2=4
(2,4)
4. (2,2)->2+2*2=6
(2,6)
UNIT IV
UNIT V
COLOR MODELS
WHITE
W White
W
What is GIMP
GIMP (GNU Image Manipulation Program) is a free and open-source image
editor tool. It is a cross-platform tool available for different operating systems such
as GNU/Linux, macOS, Windows, etc. As it is open-source, its source code can be
downloaded. It is packaged with most of the Linux distros.
It is a useful tool for Graphic Designers, Photographer, and other professionals. It
supports various third-party plug-in to make it a more advanced editing tool. We
can enhance our creativity with the help of these plug-ins.
It is a useful tool for various image manipulation tasks such as photo editing,
image composition, image construction, logo designing, painting, and many more.
It is capable enough of being used as a simple paint tool, an advanced photo
editing tool, a mass production image renderer, or an image format converter tool.
One of the other reasons for its popularity is that it is a free tool while other editing
tools such as photoshop are paid. Most Linux distributions include it as a standard
application. But, it can be downloaded for other platforms such as macOS and
Windows as well.
Gimp is licensed under the GPL (General Public License). The tools that are
licensed under the GPL provides the freedom to alter the source code.
Features of GIMP
Some key Features of GIMP are as following:
Free and Open Source
It is a free and open-source tool.
Cross-Platform
It is a cross-platform tool available for different operating systems such
as GNU/Linux, macOS, Windows, and more
High-Quality Photo Manipulation
It has massive supports for the tools needed for high-quality image editing. It can
perform some advanced tasks such as image retouching, image restoring, image
composing, etc.
Original Artwork Creation
It is enough capable and flexible to transform an image into truly unique creations.
Graphic Design Elements
The Gimp is a vital tool for creating icons, logos, graphical design elements,
interactive arts for UI, and mockups.
Programming Algorithms
It also provides an advanced framework for scripted image manipulation with
multiple programming language support like C, C++, Python, Perl, etc.
Key Component in a Desktop Publishing Workflow
It provides color management features to ensure the high-quality fadable color
reproduction across media. Further, It provides an interactive workflow in other
tools such as Scribus, Inkscape, and SwatchBooker.
Apart from all the above features, it also provides the following list of features:
o It provides a full suite of painting tools such as brushes, airbrush, pencil, cloning,
etc.
o It provides a tile-based memory management tool to limit the image size by
available disk space.
o It provides a sub-pixel sampling for high-quality and anti-aliasing.
o It provides full alpha channel support for transparency.
o It provides several layers an channels.
o It supports a procedural database for calling internal GIMP functions from an
external program.
o It has advanced scripting capabilities.
o It provides several undo/redo options.
o It provides several transformation tools such as rotate, scale, shear, and flip.
o It supports a wide range of file formats such as GIF, JPEG, PNG, TIFF, PDF,
BMP, etc.
o It provides several selection tools such as rectangle, ellipse, circle, fuzzy, bezier,
etc.
o It supports various plug-ins for the easy addition of new file formats and filters.
