Skip to navigation

BBC Micro Elite

The 3D scanner

The maths behind Elite's famous 3D elliptical scanner

References: SCAN

The elliptical 3D scanner in the centre of the dashboard is one of Elite's most celebrated features, but it almost didn't make it into the game. For almost all of the game's life the scanner consisted of two two-dimensional radars, one showing a top-down view of the area around the ship and the other showing a side-on view, but it never really worked that well. Then, at the very last minute, after the manual had been written and the game's code had been polished until it shone, David Braben hit upon the idea of the 3D ellipse, and it was so good it just had to go in, so while Braben created the elliptical background image, Ian Bell coded it up, all in time to update the manual and hit the publishing deadline.

It was worth the effort, as the scanner is a thing of beauty, not only in terms of Braben's fantastic idea, which transforms the gaming experience, but also in the elegant simplicity of Bell's code. This is the last bit of code the pair wrote as anonymous undergraduates; after this, they would become rock stars, and their worlds would change forever.

So how does it work, this spark of genius that is so essential in making the 3D world of Elite feel so immersive? Well, to display a ship on the scanner, there are six main hoops we have to jump through.

We start with the ship's coordinates in space, given relative to our position (and therefore relative to the centre of the ellipse in the scanner, which represents our ship). Let's call the other ship's coordinates (x, y, z), with our position being at the origin (0, 0, 0).

We want to display a dot on the scanner at the ship's position, as well as a stick that drops down (or rises up) from the dot onto the scanner's ellipse.

