CA5026

COMPUTER GRAPHICS
LINE DRAWING ALGORITHMS
TEXTBOOK AND RECOMMENDED REFERENCES
1. F. S. Hill, Jr., Stephen M. Kelley, Jr., “Computer graphics
using OpenGL”, Third Edition, Pearson Prentice Hall,
2007.
2. Donald D. Hearn, M. Pauline Baker, W. Carithers,
“Computer Graphics with Open GL”, Fourth Edition,
Pearson Education, 2010.
3. Alan Watt, “3D Computer Graphics”,Third Edition,Pearson
Addison Wesley, 2000.
4. Mark S. Drew,Zee Nian Li, “Fundamentals of multimedia”,
Prentice Hall, 2006.
2
INTRODUCTION
• In raster display, a picture is completely specified by the set of intensities for the
pixel positions in the display.
• Otherwise, picture can be set as complex structures, such as trees.. Positioned at
specific coordinate locations.
• If represented as intensities → loaded in frame buffer
• If represented as geometric structures → scan conversion.
• Graphics programming packages provide functions to describe a scene in terms as
basic geometric structures → output primitives.

3
COORDINATE REFERENCE FRAMES – 2D
• Point Representation in two dimensions
✓ Cartesian Coordinates: (x; y)

✓ Polar Coordinates: (; )

4
COORDINATE REFERENCE FRAMES – 2D
• When setting up a scene in computer y axis

graphics we define the scene using

P
simple geometry y

• For 2D scenes we use simple two-

dimensional Cartesian coordinates
• All objects are defined using simple
coordinate pairs
x axis
x

5
COORDINATE REFERENCE FRAMES – 2D
y

(2, 7) (7, 7)
7

3
(2, 3) (7, 3)

x
2 7
6
COORDINATE SYSTEMS
• In a 2-D coordinate system the X axis generally points from left to right, and the Y
axis generally points from bottom to top. ( Although some windowing systemswill
have their Y coordinates going from top to bottom.)
• When we add the third coordinate, Z, we have a choice as to whether the Z-axis
points into the screen or out of the screen:

7
LEFT HANDED OR RIGHT HANDED ?
• There are two different ways in which we can do 3D coordinates – left handed or right
handed

We will mostly use

the right-handed
system

Right-Hand Reference System Left-Hand Reference System

8
Images taken from Hearn & Baker, “Computer Graphics with OpenGL” (2004)
COORDINATE SYSTEMS
• Right Hand Coordinate System (RHS)
Z is coming out of the page (Points towards the User)
▪ Counterclockwise rotations are positive
if we rotate about the X axis : the rotation Y->Z is positive
if we rotate about the Y axis : the rotation Z->X is positive
if we rotate about the Z axis : the rotation X->Y is positive
• Left Hand Coordinate System (LHS)
Z is going into the page
▪ Clockwise rotations are positive
if we rotate about the X axis : the rotation Y->Z is positive
if we rotate about the Y axis : the rotation Z->X is positive
if we rotate about the Z axis : the rotation X->Y is positive
9 • so basically its the same thing ...
COORDINATE SYSTEMS
• The important thing to note is what coordinate system is being used by the package
you are working with,both for the creation of models and the displaying of them. Also
note that if the two packages use different coordinate systems, then the model(s) may
need to be inverted in some fashion when they are loaded in for viewing.

• OpenGL generally uses a right-hand coordinate system.

10
MULTIPLE COORDINATE SYSTEMS IN A GRAPHIC
• In a typical graphics program, we may need to deal with a number of different
coordinate systems

• World Coordinate System - Also known as the "universe" or sometimes "model"

coordinate system. This is the base reference system for the overall model, ( generally in
3D ), to which all other model coordinates relate.

• Object Coordinate System - When each object is created in a modelling program

• HierarchicalCoordinate Systems - Sometimes objects in a scene are arranged in a

hierarchy, so that the "position" of one object in the hierarchy is relative to its parent in
the hierarchy scheme, rather than to the world coordinate system.

11
MULTIPLE COORDINATE SYSTEMS IN A GRAPHIC
• Viewpoint Coordinate System - Also known as the "camera" coordinate system. This
coordinate system is based upon the viewpoint of the observer, and changes as they
change their view.

• Model Window Coordinate System - this coordinate system refers to the subset of the
overall model world that is to be displayed on the screen.

• Screen Coordinate System - This 2D coordinate system refers to the physical

coordinates of the pixels on the computer screen, based on current screen resolution. (
E.g. 1024x768 )

• Viewport Coordinate System - This coordinate system refers to a subset of the screen
space where the model window is to be displayed.

