Introduction

It is fairly common to calcualte a rotator that rotate a vector $v$ to another vector $u$, especially when we handle something like animation IK.

Game engines should have their own method for this feature. Quaternion.FromToRotation() in Unity, and FQuat::FindBetweenNormals() in UE4. But it is always good to know what is actually happending deep inside.

http://lolengine.net/blog/2014/02/24/quaternion-from-two-vectors-final
http://www.euclideanspace.com/maths/algebra/vectors/angleBetween/index.htm

Math Logic

A Naive Method

As we all know, a quaternion can be presented by rotating $\theta$ angle around an axis $w$:

$$q = (\theta, w)$$

Angle can be easily calculated by dot production:

$$u \cdot v = |u| \cdot |v| \cdot \cos{\theta}$$

$$|| u \times v || = |u| \cdot |v| \cdot \sin{\theta}$$

It works, in a naive way, though.

How To Build a Quaternion?

It is worth mentioning how a quaterion is built by an axis and an angle.

Quaternion is constructed by:

$$q = \cos{\frac{\theta}{2}} + i\sin{\frac{\theta}{2}}v_{x} + j\sin{\frac{\theta}{2}}v_y + k\sin{\frac{\theta}{2}}v_z$$

So the code for quat::fromaxisangle is like this:

Optimization

Avoiding Trigonometry

Trigonometry is expensive. Thus we need to avoid trigonometry if we can. Inigo Quilez has wrote an article about this: https://www.iquilezles.org/www/articles/noacos/noacos.htm

Sadly, in our naive method, we firstly compute $\theta$ by $\cos{\theta}$, then we compute $\cos{\frac{\theta}{2}}$ and $\sin{\frac{\theta}{2}}$. This is, as a matter of fact, really expensive.

Thus we can save performance by half-angle by:
$$\sin{\frac{\theta}{2}} = \sqrt{\frac{1 - \cos{\theta}}{2}}$$
$$\cos{\frac{\theta}{2}} = \sqrt{\frac{1 + \cos{\theta}}{2}}$$

So we can save these performance by:

Avoid One Square Root

Still, we can do better. We need to normalize 3 vectors: u, v andcross(u, v). But we can get the norm of w through:
$$||u \times v|| = |u| \cdot |v| \cdot |\sin{\theta}|$$
And we know $\sin{\theta}$ by:
$$\sin{\theta} = 2\sin{\frac{\theta}{2}}\cos{\theta}{2}$$
And we also have :
$$\sqrt{a} \cdot \sqrt{b} = \sqrt{a \cdot b}$$
So we can save 2 square roots:

Avoid One More Square Root

And we can simplify this by get rid of $\sin{\theta / 2}$:

This is basically code used by ORGE3D

Consider SIMD

On many SIMD architectures, normalizing a quaterion can be very fast.

So we should take this advantage:

More over, half_cos comes from a sqrt, thus we can get rid of this square root :

And for the same reason, we can have:

Unit Vector

If vector u and v are unit vectors, we can have:

For Non-Unit Vector

Because we need to calculate $dot(u, v)$ and $cross(u, v)$ no matter what, thus norm_u_norm_v can be calculated in a different way:

We can get rid of at least 3 multiplications in this way.

Final Version

I just copy code from : http://www.euclideanspace.com/maths/algebra/vectors/angleBetween/index.htm

I am so cute, please give me money...