A look at the various ways in which The Sentinel implements trigonometry
Trigonometry is a fundamental requirement for any game that works with 3D graphics, and The Sentinel is no exception. Modern computers come with all sorts of sophisticated libraries and graphics engines that manage these calculations for us, but on machines like the BBC Micro, the challenge is how to implement accurate trigonometric functions in 8-bit assembly language, given that the CPU only supports integers from 0 to 255, and only includes instructions for addition, subtraction and bitwise shifting.
The Sentinel uses a number of techniques to get around these limitations. Quite a few of these are taken directly from Geoff Crammond's previous game Revs, which you can read all about in the deep dive on reusing the geometry routines from Revs. As for the routines themselves, let's take a look at the details.
Pitch and yaw lookup tables
---------------------------
The simplest method for implementing trigonometric functions in assembly code is to use lookup tables that contain pre-calculated values. For example, The Sentinel contains two lookup tables that are used by the pitch and yaw angle routines, one for calculating arctangent, and the other for calculating sine and cosine.
The tables used in calculating pitch and yaw angles are as follows:
- arctan(Hi Lo) is used by the GetAngleFromCoords routine to calculate the yaw angle as an arctangent when converting a 3D Cartesian vector into pitch and yaw angles.
- sin is used by the GetSineAndCosine routine when calculating the view-relative pitch and yaw angles of all the points in an object.
Taking the second example, the table at sin contains the following values:
FOR I%, 0, 127 EQUB INT(0.5 + 256 * SIN((I% / 128) * (PI / 2))) NEXT
This table contains sine values for a quarter of a circle, i.e. for the range 0 to 90 degrees, or 0 to PI/2 radians. The table contains values for indexes 0 to 127, which cover the quarter from 0 to PI/2 radians. Entry X in the table is therefore (X / 128) * (PI / 2) radians of the way round the quarter circle, so the table at index X contains the sine of this value.
The value of sine across the quarter circle ranges from 0 to 1:
- sin(0) = 0
- sin(90) = sin(PI/2) = 1
It might help to think of sin(X) as an integer ranging from 0 to 256 across the quarter circle, so entry X in this table contains sin(X) * 256, where X ranges from 0 to 128 over the course of a quarter circle.
So the table contains sine values for a quarter-circle, and we can use this to work out the values of sine and cosine for the entire circle using the trigonometric identities described at the end of this article.
For more information on how the GetAngleFromCoords routine uses the arctan lookup, see the deep dives on converting angles to coordinates and converting coordinates to angles.
Approximating PI
----------------
Lookup tables are useful, but they do take up a fair amount of memory, and on the unexpanded BBC Micro, memory is at a premium (see The Sentinel memory map to see just how tight things are). To avoid this problem, the game also implements mathematical trigonometric functions that calculate the values of sine and cosine, rather than simply looking them up in a table.
In order to understand these, we need to talk about PI. Most mathematical algorithms for calculating trigonometric functions operate on radians rather than degrees - even the lookup tables above use radians. We humans tend to think in degrees, where a full circle is 360 degrees, and a quarter circle is 90 degrees, but if we're to create efficient 8-bit trigonometry, we need to think of a circle as 2 * PI radians, and a quarter circle as PI/2 radians.
So how do we represent PI in our world of 8-bit integers? Well, we can use multi-byte numbers to store floating point numbers by simply interpreting their contents differently. Consider the 16-bit number x(Hi Lo). We can consider this to represent two different numbers:
- An integer, in which case the value of the integer is xHi * 256 + xLo
- A floating point number, in which case the value of the floating point number is (xHi * 256 + xLo) / 256
This is purely a difference of interpretation: the 16-bit number x(Hi Lo) doesn't change, just our perception of it. In the latter case, the fractional part is stored in the low byte and the integer part in the high byte, but operations like addition and subtraction still work in the same way.
Given this, we can consider how to store the value of PI, which is around 3.14. PI * 256 is around 804.25, so if we store a value of 804 in a 16-bit number, and consider it to be a floating point number, then we have a value of PI that we can work with. Or, to put it another way, the following are all equivalent:
pi(Hi Lo) = 804
= 3.140625 * 256
= 3.140625 * 2^8
= 3.140625 << 8
= (3 36)
It isn't exact, but defining PI as 3.140625 is more than good enough for our needs. Similarly, we have:
402 = PI/2 201 = PI/4
The last one is particularly useful, as 201 fits into one byte. You will often find that geometric calculations involve reducing the angle to fit within one-eighth of a circle (i.e. PI/4 radians, or 201), as then the angle will fit into one byte. Applying the calculations to one byte is simpler, and we can then use trigonometric identities to apply the result to the full angle (see below for more on this).
There's a good example of this in the GetAngleInRadians routine, which converts from the game's full angle range into a quarter-circle angle, using 201 to represent PI/4.
Taylor series approximation
---------------------------
So now that we can represent angles in radians, what can we do with them?
The best example is in part 2 of GetRotationMatrix, which calculates sin(yawRadians) for small angles. By this point, we have already reduced our angle to the range of a quarter circle by calling the GetAngleInRadians routine, so "small angle" in this context means an angle in the range 0 to 121, i.e. 0 to 42.5 degrees (see the next section to see how we cope with "large angles", i.e. those in the range 122 to 255).
For these small angles, we can use what's known as the "Taylor series" to calculate the sine of the angle. The Taylor series is a way of expressing trigonometric functions as infinite sums, such as this one for sin(x), where x is in radians:
x^3 x^5 x^7
sin(x) = x - --- + --- - --- + ...
3! 5! 7!
In this, x! (or "x factorial") is equal to x * (x - 1) * (x - 2) * ... * 1, so 3! = 3 * 2 * 1 = 6, for example. See the Wikipedia entry on the Taylor series for more details on the Taylor series and how it can be used to calculate all sorts of trigonometric values.
Because the components in the above sum get smaller and smaller as the various factorials increase, we can approximate the value of sin(x) by doing just the first few calculations. The Sentinel uses this technique in GetRotationMatrix, where for small values of yawRadians, it calculates the following:
(yawRadians / 2 - (171 / 256) * (yawRadians / 2) ^ 3) * 2
Given that we have multiplication routines in Multiply8x8 and Multiply8x16 that can handle the multiplications, and bitwise shifting that can handle the powers of two, the above is relatively easy to implement in 8-bit assembler. But what does it actually do? Let's break it down:
(yawRadians / 2 - (171 / 256) * (yawRadians / 2) ^ 3) * 2 = (yawRadians / 2 - 2/3 * (yawRadians / 2) ^ 3) * 2 = yawRadians - 4/3 * (yawRadians / 2) ^ 3 = yawRadians - 4/3 * yawRadians^3 / 2^3 = yawRadians - 8/6 * yawRadians^3 * 1/8 = yawRadians - 1/6 * yawRadians^3 = yawRadians - yawRadians^3 / 3!
The calculation is therefore equivalent to the first two terms in the Taylor series above, so the result is approximately equal to sin(yawRadians). So we have built an algorithm that can calculate the sine of a small angle in radians, without needing a memory-hungry lookup table.
Small angle approximation
-------------------------
The above calculation works fine for small values of yawRadians that don't overflow the 8-bit arithmetic, but for larger angles - i.e. those in the range 122 to 255, or 42.5 to 90 degrees - we need a different approach. In this case, we can use what is known as the "small angle approximation". Let's see how this fits into the algorithm in The Sentinel.
To calculate the sine of a larger angle, we calculate the following, which we do in part 3 of GetRotationMatrix:
(U T) = (PI/4 - yawRadians / 2) ^ 2 * 2
We implement PI/4 as the integer 201, as described above, and the rest is simple subtraction and bitwise shifting. So, what does this calculation mean? Let's expand it slightly:
(U T) = (PI/4 - yawRadians / 2) ^ 2 * 2
= ((PI/2 - yawRadians) / 2) ^ 2 * 2
If we define x = PI/2 - yawRadians, then we have:
(U T) = (x / 2) ^ 2 * 2
= ((x ^ 2) / (2 ^ 2)) * 2
= (x ^ 2) / 2
= (x ^ 2) / 2!
The small angle approximation (see Wikipedia for details) states that for small values of x, the following approximation holds true:
cos(x) =~ 1 - (x ^ 2) / 2!
As yawRadians is large, this means x is small (as x = PI/2 - yawRadians), so we can legitimately use the approximation. So substituting the value of (U T) above, we get:
cos(x) =~ 1 - (x ^ 2) / 2!
= 1 - (U T)
It's a trigonometric identity that:
cos(PI/2 - x) = sin(x)
so we have:
cos(x) = cos(PI/2 - yawRadians)
= sin(yawRadians)
and we already calculated that:
cos(x) =~ 1 - (U T)
so that means that:
sin(yawRadians) = cos(x)
=~ 1 - (U T)
=~ 1 - (PI/4 - yawRadians / 2) ^ 2 * 2
In other words, we just calculated the sine of a large angle, so along with the Taylor series algorithm for small angles that we described in the previous section, we now have a routine that can calculate the sine of an angle in radians, whether the angle is large or small.
Getting cos from sin
--------------------
The above routines calculate the sine of an angle, but we can use the same routines to calculate the cosine by manipulating the angle, calculating the sine, and then manipulating the result to get the cosine. There are a few trigonometric identities that we can use to support this approach:
sin(PI/2 - x) = cos(x) cos(PI/2 - x) = sin(x) cos(-x) = cos(x) sin(-x) = -sin(x) sin(PI - x) = sin(x) cos(PI - x) = -cos(x) sin(PI + x) = -sin(x) cos(PI + x) = -cos(x)
We've already seen how we can call the GetAngleInRadians routine to reduce the range of our angle to a quarter circle while converting it into radians, so this is the first step in part 1 of GetRotationMatrix. Once this is done, we can calculate the sine using part 2 or part 3 of GetRotationMatrix, as appropriate, and we can then apply the first two identities above in part 4, so we can loop back to calculate the cosine of the same angle.
On top of this, there is a bit more logic in part 5 that uses the other six identities above to extend the algorithm to angles greater than the quarter circle, and the result is a routine that can calculate sine and cosine for all angles.
This approach saves building multiple routines for sine and cosine, when simple manipulation of the angle and result means we can make do with only one routine, thus taking up less space while giving us the same results.
So, in summary, The Sentinel uses lookup tables for arctangent and sine, and it uses radians, the Taylor series, the small angle approximation and a number of trigonometric identities to calculate sine and cosine on-the-fly. It's quite the trigonometry toolbox...