Angles, directions, and their binary representation

Something that probably every game developer has worked with at one time or another – and some of us might work with it daily – is angles.

Angles are used to represent directions and rotations and especially in 2D they are an easy way of doing so, since only a single number is needed to represent an orientation.

In 3D we need three angles – pitch, yaw and roll -, making it slightly more complicated.

In this post I want to explore the way we represent the concepts of angle, direction, orientation and rotation.

We will:

  • look at how these concepts are commonly represented in code;
  • point out some flaws with the representation;
  • explore the semantic differences – if any – between the concepts, both from a mathematical and a geometric point of view;
  • propose a better solution based on semantic requirements, translating them into a suitable binary representation.

For the purpose of this post we will only look at single angles in the 2D plane.

The straight forward implementation.

Usually we represent angles in radians, using floating point numbers.

On the surface this looks like a great solution:

Floating point arithmetic is very fast, supported by virtually any hardware, and has a huge range of possible values. Further, low level trigonometric functions typically take and return floating point numbers.

However, this approach also has some problems.

Wrapping

A common one is wrapping. If we use an angle to represent an orientation – for example the direction a character is facing in – only angles between 0 and 360 degrees are meaningful.

In fact the angles of 0 and 360 degrees are in this case functionally identical. In the general case any two angles a and b with values of a = b + 360 * n – n being any integer – are equivalent here.

This may not be a problem for all applications, for example calculating the vector along the direction using the sine and cosine of the value will return the correct result.

However, there is no trivial way of getting the angle between two such orientations. After subtracting the two values, we have to check if the value is outside the range of [-180, 180] and if so, find the equivalent angle inside that interval (using the same equivalence relation as just mentioned).

If we forget doing this, the results may be objects spinning the wrong way, or more than a full rotation to assume a desired orientation.

Floating point (in)accuracy

Another problem may result from the inherent nature of binary floating point representations. Floats have a given number of accurate digits and use an exponential multiplier to shift between low and high ranges.

Under most circumstances this is great.

When working with angles however, we may only want to represent angles in the range [0, 360] or [-180, 180].

In that case, we waste a lot of the possible range of our floating points number, and the distribution of accuracy is shifted very much to the numerically smaller values.

However, if we think of directions it makes little sense to represent certain ranges of directions with higher accuracy than others.

Represented Range

Speaking of ranges, should directions be represented as values between 0 and 360, or between -180 and 180 degrees?

Both can be useful for some application. However, converting between them requires a branch (an if statement), which is generally not ideal in low-level code.

Further we always need to keep track of which representation we are using, and make sure to enforce it manually to not get undesired results.

Also, can rotations – think of angular velocities – now have values outside of this range?

If we use the same data type – floats – for all these, we are bound to run into trouble. I certainly have had the strangest bugs resulting from not handling these issues properly

What is going on here?

I hope the above the above has convinced you that there are at least a few issues that we have to keep in mind when working with angles.

But what is really going on here? Why do we have these problems in the first place?

The causes of these issues are twofold:

  1. We are confusing two different things: relative angles and absolute directions;
  2. We use a data type without semantics to represent values with very strong semantics and special properties.

1. Angles vs. Directions

The difference between what I will call angles and directions from now on can be expressed in both geometric and mathematical terms:

