Computer Graphics_Module 2_Output Primitives.pdf

Computer Graphics

1. Computer Graphics
Module 2: Output Primitives

2. Line drawingalgorithm
•Thetwoendpointsof aline segment arespecifiedat positions
(x1,y1)and(x2,y2).
y
P2(x2,y2)
x
P1(x1,y1)
0
2

3. Line DrawingAlgorithm
3
1.AlineinComputergraphicsisaportionofstraightlinethatextendsindefinitelyin
oppositedirection
2.Itisdefinedbyitstwoendpoints
3.Itsdensityshouldbeindependentoflinelength
4.Theslopeinterceptequationforaline:
y=mx+b
where,m=Slopeoftheline
b=theyinterceptofaline

4. LineDrawingAlgorithm
4
•For drawing a line AB with endpoints (x
1, y
1) and (x
2,y
2), the slopeof theline is:
m=(y
2-y
1/x
2-x
1)orm=dy/dx
•Ifpointsare(x
k,y
k)and(x
k+1,y
k+1)thenslope of linewillbe
m=(y
k+1-y
k)/(x
k+1-x
k)
•Fordifferentvaluesofm,differentcalculationsareneeded

5. Linedrawingalgorithm
•Case1:(m<1):xco-ordinatewillchangeinunitintervals
∴x
k+1=x
k+1
m=(y
k+1-y
k)/(x
k+1-x
k)
where,(x
k+1-x
k)=1
∴m=(y
k+1-y
k)ory
k+1=y
k+m
•Case2:(m>1):yco-ordinatewillchangeinunitintervals
∴y
k+1=y
k+1
m=(y
k+1-y
k)/(x
k+1-x
k)
where,(y
k+1-y
k)=1
∴m=1/(x
k+1-x
k)orx
k+1=(1/m)+x
k
•Case3:(m=1):boththeco-ordinates(x,y)willchangeinunitintervals
∴m=(y
k+1-y
k)/(x
k+1-x
k)
5

6. DDALineDrawingAlgorithm
6
DigitalDifferentialAnalyzer
DDAisanincrementalscanconversionmethodto determinepointona
line
Itrequiresdifferencesfrompreviousstatecalculations
Thedifferences∆xand∆yinxandydirection, respectively

7. DDALineDrawingAlgorithm
7
Algorithm:
Step1.InputthecoordinatesofthetwoendpointsA(x
1,y
1)B(x
2,y
2)forline ABrespectively(pointA
&Barenotequal)
Step2.[Calculatedxanddy] dx=x
2-x
1
dy=y
2-y
1
Step3.[Calculatestep] if|dx|>=|dy| then
step=|dx|
else
step=|dy|

8. DDALineDrawingAlgorithm
8
Step4.[Calculatetheincrementalfactor]
∆x=dx/step
∆y=dy/step
Note:Thisstepmakeseither∆xor∆yequalto1,becauseLiseither
│x
2-x
1│or│y
2-y
1│.Thereforestepincrementinxorydirectionis qualto1.
Step5.[Initializeinitialpointonalineandplot] x
new=x
1
y
new =y
1
Plot(Integer(x
new),Integer(y
new))

9. DDALineDrawingAlgorithm
9
Step6.[Obtainthenewpixelonthelineandplotthesame]
Repeatthefollowingprocedurefrom0tostepvalue
x
new=x
new+∆x
y
new=y
new+∆y
Plot(Integer(x
new),Integer(y
new))

10. NumericalonDDA Algorithm
10
•ConsideralineABwithA=(0,0)andB=(4,5).ApplyasimpleDDAalgorithmand
calculatethepixelsonthisline.
•Solution:
Calculate:-dx,dy,step
Given:
x
1=0
y
1=0
x
2=4
y
2=5
dx=x
2-x
1
dx=4-0=4
dy=y
2-y
1
dy=5-0=5
step=5(∵dy>dx)
Δx=(dx/step)
Δx=(4/5)=0.8
Δy=(dy/step)
Δy=(5/5)=1
X
new=x
1=0
Y
new=y
1=0

11. NumericalonDDA Algorithm
11
X
new=x
1=0,Y
new=y
1=0,Δx=0.8,Δy= 1,step=5
step
x
new y
new
x
plot y
plot
0 0 0
0 0
1 0.8 1 1 1
2 1.6 2 2 2
3 2.4 3 2 3
4
3.2 4 3 4
5 4.0 5 4 5
5
4
3
2
1
0
01234

12. NumericalonDDA Algorithm
12
•ConsideralineABwithA=(20,10)andB=(26,14).ApplyasimpleDDAalgorithm
andcalculatethepixelsonthisline.
•Solution:
Calculate:-dx,dy,step
Given:
x
1=20
y
1=10
x
2=26
y
2=14
dx=x
2-x
1
dx=26-20=6
dy=y
2-y
1
dy=14-10=4
step=6(∵dx>dy)
Δx=(dx/step)
Δx=(6/6)=1
Δy=(dy/step)
Δy=(4/6)=0.66
X
new=x
1=20
Y
new=y
1=10

13. NumericalonDDA Algorithm
13
X
new=x
1=20,Y
new=y
1=10,Δx=1,Δy=0.66,step=6
step
x
new y
new
x
plot y
plot
0 20 10 20 10
1 2110.66 21 11
2 22 11.32 22 11
3 2311.98 23 12
4 2412.64 24 13
5 25 13.3 25 13
6 26 13.96 26 14
14
13
12
11
10
0
020212223 242526
.
.
.

