Saloni Speaks!

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.

yi+1= yi + 1 

xi+1 = xi , if d1<d2 

or

xi+1 = xi + 1, if d2 < d1 

where,

d1 = x -xi

d2= xi+1 - x,  as shown in the figure :

Therefore,

d1-d2 = 2x - xi - xi+1 

Since,

xi+1 = xi + 1

∴ d1-d2 = 2x - xi - xi - 1
           = 2x - 2xi - 1

For each x,

yi+1 = mx + c

x = (yi+1-c)/m 

∴ d1-d2 = 2((yi+1-c)/m) - 2xi - 1
             = 2((yi + 1 -c )/m ) - 2xi - 1
             = 2yi/m + 2/m -c/m - 2xi -  1
             = 2yi/m - 2xi + k 
              where k =  2/m - c/m - 1 

Replace m = dy/dx & multiply by dy
We get,

dy(d1-d2) = 2yidx - 2xidy + 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)

Pi = 2yidx - 2xidy + kdy

Similarly, decision variable for i+1_th pixel is :

Pi+1 = 2yi+1dx - 2xi+1dy + kdy

Subtracting P_i+1 and P_i, we get :

Pi+1 - Pi = 2dx(yi+1 - yi) - 2dy(xi+1 -xi )

Pi+1 = Pi + 2dx - 2dy(xi+1 - xi) 

Decision variable for the initial pixel, say (x₀, y₀)

P = 2y0dx - 2x0dy + kdy
       = 2y0dx - 2dy( y0 - c )/m + (2/m - 2c/m - 1)dy
       = 2dx - dy

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

xi+1 = xi

∴ Pi+1 = Pi + 2dx 

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

Pi+1 = Pi + 2dx - 2dy

Summarizing the steps

1. Input the 2 line end points and store the left end point as (x₀, y₀). We assume the left point as starting point because we have assumed positive slope.
2. Plot the first point (x₀, y₀).
3. Calculate constants dx, dy, 2dx, 2dy, 2dx-dy and obtain the starting value for decision variable as P = 2dx-dy.
4. 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 + 2dx

   otherwise, the next point to plot is :

         ( x_i+1 , y_i+1)  &  P_i+1 = P_i + 2dx – 2dy

5. Repeat step 4 dy times.