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).