Bresenhems line Genration derivation for Mtech

Its a derivation with steps and some numerical that may help

1. Bresenham’sLine Generation
Algorithm
Dr. R. B. Chadge
Department of Mechanical Engineering
YCCE, Nagpur

2. Introduction
•Computergraphicsusethreedifferenttypesof
algorithmstogeneratelinesnamely:
1)DDALinedrawingalgorithm
2)BresenhamLinedrawingalgorithm
3)MidPointLinedrawingalgorithm

3. Introduction
•ThisalgorithmisnamedafterBresenham.Here,themain
taskistofindalltheintermediatepointsrequiredfor
drawinglineABonthecomputerscreenofpixels.
•Inthisalgorithm,everypixelhasintegercoordinates.
Apartfromthat,theBresenhamalgorithmworkson
additionandsubtractionoperations.
•Ithasmoreprecisionoraccuracyandthecomplexityof
calculationissimple.

4. Bresenham’sLine Generation Algorithm
•GiventhecoordinateoftwopointsA(x1,y1)and
B(x2,y2).
•Thetaskistofindalltheintermediatepoints
requiredfordrawinglineABonthecomputerscreen
ofpixels.
•Notethateverypixelhasintegercoordinates.

5. Bresenham’sLine Generation Algorithm
•Examples:
1. Input : A(0,0), B(4,4)
Output : (0,0), (1,1), (2,2), (3,3), (4,4)
2. Input : A(0,0), B(4,2)
Output : (0,0), (1,0), (2,1), (3,1), (4,2)

6. Bresenham’sLine Generation Algorithm
•Belowaresomeassumptionstokeepthealgorithm
simple.
1.Wedrawlinesfromlefttoright.
2.x1<x2andy1<y2
3.Slopeofthelineisbetween0and1.Wedrawaline
fromlowerlefttoupperright.

7. Bresenham’sLine Generation Algorithm
•TheideaofBresenham’salgorithmistoavoid
floatingpointmultiplicationandadditiontocompute
mx+c,andthencomputetheroundvalueof(mx+
c)ineverystep.
•InBresenham’salgorithm,wemoveacrossthex-axis
inunitintervals.

8. Bresenham’sLine Generation Algorithm
•Wealwaysincreasexby1,andwechooseabout
nexty,whetherweneedtogotoy+1orremainony.
•Inotherwords,fromanyposition(X
k,Y
k)weneedto
choosebetween(X
k+1,Y
k)and(X
k+1,Y
k+1).

9. Bresenham’sLine Generation Algorithm

10. •Wewouldliketopicktheyvalue(amongY
k+1and
Y
k)correspondingtoapointthatisclosertothe
originalline.
•Weneedadecisionparametertodecidewhetherto
pickY
k+1orY
kasthenextpoint.
•Theideaistokeeptrackofslopeerrorfromthe
previousincrementtoy.
Bresenham’sLine Generation Algorithm

11. •Iftheslopeerrorbecomesgreaterthan0.5,weknow
thatthelinehasmovedupwardsonepixelandthat
wemustincrementourycoordinateandreadjustthe
errortorepresentthedistancefromthetopofthe
newpixel–whichisdonebysubtractingonefrom
theerror.
Bresenham’sLine Generation Algorithm