[Link]

com

Two Dimensional

Nipun Thapa(Computer Graphics)

Viewing
Unit 3

1
 [Link]

Two Dimensional Viewing

• Two-dimensional viewing is the mechanism for displaying
views of a picture on an output device. Much like what we see
in real life through a small window on the wall or the
viewfinder of a camera, a computer-generated image often
depicts a partial view of a large scene. For a 2-D picture, a

Nipun Thapa(Computer Graphics)

view is selected by specifying a subarea of the total picture
area.

2
 [Link]

2D Coordinate System
1. Modeling Coordinates
• Modeling coordinates are used to construct shape of individual parts
(objects or structures) of a 2D scene. For example, generating a circle
at the origin with a “radius” of 2 units.
• Here, origin (0, 0), and radius 2 units are modeling coordinates.

Nipun Thapa(Computer Graphics)

• Modeling coordinates define object shape.
• Can be floating-point, integers and can represent units like km, m,
miles, feet etc.

View Coordinates Device Coordinates

3
 [Link]

2D Coordinate System..
2. World Coordinates
• World coordinates are used to organize the individual parts
into a scene.
• World coordinates units define overall scene to be modeled.

Nipun Thapa(Computer Graphics)

• World coordinates represent relative positions of objects.
• Can be floating-point, integers and can represent units like km,
m, miles etc.

4
 [Link]

2D Coordinate System..
3. Viewing Coordinates
• Viewing coordinates are used to define particular view of the user.
Viewer‟s position and view angle i.e. rotated/translated.
• Viewing coordinates specify the portion of the output device that is
to be used to present the view.

Nipun Thapa(Computer Graphics)

• Normalized viewing coordinates are viewing coordinates between 0
and 1 in each direction. They are used to make the viewing process
independent of the output device (paper, mobile).

5
View Coordinates
 [Link]

2D Coordinate System..
4. Device Coordinates or Screen Coordinates
• The display coordinate system is called device coordinate
system. Device coordinates are specific to output device.
• Device coordinates are integers within the range (0, 0) to

Nipun Thapa(Computer Graphics)

(xmax, ymax) for a particular output device.

6
Device Coordinates
 [Link]

2D Coordinate System..

Nipun Thapa(Computer Graphics)

View Coordinates Device Coordinates

7
 [Link]

Window and Viewport

Window:
• A world-coordinate area selected for display is called a window or clipping
window. That is, window is the section of the 2D scene that is selected for
viewing.
• The window defines what is to be viewed.
Viewport
• An area on a display device to which a window is mapped is called a viewport.

Nipun Thapa(Computer Graphics)

• The viewport indicates where on an output device selected part will be
displayed.

8
Window to Viewport transformation
[Link]

A window is specified by four world coordinates: Xwmin, Xwmax, Ywmin

and Ywmax (see Fig.). Similarly, a viewport is described by four normalized
device coordinates: Xvmin, Xvmax, Yvmin and Yvmax.

Window Viewport

Nipun Thapa(Computer Graphics)

1. Translate the window to the origin. That is, apply T (-Xwmin, -Ywmin)
2. Scale it to the size of the viewport. That is, apply S (sx, sy)
3. Translate scaled window to the position of the viewport. That is, apply
T(Xvmin, Yvmin). 9
Therefore, net transformation,
TWV = T (Xvmin, Yvmin). S(sx, sy).T(-Xwmin, -Ywmin)
 [Link]
• Let (x, y) be the world coordinate point that is mapped onto the
viewport point (u, v), then we must have

=
=

Nipun Thapa(Computer Graphics)

v
=
=

Where 10
 [Link]

Window to Viewport transformation

Nipun Thapa(Computer Graphics)

11
 [Link]

Window to Viewport transformation

Nipun Thapa(Computer Graphics)

12
 [Link]

Window and Viewport……

• Window and viewport are often rectangular in standard
positions, because it simplifies the transformation process and
clipping process. Other shapes such as polygons, circles take
longer time to process. By changing the position of the
viewport, we can view objects at different positions on the

Nipun Thapa(Computer Graphics)

display area of an output device. Also by varying the size of
viewports, we can change size of displayed objects. Zooming
effects can be obtained by successively mapping different-sized
windows on a fixed-sized viewport.

13
 [Link]

Two-Dimensional Viewing Pipeline

Nipun Thapa(Computer Graphics)

• The mapping of a part of a world co-ordinate scene to a device co-
ordinate is referred to as viewing transformation.
• Sometimes, the 2D viewing transformation is simply referred to as
the window–to–viewport transformation or the windowing
transformation.
• The transformation that maps the window into the viewport is
applied to all of the output primitives (lines, rectangles, circles) in
world coordinates. 14
• This viewing transformation involves several steps.
 [Link]

Clipping
• The process of identifying those portions of a picture that are
either inside or outside of the specified region of space is
called clipping.
Two possible ways to apply clipping in the viewing transformation:
1. Apply clipping in the world coordinate system: ignore objects that

Nipun Thapa(Computer Graphics)

lie outside of the window.
2. Apply clipping in the device coordinate system: ignore objects that
lie outside of the viewport.

Before Clipping After Clipping

15
 [Link]

Clipping..
Why Clipping?
1. Excludes unwanted graphics from the screen.
2. Improves efficiency, as the computation dedicated to
objects that appear off screen can be significantly reduced.

Nipun Thapa(Computer Graphics)

Applications:
1. In drawing and painting, it is used to select picture parts for
copying, erasing, moving.
2. Displaying a multi-window environment.

16
 [Link]

Point Clipping
• Let W denote a clip window with coordinates (xwmin, ywmin),
(Xwmin, Ywmax), (Xwmax, Ywmin), (Xwmax, Ywmax), then a
vertex (x, y) is displayed only if following “point clipping”
inequalities are satisfied:
Xwmin ≤ x ≤ Xwmax,

Nipun Thapa(Computer Graphics)

Ywmin ≤ y ≤ Ywmax.
• Very simple and efficient.
• Only works for vertices.

17
 [Link]

Line Clipping
• Lines that do not intersect the clipping window are either
completely inside the window or completely outside the
window. On the other hand, a line that intersects the clipping
window is divided by the intersection point(s) into segments
that are either inside or outside the window.

Nipun Thapa(Computer Graphics)

18
 [Link]
For any particular line segment:
a. Both endpoints are inside the region (line AB).
• No clipping necessary.
b. One endpoint is inside and one is outside of the clipping window
(line CD).
• Clip at intersection point.
c. Both endpoints are outside the region:
• No intersection (lines EF, GH)
• Discard the line segment.

Nipun Thapa(Computer Graphics)

• Line intersects the region (line IJ)
• Clip line at both intersection points.
Before clipping After Clipping

19
 [Link]

Line Clipping…

Nipun Thapa(Computer Graphics)

20
 [Link]

Cohen-Sutherland Line Clipping Algorithm

• One of the oldest and most popular line-clipping algorithms.

In this method, coordinate system is divided into nine regions.
All regions have their associated region codes. Every line
endpoint is assigned a four digit binary code (region code or
out code). Each bit in the code is set to either a 1(true) or a

Nipun Thapa(Computer Graphics)

0(false). Assign a bit pattern to each region as shown:

Ywmax

Ywmin 21

Xwmin Xwmax
 [Link]
Step 1 : Establish Region code for all line end point
• First bit is 1, if x < Xwmin (Point lies to left of window) , else set it to 0
• Second bit is 1, if x > Xwmax (Point lies to right of window) , else set it to 0
• Third bit is 1, if y < Ywmin (Point lies to below window), else set it to 0
• Fourth bit is 1, if y > Ywmax (Point lies to above window) , else set it to 0

Fourth Bit

Nipun Thapa(Computer Graphics)

Ywmax

First Bit Second Bit

Ywmin
22

Third Bit
Xwmin Xwmax
 [Link]
Step 2: Determine which lines are completely inside window
and which are not
a) If both end points of line has region codes ‘0000’ line is
completely inside window.
b) If logical AND operation of region codes of two end points is
NOT ‘0000’. The line is completely outside (some bit position
have 1’s)

Nipun Thapa(Computer Graphics)

Astart 0000
Aend 0000 C
Completely inside

C 1001
D 0001 D
AND
0001
Completely Outside 23
 [Link]
Step 3 : If both tests fail then line is partially visible so we need to
find the intersection with boundaries of window .

a) If 1st bit is 1 then line intersect with Left boundary and

