Bresenham Line Drawing Algortithm


Computer Graphics / Sunday, November 4th, 2018
(Last Updated On: November 4, 2018)

Bresenham Line Generating Algorithm

A more efficient line drawing algorithm than DDA line drawing algorithm is Bresenham Line Drawing Algorithm to determine the pixel positions, developed by Bresenham, finds the closed integer coordinates to the actual line path using integer arithmetic.

Consider the slope(m) is positive and m < 1. Pixel positions along the line path can then be plotted by taking unit steps in the x-direction and determining the y-coordinate value of the nearest pixel to the line at each step.

Bresenhams 02
Fig. A

We assume that the pixel (x1, y1) has been plotted and we now need to decide which is the next pixel to plot. The two choices for the next pixel positions are at coordinates (xi+1, yi) and (xi+1, yi+1).

Bresenhams 03
Fig. B

In fig (B), the coordinate differences between the center of the two pixels and the line coordinate y are labeled as d1 and d2. Position y can be calculated as

\[y=m({{x}_{i}}+1)+b\]

\[\text{Then},~{{d}_{1}}=y-{{y}_{i}}=m({{x}_{i}}+1)+b-{{y}_{i}}\]

\[and,{{d}_{2}}={{y}_{i+1}}-y={{y}_{i+1}}-m({{x}_{i}}+1)-b\]

\[\text{The difference},~{{d}_{1}}-{{d}_{2}}=2m\left( {{x}_{i}}+1 \right)-2{{y}_{i}}+2b-1……(1)\]

Now, we define a parameter that provides a measure of relative distances of two pixels from the actual position on a given line. Substituting m = Δy / Δx, we can rewrite equation (1) so that it involves only integer arithmetic

\[{{P}_{i}}=\Delta x\left( {{d}_{1}}-{{d}_{2}} \right)=2\Delta y{{x}_{i}}-2\Delta x{{y}_{i}}+C……(2)\]

where C = 2Δy + Δx(2b – 1) which is a constant and could be calculated once for all points. Clearly, if Pi < 0 if the pixel position yi is closed to the line then the upper pixel, select the lower pixel; otherwise the upper pixel is chosen.

We can rewrite the equation as:

\[{{P}_{i}}=2\Delta y{{x}_{i+1}}-2\Delta x{{y}_{i+1}}+C\]

Now,

\[{{P}_{i+1}}-{{P}_{i}}=2\Delta y\left( {{x}_{i+1}}-{{x}_{i}} \right)-2\Delta x\left( {{y}_{i+1}}-{{y}_{i}} \right)\]

\[\Rightarrow {{P}_{i+1}}={{P}_{i}}+2\Delta y-2\Delta x\left( {{y}_{i+1}}-{{y}_{i}} \right)…..(3)\]

\[Since,{{x}_{i+1}}-{{x}_{i}}=1\]

The first parameter Pi is obtained from (2) with (x1, y1) as starting point and m = Δy / Δx as

\[{{P}_{1}}=2\Delta y-\Delta x\]

 Example 01

Draw line segment joining (20, 10) and (25, 14) using Bresenham line generation algorithm.

Solution:

(x1, y1) → (20, 10)   ;   (x2, y2) → (25, 14)

\[m=\frac{{{y}_{2}}-{{y}_{1}}}{{{x}_{2}}-{{x}_{1}}}=\frac{14-10}{25-20}=\frac{4}{5}<1\]

\[As,m=\frac{\Delta y}{\Delta x}=\frac{4}{5}\]

\[\Rightarrow \Delta y=4,\Delta x=5\]

Plot point (20, 10)

\[{{P}_{1}}=2\Delta y-\Delta x\]

\[{{P}_{1}}=2\times 4-5=3>0\]

So, (x1, y1) ← (21, 11). We plot (21, 11).

\[{{P}_{2}}={{P}_{1}}+2\left( \Delta y-\Delta x \right)=3+2\left( 4-5 \right)=1>0\]

So, (x1, y1) ← (22, 12). We plot (22, 12).

\[{{P}_{3}}={{P}_{2}}+2\left( \Delta y-\Delta x \right)=1+2\left( 4-5 \right)=-1<0\]

So, (x1, y1) ← (23, 12). We plot (23, 12).

\[{{P}_{4}}={{P}_{3}}+2\Delta y=-1+2\times 4=7>0\]

So, (x1, y1) ← (24, 13). We plot (24, 13).

\[{{P}_{5}}={{P}_{4}}+2\left( \Delta y-\Delta x \right)=7+2\left( 4-5 \right)=5>0\]

So, (x1, y1) ← (25, 14). We plot (25, 14).

 Example 02

Illustrate the Bresenham line generation algorithm by digitzing the line with end points (20, 10) and (30,18).

Solution:

Do it yourself  😉

Bresenham Algorithm

 Bresenham Line Generating Algorithm Implementation In C

 

 

Leave a Reply

Your email address will not be published. Required fields are marked *