# Deriving Bresenham's Line Algorithm

Bresenham’s line algorithm is a graphics algorithm for approximating a straight line between two end-points. Its popularity over other such algorithms is in its efficiency, as it avoids expensive floating point calculations.

The ‘plain’ algorithm only works for lines with a gradient in the range `[0, 1]` (i.e., non-steep lines; where the change in `x`, `dx`, is greater than the change in `y`, `dy`). The algorithm is written in the context of a graphics system where there origin, `(0, 0)`, is located in the top-left corner. However, no changes need to be made for graphics systems where the origin is at the bottom-left. It is also assumed that the starting point of the line, `x0`, is to the left (i.e., is less than) the endpoint.

To skip straight to the final algorithm, scroll down. Alternatively, continue on to the derivation.

## Derivation

The equation of a line in terms of `y` can be defined as:

``````y = f(x) = mx + b
``````

Where `m` is the slope of the line, and `b` is the y-intercept.

This equation can be transformed, as follows:

``````y = (dy/dx)x + b
(dx * y) = (dy * x) + (dx * b)
0 = (dy * x) - (dx * y) + (dx * b)

f(x, y) = 0 = Ax + By + C
where
A = dy
B = -dx
C = (dx * b)
``````

It follows that for any pair `(x, y)`:
if `(x, y)` is on the line, `f(x, y) = 0`
if `(x, y)` is off the line, `f(x, y) != 0`

• if `f(x, y) < 0`, `(x, y)` is on the ‘negative half-plane’
• if `f(x, y) > 0`, `(x, y)` is on the ‘positive half-plane’

From the previously calculated point `(xp, yp)`, we need to determine if the next point on the line is at `(xp + 1, yp)` or `(xp + 1, yp)`. That is to say, we need to find out if `y` moves across or down and across.

Note: in cases where the origin is at the bottom-left, this would be testing whether `y` moved across or up and across.

We can choose between these two options by testing the value of the line, `f(x, y)`, in terms of a midpoint, `M`, which is located half-way between the two candidate points.

``````M = (xp + 1, yp + 0.5)

f(M) = f(xp + 1, yp + 0.5)
``````

If `f(M) > 0`, select the candidate `(xp + 1, yp + 1)`, because the midpoint is in the positive plane, hence the line must pass under the midpoint, meaning is it closer to this option.

If `f(M) < 0`, select the candidate `(xp + 1, yp)`, because the midpoint is in the negative plane, hence the line must pass over the midpoint, meaning it is closer to this option. To avoid having to calculate `f(M)` all the time, we introduce the notion of a decision variable.

The ‘decision’ variable, `D`, keeps track of the current value of `f(M)`. Its initial value can be calculated as the difference between the value of `f(x, y)` at the first end point of the line (x0, y0), and the first midpoint:

``````D = f(x0 + 1, y0 + 0.5) - f(x0, y0)
``````

Using the line equation, `f(x, y) = 0 = Ax + By + C`, this can be simplified to:

``````D = [A(x0 + 1) + B(y0 + 0.5) + C] - [Ax0 + By0 + C]
= [A(x0 + 1) + B(y0 + 0.5) + C] - Ax0 - By0 - C
= Ax0 + A + By0 + 0.5B + C - Ax0 - By0 - C
= Ax0 -Ax0 + A + By0 - By0 + 0.5B + C - C
= A + 0.5B
``````

`D` can then be used to determine which candidate point to select next, using the same logic as earlier:

• if `D > 0`, select `(xp + 1, yp)`
• if `D < 0`, select `(xp + 1, yp + 1)`

As we calcuate points on the line, we need to update the value of `D` to correspond to the next midpoint. The way in which the value changes depends on which candidate point was chosen (i.e., if `y` was incremented or not).

We can calculate the increment for `D`, `dInc`, as a general increment based on the last midpoint. To make the calculations easier, we’ll do this in terms of the first and second midpoints, `M1` and `M2`, where `dInc = f(M2) - f(M1)`.

Regardless of the first ‘direction’ chosen for `y`, the first midpoint, `M1`, can be defined as:

``````M1 = (x0 + 1, y0 + 0.5)
``````

