**Bresenham's Line Drawing Algorithm Derivation**

**Bresenham Line drawing algorithm is used to determine closest points to be illuminated on the screen to form a line.**

**As we know a line is made by joining 2 points, but in a computer screen, a line is drawn by illuminating the pixels on the screen.**

**(Here pixel (1,2), (3,1) and (5,5) are illuminated and others are non-illuminated)**

**A line from pixel (2,2) to (7,5) will be shown like this on the screen.**

**The slope of a line plays a major role in the line equation that's why Bresenham line drawing algorithm calculates the equation according to the slope of the line.**

**The slope of the line can be greater than 1 (m>1) or less than or equal to 1 (m<=1).**

**Now enough talking let's derive the equations.**

**Derivation:**

**Let's say we want to draw a line on the screen.**

**so, to draw a line we have to calculate the points or pixels to be illuminated on the screen.**

**Now while drawing a line a sometimes it passes through 2 pixels at the same time then we have to choose 1 pixel from the 2 to illuminate it.**

**so, the bresenham algorithm calculates the distance from the intersection point**

**y**

**to both the pixels and whichever is smaller we choose that pixel.**

**The equation of Line is:**

**Y=mx+c ....(1)**

**Here m is the slope of Line and**

**C is y-Intercept of line****The slope can also be written as**

**First we calculate the slope of the line if slope is less than 1, then X will always be incremented.**

**so at (m<=1)**

**we calculate the**

**d**

_{1 }**which is distance between intersection point**

**y**

**to the pixel**

**y**

_{k}

**So, d**

_{1 }= y-**y**

_{k}

**d**

_{1}= m**x**

_{k+1}

_{ }**+c -**

**y**

_{k }**By using ....(1)**

**Similarly d**

_{2 }is the distance between pixel**y**

_{k+1}

_{ }**and intersection point**

**y**

**.**

**d**

_{2}= y_{k+1}-y**d**

_{2}=**y**

_{k+1}**-(m**

**x**

_{k+1}**+c)**

_{ }**By using ....(1)**

**Note: here x is always incrementing so we can write**

**x**

_{k+1}

_{ }**as**

**x**

_{k }+1**and here**

**y**

_{k+1}**is next pixel so we can write it as**

**y**

_{k}+1**.**

**subtracting d**

_{2}from d_{1}**d**

_{1}-d_{2}= m(**x**

_{k}+1)

_{ }**+c -**

**y**

_{k}

_{ }**– [**

**y**

_{k}+1**-(m**

**x**

_{k}+1**+c)]**

**= m**

**(x**

_{k}+1**)+c -**

**y**

_{k}

_{ }**–**

**y**

_{k}-1**+m**

**(x**

_{k}+1)**+c**

**d**= 2m(x_{1}-d_{2}_{k}+1)-2y_{k}+2c-1

**.....(3)****Multiplying both side by (dx)**

**dx(d**

_{1}-d_{2}) = 2dy(**x**

_{k}**+1)-2dx(**

**y**

_{k}**)+2dx(c)-dx**

**Now we need to find decision parameter P**

_{K}**P**

_{K}= dx(d_{1}-d_{2}) and,**C = 2dy+2dx(c)-dx**

**which is constant**

**So new equation is.**

**P**

_{K }=2dy(x_{k})-2dx(y_{k}) +C .......(4)

**Now our next parameter will be**

**P**_{K+1}=2dy(**x**_{k+1}**)-2dx(****y**_{k+1}**) +C****.....(5)****Subtracting P**

_{k }from PK_{+1}_{ }**P**

_{k+1}-P_{k}= 2dy(**x**

_{k+1}-x_{k}**)-2dx(**

**y**

_{k+1}-y_{k}**) +C-C**

**Note: here x is always incrementing so we can write**

**x**

_{k+1}

_{ }**as**

**x**

_{k }+1**P**

_{k+1}-P_{k}= 2dy(**x**

_{k}-x_{k}+1**)-2dx(**

**y**

_{k+1}-y_{k}**)**

**P**

_{k+1 }= P_{k}+2dy-2dx(**y**

_{k+1}-y_{k}**)........(6)**

**when P**

_{k}<0 then (d_{1}-d_{2})<0**So d**

_{1}<d_{2 }then we will write**y**

_{k+1}as y_{k}_{ }because current pixel’s distance from intersection point**y**

**is smaller.so, we will have to choose current pixel.**

**Then our formula will be:**

**P**

_{k+1 }= P_{k}+2dy-2dx(**y**

_{k}-y_{k}**)**

**P**

_{k+1 }= P_{k}+2dy**And when P**

_{k}>0 then (d_{1}-d_{2})>0**So d**

_{1}>d_{2 }then we will write**y**

_{k+1}as y_{k}+1_{ }because current pixel’s distance from intersection point**y**

**is larger.so, we will have to choose upper pixel.**

**At that time our formula will be:**

**P**

_{k+1 }= P_{k}+2dy-2dx(**y**

_{k}+1_{}-y_{k}**)**

**P**

_{k+1 }= P_{k}+2dy-2dx**We can say that (**

**y**

_{k+1}-y_{k}**) value can either be 0 or 1.**

**For Initial decision parameter**

**From 4**

^{th}equation**P**

_{K }= 2dy(**x**

_{k}**)-2dx(**

**y**

_{k}**) +C**

**P**

