Bresenham’s Line Algorithm is a highly efficient incremental algorithm for scan converting lines. This algorithm was developed by Jack Elton Bresenham in 1962 at IBM. It is better than DDA algorithm as it produces mathematically accurate results using only incremental integer calculations. It avoids the “round-off” functions and uses only integer addition, subtraction and multiplication by 2. It is faster than any other method of line generation.
Bresenham’s Line Algorithm
The Bresenham’s Line Algorithm based on finding those pixel locations that lie closest to the true path. Depending upon the slope m of line, Bresenham’s Algorithm increments either x value or y value by one unit. It then finds the other value (x or y) on the basis of the distance between the actual line location and the nearest pixel. This distance is called decision variable or decision parameter.
In order to understand the working of this algorithm, let us consider a line with a positive slope less than 1 i.e. |m|<1.
1. Let P1 (x1, y1) and P2 (x2, y2) are two endpoints of a line. Starting from left end point P1 the various pixels chosen by sampling the line at unit x interval, until P2 is reached.
2. Assuming at step i we have already determined that the pixel (xi, yi) is to be displayed then we have to choose between the bottom pixel S and the top pixel T.
3. The coordinate pixel of S are S(xi+1, yi) and whereas the coordinate of pixel T are (xi+1, yi+1).
If pixel T is chosen we have,
xi+1 = xi+1
yi+1 = yi +1
If pixel S is chosen we have,
xi+1 = xi+1
yi+1 = yi
4. The actual y coordinate of the line at x = xi+1 is:
y = mxi+1 + b
= mxi+1 + b –[1]
5. The distance from S to the actual line inn the y direction is
s = y – yi
and the distance from T to the actual line in y direction is:
t = (yi + 1) – y
6. Now, we consider the difference between two distance values s – t.
s – t = (y – yi) – [(yi + 1) – y]
s – t = y – yi – yi – 1 + y
s – t = 2y – 2 yi – 1 –[2]
7. If s – t is < 0 that means s < t i.e. s is closer than distance t. ∴ Pixel S is chosen.
If s – t is > 0 that means s > t i.e. t is closer than distance s. ∴ Pixel T is chosen.
8. Substituting the value of y from eq[1] in eq[2], we get:
s – t = 2 [mxi+1 + b] – 2 yi – 1
s – t = 2 m(xi+1) + 2b – 2 yi – 1 –[3]
We know that m = Δy/Δx. Putting value of m in eq[3], we get:
s – t = 2Δy/Δx(xi+1) + 2b – 2 yi – 1 –[4]
9. Now, introduce the decision parameter i.e. di = Δx(s-t)
di = Δx[2Δy/Δx(xi+1) + 2b – 2 yi – 1 ]
di = 2Δy(xi+1) + 2Δxb – 2 Δxyi – Δx
di = 2Δyxi+2Δy + 2Δxb – 2 Δxyi – Δx
di = 2Δyxi – 2 Δxyi + C [ where C = 2Δy + 2Δxb – Δx ]
Similarly we write decision variable for next step i.e.
di+1 = 2Δyxi+1 – 2 Δxyi+1 + C
Now find di+1 – di
di+1 – di = 2Δyxi+1 – 2 Δxyi+1 + C – [2Δyxi – 2 Δxyi + C]
di+1 – di = 2Δyxi+1 – 2 Δxyi+1 + C – 2Δyxi + 2 Δxyi – C
di+1 – di = 2Δyxi+1 – 2 Δxyi+1 + C – 2Δyxi + 2 Δxyi – C
di+1 – di = 2Δyxi+1 – 2 Δxyi+1 – 2Δyxi + 2 Δxyi
di+1 – di = 2Δy(xi+1 – xi) – 2Δx(yi+1 – yi) –[5]
10. The value of variable x for next pixel i.e. xi+1 = xi + 1 for both pixel S and T.
di+1 – di = 2Δy(xi + 1 – xi) – 2Δx(yi+1 – yi)
di+1 – di = 2Δy – 2Δx(yi+1 – yi) –[6]
11. If we choose pixel S, then the value of yi+1 = yi, from eq[6], we get:
di+1 – di = 2Δy – 2Δx(yi – yi)
di+1 – di = 2Δy
di+1 = 2Δy + di
12. If we choose pixel T, then the value of yi+1 = yi + 1 , from eq[6], we get:
di+1 – di = 2Δy – 2Δx(yi + 1 – yi)
di+1 – di = 2Δy – 2Δx
di+1 = 2(Δy – Δx) + di
13. Now to find first pixel we have to find d1 for coordinates(x1 , y1 ), from decision parameter, we get:
d1 = Δx(s -t)
Put value of (s – t) from eq[3], we get:
d1 = Δx[2m(x1+1) + 2b – 2 y1 – 1 ]
d1 = Δx[2mx1+2m + 2b – 2 y1 – 1 ]
d1 = Δx[2(mx1+ b – y1) + 2m – 1]
d1 = Δx[2m – 1] [ mx1+ b – y1 = 0 ]
Put value of m = Δy/Δx, we get:
d1 = Δx[2Δy/Δx – 1]
d1 = 2Δy – Δx
∴ The three different values of Bresenham’s Line Algorithm are:
di+1 = 2Δy + di [For pixel S]
di+1 = 2(Δy – Δx) + di [For pixel T]
d1 = 2Δy – Δx
Related posts:-
[su_posts template=”templates/list-loop.php” posts_per_page=”3″ taxonomy=”link_category” tax_operator=”NOT IN” order=”
desc”]