Previously, I discussed the basic idea of Bresenham’s Line Algorithm. As it had been discussed in the previous post that when slope of line > 1, the shadow of line falls more on y-axis and thus y-axis is the axis of maximum movement. So, when the line is plotted between 45° and 90° i.e. when slope > 1, the driving axis is Y-axis and thus we do sampling along it.

Mathematically, if ∆x = x2 − x1 and ∆y = y2 − y1 , we define the driving axis (DA) to be the x-axis if |∆x| ≥ |∆y|, and the y-axis if |∆y| > |∆x|. The DA is used as the “axis of control” for the algorithm and is the axis of maximum movement. Within the main loop of the algorithm, the coordinate corresponding to the DA is incremented by one unit. The coordinate corresponding to the other axis (usually denoted the passive axis or PA) is only incremented as needed.

I have already discussed Line Algorithm for slope < 1. When slope > 1, Y is sampled i.e incremented and X is evaluated.

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

x_{i+1}= x_{i}, if d1<d2

or

x_{i+1}= x_{i}+ 1, if d2 < d1

where,

d1 = x -x_{i}

d2= x_{i+1}- x, as shown in the figure :

Therefore,

d1-d2 = 2x - x_{i}- x_{i+1}

Since,

x_{i+1}= x_{i}+ 1

∴ d1-d2 = 2x - x_{i}- x_{i}- 1 = 2x - 2x_{i}- 1

For each x,

y_{i+1}= mx + c

x = (y_{i+1}-c)/m

∴ d1-d2 = 2((y_{i+1}-c)/m) - 2x_{i}- 1 = 2((y_{i}+ 1 -c )/m ) - 2x_{i}- 1 = 2y_{i}/m + 2/m -c/m - 2x_{i}- 1 = 2y_{i}/m - 2x_{i}+ k where k = 2/m - c/m - 1

Replace m = dy/dx & multiply by dy

We get,

dy(d1-d2) = 2y_{i}dx - 2x_{i}dy + kdy

For slope > 1, dy is always positive and hence the sign of dy(d1-d2) is same as d1-d2 which determines the pixel position for i+1_{th} pixel

∴ Decision variable is taken as P_{i} = dy(d1-d2)

P_{i}= 2y_{i}dx - 2x_{i}dy + kdy

Similarly, decision variable for i+1_{th} pixel is :

P_{i+1}= 2y_{i+1}dx - 2x_{i+1}dy + kdy

Subtracting P_{i+1} and P_{i}, we get :

P_{i+1}- P_{i}= 2dx(y_{i+1}- y_{i}) - 2dy(x_{i+1}-x_{i})

P_{i+1}= P_{i}+ 2dx - 2dy(x_{i+1}- x_{i})

Decision variable for the initial pixel, say (x_{0}, y_{0})

P = 2y_{0}dx - 2x_{0}dy + kdy = 2y_{0}dx - 2dy( y_{0}- c )/m + (2/m - 2c/m - 1)dy = 2dx - dy

Now, if P < 0 ( i.e. d1-d2 < 0 ), then

x_{i+1}= x_{i}∴ P_{i+1}= P_{i}+ 2dx

if P > 0 ( i.e. d1-d2 > 0 ), then

P_{i+1}= P_{i}+ 2dx - 2dy

**Summarizing the steps **

- Input the 2 line end points and store the left end point as (x
_{0}, y_{0}). We assume the left point as starting point because we have assumed positive slope. - Plot the first point (x
_{0}, y_{0}). - Calculate constants dx, dy, 2dx, 2dy, 2dx-dy and obtain the starting value for decision variable as P = 2dx-dy.
- At each y
_{i}along the line starting at i = 0, perform the following test :If P

_{i}< 0, the next point to plot is :( x

_{i}, y_{i+1}) & P_{i+1}= P_{i}+ 2dxotherwise, the next point to plot is :

( x

_{i+1}, y_{i+1}) & P_{i+1}= P_{i}+ 2dx – 2dy - Repeat step 4 dy times.

Very helpful. Thanks!