The value of `M2`, however, depends on the direction chosen.

So, if `y` was not incremented:

``````M2 = (x0 + 2, y0 + 0.5)

dInc = f(x0 + 2, y0 + 0.5) - f(x0 + 1, y0 + 0.5)
= [A(x0 + 2) + B(y0 + 0.5) + C] - [A(x0 + 1) + B(y0 + 0.5) + C]
= Ax0 + 2A + By0 + 0.5B + C - [Ax0 + A + By0 + 0.5B + C]
= Ax0 + 2A + By0 + 0.5B + C - Ax0 - A - By0 - 0.5B - C
= Ax0 - Ax0 + 2A - A + By0 - By0 + 0.5B - 0.5B + C - C
= A
``````

Which, going back to the original definitions of `A`, `B`, and `C`, is equal to `dy`.

If `y` was incremented:

``````M2 = (x0 + 2, y0 + 1.5)

dInc = f(x0 + 2, y0 + 1.5) - f(x0 + 1, y0 + 0.5)
= [A(x0 + 2) + B(y0 + 1.5) + C] - [A(x0 + 1) + B(y0 + 0.5) + C]
= Ax0 + 2A + By0 + 1.5B + C - [Ax0 + A + By0 + 0.5B + C]
= Ax0 + 2A + By0 + 1.5B + C - Ax0 - A - By0 - 0.5B - C
= Ax0 - Ax0 + 2A - A + By0 - By0 + 1.5B - 0.5B + C - C
= A + B
``````

Which, going back to the original definitions of `A`, `B`, and `C`, is equal to `dy + (-dx)`, which is `dy - dx`.

So, during each iteration of the algorithm, based on whether `y` was incremented or not, we increment `D` by either `dy` or `dy - dx`.

## Algorithm

Assuming the existence of a method `setPixel(x, y)`, which colours a pixel at the location `(x, y)`, the following algorithm is the general form of Bresenham’s line algorithm for drawing a straight line between two points `(x0, y0)` and `(x1, y1)`:

``````dx = x1 - x0
dy = y1 - y0

a = dy
b = -1 * dx
# do not need to calculate the value of 'c', as it is never used

d = a + 0.5b
dInc = a # increment for 'd' if 'y' was not incremented
yInc_dInc = a + b # increment for 'd' if 'y' was incremented

y = y0
for (x = x0; x <= x1; ++x):
setPixel(x, y)
# increment 'y' and update decision variable as appropriate
if d > 0:
y += 1
d += yInc_dInc
else:
d += dInc
``````

However, notice that there is still some floating point calculations, specifically in the initialisation of `d`. To avoid this we can multiply all values of `d` by `2`. This includes the initialisation of `d`, and all potential increments to `d`.

We also need to handle lines which fall outside of the constraints defined earlier, being that the line must not be too steep, that `x0 < x1`, and that `dy >= 0`. By applying changes to avoid these constraints we get the final algorithm, which handles all cases, using only integers:

``````dx = x1 - x0
dy = y1 - y0

isSteep = abs(dy) > abs(dx) # check if the line is steeper than a slope with a graident of [0, 1]

if isSteep:
# line is steep, swap the roles (i.e., values) of x and y
swap(x0, y0)
swap(x1, y1)

if x0 > x1:
# start point isn't to the left - swap the end points
swap(x0, x1)
swap(y0, y1)

a = dy
b = -1 * dx
# do not need to calculate the value of 'c', as it is never used

d = 2a + b
dInc = 2 * a # increment for 'd' if 'y' was not incremented
yInc_dInc = 2 * (a + b) # increment for 'd' if 'y' was incremented

yStep = 1
if (dy < 0):
yStep = -1 # line goes down, so if 'y' needs to be incremented, it needs to be incremented 'downwards', not 'upwards'

y = y0
for (x = x0; x <= x1; ++x):
if isSteep:
setPixel(y, x) # swap the x and y values back so the line will draw properly
else:
setPixel(x, y)

# choose next value for 'y' and update decision variable as appropriate
if d > 0:
y += yStep
d += yInc_dInc
else:
d += dInc
``````