The steps we have to perform are as follows:

  1. Check that the ship is within the scanner range (and stop if it isn't)
  2. Set X1 = the screen x-coordinate of the ship's dot (and stick)
  3. Set SC = the screen y-coordinate of the base of the ship's stick
  4. Set A = the screen height of the ship's stick
  5. Use these values to calculate Y1, the screen y-coordinate of the ship's dot
  6. Draw the dot at (X1, Y1) and draw a stick of length A from that dot (up or down as appropriate)

Before looking at these steps individually, first we need to talk about the scanner's dimensions.

Scanner dimensions
------------------

In terms of screen coordinates, the scanner is laid out as follows.

The rectangle containing the scanner and compass has the following range of screen coordinates inside the rectangle (so we definitely don't want to draw anything outside these values, or the scanner will leak out into the surrounding dashboard and space view):

  • x-coordinate from 50 to 204
  • y-coordinate from 193 to 246

The scanner's ellipse is 138 screen coordinates wide and 36 screen coordinates high, and the range of coordinates is:

  • x-coordinate from 56 to 192
  • y-coordinate from 204 to 239

The centre of the scanner is at (124, 220).

That said, this routine restricts itself to a slightly smaller range when passing coordinates to the drawing routines, only drawing dots and sticks within this range:

  • x-coordinate from 60 to 186
  • y-coordinate from 194 to 246

These values are explained in the following.

Now that we know the screen area in which we are going to show our ships, let's look at the different things we have to do.

Check the ship is in range
--------------------------

Elite does a simple check to see whether to show a ship on the scanner. Ship coordinates are stored in the INWK workspace using three bytes, like this:

  x = (x_sign x_hi x_lo)
  y = (y_sign y_hi y_lo)
  z = (z_sign z_hi z_lo)

The sign bytes only use bit 7, so the actual value is in the high and low bytes (these two bytes store the absolute value, without the sign).

A ship should be shown on the scanner if bits 7 and 6 of all the high bytes are 0. This means that ships to be shown on the scanner have high bytes in the range 0-63, as 63 = %00111111, and because the sign is kept separately, it means that for ships that we show on the scanner, the following are true:

  -63 <= x_hi <= 63
  -63 <= y_hi <= 63
  -63 <= z_hi <= 63

We can now move on to calculating the screen coordinates of the dot and stick.

Calculate the x-coordinate
--------------------------

The x-coordinate is the easiest, as all we have to do is scale x so that it fits into the horizontal range of the scanner... and it turns out that the range of (x_sign x_hi) is already pretty close to the full width of the scanner (the ellipse is 138 screen coordinates wide, while the range of (x_sign x_hi) values from -63 to +63 is 127, which is in the right ballpark).

So if we take the x-coordinate of the centre of the scanner, 124, and add (x_sign x_hi), we get a range of 61 to 187, which fits nicely within the ellipse range of 56 to 192 and is quick and easy to calculate.

There is one small tweak to this, however. If we add 124 to (x_sign x_hi), then if the other ship is dead ahead of us - i.e. when (x_sign x_hi) = 0 - the dot will be drawn with the left pixel on the centre line and the right pixel just to the right of the line. This isn't a problem, but because we draw the stick down (or up) from the right-hand pixel, this means that ships that are dead ahead have a stick that lands on the ellipse just to the right of the centre line. So to fix this, we actually add 123 to get the scanner x-coordinate, as this not only moves the stick to the correct spot, it also has the benefit of making the end-points even numbers, as the range of 123 + (x_sign x_hi) is 60 to 186 (and even numbers are good news when your pixels are always 2 screen coordinates wide).

So this is how we get the screen x-coordinate of the ship on the scanner:

  X1 = 123 + (x_sign x_hi)

This was the easy one. Now for the y-coordinate of the base of the stick, which is a bit more challenging.

Calculate the base of the stick
---------------------------------

We already know the x-coordinate of dot, as we just calculated that, and the stick will have the same x-coordinate as the dot, though we will add 1 when drawing it, as the stick is on the right side of the 2-pixel-wide dot. So we already know the x-coordinate of the base of the stick - now to find the y-coordinate.

The main observation here is that the scanner's ellipse is a plane in space, and for every point in that plane, the space y-coordinate is zero, and the space x- and z-coordinates determine where those points appear, either from left to right (for the x-axis) or front to back (the z-axis). We've already worked out where the base of the stick is in terms of left and right, but what about front to back?

If you think about it, points on the ellipse that are further in front of us will be further up the screen, while those behind us will be lower down the screen. It turns out that this is an easy way to work out the y-coordinate of the base of the stick - we just take the space y-coordinate and scale it so that it fits into the height of the ellipse on-screen. As long as we reverse things so that large positive y-coordinates (far in front of us) are scaled to smaller screen y-coordinates (higher up the screen), this should work pretty well.

The maths for this is relatively simple. We take (z_sign z_hi), which is in the range -63 to +63, divide it by 4 to get a range of -15 to +15, and then negate it. We then add this to the coordinate of the centre of the ellipse, which is at screen y-coordinate 220, to get the following:

  SC = 220 - (z_sign z_hi) / 4

This is in the range 205 to 235, which is really close to the range of y-coordinates of the ellipse on-screen (204 to 239), and fits within the ellipse nicely.

Next, we need to work out the height of the stick, and then we'll have all the information we need to draw this thing.

Convert the stick height
------------------------

The stick height should be a signed number that contains the number of pixels in the stick, with the sign set so that we can get the dot's y-coordinate by adding the height to the y-coordinate of the base of the stick. This means that we want the following to be true:

  • The stick height should be negative for dots above the ellipse (as the dot is above the base of the stick, so it has a lower y-coordinate)
  • The stick height should be zero for dots on the ellipse
  • The stick height should be positive for dots below the ellipse (as the dot is below the base of the stick, so it has a lower y-coordinate)

The main observation here is that the length of the stick is effectively the same as the ship's y-coordinate in space, just negated. Specifically:

  • If the y-coordinate is 0, then the dot is in the plane of the ellipse and there is no stick
  • If the y-coordinate is positive, then the ship is above us and the stick length should be negative
  • If the y-coordinate is negative, then the ship is above us and the stick length should be positive
  • The further the ship is above or below us, the longer the stick

It turns out that it's good enough just to scale the y-coordinate to get the stick length. Sure, if you were building an accurate scanner than the stick length would also have to be scaled for reasons of perspective, but this is an 8-bit space simulation from 1984 where every processor cycle counts, and the following approximation is easily good enough.

It also turns out that dividing the y-coordinate by 2 does a good enough job. We take (y_sign y_hi), which is in the range -63 to +63, and divide it by 2 to get a range of -31 to +31. As we noted above, the y-coordinate for the base of the stick is in the range 205 to 235, so this means the range of screen y-coordinates for our dots comes out as 174 to 266.

But this is a bit of a problem - the dashboard only covers y-coordinates from 193 to 246, so quite a few of the more distant dots will end up spilling out of the dashboard if we don't do something about it. The solution is pretty simple - if the dot is outside of the dashboard limits, we move it back inside. This does mean that the dots and sticks of distant ships don't behave correctly - they get shifted up or down to keep them within the dashboard, which isn't correct - but somehow our brains don't seem to care. The stick heights still remain correct, and the orientation of these outliers is still generally in the right direction, so we can get away with this simplification.

In terms of this clipping, we actually clip the dot's y-coordinate so that it is in the range 194 to 246, rather than 193 to 246. This is because the double-height dot-drawing routine at CPIX2 takes the coordinate of the bottom row of the dot, so we have to restrict it to a minimum of 194, as passing 193 would draw a dot that overlapped the top border of the dashboard.

So this is how we calculate the stick height from the ship's y-coordinate in space:

  A = - (y_sign y_hi) / 2

and clip the result so that it's in the range 193 to 246. So now we have all the information required to draw the ship on the scanner, and to erase it later (which we do by drawing it a second time).