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+1th pixel
∴ Decision variable is taken as Pi = dy(d1-d2)
Pi = 2yidx - 2xidy + kdy
Similarly, decision variable for i+1th pixel is :
Pi+1 = 2yi+1dx - 2xi+1dy + kdy
Subtracting Pi+1 and Pi, 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 (x0, y0)
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
- Input the 2 line end points and store the left end point as (x0, y0). We assume the left point as starting point because we have assumed positive slope.
- Plot the first point (x0, y0).
- Calculate constants dx, dy, 2dx, 2dy, 2dx-dy and obtain the starting value for decision variable as P = 2dx-dy.
- At each yi along the line starting at i = 0, perform the following test :
If Pi < 0, the next point to plot is :
( xi , yi+1 ) & Pi+1 = Pi + 2dx
otherwise, the next point to plot is :
( xi+1 , yi+1) & Pi+1 = Pi + 2dx – 2dy
- Repeat step 4 dy times.
Very helpful. Thanks!