• Yi= Y1 + m (X – X1) where X= Xwmin

b) If 2nd bit is 1 then line intersect with Right boundary and

• Yi= Y1 + m (X – X1)

Nipun Thapa(Computer Graphics)

where X= Xwmax
c) If 3rd bit is 1 then line intersect with Bottom boundary and

• Xi= X1 + (1/m) (Y – Y1) where Y= Ywmin

d) If 4th bit is 1 then line intersect with Top boundary and

• Xi= X1 + (1/m) (Y – Y1) where Y= Ywmax

24
Here, (Xi , Yi) are (X ,Y) intercepts for that the step 4 repeat step 1 through step 3
until line is completely accepted or rejected
 [Link]

Cohen-Sutherland Line Clip Examples

Nipun Thapa(Computer Graphics)

25
 [Link]

Cohen-Sutherland Line Clip Examples

Nipun Thapa(Computer Graphics)

26
Numerical [Link]
Q. Clip a line with end point A(5,30) , B(20,60) against a clip window with
lower most left corner at P1(10,10) and upper right corner at P2(100,100)
Ans:
P2(100,100)
Step 1: Establish the region
codes for end point A,B
A(5,30) B(20,60)
5<10 : (true)= 1 20<10: (false) =0
5>100 : (false) =0 20>100: (false)=0
30<10 : (false) =0 60<10 : (false)=0

Nipun Thapa(Computer Graphics)

30>100 : (false) =0 60>100: (false)=0 P1(10,10)
A(5,30) = 0001 B(20,60)=0000

Step 2: Visibility check

A: 0001
B: 0000 Partial Visibility After Clipping P2(100,100)
AND
0000
Step 3: Intersection point with boundary
A: 0001 , Condn of 1st bit is 1
Yi= Y1 + m (X – X1) where , X= 10 27
= 30 + 2 (10-5)
= 40
P1(10,10)
(X,Y)=(10,40)
Q. Clip a line with end point A(5,15) , B(110,60) against a clip
[Link]
window with lower most left corner at P1(10,10) and upper
right corner at P2(100,100)

Q. Given a clipping window P (30,0), S(0,20) use the Cohen

Sutherland algorithm to determine the visible portion of the
line A(10,30) and B(40,0).

Nipun Thapa(Computer Graphics)

Q. . Given a clipping window P(0,0), Q(10,20), S(0,20) use the
Cohen Sutherland algorithm to determine the visible portion of
the line A(10,30) and B(40,0).

Q. Clip a line with end point A(1,60) , B(20,120) against a clip

window with lower most left corner at P1(10,10) and upper 28
right corner at P2(100,100)
 [Link]

Polygon Clipping
• A polygon can be defined as a geometric object "consisting of
a number of points (called vertices) and an equal number of
line segments (called sides or edges). Polygon clipping is
defined as the process of removing those parts of a polygon
that lie outside a clipping window. Consider a general polygon

Nipun Thapa(Computer Graphics)

that is clipped with respect to a rectangular viewing region.

Window Window

29
Before clipping After clipping
 [Link]

Sutherland-Hodgeman Polygon Clipping Algorithm

• The Sutherland-Hodgeman Polygon-Clipping Algorithms clips a
given polygon successively against the edges of the given clip-
rectangle. It starts with the initial set of polygon vertices, first
clips the polygon against the left rectangle boundary of the
window. Then successively against the right boundary, bottom
boundary, and finally against the top boundary, as shown in

Nipun Thapa(Computer Graphics)

figure.

Original Polygon Clip Left Clip Right Clip Bottom Clip Top
30
 [Link]

Nipun Thapa(Computer Graphics)

Line Drawing Algorithm

31
 [Link]

Points and Lines

• Points
• Plotted by converting co-ordinate position to appropriate
operations for the output device (e.g.: in CRT monitor, the electron
beam is turned on to illuminate the screen phosphor at the
selected location.)

Nipun Thapa (Computer Graphics)

• Line
• Plotted by calculating intermediate positions along the line
path between two specified endpoint positions.
• Screen locations are referenced with integer values, so
plotted positions may only approximate actual line
positions between two specified endpoints  “the
jaggies”. E.g.: position (10.48,20.51)  (10,21).

32
 [Link]

Pixel Position
• Pixel position: referenced by scan line number and column
number

Nipun Thapa (Computer Graphics)

33
 [Link]

LINE DRAWING ALGORITHM

• DDA Algorithm- (Digital Differential Analyzer)
• Bresenham’s Line Algorithm
Note:
• Pixel- picture element smallest piece of information in an
image represented using dots, squares and rectangle

Nipun Thapa (Computer Graphics)

• Components-
• RGB
• or
Y Scan Line
• 4 components
(cyan ,magenta,
yellow & black)
Pixel
0 34
0
Column number X
 [Link]

DDA Algorithm
 Digital Differential Analyzer
Scan-conversion line – algorithm based on calculating either

Nipun Thapa (Computer Graphics)

Sample the line at unit intervals in one coordinate
Determine the corresponding integer values nearest the line
path in another co-ordinate

35
 [Link]

CASE 1
Positive Slope
(Y always increase when X increases and
Y always Decreases when X decrease)

Nipun Thapa (Computer Graphics)

CASE 2
Negative Slope
(Y always increase when X decrease and
Y always Decreases when X increases)
36
CASE 1 [Link]

Positive Slope
1. Slope less than 1 ( |M| < 1 ) and
moving Left to Right
M=1

Nipun Thapa (Computer Graphics)

Xk+1 = Xk + 1
Y2
YK+1 = Yk + M
Y1

37
X1 X2
CASE 1 [Link]

Positive Slope
2. Slope less than 1 ( |M| < 1 ) and
moving Right to Left
M=1

Nipun Thapa (Computer Graphics)

Xk+1 = Xk - 1
Y2
YK+1 = Yk - M
Y1

38
X1 X2
CASE 1 [Link]

Positive Slope
3. Slope greater than 1 ( |M| > 1 ) and
moving Left to Right
M=1

Y2

Nipun Thapa (Computer Graphics)

Xk+1 = Xk + 1/M
YK+1 = Yk + 1 Y1

X1 X2 39
CASE 1 [Link]

Positive Slope
4. Slope Greater than 1 ( |M| > 1 ) and
moving Right to Left
M=1

Y2

Nipun Thapa (Computer Graphics)

Xk+1 = Xk – 1/M
YK+1 = Yk - 1 Y1

X1 X2 40
 [Link]
CASE 2
Negative Slope
1. Slope less than 1 ( |M| < 1 ) and
moving Left to Right

M=-1

Nipun Thapa (Computer Graphics)

Xk+1 = Xk + 1
Y1
YK+1 = Yk + M
Y2

X2 41
X1
 [Link]
CASE 2
Negative Slope
2. Slope less than 1 ( |M| < 1 ) and
moving Right to Left

M=-1

Nipun Thapa (Computer Graphics)

Xk+1 = Xk - 1
Y1
YK+1 = Yk - M
Y2

X2 42
X1
 [Link]
CASE 2
Negative Slope
3. Slope greater than 1 ( |M| > 1 ) and
moving Left to Right

M=-1

Nipun Thapa (Computer Graphics)

Y1
Xk+1 = Xk – 1/M
Y2
YK+1 = Yk - 1

X1 X2 43
 [Link]
CASE 2
Negative Slope
4. Slope Greater than 1 ( |M| > 1 ) and
moving Right to Left

M=-1

Nipun Thapa (Computer Graphics)

Y1
Xk+1 = Xk +1/M
Y2
YK+1 = Yk +1

X1 X2 44
 DDA
[Link]

Nipun Thapa(Computer Graphics)

45
 [Link]
DDA Examples
Q.> Digitize a Line with end point A(2,3) and B(6,8) , using DDA.
A.> Here , Slope (M) = (8-3)/(6-2) = 1.25
here Slope is positive and greater than 1
And moving left to right and 1/m = 0.8
So , we use X = X + 1/M
k+1 k
YK+1 = Yk + 1

Nipun Thapa (Computer Graphics)

K Xk+1 = Xk + 1/M YK+1 = Yk + 1 (X,Y)

1 =2 + 0.8 = 2.8 ~ 3 4 (3,4)

2 =2.8 + 0.8= 3.6 ~ 4 5 (4,5)
3 =3.6 + 0.8 = 4.4 ~ 4 6 (4,6)
4 = 4.4 + 0.8 = 5.2 ~ 5 7 (5,7)
5 = 5.2 + 0.8 = 6 8 (6,8) 46
 [Link]
