More efficient quaternion - vector multiplication

Submitted by Daniel Gehriger

Assigned to Nobody

Link to original bugzilla bug (#1779)

Description

After using Eigen's quaternions to implement a vector rotation, and comparing the generated code with Rodrigue's formula (https://en.wikipedia.org/wiki/Rodrigues%27_rotation_formula), I've noticed that the quaternion version was significantly more complex.

This brought me to the following article, which describes a more efficient implementation for quaternion * vector multiplication: https://blog.molecular-matters.com/2013/05/24/a-faster-quaternion-vector-multiplication/. A full derivation is found here: https://gamesandsimulations.fandom.com/wiki/Quaternions.

I suggest that Eigen considers switching to this more efficient implementation.

Here is the summary:

The canonical way of multiplying a quaternion q by a vector v is given by the following formula:

v' = q * v * conjugate(q)

where the vector v is being treated as a quaternion with w=0, so the above essentially boils down to two quaternion multiplications, which are a bit expensive.

Turns out there is a faster way, which is the following:

t = 2 * cross(q.xyz, v)
v' = v + q.w * t + cross(q.xyz, t)

The faster method comes courtesy of Fabian Giesen (ryg of Farbrausch fame), who posted this to the MollyRocket forums years ago. [...]

In my SSE2 code path, the new method is about 35% faster than the original. Enjoy, and don’t forget to share this gem with other people!