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 P_{1} (x_{1}, y_{1}) and P_{2} (x_{2}, y_{2}) are two endpoints of a line. Starting from left end point P_{1 }the various pixels chosen by sampling the line at unit *x* interval, until P_{2} is reached.

2. Assuming at step *i *we have already determined that the pixel (x_{i}, y_{i}) 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(x_{i+1, }y_{i}) and whereas the coordinate of pixel T are (x_{i+1, }y_{i+1}).

If pixel T is chosen we have,

x

_{i+1 }= x_{i}+1y

_{i+1 }= y_{i}+1

If pixel S is chosen we have,

x

_{i+1 }= x_{i}+1y

_{i+1 }= y_{i}

4. The actual y coordinate of the line at x = x_{i+1} is:

y = mx

_{i+1}+ b= mx

_{i}+1 + b–[1]

5. The distance from S to the actual line inn the y direction is

s = y – y

_{i}

and the distance from T to the actual line in y direction is:

t = (y

_{i }+ 1) – y

6. Now, we consider the difference between two distance values s – t.

s – t = (y – y

_{i}) – [(y_{i}+ 1) – y]s – t = y – y

_{i}– y_{i}– 1 + ys – t = 2y – 2 y

_{i}– 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 [mx

_{i}+1 + b] – 2 y_{i}– 1s – t = 2 m(x

_{i}+1) + 2b – 2 y_{i}– 1–[3]

We know that m = Δy/Δx. Putting value of m in eq[3], we get:

s – t = 2Δy/Δx(x

_{i}+1) + 2b – 2 y_{i}– 1–[4]

9. Now, introduce the * decision parameter *i.e. d

_{i}= Δx(s-t)

d

_{i}= Δx[2Δy/Δx(x_{i}+1) + 2b – 2 y_{i}– 1 ]d

_{i}= 2Δy(x_{i}+1) + 2Δxb – 2 Δxy_{i}– Δxd

_{i}= 2Δyx_{i}+2Δy + 2Δxb – 2 Δxy_{i}– Δxd

_{i}= 2Δyx_{i}– 2 Δxy_{i}+ C[ where C = 2Δy + 2Δxb – Δx ]

Similarly we write decision variable for next step i.e.

d

_{i+1 }= 2Δyx_{i+1}– 2 Δxy_{i+1}+ C

Now find d_{i+1 }– d_{i}

d

_{i+1 }– d_{i }= 2Δyx_{i+1}– 2 Δxy_{i+1}+ C – [2Δyx_{i}– 2 Δxy_{i}+ C]d

_{i+1 }– d_{i }= 2Δyx_{i+1}– 2 Δxy_{i+1}+ C – 2Δyx_{i}+ 2 Δxy_{i}– Cd

_{i+1 }– d_{i }= 2Δyx_{i+1}– 2 Δxy_{i+1}+ C – 2Δyx_{i}+ 2 Δxy_{i}– Cd

_{i+1 }– d_{i }= 2Δyx_{i+1}– 2 Δxy_{i+1}– 2Δyx_{i}+ 2 Δxy_{i}d

_{i+1 }– d_{i }= 2Δy(x_{i+1}– x_{i}) – 2Δx(y_{i+1}– y_{i})–[5]

10. The value of variable x for next pixel i.e. x_{i+1} = x_{i }+ 1 for both pixel S and T.

d

_{i+1 }– d_{i }= 2Δy(x_{i }+ 1 – x_{i}) – 2Δx(y_{i+1}– y_{i})d

_{i+1 }– d_{i }= 2Δy – 2Δx(y_{i+1}– y_{i})–[6]

11. If we choose pixel S, then the value of y_{i+1 }= y_{i}, from eq[6], we get:

d

_{i+1 }– d_{i }= 2Δy – 2Δx(y_{i}– y_{i})d

_{i+1 }– d_{i }= 2Δy

d_{i+1 }= 2Δy + d_{i}

12. If we choose pixel T, then the value of y_{i+1 }= y_{i }+ 1 , from eq[6], we get:

d

_{i+1 }– d_{i }= 2Δy – 2Δx(y_{i }+ 1 – y_{i})d

_{i+1 }– d_{i }= 2Δy – 2Δx

d_{i+1 }= 2(Δy – Δx) + d_{i}

13. Now to find first pixel we have to find d_{1} for coordinates(x_{1} , y_{1} ), from decision parameter, we get:

d

_{1}= Δx(s -t)

Put value of (s – t) from eq[3], we get:

d

_{1}= Δx[2m(x_{1}+1) + 2b – 2 y_{1}– 1 ]d

_{1}= Δx[2mx_{1}+2m + 2b – 2 y_{1}– 1 ]d

_{1}= Δx[2(mx_{1}+ b – y_{1}) + 2m – 1]d

_{1}= Δx[2m – 1][ mx_{1}+ b – y_{1 }= 0 ]

Put value of m = Δy/Δx, we get:

d

_{1}= Δx[2Δy/Δx – 1]

d_{1}= 2Δy – Δx

∴ The three different values of Bresenham’s Line Algorithm are:

d[For pixel S]_{i+1 }= 2Δy + d_{i }

d[For pixel T]_{i+1 }= 2(Δy – Δx) + d_{i }

d_{1}= 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”]