DDA Examples
Q.> Digitize a Line with end point A(2,3) and B(6,8) , using DDA
Right to left.

Q.> Digitize a Line with end point A(3,2) and B(8,4) , using DDA

Nipun Thapa (Computer Graphics)

Q.>Digitize a Line with end point A(2,6) and B(4,2) , using DDA

47
 [Link]
DDA Final Exercise
1. Digitize the line from A(1,1) to B(10,8) using scan conversion line
algorithm.
2. Draw a line with two end point P(5,3) and Q(1,2) using DDA
3. Digitize the line with endpoints A(1,7) and B(6,3) using digital
differential analyzer line drawing algorithm. Show all necessary
steps. (TU 2013, 3 marks) .

Nipun Thapa(Computer Graphics)

4. Digitize the line with end points (1,2) and (5,6) using digital
differential analyzer method.(TU 2012, 3 marks).
5. Digitize the given line endpoints (1,1) and (5, 5) using DDA.
6. Draw a line using DDA with two end points A(0,0) and B(-10,8).
7. Digitize line with start at (5,3) and end at (1,5) using DDA.
8. Digitize DDA with all necessary steps with two end points (0,0)
and (10,0). 48
 [Link]

Bresenham’s Line Algorithm

The BLA is a more efficient method used to plot pixel position
along a straight-line path.
Advantage of BLA over DDA
• In DDA algorithm each successive point is computed in floating
point, so it requires more time and more memory space. While in

Nipun Thapa(Computer Graphics)

BLA each successive point is calculated in integer value or whole
number. So it requires less time and less memory space.
• In DDA, since the calculated point value is floating point number, it
should be rounded at the end of calculation but in BLA it does not
need to round, so there is no accumulation of rounding error.
• Due to rounding error, the line drawn by DDA algorithm is not
accurate, while in BLA line is accurate.
• DDA algorithm cannot be used in other application except line
drawing, but BLA can be implemented in other application such as
circle, ellipse and other curves. 49
 [Link]

BLA for slope +ve and |m| ≤ 1

Nipun Thapa(Computer Graphics)

+1 +1

+1 +1

+1 +1 50
 [Link]
Let us assume that pixel (xk, yk) is already
plotted assuming that the sampling direction is
along X-axis i.e. (xk+1, yk) or (xk+1, yk+1). Thus, the
common equation of the line is
y = m(xk+1) + c
Now,

Nipun Thapa(Computer Graphics)

d1 = y - yk = m (xk +1) + c - yk
and
d2 = (yk +1)- y = yk+1– {m (xk +1) + c }

51
 [Link]

The difference betn these two separation is,

d1 - d2 = [m (xk +1) + c - yk ] - [yk+1– {m (xk +1) + c }]
Or,
d1- d2 = 2m (xk+1)+ 2c - 2yk -1
Since, slope of line (m) = Δy / Δx,

Nipun Thapa(Computer Graphics)

We have,
Δx (d1- d2) = 2 Δy (xk+1)+ 2 Δx C - 2 Δx Yk – Δx
Define Decision parameter at Kth step,
Pk = Δx (d1- d2)
= 2 Δy (xk+1)+ 2 Δx C - 2 Δx yk – Δx
52
=2 Δy Xk+2 Δy + 2 Δx c - 2 Δx yk – Δx
 [Link]
Pk=2 Δy Xk+2 Δy + 2 Δx c - 2 Δx yk – Δx
Now , K+1th term
Pk+1 = 2 Δy Xk+1+2 Δy + 2 Δx c - 2 Δx yk+1 – Δx

Here,
Pk+1- Pk = 2 Δy Xk+1+2 Δy + 2 Δx c - 2 Δx yk+1 – Δx – {2 Δy Xk+2
Δy + 2 Δx c - 2 Δx yk – Δx }

Nipun Thapa(Computer Graphics)

= 2 Δy Xk+1+2 Δy + 2 Δx c - 2 Δx yk+1 – Δx – 2 Δy Xk- 2
Δy - 2 Δx c + 2 Δx yk + Δx
Pk+1 = Pk +2 Δy Xk+1 - 2 Δx yk+1– 2 Δy Xk+ 2 Δx yk

53
Pk+1 = Pk +2 Δy(Xk+1 – Xk)- 2 Δx(Yk+1– Yk)
 [Link]
Case 1
If Pk < 0 (i.e. d1-d2 is Negative )
then,
Xk+1 = Xk+1
Yk+1 = Yk

Pk = Pk + 2 Δy

Nipun Thapa(Computer Graphics)

Case 2
If Pk ≥ 0 (i.e. d1-d2 is Positive )
then,
Xk+1 = Xk+1
Yk+1 = Yk+1

Pk = Pk + 2 Δy -2Δx 54
 [Link]
Initial Decision Parameter (P0)

y = m(xk+1) + c

Let, X0 = 0 , Y0 = 0 then C = 0

Δx (d1- d2) = 2 Δy Xk+2 Δy + 2 Δx c - 2 Δx yk – Δx

Nipun Thapa(Computer Graphics)

P0 = 0 + 2 Δy + 0 + 0 – Δx

P0 = 2 Δy - Δx

55
 [Link]
Example-1: Digitize the line with end points (20, 10) and (30, 18)
using BLA.
Solution :
Here, Starting point of line = (x1, y1) = (20, 10) and
Ending point of line = (x2, y2) = (30, 18)
Thus, slope of line, m = Δy / Δx = y2-y1 / x2-x1
= (18-10) / (30-20)

Nipun Thapa(Computer Graphics)

= 8/10
As the given points, it is clear that the line is moving left to right
with the positive slop
|m| = 0.8 <1

56
Thus, [Link]
The initial decision parameter (P0) = 2Δy - Δx = 2*8 – 10 = 6
Since, for the Bresenham’s Line drawing Algorithm of slope, |m| ≤ 1, we have

If Pk < 0 (i.e. d1-d2 is Negative ) If Pk ≥ 0

then, then,
Xk+1 = Xk+1 Xk+1 = Xk+1
Yk+1 = Yk Yk+1 = Yk+1
Pk = Pk + 2 Δy Pk = Pk + 2 Δy -2Δx
(20, 10)

Nipun Thapa(Computer Graphics)

57
 [Link]
Example-2: Digitize the line with end points (15, 5) and (30, 10)
using BLA.

Nipun Thapa(Computer Graphics)

58
 [Link]
Example-3: Digitize the line with end points (20, 5) and (25, 10)
using BLA.

Nipun Thapa(Computer Graphics)

59
 [Link]

BLA for slope +ve and |m| > 1

(Xk, ) (Xk, )

Nipun Thapa(Computer Graphics)

( ,Yk) ( ,Yk)

+1 +1

+1 +1
60
+1 +1
 [Link]

Let us assume that pixel (xk, yk) is already

plotted assuming that the sampling direction is
along X-axis i.e. (xk, yk+1) or (xk+1, yk+1). Thus, the
common equation of the line is
Y=MX+C
yK+1 = mx + c

Nipun Thapa(Computer Graphics)

X= {yk+1 – c}/m
Now,

d1 = X - Xk = {yk +1 – c}/m - xk
and
d2 = (Xk +1)- X = xk+1– {yk+1 – c}/m 61
 [Link]
So,
d1 - d2 = [{yk +1 – c}/m - xk] -[xk+1–
{{yk+1 – c}/m }]
Or,
d1 - d2 = 2/m* (yk+1) - 2c/m – 2xk -1

Nipun Thapa(Computer Graphics)

Since, slope of line (m) = Δy / Δx,
we have
Pk = Δy (d1 - d2)
= 2Δx (yk+1) - 2c Δx - 2Δy xk - Δy 62
 [Link]
Pk = 2Δx (yk+1) - 2c Δx - 2Δy xk - Δy
Now , K+1th term
Pk+1 = 2Δx (yk+1+1) - 2c Δx - 2Δy xk+1 – Δy
Here,
Pk+1-Pk = {2Δx (yk+1+1) - 2c Δx - 2Δy xk+1 – Δy} -

Nipun Thapa(Computer Graphics)

{2Δx (yk+1) - 2c Δx - 2Δy xk - Δy}
= 2Δx (yk+1 - yk) - 2Δy (xk+1 - xk)
Or,

