Working out the longest side with just one lookup and one multiplication
When converting between angles and coordinates, we often need to calculate the length of the hypotenuse. For example, when we convert Cartesian coordinates into angles as described in the deep dive on converting coordinates to angles, we first calculate the yaw angle along the ground, using the triangle formed from the x-coordinate and z-coordinate as the two orthogonal sides; the angle of the hypotenuse gives us the yaw angle. We then calculate the pitch angle from the vertical triangle that's formed from the hypotenuse of the first triangle as the adjacent side, and with the y-coordinate as the opposite side.
To do this calculation we therefore need to calculate the length of the hypotenuse of the first triangle so we can then use that as the adjacent length in the second triangle. Here's our triangle:
+
|`.
|t `.
| `. h
a | `.
| `.
| `.
+------------`+
b
The traditional method is to use Pythagoras like this, where a and b are the adjacent and opposite sides of the triangle:
h = SQRT(a^2 + b^2)
It's possible to code this up in 6502 assembly language, and Elite does exactly this, for example. But to save time, The Sentinel implements a very clever algorithm in the GetHypotenuse routine that calculates an approximate hypotenuse from the angle and the two triangle sides using just one lookup and one multiplication. By this stage in the conversion process we've already calculated the angle, so this is a lot quicker than using two multiplications and a square root.
The calculation of the approximate hypotenuse h for a triangle with angle theta, adjacent side a and opposite side b is as follows:
h =~ a + tan(theta / 2) * b
Here's how the calculation of h works. We take the triangle that we want to analyse:
+
|`.
|t `.
| `.
| `.
| `.
| `. h
| `.
a | `.
| `.
| `.
| `.
| `.
| `.
+--------------------------+
and split up the hypotenuse into two parts, one part being the length of the adjacent side (a) and the other part an unknown length (c):
+
|`.
|t `.
| `.
| `. a
| `.
| `.
| `.
a | `.
| `.
| __`.´
| __--´ `.
| __--´ `. c
| __--´ `.
+´-------------------------+
This gives us the following:
h = a + c
We already know a, so our mission is to calculate c.
To do this, let's examine the two triangles that we now have. Here's the top triangle, which is an isosceles triangle with two sides of length a, an angle of theta (t) and two equal angles that we can call phi (p):
+
|`.
|t `.
| `.
a | `. a
| `.
| `.
| `.
| `.
| p `.
| __`+
| __--´
| p __--´
| __--´
+´
Because the angles in a triangle always add up to 180 degrees, we get the following:
180 - theta
phi = ----------- = 90 - (theta / 2)
2
And here's the lower triangle, which has the opposite side of length b along the bottom, and our unknown length c. Because the sides of length a and b form a right-angled triangle, we can calculate the angle on the left of the second triangle as 90 - phi, as follows:
__.+
__--´ `.
__--´ c `.
__--´ 90-p `.
+´-------------------------+
b
Combining the two angle calculations, we get:
90 - phi = 90 - (90 - (theta / 2))
= theta / 2
We now introduce our approximation, by converting the second triangle into a right-angled triangle like this:
+
__--´|
__.+´ |
__--´ `. | c´
__--´ c `. |
__--´ t/2 `.|
+´-------------------------+
b
If we can calculate c´ then it's not going to be far off the value of c, particularly for small values of theta, so that's what we do now. Our new right-angled triangle gives us this:
tan(theta / 2) = c´ / b
So:
c´ = b * tan(theta / 2)
So:
h = a + c
=~ a + c´
= a + b * tan(theta / 2)
If we implement the tan(theta / 2) part with a lookup, then we will have an approximation for the hypotenuse using just one lookup and one multiplication, as required.
The tanHalfAngle table implements the lookup. However, instead of taking the angle theta as the lookup index, the table actually uses the tangent of the angle, X = tan(theta), as the index. This is because we already have this value calculated whenever we call the GetHypotenuse routine, so it's more efficient to use this than the angle itself.
So the tanHalfAngle table contains the following at index X:
tanHalfAngle+X = 2 * tan(arctan(X) / 2)
which is implemented by this loop:
EQUB 0 FOR I%, 1, 128 EQUB INT(0.5 + 2 * 256 * TAN(ATN(I% / 128) / 2)) NEXT
So is we use X = tan(theta) as the index, we get the result:
tanHalfAngle+X = 2 * tan(arctan(X) / 2)
= 2 * tan(arctan(tan(theta)) / 2)
= 2 * tan(theta / 2)
The table contains lookup values for indexes 0 to 128, which correspond to theta angles of 0 to 45 degrees.
So that's how we can approximate the hypotenuse for angle theta and triangle sides a and b using just one lookup and one multiplication.