14. NumericalonDDA Algorithm
14
•ConsideralineABwithA=(8,4)andB=(2,1).ApplyasimpleDDAalgorithmand
calculatethepixelsonthisline.
•Solution:
Calculate:-dx,dy,step
Given:
x
1=8
y
1=4
x
2=2
y
2=1
dx=x
2-x
1
dx=2-8=-6
dy=y
2-y
1
dy=1-4=-3
step=6(∵dx>dy)
Δx=(dx/step)
Δx=(-6/6)=-1
Δy=(dy/step)
Δy=(-3/6)=-0.5
X
new=x
1=8
Y
new=y
1=4

15. NumericalonDDA Algorithm
15
X
new=x
1=8,Y
new=y
1=4,Δx=-1,Δy=-0.5,step=6
step
x
new y
new
x
plot y
plot
0 8 4 8 4
1 7 3.5 7 4
2 6 3 6 3
3 5 2.5 5 3
4 4 2 4 2
5 3 1.5 3 2
6 2 1 2 1
5
4
3
2
1
0
012345678

16. DDALineDrawingAlgorithm
16
AdvantagesofDDAalgorithm:
Simpleandfastalgorithm.
Doesnotrequiresspecialskillsforimplementingitinany programming
language.
DisadvantagesofDDAalgorithm:
Thoughthismethodisfast,accumulationofroundingoff errorsmaydriftthe
pixelawayfromtheactualpixel.
Floatingpointarithmeticisstilltimeconsuming.

17. DDALineDrawingAlgorithm(Homework)
17
•Considera lineABwithA=(0,0) andB=(8,4).Applyasimple DDAalgorithmand
calculatethepixelsonthisline.
•ConsideralineABwithA=(0,0)andB=(-5,-5).Applya
simpleDDAalgorithmandcalculatethepixelsonthisline.

18. BresanhamLineDrawingAlgorithm
18
•From position (2,3)we have to
choosebetween(3,3)and(3,4)
•Wewouldlikethepointthatis
closertotheoriginalline

19. BresenhamLinedrawingalgorithm
19
•Atsamplepositionx
k+1thevertical
separationsfromthemathematicallineare
labelledd
upperandd
lower
Theycoordinateonthemathematicallineat x
k+1 is:
y m(x
k1)b
m(x
k1)by
kd
l o w e ryy
k
1)yy
k1m(x
k1)b
d
upper2m(x
k1)2y
k2b1
my/x
d
upper(y
k
d
lower
Decisionparameter:
p
kx(d
lowd
uerp)
p2
ey
rx
k2xy
k

20. BresenhamLinedrawingalgorithm
20
Decision parameter:p
k=Δx(d
lower-d
upper)=2Δy.x
k-2Δx.y
k
p
khas thesamesign withd
lower-d
uppersinceΔx>0.
c isconstant andhas thevalue c=2Δy+Δx(2b-1)
cis independentof thepixelpositionsandiseliminatedfromdecision
parameterp
k.
Ifd
lower<d
upperthenp
kisnegative.
Plotthelowerpixel(East)
Otherwise
Plottheupperpixel(NorthEast)

21. BresenhamLinedrawingalgorithm
SuccessiveDecisionParameter
Atstepk+1
p
k+1=2Δy.x
k+1-2Δx.y
k+1+b
Subtractingtwosubsequentdecisionparametersyields:
p
k+1-p
k=2Δy.(x
k+1-x
k)-2Δx.(y
k+1-y
k)
x
k+1=x
k+1so
p
k+1=p
k+2Δy-2Δx.(y
k+1-y
k)
y
k+1-y
kiseither0 or1 dependingonthesignofp
k
Firstparameterp
0
p
0=2Δy-Δx
21

22. BresenhamLinedrawingalgorithm(|m|<1)
1.Inputthetwolineendpointsand storetheleftendpointin(x
0,y
0).
2.Load(x
0,y
0)intotheframebuffer;thatis,plotthefirstpoint.
3.CalculateconstantsΔx,Δy,2Δy,and2Δy-2Δx,andobtainthestartingvaluefor
thedecisionparameteras
p
0=2Δy-Δx
4.At each x
k along the line, starting at k = 0, perform the following test:
Ifp
k<0, thenextpointtoplotis(x
k+1,y
k)and
22
p
k+1=p
k+2Δy
Otherwise,thenextpointtoplotis (x
k+1,y
k+1)and
p
k+1=p
k+2Δy-2Δx
5.Repeatstep4Δx-1times.

23. BresenhamLine drawingalgorithm-Example
Drawthelinewithendpoints(20,10)and (30,18).
Solution:-
Calculate:-Δx,Δy,2Δy,and2Δy-2Δx
Δx= 30-20=10
Δy=18-10=8
p
0=2Δy–Δx=16-10=6
2Δy=16
2Δy-2Δx=-4
23

24. BresenhamLine drawingalgorithm-Example
24
Plottheinitialpositionat(20,10),then
k p
k (x
k+1,y
k+1) k p
k (x
k+1,y
k+1)
0 6 (21,11) 5 6 (26,15)
1 2 (22,12) 6 2 (27,16)
2 -2 (23,12) 7 -2 (28,16)
3 14 (24,13) 8 14 (29,17)
4 10 (25,14) 9 10 (30,18)

25. BresenhamLine drawingalgorithm-Example
25
k p
k (x
k+1,y
k+1) k p
k (x
k+1,y
k+1)
0 6 (21,11) 5 6 (26,15)
1 2 (22,12) 6 2 (27,16)
2 -2 (23,12) 7 -2 (28,16)
3 14 (24,13) 8 14 (29,17)
4 10 (25,14) 9 10 (30,18)