Pk+1 = Pk + 2Δx (yk+1 - yk) - 2Δy (xk+1 - xk) 63

 [Link]
Pk+1 = Pk + 2Δx (yk+1 - yk) - 2Δy (xk+1 - xk)
Case 1
If Pk < 0 (i.e. d1-d2 is Negative )
then,
Xk+1 = Xk
Yk+1 = Yk+1

Pk = Pk + 2 Δx

Nipun Thapa(Computer Graphics)

Case 2
If Pk ≥ 0 (i.e. d1-d2 is Positive )
then,
Xk+1 = Xk+1
Yk+1 = Yk+1
64
Pk = Pk + 2 Δx -2Δy
 [Link]

Initial Decision Parameter (P0)

We Know,
Pk = 2Δx (yk+1) - 2c Δx - 2Δy xk - Δy
Let, X0 = 0 , Y0 = 0 then C = 0
Then,
P0 = 2Δx (y0 +1) - 2c Δx - 2Δy x0 - Δy

Nipun Thapa(Computer Graphics)

P0 = 2 Δx - Δy
65
 [Link]
Example-4: Digitize the line with end points (1, 0) and
(3, 3) using BLA.
Solution :
Here,
Starting point of line = (x1, y1) = (1, 0) and
Ending point of line = (x2, y2) = (3, 3)
Thus,

Nipun Thapa(Computer Graphics)

slope of line, m = Δy / Δx = y2-y1 / x2-x1
= (3-0) / (3-1)
= 3/2
As the given points, it is clear that the line is moving
left to right with the positive slope,
|m| = 1.5 >1 66
 [Link]
Thus, the initial decision parameter
Δx = x2-x1 = 3-1 = 2
(P0) = 2Δx - Δy = 2*2 – 3 = 1 Δy = y2-y1 = 3-0 = 3
we have
If Pk < 0 If Pk ≥ 0
then, then,
Xk+1 = Xk Xk+1 = Xk+1
Yk+1 = Yk+1 Yk+1 = Yk+1
Pk = Pk + 2 Δx Pk = Pk + 2 Δx -2Δy

Nipun Thapa(Computer Graphics)

67
 [Link]
Example-5: Digitize A(5,2) and B(7,8) using BLA.

Nipun Thapa(Computer Graphics)

68
 [Link]
Example
1. Digitize the line A(1,1) and B(5,6) using BLA.
2. Digitize the line A(7,8) and B(1,4) using BLA.
3. Digitize the line A(1,1) and B(5,6) using DDA.
4. Digitize the line A(5,2) and B(7,8) using BLA.

Nipun Thapa(Computer Graphics)

5. Digitize the line A(0,0) and B(10,10) using
BLA.
6. Digitize the line A(1,3) and B(10,10) using
BLA and DDA.
69
 [Link]

Slope –Ve and |M| ≤ 1

(Xk-1,Yk+1) (Xk-1,Yk+1)
(Xk,Yk+1)

d2
d2
Y
Y

d1

Nipun Thapa(Computer Graphics)

d1

(Xk-1,Yk) (Xk,Yk) (Xk-1,Yk) (Xk,Yk)

d1-d2 > 0 (Positive) d1-d2 < 0 (Negative)

Xk+1 = Xk - 1 Xk+1 = Xk - 1
Yk+1 = Yk +1 Yk+1 = Yk
70
 [Link]
Let us assume that pixel (xk, yk) is already plotted assuming
that the sampling direction is along X-axis i.e. (xk-1, yk+1)
or (xk-1, yk). Thus, the common equation of the line is
Y=Mx + C
Here,
Y= m(Xk-1)+c
Now,
d1=Y-Yk

Nipun Thapa(Computer Graphics)

And
d2= (Yk+1)-Y
Or,
d1-d2= Y-Yk – {(Yk+1)-Y}
= Y-Yk –Yk-1+Y
=2y-2yk -1
=2m(Xk-1)+ 2c - 2yk - 1 71
Here slope of line (m) = - (Δy / Δx), {for –ve slope)
 [Link]
d1- d2 = 2m(Xk-1)+ 2c - 2yk - 1
Now , (m) = - (Δy / Δx),
d1- d2 = -2 {(Δy / Δx)} (Xk-1)+ 2c - 2yk - 1
Δx(d1-d2) = -2 Δy (Xk-1)+ 2 c Δx – 2 Δx Yk - Δx
Here Pk = Δx(d1-d2)
= -2 Δy (Xk-1)+ 2 c Δx – 2 Δx Yk - Δx
Pk = -2 Δy Xk + 2 Δy + 2 c Δx – 2 Δx Yk - Δx
Now k+1 th term

Nipun Thapa(Computer Graphics)

Pk+1 = -2 Δy Xk+1 + 2 Δy + 2 c Δx – 2 Δx Yk+1 - Δx
Or,
Pk+1 – Pk = -2 Δy Xk+1 - 2 Δy + 2 c Δx – 2 Δx Yk+1 - Δx
+2 Δy Xk + 2 Δy - 2 c Δx + 2 Δx Yk + Δx
= -2Δy(Xk+1 - Xk) +2Δx (-Yk+1 + Yk)

Pk+1 = Pk - 2Δy(Xk+1 - Xk) + 2Δx (-Yk+1 + Yk) 72

 [Link]
Pk+1 = Pk - 2Δy(X k+1 - Xk) - 2Δx (Yk+1 – Yk)

Case 1
If Pk < 0 (i.e. d1-d2 is Negative )
then,
Xk+1 = Xk - 1
Yk+1 = Yk

Pk = Pk + 2 Δy

Nipun Thapa(Computer Graphics)

Case 2
If Pk ≥ 0 (i.e. d1-d2 is Positive )
then,
Xk+1 = Xk - 1
Yk+1 = Yk +1
73
Pk = Pk + 2 Δy -2Δx
 [Link]

Initial Decision Parameter (P0)

We Know,
Pk = -2 Δy Xk + 2 Δy + 2 c Δx – 2 Δx Yk - Δx
Let, X0 = 0 , Y0 = 0 then C = 0
Then,
P0 = -2 Δy X0 + 2 Δy + 2 c Δx – 2 Δx Y0 - Δx

Nipun Thapa(Computer Graphics)

P0 = 2 Δy - Δx
74
 [Link]

Slope –Ve and |M| > 1

(Xk-1,Yk+1) (Xk,Yk+1)
(Xk,Yk+1) (Xk-1,Yk+1)

d1 d2 d1
d2

Nipun Thapa(Computer Graphics)

(Xk,Yk) (Xk-1,Yk)
(Xk-1,Yk) X X
(Xk,Yk)

d1-d2 > 0 (Positive) d1-d2 < 0 (Negative)

Xk+1 = Xk - 1 Xk+1 = Xk
Yk+1 = Yk +1 Yk+1 = Yk +1
75
 [Link]
Let us assume that pixel (xk, yk) is already plotted assuming that the
sampling direction is along X-axis i.e. (xk-1, yk+1) or (xk, yk +1). Thus,
the common equation of the line is
Y=Mx + C
Here,
Yk +1 = mX+c
X= {Yk +1-C}/M
Now,

Nipun Thapa(Computer Graphics)

d1=Xk-X Slope –Ve and |M|> 1
And
d2= X-{Xk-1}
Or,
d1-d2 = Xk-X – { X-{Xk-1} }
= Xk-X – X+Xk-1
= 2Xk – 2X -1
= 2Xk -2 {Yk +1-C}/M -1 76
Here slope of line (m) = - (Δy / Δx), {for –ve slope)
 [Link]
d1 – d2 = 2Xk -2 {Yk +1-C}/M -1
= 2Xk -2 {Yk +1-C}/{- (Δy / Δx)} -1
= 2Xk + 2 {Yk +1-C}/{ (Δy / Δx)} -1
Δy (d1 – d2 ) = 2 Δy Xk + 2 Δx {Yk +1-C} - Δy
= 2 Δy Xk + 2 Δx Yk + 2 Δx - 2 Δx C - Δy
Pk = Δy (d1 – d2 ) for decision parameter
Pk = 2 Δy Xk + 2 Δx Yk + 2 Δx - 2 Δx C - Δy

Nipun Thapa(Computer Graphics)

