Explain Bresenham line draw algorithm. Plot a line by using Bresenham line generating algorithm from (1, 1) to (5, 3).

397views

written 8.4 years ago by

teamques10 ★ 68k

• modified 8.4 years ago

Bresenham’s Algorithm was developed by J. E. Bresenham in 1962.
It is much accurate and much more efficient than DDA.
It scans the coordinates but instead of rounding them off it takes the incremental value in account by adding or subtracting and therefore can be used for drawing circle and curves.
Therefore if a line is to be drawn between two points x and y then next coordinates will be

$(x_a + 1, y_a) \ \ and \ \ (x_a + 1, y_a + 1)$
Where ‘a’ is the incremental value of the next coordinates and difference between these two will be calculated by subtracting or adding the equations formed by them.

i. Considering the figure 1, from start point we have to decide A or B.

ii. For a given value of x as shown in figure 2

one pixel lies at distance $t_i$ above the line, and
one pixel lies at distance $s_i$ below the line

iii. Using Decision parameter formula find out the closest pixel.

iv. Decision parameter Formula: $d_i = (s_i - t_i)$

If $d_i$ 0, then closest pixel is below true line ($s_i$ smaller).
If $d_i ≥ 0$, then closest pixel is above true line ($t_i$ smaller).

v. We must calculate the new values for $d_i$ as we move along the line.

Example:

Let gradient (slope) < 0.5 $(i.e \ \ \frac{dy}{dx} \lt 0.5 \ \ or \ \ 2dy \lt dx)$

Consider the figure 3, we consider gentle slope case we will move along the x-axis only.

Start pixel at $(x_0, y_1)$

At x1:

$s_1 = dy \ \ and \ \ t_1 = dx – dy$,

$Therefore \ \ by \ \ decision \ \ parameter,\ \ d_1 = (s_i - t_i)$

= dy - (dx - dy)

= 2dy - dx

But 2dy  dx ⇨ di 0 → y stays the same. Hence next pixel is at $(x_1, y_1)$

At x2:

$s_2 = 2dy \ \ and \ \ t_2 = dx - 2dy$

Therefore by decision parameter, $d_2 = (s_2 – t_2)$

= 2dy - (dx - 2dy)

= 4dy - dx

Suppose d2 ε 0 ⇨ y is incremented. Hence next pixel is at $(x_2, y_2)$

At x3:

$s_3 = 3dy – dx \ \ and \ \ t_2 = 2dx - 3dy$

Therefore by decision parameter, $d_3 = (s_2 – t_3)$

= 6dy - 3dx  0

So y stays the same. Hence next pixel is at $(x_3, y_2)$

Continue the same process till $X_5$.

In general,

For a line with gradient ≤ 1	For a line with gradient  1
$d_0 = 2dy - dx$ if $d_i$  0 then $Y_{i + 1} = Y_i d_{i + 1} = d_i + 2dy \ \ if d_i ≥ 0 then Y_{i + 1} = Y_i + 1 \ \ d_{i + 1} = d_i + 2(dy - dx) \ \ X_{i + 1} = x_i + 1$	$d_0 = 2dy - dx$ if $d_i$  0 then $X_{i + 1} = X_i d_{i + 1} = d_i + 2dx \ \ if d_i ≥ 0 then X_{i + 1} = X_i + 1 \ \ d_{i + 1} = d_i + 2(dy - dx) \ \ y_{i + 1} = y_i + 1$

Advantages:

● A fast incremental algorithm.

● Uses only integer calculations.

Plot a line by using Bresenhams line generating algorithm from (1, 1) to (5, 3).

Given:

$X_1 = 1, \ \ \ \ Y_1 = 1$

$X_2 = 5, \ \ \ \ Y_2 = 3$

Dx = X2 – X1 = 5 – 1 = 4

Dy = Y2 – Y1 = 3 – 1 = 2

Therefore Slope = 2Dy – Dx = 2 (2) – 4 = 0

Plot 1st point (1, 1) here as | Dx | > | Dy | that means line is Gentle slope, so here we have to move on X till $X_2$ i.e. 5.

After plotting 1st point as (1, 1) increase X by 1.

Therefore X = 2.

Here G = 0, so we have to increase Y by 1 and update G as,

G = G + 2 (Dy - Dx)

= 0 + 2 (2 - 4)

= -4

So, plot next point as (2, 2) then again increase X by 1. Now it will become X = 3.

Here G = -4

So, don’t increase Y just Update G only as,

G = G + 2 Dy

= -4 + 2 (2)

= 0

So, plots (3, 2) go on doing this till X reaches to $X_2$.

We will get points as,

X	Y
1	1
2	2
3	2
4	3
5	3

So, the final points on line will be shown in figure 5

ADD COMMENT EDIT