The why of the how

I've used quaternions in the past to make some 3D rendering programs, most notably Graf (which I haven't worked on for months), and to be honest had no idea how they worked beyond the "classic" $ij = k$, $jj = -1$, $jk = -i$... Although today's project didn't deepen my understanding of quaternions to where I could recite the formula for get a quaternion from euler angles (yaw, pitch, roll), I got a ridiculous idea: what if we encode messages using your good ol' $w + ix + jy + kz$?

The main idea

Sooo... How do we do it? We create a list of rotations base Euler Angles with the Tait–Bryan convention(yaw, pitch, roll), we then associate a character to each of the rotations. In simple terms, it's like having an array of cubes uniquely rotation and paired with a character. I've made a visualization tool that helps you see the idea behind it.

Originally, I imagined this as a sphere of points: you would associate a unit vector $\overrightarrow{OM}$ for each rotation, and since a vector from the origin of the 3D space ($\vec 0_{\mathbb{R}^3}$) can be modeled as point you'd just draw a sphere of points. When creating the visualization tool, I realized a big flaw with this: you only need a rotation around two axis to make a sphere (and one in the 2D space). Since I was generating a rotation around 3 axis, I was losing a $1/3$ of the information my system was giving. That's why I ended up scrapping the whole point idea, it didn't change anything to my pre-existing code, just that my mental model was off by a bit. That gave us this interesting sphere of cubes, I spread them out of course or else they would've been in the same position! The 3D fancy visualization is just here to get you help a good grasp of the mathematical concepts behind it, the actual code behind it has no idea of that. I really want to emphasize the fact that the sphere is one way to visualize it, I experimented with different options and plan on adding more.

The actual program

I decided to make this in Haskell, as it is quite flexible, concise and well suited for these kinds of projects.

A few definitions

We first need to define the two important types: Quaternion and Vec3, defining them explicitely instead of using just tuples allows us to add type bounds.

1data Quaternion x = Quaternion x x x x deriving (Show)
2data Vec3 x = Vec3 x x x deriving (Show)

This defines two types that respectively have 4 and 3 elements of type x.

Operations

Vector3

We'll add a few operations to make operating on vectors of $\mathbb R^3$:

1-- Loosely compare to floating numbers by specfiying an `epsilon` value, a.k.a the max distance between the two numbers.
2almostEqual :: (RealFloat a) => a -> a -> a -> Bool
3almostEqual epsilon a b = abs (a - b) <= epsilon
4
5-- Applies `almostEqual` to the 3 components of `Vec3` respectively. 
6almostEqualVec3 :: (RealFloat a) => a -> Vec3 a -> Vec3 a -> Bool
7almostEqualVec3 epsilon (Vec3 y1 p1 r1) (Vec3 y2 p2 r2) =
8  almostEqual epsilon y1 y2
9    && almostEqual epsilon p1 p2
10    && almostEqual epsilon r1 r2

Quaternion