Now K+1 th term
Pk+1 = 2 Δy Xk+1 + 2 Δx Yk+1 + 2 Δx - 2 Δx C - Δy
Or,
Pk+1- Pk = 2 Δy Xk+1 + 2 Δx Yk+1 + 2 Δx - 2 Δx C - Δy
- 2 Δy Xk - 2 Δx Yk - 2 Δx + 2 Δx C + Δy
= 2 Δy (Xk+1 - Xk ) + 2 Δx (Yk+1 - Yk )
77
Pk+1 = Pk +2 Δy (Xk+1 - Xk ) + 2 Δx (Yk+1 - Yk )
 Pk+1 = Pk +2 Δy[Link]
(Xk+1 - Xk ) + 2 Δx (Yk+1 - Yk )
Case 1
If Pk < 0 (i.e. d1-d2 is Negative )
then,
Xk+1 = Xk
Yk+1 = Yk +1

Pk = Pk + 2 Δx

Nipun Thapa(Computer Graphics)

Case 2
If Pk ≥ 0 (i.e. d1-d2 is Positive )
then,
Xk+1 = Xk - 1
Yk+1 = Yk +1
78
Pk = Pk+ 2Δx - 2 Δy
 [Link]

Initial Decision Parameter (P0)

We Know,
Pk = 2 Δy Xk + 2 Δx Yk + 2 Δx - 2 Δx C - Δy
Let, X0 = 0 , Y0 = 0 then C = 0
Then,
P0 = 2 Δy X0 + 2 Δx Y0 + 2 Δx - 2 Δx C - Δy

Nipun Thapa(Computer Graphics)

P0 = 2 Δx - Δy
79
Example: Digitize the given line endpoints (5, 10) and (10, 7) using Bresenham’s line
[Link]
drawingalgorithm.(TU 2014)
Solution:
Here, (X1,Y1)= (10,7) & Δx = |5-10| = 5
(X2,Y2)=(5,10) Δy = |10-7| = 3
M= (10-7)/(5-10) = -3/5 –ve slope and |M| < 1 here,
Initial (P0) = 2 Δy – Δx
If Pk < If Pk ≥ 0
Xk+1 = Xk - 1 = 2x3-5
Xk+1 = Xk - 1
Yk+1 = Yk Yk+1 = Yk +1 =1
Pk = Pk + 2 Δy Pk = Pk + 2 Δy -2Δx

Nipun Thapa(Computer Graphics)

(10, 7)
K Pk Xk+1 Yk+1 (Xk+1, Yk+1)
0 1 9 8 (9,8)
1 = 1 + 2x3 - 2x5 =-3 8 8 (8,8)
2 = -3 + 2x3 = 3 7 9 (7,9)
3 = 3 + 2x3 – 2x5 = -1 6 9 (6,9)
4 = -1 + 2x3 = 5 5 10 (5,10) 80
Example: Digitize line with endpoints (3, 10) and (6,2) using Bresenham's Line
[Link]
DrawingAlgorithm. ( TU 2016)
Solution:
Here, (X1,Y1)= (6,2) & Δx = |3-6| = 3
(X2,Y2)=(3,10) Δy = |10-2| = 8
M= (10-2)/(3-6) = 8/-3 –ve slope and |M| > 1 here,
If Pk < 0 If Pk ≥ 0 Initial (P0) = 2 Δx – Δy
Xk+1 = Xk Xk+1 = Xk - 1 = 2x3-8
Yk+1 = Yk +1 Yk+1 = Yk +1 = -2
Pk = Pk + 2 Δx Pk = Pk+ 2Δx - 2 Δy

Nipun Thapa(Computer Graphics)

(6, 2)
K PK Xk+1 Yk+1 (Xk+1 ,Yk+1)
0 -2 6 3 (6,3)
1 =-2+2x3 = 4 5 4 (5,4)
2 =4+6-16=-6 5 5 (5,5)
3 =-6+6=0 4 7 (4,7)
4 =0+6-16=-10 4 8 (4,8) 81
5 =-10+6= -4 4 9 (4,9)
6 =-4 +6 =2 3 10 (3,10)
Example: Digitize the given line endpoints (15, 15) and (10, 18) using Bresenham’s
[Link]
line drawingalgorithm.
Solution:
Here, (X1,Y1)= (15,15) & Δx = |10-15| = 5
(X2,Y2)= (10,18) Δy = |18-15| = 3
M= (18-15)/(10-15) = 3/-5 –ve slope and |M| < 1 here,
Initial (P0) = 2 Δy – Δx
If Pk < If Pk ≥ 0
Xk+1 = Xk - 1 = 2x3-5
Xk+1 = Xk - 1
Yk+1 = Yk Yk+1 = Yk +1 =1
Pk = Pk + 2 Δy Pk = Pk + 2 Δy -2Δx

Nipun Thapa(Computer Graphics)

(15, 15)
K Pk Xk+1 Yk+1 (Xk+1, Yk+1)
0 1 14 16 (14,16)
1 = 1 + 2x3 - 2x5 =-3 13 16 (13,16)
2 = -3 + 2x3 = 3 12 17 (12,17)
3 = 3 + 2x3 – 2x5 = -1 11 17 (11,17)
4 = -1 + 2x3 = 5 10 18 (10,18) 82
Example: Digitize the given line [Link]
endpoints (10, 10) and (20, 5) using Bresenham’s
line drawingalgorithm.
Solution:
Here, (X1,Y1)= (20,5) & Δx = |10-20| = 10
(X2,Y2)= (10,10) Δy = |10-5| = 5
M= (10-5)/(10-20) = 5/-10 –ve slope and |M| < 1 here,
Initial (P0) = 2 Δy – Δx
If Pk < If Pk ≥ 0
Xk+1 = Xk - 1 = 2x5-10
Xk+1 = Xk - 1
Yk+1 = Yk Yk+1 = Yk +1 =0
Pk = Pk + 2 Δy Pk = Pk + 2 Δy -2Δx

Nipun Thapa(Computer Graphics)

(20, 5)
K Pk Xk+1 Yk+1 (Xk+1, Yk+1)
0 0 19 6 (19,6)
1 = 0 + 2x5 - 2x10 =-10 18 6 (18,6)
2 = -10 + 2x5 = 0 17 7 (17,7)
3 = 0 + 2x5 - 2x10 =-10 16 7 (16,7)
4 = -10 + 2x5 = 0 15 8 (15,8)
5 = 0 + 2x5 - 2x10 =-10 14 8 (14,8)
6 = -10 + 2x5 = 0 13 9 (13,9)
7 = 0 + 2x5 - 2x10 =-10 12 9 (12,9)
83
8 = -10 + 2x5 = 0 11 10 (11,10)
9 = 0 + 2x5 - 2x10 =-10 10 10 (10,10)
Example: Digitize line with endpoints (5, 6) and (6,3) using Bresenham's Line
[Link]
DrawingAlgorithm.
Solution:
Here, (X1,Y1)= (6,3) & Δx = |5-6| = 1
(X2,Y2)=(5,6) Δy = |6-3| = 3
M= (6-3)/(5-6) = 3/-1 –ve slope and |M| > 1 here,
If Pk < 0 If Pk ≥ 0 Initial (P0) = 2 Δx – Δy
Xk+1 = Xk Xk+1 = Xk - 1 = 2x1-3
Yk+1 = Yk +1 Yk+1 = Yk +1 = -1
Pk = Pk + 2 Δx Pk = Pk+ 2Δx - 2 Δy

Nipun Thapa(Computer Graphics)

(6, 3)
K PK Xk+1 Yk+1 (Xk+1 ,Yk+1)
0 -1 6 4 (6,4)
1 =-1+2x1 = 1 5 5 (5,5)
2 =1+2x1-2x3=-3 5 6
(5,6)
84
 [Link]
BLA for slope +ve
|M| ≤ 1 |M| >1

if Pk < 0 If Pk ≥ 0 If Pk < 0 If Pk ≥ 0
Xk+1 = Xk+1 Xk+1 = Xk+1 Xk+1 = Xk Xk+1 = Xk+1
Yk+1 = Yk Yk+1 = Yk+1 Yk+1 = Yk+1 Yk+1 = Yk+1
Pk = Pk + 2 Δy Pk = Pk + 2 Δy -2Δx Pk = Pk + 2 Δx Pk = Pk + 2 Δx -2Δy

P0 = 2 Δy - Δx P0 = 2 Δx - Δy

Bresenham’s Line Algorithm

Nipun Thapa(Computer Graphics)

BLA for slope -ve
|M| ≤ 1 |M| >1

