Lecture _Line Scan Conversion.ppt

Line scan

1. Chapter 3
Scan Conversion Algorithms
(Point and Line)

2. April 23, 2023 Computer Graphics 2
Scan Conversion
•RasterizationorScanConversionisdefinedasthe
processofrepresentingcontinuousgraphicobjectasa
collectionofdiscretepixels.
–Various graphic objects are
•Point
•Line
•Rectangle, Square
•Circle, Ellipse
•Sector, Arc
•Polygons……
–Hardware, Software, Firmware Implementation

3. April 23, 2023 Computer Graphics 3
Scan Conversion
•Scan Conversionis required in order to convert vector data
to Raster format for a scan line display device
–convert each graphic object to a set of regular pixels.
–determine inside/outside areas when filling polygons.
–scan-convert curves

4. April 23, 2023 Computer Graphics 4
Scan Conversion Algorithms
1.Scan Conversion of Point
2.Scan Conversion of Line
3.Scan Conversion of Circle
4.Scan Conversion of Ellipse
5.Scan Conversion of Polygons

5. April 23, 2023 Computer Graphics 5
Scan Converting a Point
MODELLING CO -ORDINATES
•Mathematicallyvectorsaredefinedinan
infinite,“real-number”Cartesianco-
ordinatesystem
SCREEN COORDINATES
•a.k.a device co-ordinates, pixel co-ordinates
•On display hardware we deal with finite, discrete
coordinates
•X, Y values in positive integers
•0,0 is measured from top-left usually with +Y
pointing down
Y
X
A pixel (10, 6)
X
Y
Z
A point (-12.3,
10.3, 0)

6. April 23, 2023 Computer Graphics 6
Scan Converting a Point
•Eachpixelongraphicdisplaydoesnotrepresenta
mathematicalpointlikeP(2.6,3.33).Butitcanbe
accommodatedtothenearestpositionbyapplyingfew
mathematicalfunctionssuchas
–CEILP(3,4)
–FLOORP(2,3)
–GREATESTINTEGERFUNCTIONP(3,3)
–ROUNDP(3,3)

7. April 23, 2023 Computer Graphics 7
Scan Conversion Algorithms
1.Scan Conversion of Point
2.Scan Conversion of Line
3.Scan Conversion of Circle
4.Scan Conversion of Ellipse

8. April 23, 2023 Computer Graphics 8
Scan Converting a Line
How does a machine draw Lines?
1.Give it a start and end position.
2.Figure out which pixels to colour in between these…
–How do we do this?
–Line-Drawing Algorithms: DDA, Bresenham’s Algorithm

9. April 23, 2023 Computer Graphics 9
Scan Converting a Line
Line and its slope
–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 = 0
m = -
1
/
3
m = -
1
/
2
m = -1
m = -2
m = -4
m = ∞
m =
1
/
3
m =
1
/
2
m = 1
m = 2
m = 4
m = 0

10. April 23, 2023 Computer Graphics 10
Line Drawing Algorithms
1.DDA Line Algorithm
2.Bresenham Line Algorithm

11. April 23, 2023 Computer Graphics 11
1. Introduction
–Digital Differential Analyser is an
an algorithm for scan-converting lines
–The original differential analyzer
was a physical machine developed by
Vannevar Bushat MIT in the 1930’s
in order to solve ordinary differential equations.
–It calculates pixel positions along a line by taking unit step
increment along one direction and calculating corresponding
coordinate position based on the rate of changeof the
coordinate (Dx orDy ) (Incremental Approach)
DDA Algorithm

12. April 23, 2023 Computer Graphics 12
2. Basic Concept
–For each part of the line the following holds true:
–IfDx = 1 i.e. 1 pixel then …
–i.e. for each pixel we move right (along the x axis), we need to
move down (along the y-axis) by m pixels.
–In pixels, the gradient represents how many pixels we step
upwards (Dy) for every step to the right (Dx)
DDA AlgorithmmyD xmy
x
y
m DD
D
D


13. April 23, 2023 Computer Graphics 13
3. Derivation
Assume that 0<m<1, Dx > 0 and Dy >0
For a point P(x
i, y
i) on a line we know that
y
i= mx
i + b
At next position P(x
i+1, y
i+1)
y
i+1= mx
i+1+ b
Having unit step increment along x-axis means x
i+1 = x
i + 1
Therefore y
i+1= m(x
i + 1)+ b
= mx
i + m+ b
= mx
i + b+ m
= y
i+ m
DDA Algorithm

14. April 23, 2023 Computer Graphics 14
DDA Algorithm
4. Simple Algorithm
1.Input (x1,y1) and (x2,y2)
2.Let x = x1; y = y1;
m = (y2-y1)/(x2-x1);
3.Draw pixel (x, y)
4.WHILE (x < x2) //i.e. we reached the second
endpoint
5.{
x = x + 1; //step right by one pixel
y = y + m; //step down by m pixels
Draw pixel (ROUND(x), ROUND(y));
}

