BCT 2405 Computer Graphical systems
Karanja Mwangi
LineDrawing
Algorithms
Concept: Line drawing algorithm
Programmer specifies (x,y) values of end pixels
Need algorithm to figure out which intermediate pixels
are on line path
Pixel (x,y) values constrained to integer values
Actual computed intermediate line values may be floats
Rounding may be required. E.g. computed point
(10.48, 20.51) rounded to (10, 21)
Rounded pixel value is off actual line path (jaggy!!)
• Jaggies are stair-like lines that appear where there should be
"smooth" straight lines or curves
Sloped lines end up having jaggies
Vertical, horizontal lines, no jaggies
Concept: Line Drawing Algorithm
8
7 Line: (3,2) -> (9,6)
6
5
4
? Which intermediate
3 pixels to turn on?
2
1
0 1 2 3 4 5 6 7 8 9 10 11 12
Concept: Line Drawing Algorithm
Slope-intercept line equation
y = mx + b
Given two end points (x0,y0), (x1, y1), how to compute m
and b?
dy y1 y 0 b y 0 m * x0
m
dx x1 x 0
(x1,y1)
dy
(x0,y0)
dx
Line Drawing Algorithm -Gradient
Numerical example of finding slope m:
(Ax, Ay) = (23, 41), (Bx, By) = (125, 96)
By Ay 96 41 55
m 0.5392
Bx Ax 125 23 102
The various Line drawing Algorithms
• DDA(Digital Differential Analyzer) Line
Drawing Algorithm
• Mid Point Line Drawing Algorithm
• Bresenham Line Drawing Algorithm
Read about ( Important to do so)
• Xiaolin Wu's line algorithm
• Gupta-Sproull algorithm
There are many others but we
limit ourselves to these
Line Drawing Algorithm: Digital Differential
Analyzer (DDA): The Notion -1
• Given the starting and ending coordinates
of a line,
• DDA Algorithm attempts to generate the
points between the starting and ending
coordinates.
DDA Procedure-
If we have the
Starting coordinates = (X0, Y0)
Ending coordinates = (Xn, Yn)
The points generation using DDA Algorithm
is as follows
Line Drawing Algorithm: Digital Differential
Analyzer (DDA): The Notion -2
Step-1:
Calculate ΔX, ΔY and M from the given input.
These parameters are calculated as-
ΔX = Xn – X0
ΔY =Yn – Y0
M = ΔY / ΔX
For example to calculate the points between the starting point (5, 6) and
ending point (8, 12).
# Starting coordinates = (X0, Y0) = (5, 6)
Ending coordinates = (Xn, Yn) = (8, 12)
#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
Line Drawing Algorithm: Digital Differential
Analyzer (DDA): The Notion -3
Step-2:
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);
# in our case example of starting point (5, 6) and ending point (8, 12).
The number of steps are
|ΔX| < |ΔY| = 3 < 6, so number of steps = ΔY = 6
Line Drawing Algorithm: Digital Differential
Analyzer (DDA): The Notion -4
Step-3:
If 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-
Line Drawing Algorithm: Digital Differential
Analyzer (DDA): The Notion -5
Step-3: continued
# As M > 1, so case-03 is satisfied in our example
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)
Line Drawing Algorithm: Digital Differential
Analyzer (DDA): The Notion -5
Step-3: The plot
DDA Line Drawing Algorithm advantages
DDA is the simplest line drawing algorithm
It is easy to implement.
It avoids using the multiplication operation which is
costly in terms of time complexity.
DDA Line Drawing Algorithm Drawbacks
DDA is the simplest line drawing algorithm
Not very efficient
Round operation is expensive
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.
Exercise Gauge yourself with the tasks
given in Print
Line Drawing Algorithm: Mid Point Line Drawing
Algorithm The Notion -1
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.
Midpoint Procedure-
If we have the
Starting coordinates = (X0, Y0)
Ending coordinates = (Xn, Yn)
The points generation using midpoint
Algorithm is as follows
Line Drawing Algorithm :Mid Point Line Drawing
Algorithm :The Notion -2
Step-1:
Calculate ΔX and ΔY from the given input.
These parameters are calculated as-
ΔX = Xn – X0
ΔY =Yn – Y0
For example to calculate the points between the starting point (20, 10)
and ending coordinates (30, 18).
Starting coordinates = (X0, Y0) = (20, 10)
Ending coordinates = (Xn, Yn) = (30, 18)
#Calculate ΔX and ΔY from the given input.
ΔX = Xn – X0 = 30 – 20 = 10
ΔY =Yn – Y0 = 18 – 10 = 8
Line Drawing Algorithm :Mid Point Line Drawing
Algorithm :The Notion -3
Step-2:
Calculate the value of initial decision parameter and
ΔD.
These parameters are calculated as-
Dinitial = 2ΔY – ΔX
ΔD = 2(ΔY – ΔX
Starting coordinates = (X0, Y0) = (20, 10)
Ending coordinates = (Xn, Yn) = (30, 18)
#Calculate ΔX and ΔY from the given input.
ΔX = Xn – X0 = 30 – 20 = 10
ΔY =Yn – Y0 = 18 – 10 = 8
Calculate Dinitial and ΔD as-
Dinitial = 2ΔY – ΔX = 2 x 8 – 10 = 6
ΔD = 2(ΔY – ΔX) = 2 x (8 – 10) = -4
Line Drawing Algorithm :Mid Point Line Drawing
Algorithm :The Notion -4
Step-3:
The decision whether to increment X or Y coordinate depends upon the
flowing values of Dinitial.
Follow the below two cases-
Line Drawing Algorithm :Mid Point Line Drawing
Algorithm :The Notion -4
Dinitial Dnew Xk+1 Yk+1
Step-3: continued 20 10
# As Dinitial >= 0, so case-02 is satisfied.
6 2 21 11
Thus, 2 -2 22 12
Xk+1 = Xk + 1 = 20 + 1 = 21 -2 14 23 12
14 10 24 13
Yk+1 = Yk + 1 = 10 + 1 = 11
10 6 25 14
Dnew = Dinitial + ΔD = 6 + (-4) = 2
6 2 26 15
Similarly, Step 3 is executed until the end point
2 -2 27 16
is reached.
. -2 14 28 16
14 10 29 17
10 30 18
Line Drawing Algorithm :Mid Point Line Drawing
Algorithm :The Notion -5
Step-3: The plot
Mid Point Line Drawing Algorithm :
Advantages
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
Mid Point Line Drawing Algorithm :
Drawbacks
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.
Line Drawing Algorithm- Bresenham’s Line-
Drawing Algorithm :The Notion -1
• Given the starting and ending coordinates of a line,
Bresenham’s algorithm attempts to generate the points
between the starting and ending coordinates.
Bresenham Procedure-
If we have the
Starting coordinates = (X0, Y0)
Ending coordinates = (Xn, Yn)
The points generation using Bresenham’s algorithm is as
follows
Line Drawing Algorithm- Bresenham’s Line-
Drawing Algorithm :The Notion -2
Step-1:
Calculate ΔX and ΔY from the given input.
These parameters are calculated as-
ΔX = Xn – X0
ΔY =Yn – Y0
For example to calculate the points between the starting point (9, 18)
and ending coordinates (14, 22).
Starting coordinates = (X0, Y0) = (9, 18)
Ending coordinates = (Xn, Yn) = (14, 22)
#Calculate ΔX, ΔY from the given input.
ΔX = Xn – X0 = 14 – 9 = 5
ΔY =Yn – Y0 = 22 – 18 = 4
Line Drawing Algorithm- Bresenham’s Line-
Drawing Algorithm :The Notion -3
Step-2:
Calculate the decision parameter Pk.
It is calculated as-
Pk = 2ΔY – ΔX
.
# in our case example of starting point (9, 18) and ending coordinates
(14, 22). Where ΔX = Xn – X0 = 14 – 9 = 5 and ΔY =Yn – Y0 = 22 – 18
=4
The decision parameter will be
Pk = 2ΔY – ΔX
=2x4–5
=3
So, decision parameter Pk = 3
Line Drawing Algorithm- Bresenham’s Line-
Drawing Algorithm :The Notion -4
Step-3:
If the current point is (Xp, Yp) and the next point is (Xp+1, Yp+1). Find the next
point the next point depending on the value of decision parameter Pk.
Follow the below two cases-
Line Drawing Algorithm- Bresenham’s Line-
Drawing Algorithm :The Notion -5
Step-3: continued
# 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-3 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
Line Drawing Algorithm- Bresenham’s Line-
Drawing Algorithm :The Notion -5
Step-3: The plot
Bresenham’s Line-Drawing Algorithm:
Advantages
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.
This uses only integer calculations.
Bresenham’s Line-Drawing Algorithm:
Drawbacks
Cannot effectively handle “jaggies”
Remember: WHAT ARE jaggies - Jaggies are stair-like lines
that appear where there should be "smooth" straight lines or
curves
• We will deal with them when dealing with aliasing effect
Improves line accuracy in generation of points but not yet
smooth
Assignment ( Important to do so)
1. Read on various image formats such as Ai, wmf, Cmx,
cgm,svg ,odg, eps , dxf , bmp, jpeg ,Gif ,Tiff,PICT and png
Explain what the abbreviation stand for and some
history on the format
State whether each of the graphic format above is
raster or vector
Briefly explain a typical application or area of usage of
each of the format
2. Read about Xiaolin Wu's line algorithm and
• Gupta-Sproull algorithm
Can you implement all the Five algorithms in a
programming language of your choice?OpenGL
3 .How is Rasterization carried for other 2D primitives?
Circles , Polygon, Ellipses , Triangles etc ?Read the
textbook
Assignment ( Important to do so)
3. Can you implement all the Five algorithms in a
programming language of your choice? OpenGL
4 .How is Rasterization carried for other 2D primitives?
Circles , Polygon, Ellipses , Triangles etc ?
Read the textbook
https://piazza.com/class_profile/get_resource/kp2du
2rm59l1rh/kp2e1yk9gkx4hy
Read page Graphics Output Primitives from page 45