If Pk < 0 If Pk ≥ 0 If Pk < 0 If Pk ≥ 0
Xk+1 = Xk - 1 Xk+1 = Xk - 1 Xk+1 = Xk Xk+1 = Xk - 1
Yk+1 = Yk Yk+1 = Yk +1 Yk+1 = Yk +1 Yk+1 = Yk +1
Pk = Pk + 2 Δy Pk = Pk + 2 Δy -2Δx Pk = Pk + 2 Δx Pk = Pk+ 2Δx - 2 Δy 85

P0 = 2 Δy - Δx P0 = 2 Δx - Δy
Circle Algorithm
[Link]

What is Circle ?
• Similarly to the case with lines, there is an incremental
algorithm for drawing circles – the mid-point circle algorithm
• In the mid-point circle algorithm we use eight-way symmetry
so only ever calculate the points for the top right eighth of a
circle, and then use symmetry to get the rest of the points

Nipun Thapa(Computer Graphics)

86
 [Link] Clockwise direction

Mid Point Circle Algorithm

(Xk,Yk) (Xk+1,Yk)

Pk<0

Pk≥0 (Xk+1,Yk-1/2)

Nipun Thapa(Computer Graphics)

(Xk+1,Yk-1)

Pk< 0 Pk ≥ 0
XK+1 = Xk+1 XK+1 = Xk+1
87
YK+1 = Yk YK+1 = Yk-1
 [Link]

Mid Point Circle Algorithm

Nipun Thapa(Computer Graphics)

88
 [Link]

Mid Point Circle Algorithm

Nipun Thapa(Computer Graphics)

89
 [Link]

Nipun Thapa(Computer Graphics)

90
 [Link]

(Xk+1,Yk)
(Xk,Yk)
Pk<0
Case 1 : Pk < 0
Xk+1 = Xk +1
Yk+1 = Yk
Pk≥0 (Xk+1,Yk-1/2)
Pk+1 = Pk + 2(Xk+1) + 1
Pk+1 = Pk + 2Xk+1 + 1

Nipun Thapa(Computer Graphics)

Case 2: Pk ≥ 0 (Xk+1,Yk-1)
Xk+1 = Xk +1
Yk+1 = Yk - 1
Pk+1 = Pk + 2(xk+1) + [(yk – 1)2 - yk2)] - (yk - 1 - yk) +1
= Pk+2(xk+1) + [(yk 2 - 2yk +1 – yk 2)] - (yk-1- yk) + 1
= Pk+2(xk+1) - 2yk +1 +1 + 1 91
= Pk+2(xk+1) – 2(yk +1) +1
Pk+1 = Pk+2Xk+1 – 2Yk+1 +1
 [Link]
Initial decision parameter
(1,r)
(0,r)
i.e.,
(x0,y0) = (0,r)
(1,r-1/2)
Here ,

Nipun Thapa(Computer Graphics)

Fcircle (1,r-𝟏/𝟐) = P0

Now, (1,r-1)
P0 = 12+(r-1/2 )2 – r2
= 1 + r2- r + ¼ - r2
= 5/4 – r
P0 ≈ 1-r
92
P0 ≈ 1-r
 [Link]
Example : Digitize a circle with radius 10 at center (0,0)
Solution
Here, the initial decision parameter (P0) =1 – r = 1-10 = - 9
Since, for the Midpoint Circle Algorithm of initial point(0, r) &
center at origin (0, 0) rotating at clockwise direction, we have
Initial point (x0,y0) = (0,10)
P0=1-r = 1-10 = -9

Nipun Thapa(Computer Graphics)

93
 [Link]
Case 1 : Pk < 0 Case 2: Pk ≥ 0
Xk+1 = Xk +1 Xk+1 = Xk +1
Yk+1 = Yk Yk+1 = Yk - 1
Pk+1 = Pk + 2Xk+1 + 1 Pk+1 = Pk+2Xk+1 – 2Yk+1 +1
Thus, (0 , 10)
K PK X k+1 Y k+1 ( X k+1, Y k+1)
0 -9 0+1 = 1 10 (1,10)

Nipun Thapa(Computer Graphics)

1 = -9 + 2*1 +1= -6 1+2 =2 10 (2, 10)
2 =-6 + 2*2 +1= -1 2+1=3 10 (3, 10)
3 =-1 + 2*3 +1= 6 3+1 = 4 10-1=9 (4, 9)
4 =6 + 2*4 - 2*9 +1= -3 4+1 = 5 9 (5, 9)
5 =-3 + 2*5 +1= 8 5+1 = 6 9-1=8 (6, 8)
6 =8 + 2*6 - 2*8 +1= 5 6+1 = 7 8-1=7 (7, 7)
94
7 =5 +2*7 – 2*7 +1 =6 7+1 = 8 7-1=6 (8,6)
 [Link]

Nipun Thapa(Computer Graphics)

95
 [Link]

Example : Digitize a circle with radius 8

Nipun Thapa(Computer Graphics)

96
 [Link]
Example: Digitize a circle with radius 9 and
center at (6, 7).
Here, the initial decision parameter (P0)
P0 =1 – r = 1-9 = - 8
Since, for the Midpoint Circle Algorithm of starting point (0, r) &
centre at origin (0, 0) rotating at clockwise direction, we have

Nipun Thapa(Computer Graphics)

If P < 0
Plot (xk +1, yk )
Pk+1 = Pk + 2xk+1 + 1
Else (P ≥ 0)
Plot (xk +1, yk - 1)
Pk+1 = Pk+2xk+1 – 2yk+1 +1
97
 [Link]

k Pk Xk+1 Yk+ (Xk+1, Yk+1) (Xk+1, Yk+1)

1 At (0, 0) At (6, 7)

0. -8 0+1 = 1 9 (1, 9) (1+6, 9+7) = (7, 16)

1. = -8 + 2*1 +1= -5 1+1 = 2 9 (2, 9) (2+6, 9+7) = (8, 16)
2. = -5 + 2*2 +1= 0 2+1 = 3 8 (3, 8) (3+6, 8+7) = (9, 15)

Nipun Thapa(Computer Graphics)

3. = 0 + 2*3 - 2*8 +1=-9 3+1 = 4 8 (4, 8) (4+6, 8+7) = (10,15)

4. = -9 + 2*4 +1= 0 4+1 = 5 7 (5, 7) (5+6, 8+7) = (11,15)

5. = 0 + 2*5 - 2*7 +1=-3 5+1 = 6 7 (6, 7) (6+6, 7+7) = (12,14)

6. = -3 + 2*6 +1= 10 6+1 = 7 6 (7, 6) (7+6, 6+7) = (13,13)

98
 [Link]

Nipun Thapa(Computer Graphics)

99
 [Link] Anti-Clockwise direction

Mid Point Circle Algorithm

(Xk-1,Yk) (Xk,Yk)

Pk<0

(Xk-1,Yk-1/2) Pk ≥ 0

Nipun Thapa(Computer Graphics)

(Xk-1,Yk-1)

Pk< 0 Pk ≥ 0
XK+1 = Xk-1 XK+1 = Xk-1
100
YK+1 = Yk YK+1 = Yk-1
Here, [Link]
Decision parameter(Pk) = Fcircle (Xk -1,Yk-1/2)
= (Xk -1)2 + (Yk-1/2)2 - r2
Then, K+1th term is,
Pk+1= (Xk+1 -1)2 + (Yk+1 - 1/2)2 - r2

Now,
Pk+1 – Pk = (Xk+1 -1)2 + (Yk+1 - 1/2)2 - r2 – {(Xk -1)2 + (Yk-1/2)2 - r2}
= -2(xk-1)+(Y2k+1-Y2k) – (Yk+1 – Yk) + 1

Nipun Thapa(Computer Graphics)

[ ‫ ؞‬Xk+1 =Xk-1 in both condition ]

Pk+1= Pk-2xk+1+(Y2k+1-Y2k) – (Yk+1 – Yk) + 1

Case 1 : Pk< 0 Case 2: Pk ≥ 0

XK+1 = Xk-1 XK+1 = Xk-1
YK+1 = Yk YK+1 = Yk-1 101
Pk+1= Pk-2Xk+1 +1 Pk+1= Pk-2Xk+1 – 2Yk+1 +1
 [Link]
Initial decision parameter
(-1,r) (0,r)

i.e.,
(x0,y0) = (0,r)
(-1,r-1/2)
Here ,

Nipun Thapa(Computer Graphics)

Fcircle (-1,r-𝟏/𝟐) = P0