12
COORDINATE REPRESENTATION
Modeling coordinates: (xm , ym)
World coordinates: (xw , yw)
Normalized coordinates (Range: 0 - 1): (xn , yn)
Device coordinates: (xd , yd)

13
WORLD TO DEVICE

(xw ,yw) (xd ,yd)

Display area

MaxX w −MinX w xw −MinX w

xScale = xd =
DeviceWidth xScale
MaxYw −MinYw y w −MinYw
yScale = yd =
DeviceHeight yScale

14
COORDINATE REPRESENTATION
• World to Normalized

x w −MinX w y w −MinYw
xn = yn =
MaxX w −MinX w MaxYw −MinYw

• Normalized to Device

yd = y n  DeviceHeight
xd = xn  DeviceWidth

15
DEVICE COORDINATES
(xd ,yd)

(0,0)
(xw ,yw)

(0,0)
(xd ,DeviceHeight-yd)
Display area

16
POINTS AND LINES
Points:
❑A point in two-dimensional space is given as an ordered pair (x, y)
❑In three dimensions a point is given as an ordered triple (x, y, z)
Lines:
❑A line is defined using a start point and an end-point
• In 2d: (xstart, y start) to (x end, y end)
• In 3d: (xstart, y start , z start) to (x end, y end , z end)
Vector: direction and magnitude
v = (v x , vy), etc.

17
LINE DRAWING ALGORITHMS

The lines of this object appear However, they are

continuous made of pixels
18
LINE DRAWING ALGORITHMS
• We are going to analyze how this process is achieved.
• Rasterization:Process of determining which pixels provide the best approximation to
a desired line on the screen.

• Scan Conversion:
Combination of Rasterization and generating the picture in scan line
order.
19
LINE DRAWING ALGORITHMS

20
LINE DRAWING ALGORITHMS

Rasterization yields uneven brightness: Horizontal and vertical lines appear brighter than the 45º lines.

21
THE PROBLEM OF SCAN CONVERSATION
• A line segment in a scene is defined by the coordinate positions of the line end-points

(7, 5)

(2, 2)

22
PROBLEM (CONT...)
• But what happens when we try to draw this on a pixel-based display?

• How do we choose which pixels to turn on?

23
CONSIDERATIONS
• Considerations to keep in mind:
– The line has to look good
• Avoid jaggies
– It has to be lightening fast!
• How many lines need to be drawn in a typical scene?

24
THE EQUATION OF A LINE
• The slope-intercept equation of a line is: y

y = m x +b
yend
• where:
yend −y0
m=
xend −x0
y0
b = y0 −m  x0
x
x0 xend
• The equation of the line gives us the corresponding y point for every x point

25
LINES & SLOPES
• The slope of a line (m) is defined by its start and end coordinates
• The diagram below shows some examples of lines and their slopes

m=∞
m = -4 m=4
m = -2 m=2

m = -1 m=1

m = -1/2 m = 1/2
m = -1/3 m = 1/3

m=0 m=0

26
LINES & SLOPES
+ve -ve

if |m| = 1
45°
 = 45° 45°

if |m|  1
-45° <  < 45°
°
°

if |m|  1
45° <  < 90° or
-90° <  < -45° °
27 °
A SIMPLE SOLUTION
• We could simply work out the corresponding y coordinate for each unit x coordinate.
Let’s consider the following example:
y

(7, 5)
5

2
(2, 2)

x
2 7
28
RESULT
y
(7, 5)  First work out m and b:
5
5 −2 3
m= =
7 −2 5
3 4
2
(2, 2)
b = 2− 2 =
5 5

x 3 4 4
2 3 4 5 6 7 y (5) =  5 + = 3
5 5 5
3 4 3 3 4 1 3 4 2
y (3) =  3 + = 2 y ( 4) =  4 + = 3 y ( 6) =  6 + = 4
5 5 5 5 5 5 5 5 5
29
RESULT
• Now just round off the results and turn on these pixels to draw our line

3
7 y (3) = 2  3
6
5
5 1
y ( 4) = 3  3
4 5
3
4
2 y (5) = 3 4
5
1
0 2
y ( 6) = 4 4
0 1 2 3 4 5 6 7 8 5
30
ALGORITHM 1: DIRECT SCAN CONVERSION

