Crate cube_rotations

Source
Expand description

§Introduction

This crate serves to model and solve the following couple of problems:

  1. How can we model all the possible rotations that can happen to a cube, that leave all its edges parallel to the same axes as before?

  2. How many and which points must we place on this cube’s surface such that a) they are absolutely symmetric according to the previous rotations, and b) they have absolutely no mirror symmetry? In other words, how can we make sure that the cube will look the same from every possible orientation, while being different than its mirror image?

This is known as octahedral symmetry in the available literature. The linked article does contain an explanation, but this documentation aims to be a smidge more accessible.

§Initial approach and restrictions

Let there be a cube centred around the origin, with an edge-length of 6; the criterion for the length will shortly become apparent. The vertices of this cube are the eight points [±3, ±3, ±3].

Our first order of business, obviously, is to place one point on some face of this cube. Its faces are the set of points whose maximum coördinate by absolute value is equal to 3. Thus, it immediately follows that all coördinates must be between -3 and 3 inclusive.

The next thing to do is to ensure that, if the cube is reflected along one of its planes of symmetry, no point will coincide with itself. Thus, the question is raised: What is the effect that a reflection has on the coördinates of a point?

The answer: If the plane if symmetry is horizontal or vertical, it negates one of the coördinates. If it is diagonal, it swaps the values of two coördinates.

With that in mind, we immediately arrive at two fundamental restrictions: no coördinate can be zero, or else negating it would not change it; and no coördinate can be equal to another, or else swapping them would change nothing.

§Encoding the transforms

Next question: What do rotations do to a point’s coördinates? And the answer is that each even amount of reflections corresponds to a rotation1. In other words, each rotation can be decomposed to an even amount of negations and swaps.

This immediately answers both our questions. 3 coördinates can be ordered in 6 different ways in total, and their possible combinations of signs are 8. Thus, the possible transformations are 6×8 = 48 in total: 24 of them are rotations, and the other 24 are so-called improper rotations or rotoreflections.

Apart from that, for each complete transformation, each elementary reflection that comprises it needs only occur once, and they can always be examined in the same order. This permits us to encode, in just 1 bit, the application-or-not of each one of them, and thus fit all possible transformations within 6 bits. Of those, the rotations can be discerned by the fact that their binary representation will have an even amount of ones.

§Encoding coördinates

With regards to the encoding of the coördinates themselves, the choice of 6 for the size of the cube permits us to use integers for all 3 coördinates: ±1, ±2, ±3. By choosing a specific order and signs, each of the 48 possible combinations can be found.

It is noteworthy that, if we assume one point to be a reference, ([1, 2, 3] in our case,) every other point can be found by applying one of those transformations –a different one each time– on it. This has the extremely useful property that it permits us to encode transformations and points in the exact same way. It also immediately separates those 48 possible points into two groups of 24: [1, 2, 3] and its possible rotations, and [3, 2, 1] and its possible rotations. Each point belonging to one of those groups can, with some suitable rotation, be made to coincide with any other point of the same group; however, it is impossible for a rotation to make it coincide with a point from the other group. Thus, each of those two groups can comprise the solution to our original question.

Of note: since each transformation retains the absolute values of the coördinates of each point, their exact values are not important. The point [-400, 0.5, 14] can be considered to be in [-3, 1, 2] and all operations remain correct.

§Nomenclature

In the rest of the documentation, each point is called a “CubeSurfacePoint”, and each set of operations on it (swaps and/or sign flips) is called a “Transformation” or a “Rotation”. The point [1, 2, 3] as also commonly called a Reference Point, because we judge all transformations relative to it.

In the documentation, the two possible groups of 24 points are called Geometric Groups. They are sometimes distinguished into the Reference Geometric Group, ie the Point of Reference and the points in the same group as it, and the Opposite Geometric Group, ie the mirror image of the Reference Geometric Group.

The afore-mentioned reflections to which each of the 6 bits corresponds (ie, swapping the value of two coördinates or negating one of them) are collectively referred to as Elementary Reflections.

§Using the crate

Let there be three points on a cube, x, y, and z.

let x = NegThreePosOnePosTwo;
let y = PosTwoPosThreeNegOne;
let z = PosThreePosOneNegTwo;

We eventually realise that x’s actual orientation is different:

let x_actual = PosThreePosTwoPosOne;

We want our cube to be rotated in such a way, that x ends up coïnciding with x_actual. That means that each of those points has to be rotated in the exact same way.