Now, (-1,r-1)
P0 = (-1)2+(r-1/2 )2 – r2
= 1 + r2- r + ¼ - r2
= 5/4 – r
P0 ≈ 1-r
102
P0 ≈ 1-r
 [Link]

2D Geometric

Nipun Thapa-Computer Graphics

Transformation

103
 [Link]

Introduction
Basic Transformations
The orientation, size, and shape of the output primitives
are accomplished with geometric transformations that alter the
coordinate descriptions of objects. The basic geometric

Nipun Thapa-Computer Graphics

transformations are translation, rotation, and scaling. Other
transformations that are often applied to objects include
reflection and shear. In these all cases we consider the
reference point is origin so if we have to do these
transformations about any point then we have to shift these
point to the origin first and then perform required operation and
then again shift to that position.
104
 [Link]

Introduction
Basic Transformations
1. Translation

Nipun Thapa-Computer Graphics

2. Rotation
3. Scaling
4. Reflection
5. shearing 105
 [Link]

HOMOGENOUS FORM
Expressing position in homogeneous coordinates allows
us to represent all geometric transformations equation as matrix
multiplications.
( x, y) -------------------- (xh, yh ,h)

Nipun Thapa-Computer Graphics

x= xh /h y= yh /h
where h is any non zero value
For convenient h=1

(x,y)-------------------------(x, y, 1).
106
 [Link]

1. Translation
A translation is applied to an object by repositioning it
along a straight-line path from one coordinate location to
another. We translate a two-dimensional point by adding
translation distances, tx, and ty, to the original coordinate
position (x, y) to move the point to a new position (x ' , y').

Nipun Thapa-Computer Graphics

x’ = x + tx
y’ = y + ty where the pair (tx, ty) is called the translation vector or shift vector.

107
 [Link]

1. Translation
We can write equation as a single matrix equation by using
column vectors to represent coordinate points and translation
vectors. Thus,

Nipun Thapa-Computer Graphics

P’ = P + T
So we can write

In homogeneous representation if position P = (x, y) is translated to

new position P’= (x’, y’) then:

108
 [Link]

2. ROTATION
A two-dimensional rotation is applied to an object by
repositioning it along a circular path in the xy plane. To generate
a rotation, we specify a rotation angle θ and the position (xr , yr)
of the rotation point (or pivot point) about which the object is to
be rotated.

Nipun Thapa-Computer Graphics

+ Value for ‘θ’ define counter-clockwise rotation about a point
- Value for ‘θ’ defines clockwise rotation about a point

109
 [Link]

Nipun Thapa-Computer Graphics

110
 [Link] Anticlockwise direction

2. ROTATION
At Origin

Coordinates of point ( x,y ) in polar form

y

Nipun Thapa-Computer Graphics

111
 [Link]

2. ROTATION
In homogeneous co-ordinate
Anticlockwise direction

Nipun Thapa-Computer Graphics

Clockwise direction

-
112
 [Link]

[Link]
A scaling transformation alters the size of an object. This
operation can be carried out for polygons by multiplying the coordinate
values (x, y) of each vertex by scaling factors sx and sy to produce the
transformed coordinates (x', y').
• sx scales object in ‘x’ direction
• sy scales object in ‘y’ direction

Nipun Thapa-Computer Graphics

113
 [Link]

[Link]
Thus, for equation form,
x' = x. sx and
y’ = y. sy

Nipun Thapa-Computer Graphics

• Values greater than 1 for sx , s y produce enlargement
• Values less than 1 for sx , s y reduce size of object
• s x = s x = 1 leaves the size of the object unchanged
• When sx , s y are assigned the same value s x = s x = 3 or 4 etc
114
then a Uniform Scaling is produced
 [Link]

[Link]
P‘= S.P

Nipun Thapa-Computer Graphics

115
 [Link]

4. Reflection
A reflection is a transformation that produces a mirror
image of an object. The mirror image for a 2D reflection is
generated relative to an axis of reflection by rotating the object
180" about the reflection axis. We can choose an axis of
reflection in the xy-plane or perpendicular to the xy plane.

Nipun Thapa-Computer Graphics

When the reflection axis is a line in the xy plane, the rotation
path about this axis is in a plane perpendicular to the xy-plane.
For reflection axes that are perpendicular to the xy-plane, the
rotation path is in the xy plane.

116
 [Link]

4. Reflection
(i) Reflection about x axis or about line y = 0

x
Keeps value same but flips Y value of
coordinate points

Nipun Thapa-Computer Graphics

x’ = x
y’ = -y

Homogeneous co-ordinate

117
 [Link]

4. Reflection
(ii) Reflection about y axis or about line x = 0

Keeps ‘y’ value same but flips x value of

coordinate
points

Nipun Thapa-Computer Graphics

x’ = -x
y’ = y

Homogeneous co-ordinate

118
 [Link]

4. Reflection
(iii) Reflection about origin

Flip both ‘x’ and ‘y’ coordinates of a point

x’ = -x

Nipun Thapa-Computer Graphics

y’ = -y

Homogeneous co-ordinate

119
 [Link]

4. Reflection
(iv) Reflection about line y = x
x’ = y
y’ = x

Nipun Thapa-Computer Graphics

Homogeneous co-ordinate Equivalent to:
• Reflection about x-axis
• Rotate anticlockwise 90˚
OR
• Clockwise rotation 45 ˚ 120
• Reflection with x-axis
• anticlockwise rotation 45 ˚
 [Link]

4. Reflection
(v) Reflection about line y = -x
x’ = -y
y’ = -x

Nipun Thapa-Computer Graphics

121
 [Link]

5. Shearing
It distorts the shape of object in either ‘x’ or ‘y’ or both
direction. In case of single directional shearing (e.g. in ‘x’
direction can be viewed as an object made up of very thin layer
and slid over each other with the base remaining where it is).
Shearing is a non-rigid-body transformation that moves objects

Nipun Thapa-Computer Graphics

with deformation.

122
 [Link]

5. Shearing

Nipun Thapa-Computer Graphics

123
 [Link]

5. Shearing

Nipun Thapa-Computer Graphics

124
 [Link]

Homogenous Coordinates
The matrix representations for translation, scaling and rotation
are respectively:
• Translation: P’ = T + P (Addition)
• Scaling: P’ = S . P (Multiplication)
• Rotation: P’ = R . P (Multiplication)

Nipun Thapa-Computer Graphics

Since, the composite transformation such as include many
sequence of translation, rotation etc and hence the many naturally
differ addition & multiplication sequence have to perform by the
graphics allocation. Hence, the applications will take more time for
rendering.
Thus, we need to treat all three transformations in a consistent
way so they can be combined easily & compute with one
mathematical operation. If points are expressed in homogenous
coordinates, all geometrical transformation equations can be
represented as matrix multiplications. 125
 [Link]

Homogenous Coordinates

Nipun Thapa-Computer Graphics

126
 [Link]

Homogenous Coordinates
Here, in case of homogenous coordinates we add a third
coordinate ‘h’ to a point (x, y) so that each point is represented
by (hx, hy, h). The ‘h’ is normally set to 1. If the value of ‘h’ is
more the one value then all the co-ordinate values are scaled by
this value.

Nipun Thapa-Computer Graphics

127
 [Link]

Homogenous Coordinates
• For translation

With T( tx , ty ) as translation matrix, inverse of this translation matrix is

Nipun Thapa-Computer Graphics

obtained by representing tx, ty with -tx, -

• For rotation

Here, figure-a shows the Counter Clockwise (CCW) rotation & figure-b
shows the Clockwise (CW) rotation.
128
• For scaling [Link]

• For Reflection
• Reflection about x-axis

• Reflection about y-axis

• Reflection about y=x-axis

Nipun Thapa-Computer Graphics

• Reflection about y=-x-axis

• Reflection about any line y=mx+c

129
 [Link]

Composite Transformation
With the matrix representation of transformation
equations it is possible to setup a matrix for any sequence of
transformations as a composite transformation matrix by
calculating the matrix product of individual transformation.
Forming products of transformation matrices is often referred to

Nipun Thapa-Computer Graphics

as a concatenation, or composition, of matrices. For column
matrix representation of coordinate positions we form
composite transformation by multiplying matrices in order from
right to left.
Right to Left
A.B ≠ B.A 130
 [Link]

Fixed Point Rotation

Nipun Thapa-Computer Graphics

(Xf,Yf)
(Xf,Yf)

131
 [Link]

