BBC Micro Elite

# Bresenham's line algorithm

```The main line-drawing algorithm used to draw non-horizontal lines
-----------------------------------------------------------------
References: LOIN
Most of what you see in the space view in Elite is composed of straight lines.
The ships are drawn using wireframes that are made up of straight lines, the
planets are made from circles and arcs that consist of lots of small, straight
lines, and the sun is no more than a sequence of horizontal lines, drawn along
a vertical axis. Having a fast line-drawing algorithm is essential in a game
like Elite.

Horizontal lines are a special case and have their own optimised routine at
HLOIN, but all non-horizontal lines in Elite are drawn using Bresenham's line
algorithm. Let's look at how that works.

The core algorithm
------------------
The basic idea is quite simple. Let's consider a line from (X1, Y1) to (X2,
Y2), where that line slopes down and right at a reasonably shallow angle, like
this:

(X1, Y1) ''-..__
''--..__
''--..__
''--.._
(X2, Y2)

As we move along the line from (X1, Y1) to (X2, Y2), let's say that we move
across by delta_x and down by delta_y, like this:

<---------- delta_x --------->

(X1, Y1) ''-..__                                    ^
''--..__                            | delta_y
''--..__                    |
''--.._             v
(X2, Y2)

So we have the following:

* As we move along the line by delta_x in the x-direction, we move down by
delta_y in the y-direction.

If we divide each side of the triangle by delta_x, we also get the following:

* As we move along the line by 1 in the x-direction, we move down by
(delta_y / delta_x) in the y-direction.

This is the core of the algorithm: if we step along the x-axis, 1 pixel at a
time, then if we also move down by (delta_y / delta_x) in the y-direction and
plot a point each time, we'll have our line. In pseudo-code, it looks like
this:

function line(x1, y1, x2, y2)
delta_x = x2 - x1
delta_y = y2 - y1
y = y1
for x from x1 to x2
plot(x, y)
y = y + (delta_y / delta_x)

If our screen had an infinite resolution, then this would do nicely... but, of
course, it doesn't, so we need to refine this idea. Internally we still do the
same calculation for y, but when we come to plot the point with plot(x, y), we
need to convert y into an integer. We could just convert y to the nearest
integer each time, but working with floating point numbers is pretty slow, so
the algorithm speeds things up by using the concept of a "slope error".

We're drawing a pixel line, so each time we step along the x-axis by 1 pixel,
we have a choice of either staying where we are in the y-axis, or moving down
one line (i.e. incrementing y by 1). We can't increase y by fractions, so
instead, each time we step along the x-axis, we keep a running total of how
far we would step down in the y-axis if we weren't constrained by only being
able to move down by 1. In other words, we keep a tally of the (delta_y /
delta_x)'s that we would ideally be adding to y, until we know we've moved
onto the next line, at which point we add 1 to y. This tally is known as the
"slope error", as it's a running tally of the current error between our pixels
and the real slope of the line.

There's one final tweak, and that's starting our slope error tally at 0.5,
which denotes the centre of the starting pixel. So the final algorithm looks
like this:

function line(x1, y1, x2, y2)
delta_x = x2 - x1
delta_y = y2 - y1
slope_err = abs(delta_y / delta_x)
error = 0.5
y = y1
for x from x1 to x2
plot(x, y)
error = error + slope_err
if error >= 1.0 then
y = y + 1
error = error - 1.0

Implementing Bresenham in 8-bit integers
----------------------------------------
You may have noticed that the algorithm above still uses real numbers. When we
actually use this approach in Elite, we multiply all the real numbers by 256,
so that 256 is equivalent to 1.0. We can now initialise error to 128, and
instead of checking whether error >= 1.0, we can check whether error is >=
256, like this:

function line(x1, y1, x2, y2)
delta_x = x2 - x1
delta_y = y2 - y1
slope_err = abs(delta_y / delta_x)
error = 128
y = y1
for x = x1 to x2
plot(x, y)
error = error + slope_err
if error >= 256 then
y = y + 1
error = error - 256

There is one final improvement. If we use a single byte to store the error,
then error >= 256 is the same as saying "has the addition just overflowed", in
which case we don't need to subtract 256 as the byte will already have rolled
around to 0. So here is the final algorithm used in Elite:

function line(x1, y1, x2, y2)
delta_x = x2 - x1
delta_y = y2 - y1
slope_err = abs(delta_y / delta_x)
error = 128
y = y1
for x = x1 to x2
plot(x, y)
error = error + slope_err
if C flag is set then
y = y + 1

This is the algorithm that's implemented in part 4 of the LOIN routine, for
gently sloping lines that go right and down. It uses Q, S, X and Y as follows:

Q = |delta_y| / |delta_x|
S = 128
Y = Y1
for X = X1 to X2
plot(X, Y)
S = S + Q
if C flag set then
inc Y

The full LOIN routine implements the same basic algorithm multiple times,
tweaked to cater for all the other variations of sloping line (such as more
vertical lines that slope sharply up and to the left, for example). But the
same principles apply, just with different signs.

Also, it's worth noting that Elite doesn't plot the last pixel in any of its
lines. This is to prevent corners from disappearing; if you imagine us drawing
a triangle by drawing a line from point A to point B, then from B to C, and
then from C to A again, then if we plotted the end points, each of the
triangle's vertices (A, B and C) would be plotted twice, once as the start of
a line, and again as the end of the line. Normally this wouldn't be a problem,
but because Elite draws everything on-screen using EOR logic (so objects can
be drawn and then erased by simply drawing them again), this would mean the
corner points would disappear, and that would look very strange. So there is
also logic in the following to omit the last pixel from the line, in the same
way that HLOIN omits the final pixel from its lines too.

Summary of the routine
----------------------
To help with understanding the 7 parts of the line-drawing routine, here's a
summary of what each part does.

1. Calculate delta_x, delta_y
Choose either parts 2-4 or parts 5-7

If the line is closer to being horizontal than vertical, we step right along
the x-axis:

2. Potentially swap coordinates so X1 < X2
Calculate |delta_y| / |delta_x|
Choose either part 3 or part 4

3. The line is going right and up (no swap) or left and down (swap)
X1 < X2 and Y1-1 > Y2
Draw from (X1, Y1) at bottom left to (X2, Y2) at top right
If we swapped, don't plot (X1, Y1)

4. The line is going right and down (no swap) or left and up (swap)
X1 < X2 and Y1-1 <= Y2
Draw from (X1, Y1) at top left to (X2, Y2) at bottom right
If we didn't swap, skip plotting (X1, Y1)

If the line is closer to being vertical than horizontal, we step up along
the y-axis:

5. Potentially swap coordinates so Y1 >= Y2
Calculate |delta_x| / |delta_y|
Choose either part 6 or part 7

6. The line is going up and left (no swap) or down and right (swap)
X1 < X2 and Y1 >= Y2
Draw from (X1, Y1) at bottom right to (X2, Y2) at top left
If we didn't swap, skip plotting (X1, Y1)

7. The line is going up and right (no swap) or down and left (swap)
X1 >= X2 and Y1 >= Y2
Draw from (X1, Y1) at bottom left to (X2, Y2) at top right
If we didn't swap, skip plotting (X1, Y1)

```