15. April 23, 2023 Computer Graphics 15
DDA ALGORITHM
Sample at unit x:1
1

D

k
kk
x
xxx
Corresponding ypos.:)1(

1

D
D

my
xmy
yyy
k
k
kk
5. Example

16. April 23, 2023 Computer Graphics 16
DDA ALGORITHM
Sample at unit x:1
1

D

k
kk
x
xxx
Corresponding ypos.:)1(

1

D
D

my
xmy
yyy
k
k
kk
5. Example

17. April 23, 2023 Computer Graphics 17
DDA ALGORITHM
Sample at unit x:1
1

D

k
kk
x
xxx
Corresponding ypos.:)1(

1

D
D

my
xmy
yyy
k
k
kk
5. Example

18. April 23, 2023 Computer Graphics 18
DDA ALGORITHM
Sample at unit x:1
1

D

k
kk
x
xxx
Corresponding ypos.:)1(

1

D
D

my
xmy
yyy
k
k
kk
5. Example

19. April 23, 2023 Computer Graphics 19
DDA ALGORITHM
Sample at unit x:1
1

D

k
kk
x
xxx
Corresponding ypos.:)1(

1

D
D

my
xmy
yyy
k
k
kk
5. Example

20. April 23, 2023 Computer Graphics 20
DDA ALGORITHM
Sample at unit x:1
1

D

k
kk
x
xxx
Corresponding ypos.:)1(

1

D
D

my
xmy
yyy
k
k
kk
5. Example

21. April 23, 2023 Computer Graphics 21
DDA ALGORITHM
Consider endpoints:
P1(0,0), P2(7,4)
Sample at unit x:1
1

D

k
kk
x
xxx
Corresponding ypos.:)1(

1

D
D

my
xmy
yyy
k
k
kk
5. Example

22. April 23, 2023 Computer Graphics 22
DDA ALGORITHM
6. Exercise
1.Consider endpoints:
P1(0,0), P2(6, 4)
Calculate the points that made up the line P1P2
2.Now, consider endpoints:
P3(0,0), P4(4, 6)
Calculate the points that made up the line P3P4
What happened with P3P4??????

23. April 23, 2023 Computer Graphics 23
DDA Algorithm
7. Y-Version (|m|>1)
–Iftheslopeisverysteep(i.e.Dyis
muchgreaterthanDx)thenthere’sa
problem.i.e.mismuchgreater
than1
–Thisisbecauseweonlydrawone
pixelforeachxvalue(eachtimewe
stepright)
–Solution:iftheslopeistoobig,step
foryinstead

24. April 23, 2023 Computer Graphics 24
8. Generic solution
–Modify Basic idea
–Take unit step increment along direction having more rate of change, and
compute the coordinates for the other position to maximize the number of
points to be computed along the path of line and avoid discontinuitiesy
m
x
mxmy
DD
DD
1
0 1m0 :
1:
1
1




myy
xx
ii
ii
orm1
1
:
1:
1
1




m
xx
yy
ii
ii
DDA Algorithm
Why?
discontinuity !!

25. April 23, 2023 Computer Graphics 25
–What is m<0 ?
–We must see the sign of Dx and Dy
–Or can we have simple solution???????
DDA Algorithm -Generic solution
Vario
us
Cases
Dx>0
Dy>0
Dx>0
Dy<0
Dx<0
Dy>0
Dx<0
Dy<0
|m|<1
x
i+1 = x
i + 1
y
i+1 = y
i +
m
x
i+1 = x
i + 1
y
i+1 = y
i -m
x
i+1 = x
i -1
y
i+1 = y
i +
m
x
i+1 = x
i -1
y
i+1 = y
i –m
(or swap
points)
|m|>1
x
i+1 = x
i +
1/m
y
i+1 = y
i + 1
x
i+1 = x
i +
1/m
y
i+1 = y
i -1
x
i+1 = x
i -
1/m
y
i+1 = y
i +
1
x
i+1 = x
i -1/m
y
i+1 = y
i –1
(or swap
points)

26. April 23, 2023 Computer Graphics 26
Incremental DDA Algorithm
1.Input (x1,y1) and (x2,y2)
2.Compute
dx = x2-x1 and dy = y2-y1
m = dy/dx
3.If abs(dx)>abs(dy)
step = abs(dx)
else
step = abs(dy)
4.Compute xinc = dx/step
yinc = dy/step
5.Initialize x = x1 and y = y1
6.Draw pixel (x, y)
7.For k = 1 to steps do //we reach the other endpoint
{
x = x + xinc;
y = y + yinc;
Draw pixel (ROUND(x), ROUND(y));
}

27. April 23, 2023 Computer Graphics 27
8. Limitations
–Rounding integers takes time
–Variables y and m must be a real or fractional binary because
the slope is a fraction
–Real variables have limited precision, summing an inexact
slope m repetitively introduces a cumulative error buildup
DDA Algorithm

28. April 23, 2023 Computer Graphics 28
DDA Algorithm
Rounding Error
–Note that the actual pixel position is
actually stored as a REAL number
(in C/C++/java a float or a double)
–But we Round Off to the nearest
whole number just before we draw
the pixel.
–e.g. if m=.333 …
1.0
2.0
3.0
4.0
X Y Rounded { x, y }
0.33
0.66
0.99
1.32
{ 1, 0 }
{ 2, 1 }
{ 3, 1 }
{ 4, 1 }

29. April 23, 2023 Computer Graphics 29
Line Drawing Algorithms
1.DDA Line Algorithm
2.Bresenham Line Algorithm

30. April 23, 2023 Computer Graphics 30
1.Introduction
–One disadvantage of DDA is the ROUNDing part which can
be expensive
–Developed by Jack Bresenham
at IBM in the early 1960s
–One of the earliest algorithms in
computer graphics
–The Algorithm is based on essentially
the same principles but is completely
based on integer variables
Bresenham’s Line Algorithm

31. April 23, 2023 Computer Graphics 31
Bresenham’s Line Algorithm
2. Basic Concept
–Find the closest integer coordinatesto the actual line path using
only integer arithmetic
–Candidate for the next pixel position
–No division, Efficient comparison, No floating point operations
Specified
Line Path10 m
Specified
Line Path

32. April 23, 2023 Computer Graphics 32
Bresenham’s Line Algorithm
3. Derivation
–The algorithm is derived for a line having slope 0< m < 1 in
the first quadrant.
–Pixel position along the line are plotted by taking unit step
increments along the x-direction and determining y-
coordinate value of the nearest pixel to the line at each step.
–Can be generalized for all the cases

33. April 23, 2023 Computer Graphics 33
Bresenham’s Line Algorithm
–Let us assume that P(x
k, y
k) is the currently plotted pixel.
Q(x
k+1, y
k+1) (x
k+1, y ) is the next point along the actual
path of line. We need to decide next pixel to be plotted from
two candidate positions Q1(x
k+1, y
k) or Q2(x
k+1, y
k+1) lkxxm lk  , ,10 1kx ky 1ky y 2d 1d bmxy  kx 1kx 2kx 2ky 1ky ky P P Q 1Q 2Q 1Q 2Q Q

34. April 23, 2023 Computer Graphics 34
Bresenham’s Line Algorithm
Given the equation of line
y= mx+ b
Thus actual value of yat x = x
k+1is given by
y= mx
k+1 + b = m(x
k+ 1) + b
Let d
1= | QQ
1|=distance of y
k from actual value of y
= y–y
k =m(x
k+ 1) + b –y
k
d
2= | QQ
2| =distance of actual value of y from y
k +1
= y
k+1 –y =(y
k+ 1)–[m(x
k+ 1) + b]
The difference between these 2 separations is
d
1-d
2= 2m(x
k+ 1) + 2b –y
k–(y
k+ 1)
= 2m(x
k+ 1) –2 y
k+ 2b –1

35. April 23, 2023 Computer Graphics 35
Bresenham’s Line Algorithm
we can define a decision parameterp
kfor the k
th
step to by
simplifying above equation such that the sign of P
kis the same as
the sign of d
1-d
2, but involves only integer calculations.
Define P
k= Δx ( d
1-d
2))122)1(2( 
D
D
D byx
x
y
x
kk )12(222 DDDD bxyyxxy
kk constant a 122 where
22
)bΔx(Δyc
kk
cyxxy

DD )122)1(2( D byxmx
kk

36. April 23, 2023 Computer Graphics 36
Bresenham’s Line Algorithm
If p
k< 0
( d
1-d
2)<0
distance d
1 is less than d
2
y
kis closer to line-path
Hence Q1(x
k+1, y
k) is the better choice
else
Q2(x
k+1, y
k+1) is the better choice
Thus if the parameter p
kis negative lower pixel is plotted else
upper pixel is plotted

37. April 23, 2023 Computer Graphics 37


DD
D







DD
DD
DD

DD






otherwisexyp
pifyp
p
otherwisey
pify
y
yyxypp
yyxxxypp
pp
cyxxyp
cyxxyp
k
kk
k
k
kk
k
kkkk
kkkkkk
kk
kkk
kkk
22
0 2
1
0

)(22
)(2)(2
fromsubtract
.2.2
1k k Replacing
.2.2
1
1
11
111
1
111
Bresenham’s Line Algorithm
To put p
kin the iterative form, we derived that

38. April 23, 2023 Computer Graphics 38
Bresenham’s Line Algorithm
The first parameter p
0is directly computed as:
p
0= 2 Δy.x
0-2 Δx.y
0+ c
= 2 Δy.x
0-2 Δx.y
0+ 2 Δy + Δx (2b-1)
Since (x
0,y
0)satisfies the line equation , we also have
y
0= Δy/ Δx * x
0+ b
b = y
0 -Δy/ Δx * x
0
Combining the above 2 equations , we will have
p
0 = 2Δy –Δx
The constants 2Δy, 2Δy –Δxand 2Δy-2Δxare calculated once.

39. April 23, 2023 Computer Graphics 39
Bresenham’s Line Algorithm
STEPS FOR BRESENHAM’S LINE DRAWING ALGORITHM (for | m| < 1.0)
1.Input the two line end -points (x
0, y
0) and (x
1, y
1)
2.Plot the point (x
0, y
0)
3.Compute Δx = x
1-x
0 , Δy = y
1-y
0
4.Initialize p
0 = 2Δy –Δx
5.At each x
kalong the line, starting at k = 0, perform the
following test.
If p
k< 0
the next point to plot is (x
k+1, y
k)
p
k = p
k+2Δy
else
the next point to plot is ( x
k+1, y
k+1)
p
k = p
k+2Δy –2Δx
6.Repeat step 5 (Δx –1) times
7.Plot the point (x
1, y
1)
8.Exit

40. April 23, 2023 Computer Graphics 40

41. April 23, 2023 Computer Graphics 41
Bresenham’sLine Algorithm
4. General solution
–The algorithm can be generalized for all slopes
Cases/
slope
CaseI
Dx>0 , Dy>0
CaseII
Dx>0, Dy<0
Case III
Dx<0, Dy>0
Case IV
Dx<0, Dy<0
|m|<1
p = 2dy-dx
for x = x1 to x2
if p<0
p = p+ 2dy
else { y=y+1
p = p+2(dy-dx)}
p = 2dy-dx
for x = x1 to x2
if p<0
p = p+ 2dy
else { y=y-1
p = p+2(dy-dx)}
swap points
Case II
swap points
Case I
|m|>1
p = 2dx-dy
for y= y1 to y2
if p<0
p = p+ 2dx
else { x=x+1
p = p+2(dx-dy)}
p = 2dx-dy
for y= y2 to y1
if p<0
p = p+ 2dx
else { x=x+1
p = p+2(dx-dy)}
swap points
Case II
swap points
Case I

42. April 23, 2023 Computer Graphics 42
Bresenham’sLine Algorithm
5. Exercise
Calculate pixel positions that made up the line connecting endpoints:
(12, 10) and (17, 14).
2. Dx = ?, Dy =?, 2Dy = ?, 2Dy–2Dx =?
1. (x
0, y
0) = ?
3. p
0= 2Dy–Dx =?
k p
k (x
k+1, y
k+1)

43. April 23, 2023 Computer Graphics 43
Bresenham’sLine Algorithm
5. Exercise
Calculate pixel positions that made up the line connecting endpoints:
(12, 10) and (17, 14).
2. Dx = 5, Dy =4, 2Dy = 8, 2Dy–2Dx =-2
1. (x
0, y
0) = (12,10)
3. p
0= 2Dy–Dx =3
k p
k (x
k+1, y
k+1)
0 3
1
2

44. April 23, 2023 Computer Graphics 44
Bresenham’sLine Algorithm
5. Exercise
Calculate pixel positions that made up the line connecting endpoints:
(12, 10) and (17, 14).
2. Dx = 5, Dy =4, 2Dy = 8, 2Dy–2Dx =-2
1. (x
0, y
0) = (12,10)
3. p
0= 2Dy–Dx =3
k p
k (x
k+1, y
k+1)
0 3 (13, 11)
1 1 (14, 12)
2 -1 (15, 12)
3 7 (16, 13)
4 5 (17, 14)

45. April 23, 2023 Computer Graphics 45
Bresenham’s Line Algorithm
17
16
15
14
13
12
11
10
18
292726252423222120 28 30
kp
k
(x
k+1,y
k+1)
5. Exercise: Trace for (20,10) to (30,18)

46. April 23, 2023 Computer Graphics 46
Bresenham’s Line Algorithm
17
16
15
14
13
12
11
10
18
292726252423222120 28 30
k p
k (x
k+1,y
k+1)
0
1
2
3
4
5
6
7
8
9
6
2
-2
14
10
6
2
-2
14
10
(21,11)
(22,12)
(23,12)
(24,13)
(25,14)
(26,15)
(27,16)
(28,16)
(29,17)
(30,18)
Answer