Fixed Point Rotation

Step 1: The fixed point along with the object is translated to
coordinate origin.

Nipun Thapa-Computer Graphics

(Xf,Yf)

132
(Xf,Yf)
 [Link]

Fixed Point Rotation

Step 2: Rotate the objet about origin

Nipun Thapa-Computer Graphics

(Xf,Yf)

(Xf,Yf) 133
 [Link]

Fixed Point Rotation

Step 3: The fixed point along with the object is translated back
to its original position.

Nipun Thapa-Computer Graphics

(Xf,Yf) (Xf,Yf)

134
 [Link]

Fixed Point Rotation

Original
Image

(Xf,Yf)

Nipun Thapa-Computer Graphics

Step 1 Step 2 Step 3
T’x = Translate its
original place

Tx = Translate to origin R θ = Rotate angle θ

(Xf,Yf)
135

(Xf,Yf) (Xf,Yf)
 [Link]

Fixed Point Rotation

Composite Transformation

= T’(Xf ,Yf) . R θ . T(-Xf ,-Yf)

Nipun Thapa-Computer Graphics

= [ ][ ][ ]
1

0
0

0
Xf

Yf

1
.
Cos θ -Sin θ

Sin θ Cos θ

0 0 1
0
0
.
1

0
0

0
-Xf

-Yf

136
 [Link]
Exercise 1
Q. N. > Rotate the triangle (5, 5), (7, 3), (3, 3) in counter
clockwise (CCW) by 90 degree.
A:
P’ = R. P

Nipun Thapa-Computer Graphics

=

=
.

[ ]
-5 -3 -3
= 5 7 3 137

1 1 1
 [Link]

Exercise 2
Q.>Rotate the triangle (5, 5), (7, 3), (3, 3) about fixed point (5, 4)
in counter clockwise (CCW) by 90 degree.
A : Solution
Here, the required steps are:

Nipun Thapa-Computer Graphics

1. Translate the fixed point to origin.
2. Rotate about the origin by specified angle θ .
3. Reverse the translation as performed earlier.

138
 [Link]
Thus, the composite matrix is given by
Com = T(xf, yf) . Rθ .T(-xf, -yf)

Nipun Thapa-Computer Graphics

139
 [Link]
Now, the required co-ordinate can be
calculated as:

P’ = Com . P

Nipun Thapa-Computer Graphics

Hence, the new required coordinate points are 140
(4, 4), (6, 6) & (6, 2).
 [Link]

Fixed Point Scaling

Nipun Thapa-Computer Graphics

(Xf,Yf)
(Xf,Yf)

141
 [Link]

Fixed Point Scaling

Step 1: The fixed point along with the object is translated to
coordinate origin.

Nipun Thapa-Computer Graphics

(Xf,Yf)

142
(Xf,Yf)
 [Link]

Fixed Point Scaling

Step 2 : Scaling the objet about origin

Nipun Thapa-Computer Graphics

(Xf,Yf)

(Xf,Yf) 143
 [Link]

Fixed Point Scaling

Step 3: The fixed point along with the object is translated back
to its original position.

Nipun Thapa-Computer Graphics

(Xf,Yf) (Xf,Yf)

144
 [Link]

Fixed Point Scaling

Original
Image

(Xf,Yf)

Nipun Thapa-Computer Graphics

Step 1 Step 2 Step 3
T’x = Translate its
original place
S = Scalig at origin
Tx = Translate to origin
(Xf,Yf)
145

(Xf,Yf) (Xf,Yf)
 [Link]

Fixed Point Rotation

Composite Transformation

= T’(Xf ,Yf) . Saxix . T(-Xf ,-Yf)

Nipun Thapa-Computer Graphics

= [ ][ ][ ]
1

0
0

0
Xf

Yf

1
.
Sx

0
0

Sy

0 1
0
0
.
1

0
0

0
-Xf

-Yf

146
 [Link]

Exercise 2
Q.N.1. > Find the coordinate of a triangle A(1,3) , B(2,5) and C(3,3)
after twice its original size about fixed point (2,3)

Q.N.2. > Find the coordinate of a triangle A(1,3) , B(2,5) and C(3,3)
after being rotated about fixed point p(2,4) by 45 in clockwise

Nipun Thapa-Computer Graphics

direction and then translate (3,4) .

Q.N.3.>Find the coordinate of a triangle A(1,3) , B(2,5) and C(3,3) after

being rotated about fixed point p(2,4) by 45 in clockwise direction and
then translate by 3 unit along x-direction.

Q.N.4 >Find the coordinate of a triangle (5, 5), (7, 3), (3, 3) after scaling
(2,3) and then rotate 45 CCW then translate (1,1) and then reflect y=0 147
line.
 [Link]

Reflection about Line y=mx+c

Nipun Thapa-Computer Graphics

148
 [Link]

Reflection about Line y=mx+c

Nipun Thapa-Computer Graphics

149
 [Link]

Reflection about Line y=mx+c

Nipun Thapa-Computer Graphics

150
 [Link]
Reflection about Line y=mx+c

Nipun Thapa-Computer Graphics

151
 [Link]

Reflection about Line y=mx+c

CM=T’(0,C) . R’θ. Rrefl. Rθ . T(0,-C)

Nipun Thapa-Computer Graphics

152
Exercise [Link]

Q.N.1 > Reflect an object (2, 3), (4, 3), (4, 5) about line y = x +1.
Solution
Here,
The given line is y = x +1.
Thus,
When x = 0, y=1
When x = 1, y=2

Nipun Thapa-Computer Graphics

When x = 2, y=3

(0,1)
(C=1)
Also, (0,0)
The slope of the line (m) = 1 153
Thus, the rotation angle (θ) = Tan-1(m) = Tan-1(1) = 450
 [Link]
Here, the required steps are:
• Translate the line to origin by decreasing the y-intercept with
one.
• Rotate the line by angle 450 in clockwise direction so that the
given line must overlap x-axis.
• Reflect the object about the x-axis.
• Reverse rotate the line by angle -450 in counter-clockwise
direction.

Nipun Thapa-Computer Graphics

• Reverse translate the line to original position by adding the y-
intercept with one.

Thus, the composite matrix is given by:

CM=T’(0,C) . R’θ. Rrefl. Rθ . T(0,-C)

154
 [Link]

Nipun Thapa-Computer Graphics

155
 [Link]

Nipun Thapa-Computer Graphics

156
 [Link]

Now, the required co-ordinate can be calculated as:

P’ = Com x P

Nipun Thapa-Computer Graphics

157
Hence, the final coordinates are (2, 3), (2, 5) & (4, 5).
 [Link]

Exercise
Q.N.> Reflect a triangle A(1,8) B(3,8) and C(1,6)
about line y= x+2

Nipun Thapa-Computer Graphics

X Y
0 2
1 3
2 4
3 5

158
 [Link]

Exercise (Imp)
Q.N> A mirror is placed such that it passes through (0,10),
(10, 0). Fin the mirror image of an object (6,7), (7, 6), (6, 9).

Solution

Nipun Thapa-Computer Graphics

Here,
The given mirror or line is
passing through the
points (0, 10) & (10, 0).
Now, the slope of the line
(m) = (y2-y1) / (x2-x1)
= (0 - 10) / (10 - 0) = -1
Thus, the rotation angle (θ) 159
= Tan -1 (m) = Tan -1(-1)
= - 450
 [Link]
The composite matrix is given by:
Com
= T(0, 10) or (10, 0). Rθ in CW .Rfx .R θ in CCW .T(0, -10) or (-10, 0)

Nipun Thapa-Computer Graphics

160
 [Link]

Nipun Thapa-Computer Graphics

161
 [Link]
Now, the required co-ordinate can be calculated as:
P’ = Com . P

Nipun Thapa-Computer Graphics

Hence, the final coordinates are (3, 4), (4, 3) & (1, 4).

162
 [Link]

Exercise
• Rotate a triangle A(5,6), B(6,2) and C(4,1) by 45 degree about
an arbitrary pivot point (3,3).
• Find the coordinate of a line A(1,2) ,B(3,3) after translate (2,2)
then rotate 35o angle clockwise and then again translate the
line on (-2,-2) and rotate Counter clockwise direction of 35o

Nipun Thapa-Computer Graphics

angle and last reflect those line on X-axis .
• Digitize x2+y2 = 100 in first octant.

163
 [Link]

Unit 3 Finished

Nipun Thapa(Computer Graphics)

164