U.V.
Patel College of Engineering
Ganpat University
1
Points and lines
Points are displayed using pixel location
Application program
Two ways
Raster scan conversion
The electron beam sweeps across each horizontal
scan line, it emits a burst of electrons whenever a
value of 1 is encountered in the frame buffer
Vector scan conversion
point plotting instructions in the display list and the
coordinate values in these instructions are
converted to deflection voltages that position the
electron beam at the screen location.
Points and lines (conti)
Line drawing is accomplished by calculating intermediate positions
along the line path between specified end points.
Precise definition of line drawing
Given two points P and Q in the plane, both with integer
coordinates, determine which pixels on a raster screen should
be on in order to make a picture of a unit-width line segment
starting from P and ending at Q.
Points and lines (conti)
screen locations are in integers.
A computed point (10.48,20.51) would be converted to pixel
position (10,21).
rounding causes lines to be displayed with stair step appearance
also called jaggies
remedies by using high resolution screen
Line drawing
A line segment in a scene is defined by the coordinate positions of the line
end-points.
scanlines a
scan lines are numbered consecutively from 0, left to right across each
scan line.
To load a specified color into frame buffer at a position corresponding to
column x along scan line y.
5
Line Equation
Lets quickly review the equations
involved in drawing lines
y
yend
Slope-intercept line
equation:
y m x b
yend y0
m
xend x0
y0
x0
xend
b y0 m x0
6
Line Drawing Algorithm
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
We could simply work out the corresponding y coordinate for each
unit x coordinate
7
Line Drawing Algorithm
First work out m
y
5
(7, 5)
and b:
m
(2, 2)
52 3
72 5
3
4
b 2 2
5
5
2 3 4 5 6 7 x
Now for each x value work out the y value:
3
4
3
3
4
1
y (3) 3 2
y (4) 4 3
5
5
5
5
5
5
3
4
4
3
4
2
y (5) 5 3
y ( 6) 6 4
5
5
5
5
5
5
Line Drawing Algorithm
Now just round off the results and turn on these pixels to draw
our line
3
y (3) 2 3
5
1
y ( 4) 3 3
5
4
y (5) 3 4
5
y (6) 4
2
4
5
However, this approach is just way too slow
The equation y = mx + b requires the multiplication of m by x
Rounding off the resulting y coordinates
9
Line Drawing Algorithm
In the previous example we chose to solve the parametric line
equation to give us the y coordinate for each unit x coordinate
What if we had done it the other way around ?
y b
x
m
m
yend y0
xend x0
b y0 m x0
10
Line Drawing Algorithm
If the slope of a line is between -1 and 1 then we work out the x
coordinates for a line based on its unit y coordinates
Otherwise we do the opposite y coordinates are computed based
on unit x coordinates
m = -4
m = -2
m = -1
m = - 1 /2
m = - 1 /3
m=0
m=
m=4
m=2
m=1
m = 1/ 2
m = 1 /3
m=0
11
DDA line drawing Algorithm
Digital Differential Analyser
The Cartesian slope-intercept equation for a straight line is
y= m. x + b
m is the slope of the line and b is the y intercept.
Given the endpoints of a line segment.
m = y2-y1 / x2-x1
b= y1-m.x1
Also for any given interval x along a line, we can compute the
corresponding y interval y from
y= m. x
Similarly we can obtain the x interval x corresponding to a
specified y as
x= y / m
These equations form the basis for determining deflection
voltages in analog devices.
12
DDA line drawing Algorithm
Also , for any given x interval x along a line, we
can compute the corresponding y interval y
from
y= m. x
These equations form the basis for determining
deflection voltages in analog devices.
On Raster systems, lines are plotted with pixels,
and step sizes in the horizontal and vertical
directions are constrained by pixel separations.
Hence we ought to sample a line at discrete
positions and determine the nearest pixel to the
line at each sampled position.
13
DDA line Concept
14
Use of Symmetry
If we could draw lines with positive slope (0<=slope<=1)
we would be done.
For a line with negative slope (0>=slope>=-1)
We negate all Y values
For a line with slope > 1 or slope <-1
we just swap x and y axes
yk 1 yk m
1
xk 1 xk
m
15
DDA line drawing
Algorithm(conti)
Again the values calculated by the equations used by the DDA
algorithm must be rounded to match pixel values
16
DDA line drawing
Algorithm(conti)
summary
The DDA algorithm is much faster than our previous attempt
In particular, there are no longer any multiplications involved
However, there are still two big issues:
Accumulation of round-off errors can make the pixelated line
drift away from what was intended
The rounding operations and floating point arithmetic involved
are time consuming
17
Bresenhams Line Algorithm
An accurate and efficient raster line algorithm
Uses only integer calculations
Scan lines and pixel columns
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
have to choose between (3, 3) and
(3, 4)
We would like the point that is closer
to
the original line
18
Bresenhams Line Algorithm
(conti)
yk+1
y
yk
dupper
dlower
xk+1
At sample position xk+1 the vertical
separations from the mathematical line
are labelled dupper and dlower
19
Bresenhams Line Algorithm
(conti)
The y coordinate on the mathematical line at xk+1
is:
y m( xk 1) b
So, dupper and dlower are given as follows:
d lower y yk m( xk 1) b yk
d upper ( yk 1) y yk 1 m( xk 1) b
We can use these to make a simple decision about
which pixel is closer to the mathematical line
20
Bresenhams Line Algorithm
(conti)
This simple decision is based on the difference
between the two pixel positions:
d lower d upper 2m( xk 1) 2 yk 2b 1
x(d lower
y
d upper ) x(2 ( xk 1) 2 yk 2b 1)
x
2y xk 2x yk 2y x(2b 1)
2y xk 2x yk c
a decision parameter pk for the kth step along a line
is given by: pk x(d lower d upper )
2y xk 2x yk c
21
Bresenhams Line Algorithm
(conti)
If pk is negative, then we choose the lower pixel,
otherwise we choose the upper pixel
yk+1
y
yk
dupper
dlower
xk+1
At step k+1 the decision parameter is given as:
pk 1 2y xk 1 2x yk 1 c
pk 1 pk 2y ( xk 1 xk ) 2x( yk 1 yk )
22
Bresenhams Line Algorithm
(conti)
But, xk+1 is the same as xk+1 so:
pk 1 pk 2y 2x( yk 1 yk )
where yk+1 - yk is either 0 or 1 depending on the sign
of pk
The first decision parameter p0 is evaluated at
2y as:
x
(x0, y0)pis
0 given
23
Bresenhams Line Algorithm
(conti)
Bresenhams Line Algorithm steps: (for |m| < 1.0)
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, 2y, and (2y - 2x) and get the first value
for the decision parameter as:
p0 2y 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 2y
Otherwise, the next point to plot is ( xk+1, yk+1) and:
pk 1 pk 2y 2x
5. Repeat step 4 (x 1) times
24