To calculate the rotation, it suffices to perform one division: rotation = x_actual / x. Afterwards, the operations r * x, r * y, and r * z give us the results we want. Please note that the operation (x_actual / x) * x gives just x_actual, exactly as one would suppose from the notation.

let rotation = x_actual / x;

Here is the complete code, including validation of results:

let x = NegThreePosOnePosTwo;
let y = PosTwoPosThreeNegOne;
let z = PosThreePosOneNegTwo;

let x_actual = PosThreePosTwoPosOne;

let rotation = x_actual / x;

assert_eq!(rotation * x, PosThreePosTwoPosOne);
assert_eq!(rotation * y, NegTwoNegOnePosThree);
assert_eq!(rotation * z, NegThreeNegTwoPosOne);

§Implementation details

This crate was implemented with the following criteria, in descending order of importance:

  1. Correct structuring of API
  2. Serving as a proof-of-concept
  3. Needing as little memory as possible (RAM + program memory)
  4. Performance

Performance is last as, for the use-case for which this crate was implemented, those calculations are far outside of the critical path.

§Safety and panics

Despite this code using unsafe internally, running cargo build successfully is enough to guarantee the complete absence of panics or undefined behaviour –henceforth “UB”– in this code. This is thanks to the following properties:

  • All functions are pure, ie stateless: this permits them to all be const. Additionally, no function has more than 2304 possible inputs. This means that all of them can be checked exhaustively in a relatively short amount of time, even under miri.
  • All panics/unsafety in this crate have been corralled into one function, unreachable_semichecked. In debug mode, it panics; in release mode, it’s UB; and it is the only function in the entire code-base that is permitted to do either of those things. As a result, as long as it remains indeed unreachable, the entire code-base is free from both panics and UB.
  • Each function has a corresponding one that operates using a Look-Up Table— henceforth “LUT”. The LUT is populated at compile-time by calling the corresponding const function iteratively, and exhaustively. This means that every function ends up being called with every possible input during compilation: in other words, every possible code-path gets activated at compile-time. (A funny result of this is that the code builds faster with --release than without it.)
  • As a combination of the above, any possible code-path leading to the unreachable_semichecked function will indeed call it during compile-time, resulting in a compilation error as long as debug assertions are enabled. Thus, the absence of compilation errors suffices to prove the complete absence of panics or UB in the entire code-base.
  • Lastly, as a bonus: The test suite is so comprehensive that, as long as it is intact, even a purposeful sabotage of the crate would struggle to cause serious damage without test-breakage.

That said, this crate has also been annotated with the following attribute:

#![cfg_attr(debug_assertions, forbid(unsafe_code))]

Thus, any down-stream user that prefers to forbid unsafe code entirely can do so by including the following snippet in their Cargo.toml file:

[profile.dev.package.cube-rotations]
debug-assertions = true

This, of course, opens the door for some missed optimisations. If there is any way to achieve both of those things, either through regular compiler optimisations or through PGO, that has not been investigated as of yet.

§Look-up tables and proper rotations

The most basic and most broadly applicable data-types contained herein are CubeSurfacePoint and Rotation. They can be used to model all relevant operations, but offer no particular guarantees.

Each of those two data-types is further split into two equally-sized, compementary sub-sets, each offering a particular geometric guarantee. Further, all of those 3 point-types also have wrapper data-types that operate using look-up tables. In turn, all 7 of the point data-types are generalised in the OctahedrallySymmetricPoint trait.

The full list is as follows:

The Geometric-Group-specific data-types of the luts module only operate using big LUTs, for reasons further analysed in their documentation.

  1. This is a general property of geometry, irrespective of amount of dimensions or possibly even Euclideanness. ↩

Modules§

luts
A module containing wrapper data-types whose calculations are performed using Look-Up Tables.

Structs§

ImproperRotation
As per a Rotation, but one that specifically needs at least one reflection.
ProperRotation
As per a Rotation, but one that specifically needs no reflections.
Rotation
A data-type that describes, within 6 bits, the transformation from one CubeSurfacePoint to another.

Enums§

CubeSurfacePoint
Encodes the 48 possible points in space whose coördinates, in ascending order of absolute value, are equal to [1, 2, 3].
Direction
Describes towards which direction the face of a cube is oriented.
OppositeGroupPoint
The set of CubeSurfacePoints that can be made to coincide with the Reference Point using just one improper rotation.
ReferenceGroupPoint
The set of CubeSurfacePoints that can be made to coincide with the Reference Point using just one proper rotation.

Traits§

OctahedrallySymmetricPoint
A trait that groups the common behaviour of all possible data-types that represent points on the surface of a cube.