**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

ReplyDelete