Skip to navigation

BBC Micro Elite

Pitching and rolling

Applying our pitch and roll to another ship's orientation in space
------------------------------------------------------------------
References: MVS4
  In order to understand the MVS4 routine, we need first to understand what it's
  for, so consider our Cobra Mk III sitting in deep space, minding its own
  business, when an enemy ship appears in the distance. Inside the little
  bubble of universe that Elite creates to simulate this scenario, our ship is
  at the origin (0, 0, 0), and the enemy ship has just popped into existence at
  (x, y, z), where the x-axis is to our right, the y-axis is up, and the z-axis
  is in the direction our Cobra is pointing in.
  
  Of course, our first thought is to pitch and roll our Cobra to get the new
  arrival firmly into the crosshairs, and in doing this the enemy ship will
  appear to move in space, relative to us. For example, if we do a pitch by
  pulling back on the joystick or pressing "X", this will pull the nose of our
  Cobra Mk III up, and the point (x, y, z) will appear to move down in the sky
  in front of us.
  
  So this routine calculates the movement of the enemy ship in space when we
  pitch and roll, as then the game can show the ship on-screen and work out
  whether our lasers are pointing in the correct direction to unleash fiery
  death on the pirate/cop/innocent trader in our sights.
  
  Pitch and roll
  --------------
  To make it easier to work with the 3D rotations of pitching and rolling, we
  break down the movement into two separate rotations, the roll and the pitch,
  and we apply one of them first, and then the other (in Elite, we do the roll
  first, and then the pitch).
  
  So let's look at the first one: the roll. Imagine we're sitting in our
  spaceship and do a roll to the right by pressing ">". From our perspective
  this is the same as the universe doing a roll to the left, so if we're
  looking out of the front of our ship, and there's a stationary enemy ship at
  (x, y, z), then rolling by an angle of a will look something like this:
  
    y
  
    ^         (x´, y´, z´)
    |       /
    |      /    <-.
    |     /       a`.
    |    /          |
    |   /
    |  /              __ (x, y, z)
    | /       __..--''
    |/__..--''
    +-----------------------> x
  
  So the enemy ship will move from (x, y, z) to (x´, y´, z´) in our little
  bubble of universe. Moreover, because the enemy ship is stationary, rolling
  our ship won't change the enemy ship's z-coordinate - it will always be the
  same distance in front of us, however far we roll. So we know that z´ = z,
  but how do we calculate x´ and y´?
  
  First, let's ditch the z-coordinate, as we know this doesn't change. This
  leaves us with a 2D rotation to consider; we are effectively only interested
  in what happens in the 2D plane at distance z in front of our ship (imagine a
  cinema screen at distance z, and that's what we're about to draw graphs on).
  
  Now, let's look at the triangle formed by the original (x, y) point:
  
    ^
    |
    |
    |
    |
    |
    |         h       __ (x, y)
    |         __..--''  |
    | __..--''    t     | <------- y
    +----------------------->
         <---- x ---->
  
  In this triangle, let's call the angle at the origin t and the hypotenuse h,
  and we already know the adjacent side is x and the opposite side is y. If we
  plug these into the equations for sine and cosine, we get:
  
    cos t = adjacent / hypotenuse = x / h
    sin t = opposite / hypotenuse = y / h
  
  which gives us the following when we multiply both sides by h:
  
    x = h * cos(t)
    y = h * sin(t)
  
  (We could use Pythagoras to calculate h from x and y, but we don't need to -
  you'll see why in a minute.)
  
  Now let's look at the 2D triangle formed by the new, post-roll (x´, y´)
  point:
  
    ^         (x´, y´)
    |       /|
    |      / |
    |     /  |
    |  h /   |
    |   /    | <------- y´
    |  /     |
    | /      |
    |/ t+a   |
    +----------------------->
    <-- x´ -->
  
  In this triangle, the angle is now t + a (as we have rolled left by an angle
  of a), the hypotenuse is still h (because we're rotating around the origin),
  the adjacent is x´ and the opposite is y´. If we plug these into the
  equations for sine and cosine, we get:
  
   cos(t + a) = adjacent / hypotenuse = x´ / h
   sin(t + a) = opposite / hypotenuse = y´ / h
  
  which gives us the following when we multiply both sides by h:
  
    x´ = h * cos(t + a)                                   (i)
    y´ = h * sin(t + a)                                   (ii)
  
  We can expand these using the standard trigonometric formulae for compound
  angles, like this:
  
    x´ = h * cos(t + a)                                   (i)
       = h * (cos(t) * cos(a) - * sin(t) * sin(a))
       = h * cos(t) * cos(a) - h * sin(t) * sin(a)        (iii)
  
    y´ = h * sin(t + a)                                   (ii)
       = h * (sin(t) * cos(a) + cos(t) * sin(a))
       = h * sin(t) * cos(a) + h * cos(t) * sin(a)        (iv)
  
  and finally we can substitute the values of x and y that we calculated from
  the first triangle above:
  
    x´ = h * cos(t) * cos(a) - h * sin(t) * sin(a)        (iii)
       = x * cos(a) - y * sin(a)
  
    y´ = h * sin(t) * cos(a) + h * cos(t) * sin(a)        (iv)
       = y * cos(a) + x * sin(a)
  
  So, to summarise, if we do a roll of angle a, then the ship at (x, y, z) will
  move to (x´, y´, z´), where:
  
    x´ = x * cos(a) - y * sin(a)
    y´ = y * cos(a) + x * sin(a)
    z´ = z
  
  Transformation matrices
  -----------------------
  We can express the exact same thing in matrix form, like this:
  
    [  cos(a)  sin(a)  0 ]     [ x ]     [ x * cos(a) + y * sin(a) ]
    [ -sin(a)  cos(a)  0 ]  x  [ y ]  =  [ y * cos(a) - x * sin(a) ]
    [    0       0     1 ]     [ z ]     [            z            ]
  
  The matrix on the left is therefore the transformation matrix for rolling
  through an angle a.
  
  We can apply the exact same process to the pitch rotation, which gives us a
  transformation matrix for pitching through an angle b, as follows:
  
    [ 1    0        0    ]     [ x ]     [            x            ]
    [ 0  cos(b)  -sin(b) ]  x  [ y ]  =  [ y * cos(b) - z * sin(a) ]
    [ 0  sin(b)   cos(b) ]     [ z ]     [ y * sin(b) + z * cos(b) ]
  
  Finally, we can multiply these two rotation matrices together to get a
  transformation matrix that applies roll and then pitch in one go:
  
    [       cos(a)           sin(a)         0    ]     [ x ]
    [ -sin(a) * cos(b)  cos(a) * cos(b)  -sin(b) ]  x  [ y ]
    [ -sin(a) * sin(b)  cos(a) * sin(b)   cos(b) ]     [ z ]
  
  So, to move our enemy ship in space when we pitch and roll, we simply need
  to do this matrix multiplication. In 6502 assembly language. In a very small
  memory footprint. Oh, and it needs to be quick, too, because we're going to
  be using this routine a lot. Got that?
  
  Small angle approximation
  -------------------------
  Luckily we can simplify the maths considerably by applying the "small angle
  approximation". This states that for small angles in radians, the following
  approximations hold true:
  
    sin a ~= a
    cos a ~= 1 - (a^2 / 2) ~= 1
    tan a ~= a
  
  These approximations make sense when you look at the triangle geometry that
  is used to show the ratios of trigonometry, and imagine what happens when the
  angle gets small; for example, cosine is defined as the adjacent over the
  hypotenuse, and as the angle tends to 0, the hypotenuse "hinges" down on top
  of the adjacent, so it's intuitive that cos a tends to 1 for small angles.
  
  The approximations above state that cos a approximates to 1 - (a^2 / 2), but
  Elite actually uses cos a ~= 1 and corrects for the inaccuracy by regularly
  calling the TIDY routine to. So dropping the small angle approximations into
  our rotation calculation above gives the following, much simpler version:
  
    [  1   a   0 ]     [ x ]     [    x + ay     ]
    [ -a   1  -b ]  x  [ y ]  =  [ y - ax  - bz  ]
    [ -ab  b   1 ]     [ z ]     [ z + b(y - ax) ]
  
  So to move rotate a point (x, y, z) around the origin (the centre of our
  ship) by the current pitch and roll angles (alpha and beta), we just need to
  calculate these three relatively simple equations:
  
    x -> x + alpha * y
    y -> y - alpha * x - beta * z
    z -> z + beta * (y - alpha * x)
  
  There's a fascinating document on Ian Bell's Elite website that shows this
  exact calculation, in the author's own handwritten notes for the game. You
  can see it in the third image here:
  
    http://www.elitehomepage.org/design/
  
  just below the original design for the cockpit, before the iconic 3D scanner
  was added (which is a whole other story...).
  
  Minsky circles
  --------------
  So that's what this routine does... it transforms x, y and z when we roll and
  pitch. But there is a twist. Let's write the transformation equations as you
  might write them in code (and, indeed this is how the routine itself is
  structured).
  
  First, we do the roll calculations:
  
    y = y - alpha * x
    x = x + alpha * y
  
  and then we do the pitch calculations:
  
    y = y - beta * z
    z = z + beta * y
  
  At first glance this code looks the same as the matrix calculation above, but
  then you notice that the value of y used in the calculations of x and z is not
  the original value of y, but the updated value of y. In fact, the above code
  actually does the following transformation of (x, y, z):
  
    x -> x + alpha * (y - alpha * x)
    y -> y - alpha * x - beta * z
    z -> z + beta * (y - alpha * x - beta * z)
  
  Oops, that isn't what we wanted to calculate... except this version turns out
  to do a better job than our original matrix multiplication above. This new
  version, where we reuse the updated y in the calculations of x and z instead
  of the original y, was "invented by mistake when [Marvin Minsky] tried to save
  one register in a display hack", and inadvertently discovered a way to rotate
  points within a pretty good approximation of a circle without using complex
  maths. The method appeared as item 149 in the 1972 HAKMEM memo, and if that
  doesn't mean anything to you, see if you can take the time to look it up.
  It's worth the effort if you're interested in this kind of thing (and you're
  the one reading a commentary on 8-bit code from 1984, so I'm guessing this
  might include you).
  
  Anyway, the rotation in Minsky's method doesn't describe a perfect circle,
  but instead it follows a slightly sheared ellipse, but that's close enough
  for 8-bit space combat in 192 x 256 pixels. So, coming back to the Elite
  source code, the MVS4 routine implements the rotation like this (shown
  here for the nosev orientation vectors, i.e. nosev_x, nosev_y and nosev_z):
  
  Roll calculations:
  
    nosev_y = nosev_y - alpha * nosev_x_hi
    nosev_x = nosev_x + alpha * nosev_y_hi
  
  Pitch calculations:
  
    nosev_y = nosev_y - beta * nosev_z_hi
    nosev_z = nosev_z + beta * nosev_y_hi
  
  And that's how we rotate a point around the origin by pitch alpha and roll
  beta, using the small angle approximation to make the maths easier, and
  incorporating the Minsky circle algorithm to make the rotation more stable.