Proof: Quaternion from two vectors

Given two vectors \(\mathbf{u}, \mathbf{v}\in\mathbb{R}^3\) enclosed by the angle \(\theta\), we want to find the quaternion to rotate from \(\mathbf{u}\) to \(\mathbf{v}\).

The text-book solution for this problem is creating an orthogonal rotation axis to both vectors using the cross product and calculating the rotation angle between the vectors using the dot product. Using the axis-angle form allows us to create the desired quaternion. However, this naive solution is very slow when implemented straight ahead due to a lot of square roots and divisions.

Propositions

From the definition of the vector dot-product follows that

\[\mathbf{u}\cdot\mathbf{v} = |\mathbf{u}| |\mathbf{v}| \cos\theta\]

The length of the vector cross-product is given by

\[|\mathbf{u}\times\mathbf{v}| = |\mathbf{u}| |\mathbf{v}| |\sin\theta|\]

Quaternions can be created using axis-angle form

\[\mathbf{Q} = \left(\cos\frac{\theta}{2}, \mathbf{\hat{v}}\sin\frac{\theta}{2}\right)\]

From Lagrange Identity we can conclude that

\[|\mathbf{a}\times\mathbf{b}|^2 = |\mathbf{a}|^2|\mathbf{b}|^2 - (\mathbf{a}\cdot\mathbf{b})^2\]

From trigonometry we know the half-angle formulas

\[\sin\frac{\theta}{2} = \sqrt{\frac{1-\cos\theta}{2}}\]

\[\cos\frac{\theta}{2} = \sqrt{\frac{1+\cos\theta}{2}}\]

\[\sin\theta = 2\sin\frac{\theta}{2}\cos\frac{\theta}{2}\]

Derivaton

\[\begin{array}{rl} \mathbf{Q} &= \left(\cos\frac{\theta}{2}, \mathbf{\hat{w}}\sin\frac{\theta}{2}\right)\\ &= \left(\sqrt{\frac{1+\mathbf{\hat{u}}\cdot\mathbf{\hat{v}}}{2}}, \frac{\mathbf{u}\times\mathbf{v}}{|\mathbf{u}\times\mathbf{v}|}\sqrt{\frac{1-\mathbf{\hat{u}}\cdot\mathbf{\hat{v}}}{2}}\right)\\ &= \left(\sqrt{\frac{1+\mathbf{\hat{u}}\cdot\mathbf{\hat{v}}}{2}}, \frac{\mathbf{u}\times\mathbf{v}}{|\mathbf{u}| |\mathbf{v}| |\sin\theta|}\sqrt{\frac{1-\mathbf{\hat{u}}\cdot\mathbf{\hat{v}}}{2}}\right)\\ &= \left(\sqrt{\frac{1+\mathbf{\hat{u}}\cdot\mathbf{\hat{v}}}{2}}, \frac{\mathbf{u}\times\mathbf{v}}{|\mathbf{u}| |\mathbf{v}| \left|2\sin\frac{\theta}{2}\cos\frac{\theta}{2}\right|}\sqrt{\frac{1-\mathbf{\hat{u}}\cdot\mathbf{\hat{v}}}{2}}\right)\\ &= \left(\sqrt{\frac{1+\mathbf{\hat{u}}\cdot\mathbf{\hat{v}}}{2}}, \frac{\mathbf{u}\times\mathbf{v}}{|\mathbf{u}| |\mathbf{v}| 2 \sqrt{\frac{1+\mathbf{\hat{u}}\cdot\mathbf{\hat{v}}}{2}} }\right)\\ \end{array}\]

This is a quite good finding, we don’t need trig functions at all and have a lot of repetitive elements to compute only once. However, for numerical stability, we should normalize the quaternion at the end, which brings in another square root though.

When we want to normalize the quaternion at the end in any case, we can scale it arbitrarily until then. When we first scale it by \(2 \sqrt{\frac{1+\mathbf{\hat{u}}\cdot\mathbf{\hat{v}}}{2}}\) and after that by \(|\mathbf{u}| |\mathbf{v}|\), we find that

\[\begin{array}{rl} \mathbf{Q}' &= \left(1+\frac{\mathbf{{u}}\cdot\mathbf{{v}}}{|\mathbf{u}| |\mathbf{v}|}, \frac{\mathbf{u}\times\mathbf{v}}{|\mathbf{u}| |\mathbf{v}| }\right)\\ &= \left(|\mathbf{u}| |\mathbf{v}|+ \mathbf{{u}}\cdot\mathbf{{v}}, \mathbf{u}\times\mathbf{v}\right)\\ \end{array}\]

This is pretty nice! We could use this result already and would have a much faster solution than the naive implementation. But when we look at \(|\mathbf{u}| |\mathbf{v}|\), we can use the Lagrange Identity to come up with \(|\mathbf{u}|^2 |\mathbf{v}|^2 = |\mathbf{u}\times\mathbf{v}|^2 + (\mathbf{u}\cdot\mathbf{v})^2\), which gives the final form:

\[\begin{array}{rl} \mathbf{Q}' &= \left(\sqrt{|\mathbf{u}\times\mathbf{v}|^2 + (\mathbf{u}\cdot\mathbf{v})^2}+ \mathbf{{u}}\cdot\mathbf{{v}}, \mathbf{u}\times\mathbf{v}\right)\\ &= \left(\mathbf{{u}}\cdot\mathbf{{v}}+\sqrt{\mathbf{w}\cdot \mathbf{w} + (\mathbf{u}\cdot\mathbf{v})^2}, \mathbf{w}\right)\\ \end{array}\]

Implementing the algorithm is then pretty straightforward:

function fromVectors(u, v) {

  d = dot(u, v)
  w = cross(u, v)

  return Quaternion(d + sqrt(d * d + dot(w, w)), w).normalize()
}

The unit vector case

For the case that \(\mathbf{u}\) and \(\mathbf{v}\) are already normalized unit vectors, the solution becomes much prettier:

\[\begin{array}{rl} \mathbf{Q}' &= \left(1+ \mathbf{\hat{u}}\cdot\mathbf{\hat{v}}, \mathbf{\hat{u}}\times\mathbf{\hat{v}}\right)\\ \end{array}\]

Implementing the algorithm is also pretty straightforward:

function fromUnitVectors(u, v) {
  return Quaternion(1 + dot(u, v), cross(u, v)).normalize()
}