The algorithm performs a floating-point multiplication for every step in x. This method therefore requires an
enormous number of floating-point multiplications and is therefore expensive.
31
ALGORITHM 2: DIGITAL DIFFERENTIAL ANALYZ
• The digital differentialanalyzer (DDA) algorithm takes an incremental approach in
order to speed up scan conversion
• Simply calculate yk + 1 based on y k
• When the slope of the line is between -1 and 1 begin at the first point in the line and,
by incrementing the x coordinate by 1, calculate the corresponding y coordinates as
follows:
yk +1 = yk + m
• When the slope is outside these limits, increment the y coordinate by 1 and calculate
the corresponding x coordinates as follows:
1
x k + 1 = xk +
m
32
ALGORITHM 2: DIGITAL DIFFERENTIAL ANALYZ

33
ALGORITHM 2: DIGITAL DIFFERENTIAL ANALYZ

34
ALGORITHM 2: DIGITAL DIFFERENTIAL ANALYZ

35
ALGORITHM 2: DIGITAL DIFFERENTIAL ANALYZ

36
DDA ALGORITHM
Step 1: Receive Both Line-End Points
Step 2: Compute Slope
Step 3: Assign (x , y) as First Line-End Point & Display
Step 4: Increment x by 1 (one) and y by slope
Step 5: Truncate y only
Step 6: Display the computed next point
Step 7: Repeat Steps 4, 5 & 6 Until LAST Line-End Point
Step 8: End of Drawing

37
DDA ALGORITHM
• Again the values calculated by the equations used by the DDA algorithm must be
rounded to match pixel values

(xk+1, round(yk+m)) (round(xk+ 1/m), yk+1)

(xk, yk) (xk+ 1/m, yk+1)

(xk+1, yk+m) (xk, yk)

(round(xk), yk)

38
DIGITAL DIFFERENTIAL ANALYZER (DDA) ALGO
Input line endpoints, (x0 ,y0 ) and (x n, yn)
set pixel at position (x0 ,y0 )
calculate slope m
Case |m|≤1: repeat the following steps until (x n, yn) is reached:
yi+1 = y i + y/ x
xi+1 = x i + 1
set pixel at position (xi+1 ,Round(yi+1 ))
Case |m|>1: repeat the following steps until (x n, yn) is reached:
xi+1 = x i + x/ y
yi+1 = y i + 1
39 set pixel at position (Round(xi+1 ), yi+1 )
DDA ALGORITHM (PSEUDO-CODE)
// Assume that slope is gentle
DDA(float x0, float x1, float y0, float y1) {
float x, y;
float xinc, yinc;
int numsteps;

numsteps = Round(x1) – Round(x0); Q: For each step, how many floating

xinc = (x1 – x0) / numsteps; point operations are there?
yinc = (y1 – y0) / numsteps; A: 4
x = x0;
y = y0; Q: For each step, how many integer
ColorPixel(Round(x),Round(y)); operations are there?
A: 2
for (int i=0; i<numsteps; i++) {
x += xinc;
y += yinc;
ColorPixel(Round(x),Round(y));
}
}
40
DDA ALGORITHM (EXAMPLE)
• Suppose we want to draw a line starting t x y R(x) R(y)
at pixel (2,3) and ending at pixel (12,8). 0 2 3 2 3
1 3 3.5 3 4
• What are the values of the variables x
and y at each time step? 2 4 4 4 4
3 5 4.5 5 5
• What are the pixels colored, according 4 6 5 6 5
to the DDA algorithm? 5 7 5.5 7 6
numsteps = 12 – 2 = 10 6 8 6 8 6
xinc = 10/10 = 1.0
7 9 6.5 9 7
yinc = 5/10 = 0.5
8 10 7 10 7
9 11 7.5 11 8
10 12 8 12 8
41
DIGITAL DIFFERENTIAL ANALYZER (DDA) ALGO
m<1

42
DIGITAL DIFFERENTIAL ANALYZER (DDA) ALGO
m>1 m>1

43
DDA ALGORITHM - ADVANTAGES
❑ This is faster for calculating pixel positions than the direct equations

❑ Computation Time for Truncating is reduced

❑ Variable x is incremented and hence sure to reach endpoint x value

❑ Difficulty in Choosing a δ is avoided

❑ Complexity is less

❑ Reduced CPU requirement increases display rate

44
DDA ALGORITHM - DRAWBACKS
• Although DDA is fast,the accumulation of round-off error is successive additions of
floating-point increment, however can cause the calculated pixel positions to drift
away from the true line path for long line segments.

• Floating-point operations and rounding-off in DDA is time consuming.

45
BRESENHAM’S LINE-DRAWING ALGORITHM
• The Bresenham’s algorithm is another incremental scan conversion algorithm.

• An accurate and efficient raster line-generating algorithm.

• Uses distance between ideal y-coordinate and the upper and lower pixel (assuming
gentle slope)

• The big advantage of this algorithm is that it uses only integer calculations