_{K }= 2dy(**x**

_{k}**)-2dx(**

**y**

_{k}**)+2dx(c)-dx+2dy**

**By using 1**

^{st}equation**y**

_{k}=m(x_{k})+c**c=y**

_{k}-m(**x**

_{k})_{ }

_{ }**P**

_{0 }= 2dy(**x**

_{k}**)-2dx(**

**y**

_{k}**)+2dx(y**

_{k}-m(x_{k})-dx (By using 2)

_{ = }**2dy(**

**x**

_{k}**)-2dx(**

**y**

_{k}**)+2dx**

**y**

_{k}**-2dy**

**x**

_{k}**+2dy-dx**

**P**

_{0 }=2dy-dx**But if the slope of line is greater then 1 (m>1).**

**then our Y coordinate will always be incremented and we have to choose between x**_{k }or x_{k+1}.

**So, our Line equation will be:**

**Y**_{k+1 }= m(x)+c

**Now, In this case our d**_{1}will be the distance between intersection point x and pixel x_{k}

_{ }

**d**_{1}= x-x_{k }**By using ....(7)**

**d**_{1}= 1/m(y_{k+1}-c)-x_{k }

**And similarly our d**_{2}will be the distance between intersection point x and pixel x_{k+1}**d**_{2}= x_{k+1}-x_{ }**By using ....(7)****d**_{2}= x_{k+1}-1/m(y_{k+1}-c)

**Note: here y is always incrementing so we can write****y**_{k+1}_{ }**as****y**_{k}**+1 and here****x**_{k+1}**is next pixel so we can write it as****x**_{k}+1**.****subtracting d**_{2 }from d_{1}**d**_{1}-d_{2 }=1/m(y_{k}+1-c)-x_{k }– [x_{k}+1-1/m(y_{k}+1-c)]**= 1/m(y**_{k}+1-c)-x_{k }– x_{k}-1+1/m(y_{k}+1-c)**d**_{1}-d_{2 }= 2/m(y_{k}+1-c)-2x_{k}-1**d**_{1}-d_{2 }= 2dx(y_{k}+1-c)-2dyx_{k}-dy

**Multiplying both side by (dy)**

**dy(d**_{1}-d_{2}) = 2dxy_{k}+2dx-2dxc-2dyx_{k}-dy

**Now we need to find decision parameter P**_{K}

**P**_{K}= dy(d_{1}-d_{2})**C = 2dx-2dxc-dy**

**which is constant**

**So new equation is**

**P**_{K}= 2dxy_{k}-2dyx_{k}+C

**......(8)****Now our next parameter will be**

**P**

_{k+1}= 2dx(y_{k+1})-2dy(x_{k+1})+C**Substracting P**

_{k }from P_{k+1}**P**

_{k+1}-P_{k }=_{ }2dx(y_{k+1}-y_{k})-2dy(x_{k+1}-x_{k})+C-C**Note: here x is always incrementing so we can write**

**y**

_{k+1}

_{ }**as**

**y**

_{k}+1**P**

_{k+1}-P_{k }=_{ }2dx(

**)-2dy(x****y**+1-y_{k}_{k}_{k+1}-x_{k})**P**

_{k+1}**=**

**P**

_{k}+2dx-2dy(x_{k+1}-x_{k})**when P**

_{k}<0 then (d_{1}-d_{2})<0**So d**

_{1}<d_{2 }then we will write x

_{k+1}as x_{k}_{ }because current pixel’s distance from intersection point**x**

**is smaller.so, we will have to choose current pixel.**

**Then our formula will be:**

**P**_{k+1 }=_{ }P_{k}+2dx-2dy(x_{k}-x_{k})

**P**_{k+1 }=_{ }P_{k}+2dx**And when P**

_{k}>0 then (d_{1}-d_{2})>0**So d**

_{1}>d_{2 }then we will write**x**

_{k+1}as x_{k}_{}+1 because current pixel’s distance from intersection point**x**

**is Larger.so, we will have to choose next pixel.**

**At that time our formula will be:****P**

_{k+1}=_{ }P_{k}+2dx-2dy(x_{k}+1-x_{k})**P**

_{k+1}=_{ }P_{k}+2dx-2dy**For Initial decision parameter**

**From 8**

^{th}equation

**P**_{K}= 2dxy_{k}-2dyx_{k}+C

**P**_{0}

**=**

**2dxy**_{0}+2dx-2dxc-2dyx_{0}-dy

**By using 1**^{st}equation**y**

_{k}=m(x_{k})+c**c=y**

_{k}-m(**x**

_{k})

**P**_{0}

**=**

**2dxy**_{0}

**-2dyx**_{0}

**+**

**2dx-2dx(**

**-****y**_{0}

**m**

**-dy****))****x****(**_{0}

**P**_{0}**=****2dxy**_{0}**-2dyx**_{0}**+****2dx-2dx****+****y**_{0}

**2dy****-dy****x**_{0}**(By using 2)**

**P**_{0}**=**

**2dx**

**-dy****hence formulas for bresenham is derived.**

derivation part of bresenhams algorithm is high

ReplyDeleteVery nice and easily understandable .Thank uh

ReplyDeleteBest derivation for bresenham algo on internet AFAIK

ReplyDeletebest derivation ever

ReplyDeleteFor slope is negative

ReplyDeleteThank you

ReplyDeleteMy teacher is mad ��

But u explained it very well