Mathematically, a direction is a set with elements semantically corresponding to the (half-open) interval of [0, 360[ degrees or the points on a circle.

Geometrically, a direction is an absolute direction or orientation in the 2D plane, given a fixed reference frame (a zero direction).

Mathematically, an angle is a 1D vector space with naturally defined addition, subtraction and scalar multiplication.

Geometrically, an angle is the difference between two directions. As such it can also represent a rotation from one direction to another.

Note how in terms of operations on elements of these two sets, we have those inherent to the vector space of angles, but none within the set of directions.

We do however have at least one operation between two directions obtaining the angle between them. This operation can seemingly be inverted by adding an angle to a direction to obtain another direction.

Note that because of the equivalence of directions pointed out above these two operations are not in fact inverses of each other. They are however inverses for a subset of angles.

Which subset this is depends on the exact definition of the operation between two directions. As we will see below there are multiple valid definitions.

For completeness, be aware that while the set of directions seems to have a limited range, and the set of angles seems infinite, both have the same cardinality (specifically |ℝ|, the cardinality of the continuum).

2. Data type

With angles being a one dimensional vector space as described above, representing them using floating point numbers makes sense.

We could argue that using the same data type for angles and scalars is somewhat dubious, but we will not do so in this post.

That being said, we will create a custom type for our angles to enforce type-safe and unambiguous usage below.

What we are more concerned with is the special nature of directions. As described, they have very distinct properties which are only badly represented by a floating point number.

The type we will create to represent directions is the main content of this post and we will next define the exact properties we want that type to have.

Requirements for a better Direction representation

Based on the semantics explained above, following are the requirements for an accurate representation of the direction concept:

  • Our representation has to handle the wrapping, or equivalence relation of directions;
  • Directions and angles should be distinct and not be confused easily;
  • We would like a variety of useful behaviour, like:
    • converting a direction into a directed vector and back,
    • getting the angle between two directions,
    • all the operations outlined above, both on the angle vector space, and between the sets of angles and vectors,
    • and possibly more…
  • Ideally our representation will be entirely type-safe, so that it cannot be abused implicitly.

In a more practical sense, we do not want to have to think about our underlying representation and its edge cases every time we use it, like we have to when using simple floating point numbers for both angles and directions.

For example, when implementing a homing effect for a projectile, we want to be able to write code that is obviously equivalent to the following pseudo code.

It should be easily readable and not require any extra checks.

Implementation

The key constraint for our representation is the wrapping behaviour.

In principle we could still use a floating point number to store the value internally and include checks within each of our custom operations.

While this seemingly prevents the problems discussed above, it comes at potentially significant loss of performance and also still wastes the large range of floating point representations.

Ideally we would use an binary representation that natively supports our basic requirements.

As it turns out, there is a data type that does: integers.

Integers exhibit overflow, where incrementing past their maximum value they wrap around to their minimum one, simply as a result of their binary representation. This is exactly the behaviour we are looking for.

This approach is by no means new.

In fact, in earlier days of game development this was the preferred way to handle directions. Also see this post by Shawn Hargreaves on the topic: Angles, integers, and modulo arithmetic.

That post includes a small function to convert a floating point number angle to a short (16 bit) integer. The trick is that we equate the angle 0 with the integer value 0, and the angle of 360 degrees with integer value 216.

Similarly, all angles in between are represented linearly by that range of integer values.

As it turns out, if we try to assign 216 to a short integer, it causes overflow and results in 0, which is exactly what we want.

In other words, we are (ab)using the modulo arithmetic inherent to the integer’s binary representation to enforce the directional equivalence classes.

Some objections

It may seem unintuitive to use an integer for a value – in this case a direction – that does not have discrete steps in reality. We want to be able to represent any angles, not just a fixed number of them.

However, floating point numbers also have a limited number of values they can represent. Especially when limited to a small range the exponent bits of the float are of little use to us, and we are left with the about seven decimal digits of accuracy of the float’s mantissa.

Using a short integer only gives us less than five decimal digits of accuracy. However, for most applications this is more than enough, and we can simply use a 32bit integer for nine decimal digits.

Additionally, using integers, our available values are distributed uniformly in the range of available directions, instead of being biased to low numerical values, as explained above.

Code

The basic code for our representation of directions is simple.
Note that all of the following snippets are (partly modified) excerpts from a full implementation which is freely available as part of the general C# utilities library Bearded.Utilities.
The full code can be found in the types Angle and Direction2 under src/Math.

Note that we use 32 bits of accuracy here. For most applications 16 bits might be more than enough, and we could make an argument that smaller types are good for binary serialisation, for example to send them over the network.

However, unless there are specific constraints, 32 bits is a safe bet.

We can further use the following methods to convert between directional vectors and directions.

Below follows the basic type that we will use to represent angles.

We then add the following operator overloads to our direction type, to be able to determine the difference angle between two directions, and to add a direction to an angle. This is where the integer representation shows its advantages.

With this setup we can implement a TurnedTowards method that turns a direction towards another one with a given maximum step.

For what this method does, it is very short and concise. Taking advantage of our integer representation it also needs no extra checks for wrapping and almost trivially returns the correct result.

Note that the full implementation is even more concise by using more custom operators and methods.

The Result

Using the custom types we just constructed, the example pseudo code from above can be implemented as follows.

This code clearly shows our intend and reads virtually the same as our pseudo code.

We need no extra checks – neither in this code or in the underlying calls – and while I am using the var keyword for brevity, out code is entirely type-safe and semantically corresponds with what we try to express with it.

Disadvantages

I am sure the above makes it clear that I am a strong proponent of this approach. Next to handling the wrapping of directions, I consider the type-safety one of its strongest features.

There are however possible disadvantages as well.

For one, types like these have to be used rigorously to make them truly worth while. Converting between safe and unsafe generic types a lot can easily result in bloat and make the relevant code less clear.

Secondly, as the above snippets show, this approach requires for casting between integers and floats for many operations. While this is a very fast conversion, it can add up and result in code that may run significantly slower.

For most applications the latter should not matter. However, for performance-critical code, careful measurements should be performed for whether the lack of wrapping checks outweighs the many casts.

Unless a negative impact on performance can be determined, I consider this possible trade-off worthwhile however.

To me, the increased readability and type-safety elevate this approach over the simpler usage of floats.

Conclusion

I would like to believe that the above makes a good case for the described approach.

Please let me know what you think in the comments.

Especially if you have experience with this kind of representation and/or you have arguments for or against it that I did not mention above, feel free to share them below.

If you are interested in a more complete implementation with a large number of additional features, make sure to check out the Angle and Direction2 types in Bearded.Utilities.Math.

That code is published under the MIT license, so feel free to do with it as you please.

Enjoy the pixels!

Leave a Reply