46
BRESENHAM’S LINE-DRAWING ALGORITHM
• Move across the x axis in unit intervals and at each step choose between two different
y coordinates.

For example, from position (2, 3) we

5
have to choose between (3, 3) and (3,
(xk+1, yk+1)
4)
4
We would like the point that is closer to
(xk, yk) the original line
3
(xk+1, yk)
2

2 3 4 5
47
ALGORITHM 3: BRESENHAM’S LINE ALGORITHM
y = mx + b

d2
y = m(x+1) + b
y d1

x x+1

48
ALGORITHM 3: BRESENHAM’S LINE ALGORITHM
y =mx+c
y=m(xk+1 )+c
d1= y –y k => m(xk+1 )+c – yk
d2 = y k+1 – y => yk+1 - m(x k+1 )-c
d1- d2 = m(xk+1 )+c – yk - [yk+1 - m(x k+1 )-c ]
= 2m(xk+1 ) - 2y k + 2c-1
= 2∆y/∆x (x k+1 ) - 2y k + 2c-1
(d1-d2)∆x = 2∆y (x k+1 ) - 2∆x y k+ 2c ∆x - ∆x
Pk = 2∆y (x k+1 ) - 2∆x y k + 2c ∆x - ∆x
Pk = 2∆y (x k) - 2∆x y k+ 2∆y +2(c -1)∆x
49
ALGORITHM 3: BRESENHAM’S LINE ALGORITHM
Pk = 2∆y x k - 2y k∆x + b b=2∆y +2(c -1)∆x

Pk +1 = 2∆yx k+1 - 2y k+1∆x + b

Pk +1 – P k = 2∆y(x k+1 – x k ) - 2∆x (yk+1 - y k )

Pk +1 = P k + 2∆y(x k+1 – x k ) - 2∆x (yk+1 - y k )

Observe we are stepping in x by 1,
Pk +1 = P k + 2∆y - 2∆x (xk+1-xk) = 1

There are two possibilities for (y(k+1) – y(k)), 0 or 1

dp = P k + 2∆y - 2∆x(0) = P k + 2∆y

dp = P k + 2∆y - 2∆x(1) = P k + 2∆y - 2∆x

50
ALGORITHM 3: BRESENHAM’S LINE ALGORITHM
The first parameter P0 is Pk = 2∆y x k - 2 ∆x y k+ b where (x 0 ,y0) is the starting position
and m is evaluated as ∆y / ∆x

P0 = 2∆y - ∆x

51
BRESENHAM’S LINE ALGORITHM (FOR |M| < 1)
1. Input the two line end-points, storing the left end-point in(x0, y0)
2. Plot the point (x0, y0)
3. Calculate the constants Δx, Δy, 2Δy, and ( 2Δy - 2Δx) and get the first value for the
decision parameter as:
p0 = 2y −x
4. At each xk along the line, starting at k = 0, perform the following test.
If pk < 0, the next point to plot is (xk+1, yk) and:
pk +1 = pk + 2y
Otherwise, the next point to plot is (xk+1, yk+1) and:
pk +1 = pk + 2y −2x ❑ Switch Point 0 and Point 1 if necessary
❑ If negative slope, reflect
5. Repeat step 4 ( Δx – 1) times ❑ If steep slope, flip y and x
52
BRESENHAM’S LINE ALGORITHM
input line endpoints, (x0 ,y0 ) and (xn, yn)
calculate x = x n - x0 and y = y n - y0
calculate parameter p 0 = 2 y - x
set pixel at position (x0 ,y0 )
repeat the following steps until (xn, yn) is reached:
if p i < 0
set the next pixel at position (xi +1, y i )
calculate new pi+1 = p i + 2 y
if p i ≥ 0
set the next pixel at position (xi +1, y i + 1 )
53 calculate new pi+1 = p i + 2( y - x)
BRESENHAM’S (EXAMPLE)
t P(x) P(y) p
• Suppose we want to draw a line
0 2 3 0
starting at pixel (2,3) and ending at
1 3 4 -10
pixel (12,8). 2 4 4 0

• What are the values of p 0 , d x and d y? 3 5 5 -10

4 6 5 0
• What are the values of the variable p 5 7 6 -10
at each time step? 6 8 6 0
7 9 7 -10
• What are the pixels colored, according 8 10 7 0
to Bresenham’s algorithm? 9 11 8 -10
10 12 8 0

54
DDA VERSUS BRESENHAM’S ALGORITHM
• DDA works with floating point arithmetic
• Rounding to integers necessary

• Bresenham’s algorithm uses integer arithmetic

• Constants need to be computed only once

• Bresenham’s algorithm generally faster than DDA

55