We don't actually need anything other than a function to get a rotation quaternion from a yaw, pitch, roll for quaternions (we'll implement that further down), but in case you might want to add a rotating cypher (which I'll cover at the end of the article), I thought I'd still include an example:

1mulq :: forall x. (Num x) => Quaternion x -> Quaternion x -> Quaternion x
2mulq (Quaternion w1 x1 y1 z1) (Quaternion w2 x2 y2 z2) = Quaternion (w1 * w2 - x1 * x2 - y1 * y2 - z1 * z2) (w1 * x2 + x1 * w2 + y1 * z2 - z1 * y2) (w1 * y2 - x1 * z2 + y1 * w2 + z1 * x2) (w1 * z2 + x1 * y2 - y1 * x2 + z1 * w2)

Generating the char map

We first define a way to generate an angle in the range $]-\pi/2; pi/2[$ based on an integer. It is expected for the integer to be in the range $[[1; 9]]$. This was initially do to exclude $\pi/2, -\pi/2$ which would've caused redundancy errors if we were using on 2 axis, but with 3 the issue wouldn't normally show up. Feel free to adjust at your will if you're following along. The actual values in the ranges limit how many characters you can encode but also require more float precision the higher you go.

1toangle :: forall x. (RealFloat x) => x -> x
2toangle x = x * (pi / 10) - pi / 2
3
4angles :: [Vec3 Double]
5angles = [Vec3 (toangle a) (toangle b) (toangle g) | a <- [1 .. 9], b <- [1 .. 9], g <- [1 .. 9]]

Defining the map

We then create a list of characters and zip it to the angles list to create the map.

1chars :: [Char]
2-- "Naive" approach
3chars = ['a' .. 'z'] ++ ['A' .. 'Z'] ++ ['0' .. '9'] ++ [' ', ',', '!', '?', '.'] ++ show [1.500]
4
5-- Easier to encode more characters
6chars = ['\0' .. '\800']
7
8charVecMap = zip angles chars

From Euler angles to Quaternions

I won't go into much detail about the actual formulas to getthe corresping quaternion from a 3D vector of Euler angles, you can read all about it here. I pretty much just rewrote their example in C++ to Haskell.

1qFromEuler :: forall x. (RealFloat x) => Vec3 x -> Quaternion x
2qFromEuler (Vec3 y p r) = Quaternion (cr * cp * cy + sr * sp * sy) (sr * cp * cy - cr * sp * sy) (cr * sp * cy + sr * cp * sy) (cr * cp * sy - sr * sp * cy)
3  where
4    cr = cos $ r / 2
5    sr = sin $ r / 2
6    cp = cos $ p / 2
7    sp = sin $ p / 2
8    cy = cos $ y / 2
9    sy = sin $ y / 2

Character to Quaternion map

We can then use our newly defined function to create a map that pairs a character and a quaternion:

1charQuatMap = map f charVecMap where f (v, c) = (qFromEuler v, c)

Finally encoding

After all these lines, we can finally encode a message:

1encodeMessage message = [quat | Just (quat, _) <- map findTuple message]
2  where
3    findTuple char = find (doesTupleMatch char) charQuatMap
4    doesTupleMatch target (_, c) = target == c

This may seem a bit verbose, so let me break it down to you:

• We define a function that takes a message as its argument
• It returns a list defined via a list comprehension
• Said list comprehension maps over the message's characters, finds a matching $(q, c) \in \mathbb H\text x \{\text{characters}\}$ pair, only returning its quaternion component (it skips any non matched characters).

The two other functions use the Haskell's magic with function composition to find a match. I encourage that you try to figure out how it works!

Let's run a simple program:

1main = do
2  let message = "Hey, there! These are a few symbols: $ {} [] () ²"
3  print $ encodeMessage message

How to decode

To decode the message, we do the opposite process, I won't detail everything here as it's quite redundant. We just follow the opposite step:

• Convert each quaternion of the message back to a vector
• For each vector try to find a matching on the map by loosely matching it (because of floating point precision limitations)
• You're done

Why not directly use the quaternion map?

Ideally, you'd only need the euler angles and chars as an input, having a quaternion input is really redundant. And yes while reusing the previously computed map completely works, here are a few counter arguments:

• It's much easier for us to reason on euler angles precision. You can say "I want to loosely compare my angles with a 0.001 radians precision", using quaternions it's much harder to think about!
• Rotating cyphers which I'll explain later are trivial to implement when convert back to euler angles, whereas as quaternions require multiplication. (They do avoid gimball lock though)
• Also this was mostly an overcomplication/excuse because I just really wanted to have it work back and forth :) (converting from Vec3s to Quaternions and vice versa)

So here's the implementation:

1vec3FromQuat :: forall t. (RealFloat t) => Quaternion t -> Vec3 t
2vec3FromQuat (Quaternion w x y z) = Vec3 (atan2 (2 * (w * z + x * y)) (1 - 2 * (y ^ 2 + z ^ 2))) (-(pi / 2) + 2 * atan2 (sqrt (1 + 2 * (w * y - x * z))) (sqrt (1 - 2 * (w * y - x * z)))) (atan2 (2 * (w * x + y * z)) (1 - 2 * (x ^ 2 + y ^ 2)))
3
4decodeMessage vecs = [c | Just (v, c) <- map f vecs]
5  where
6    f x = g $ vec3FromQuat x
7    g v = find (h v) charvecmap
8    h v1 (v2, c2) = almostEqualVec3 0.0001 v1 v2

To go further

What's really cool with this is that you have infinite possibilities to add complexity to your encoding/decoding program! You may add arbirtrary rules that can only be decoded if you know the alogrithm.

Rotating cyphers

So... What have I been "yapping" about with "rotating cyphers"? It's just a fancy term that probably doesn't mean much coming out my mouth but here's what I mean:

For each encoded character you can rotate the """sphere""" (basically offsetting all of the rotation) for each decoded character, or maybe for each odd number of characters. If you're feeling extra you may make it so if the encode character is a vowel you rotate everything by 12° on the z-axis, if it's a consonant 56° on the y-axis. This process can be reversed during the decoding phase which is why I call it a "rotating cypher" (bidirectionnal if you want).

Footnote

This really esoteric program that is basically a giant Rube Golberg machine opens up a gate to a veriety of fun and creative way to encode messages in a really obscure and obfuscated way!

And so...

I thank you for making it through this verbose article! If you want me to edit anything or you have suggestions/questions etc... feel free to leave a comment or send me a message on discord ^^