I have two vectors u and v. Is there a way of finding a quaternion representing the rotation from u to v?
Quaternion q;
vector a = crossproduct(v1, v2);
q.xyz = a;
q.w = sqrt((v1.Length ^ 2) * (v2.Length ^ 2)) + dotproduct(v1, v2);
Don't forget to normalize q.
Richard is right about there not being a unique rotation, but the above should give the "shortest arc," which is probably what you need.
-
31Be aware that this does not handle the case of parallel vectors (both in the same direction or pointing in opposite directions).
crossproduct
will not be valid in these cases, so you first need to checkdot(v1, v2) > 0.999999
anddot(v1, v2) < -0.999999
, respectively, and either return an identity quat for parallel vectors, or return a 180 degree rotation (about any axis) for opposite vectors. – sinisterchipmunk May 17 '12 at 13:19 -
11
-
4@sinisterchipmunk Actually, if v1 = v2, crossproduct would be (0,0,0) and w would be positive, which normalizes to identity. According to gamedev.net/topic/… it should work just fine also for v1 = -v2 and in their close vicinity. – jpa Aug 30 '12 at 16:32
-
3How has anyone got this technique to work? For one,
sqrt((v1.Length ^ 2) * (v2.Length ^ 2))
simplifies tov1.Length * v2.Length
. I couldn't get any variation of this to produce sensible results. – Joseph Thomson Jan 19 '13 at 2:28 -
2Yes, this works. See source code. L61 handles if the vectors face opposite directions (return PI, otherwise it'd return identity per @jpa's remark). L67 handles parallel vectors: mathematically unnecessary, but faster. L72 is Polaris878's answer, assuming both vectors are unit length (avoids a sqrt). See also unit tests. – sinisterchipmunk Feb 6 '13 at 1:09
Half-Way Vector Solution
I came up with the solution that I believe Imbrondir was trying to present (albeit with a minor mistake, which was probably why sinisterchipmunk had trouble verifying it).
Given that we can construct a quaternion representing a rotation around an axis like so:
q.w == cos(angle / 2)
q.x == sin(angle / 2) * axis.x
q.y == sin(angle / 2) * axis.y
q.z == sin(angle / 2) * axis.z
And that the dot and cross product of two normalized vectors are:
dot == cos(theta)
cross.x == sin(theta) * perpendicular.x
cross.y == sin(theta) * perpendicular.y
cross.z == sin(theta) * perpendicular.z
Seeing as a rotation from u to v can be achieved by rotating by theta (the angle between the vectors) around the perpendicular vector, it looks as though we can directly construct a quaternion representing such a rotation from the results of the dot and cross products; however, as it stands, theta = angle / 2, which means that doing so would result in twice the desired rotation.
One solution is to compute a vector half-way between u and v, and use the dot and cross product of u and the half-way vector to construct a quaternion representing a rotation of twice the angle between u and the half-way vector, which takes us all the way to v!
There is a special case, where u == -v and a unique half-way vector becomes impossible to calculate. This is expected, given the infinitely many "shortest arc" rotations which can take us from u to v, and we must simply rotate by 180 degrees around any vector orthogonal to u (or v) as our special-case solution. This is done by taking the normalized cross product of u with any other vector not parallel to u.
Pseudo code follows (obviously, in reality the special case would have to account for floating point inaccuracies -- probably by checking the dot products against some threshold rather than an absolute value).
Also note that there is no special case when u == v (the identity quaternion is produced -- check and see for yourself).
// N.B. the arguments are _not_ axis and angle, but rather the
// raw scalar-vector components.
Quaternion(float w, Vector3 xyz);
Quaternion get_rotation_between(Vector3 u, Vector3 v)
{
// It is important that the inputs are of equal length when
// calculating the half-way vector.
u = normalized(u);
v = normalized(v);
// Unfortunately, we have to check for when u == -v, as u + v
// in this case will be (0, 0, 0), which cannot be normalized.
if (u == -v)
{
// 180 degree rotation around any orthogonal vector
return Quaternion(0, normalized(orthogonal(u)));
}
Vector3 half = normalized(u + v);
return Quaternion(dot(u, half), cross(u, half));
}
The orthogonal
function returns any vector orthogonal to the given vector. This implementation uses the cross product with the most orthogonal basis vector.
Vector3 orthogonal(Vector3 v)
{
float x = abs(v.x);
float y = abs(v.y);
float z = abs(v.z);
Vector3 other = x < y ? (x < z ? X_AXIS : Z_AXIS) : (y < z ? Y_AXIS : Z_AXIS);
return cross(v, other);
}
Half-Way Quaternion Solution
This is actually the solution presented in the accepted answer, and it seems to be marginally faster than the half-way vector solution (~20% faster by my measurements, though don't take my word for it). I'm adding it here in case others like myself are interested in an explanation.
Essentially, instead of calculating a quaternion using a half-way vector, you can calculate the quaternion which results in twice the required rotation (as detailed in the other solution), and find the quaternion half-way between that and zero degrees.
As I explained before, the quaternion for double the required rotation is:
q.w == dot(u, v)
q.xyz == cross(u, v)
And the quaternion for zero rotation is:
q.w == 1
q.xyz == (0, 0, 0)
Calculating the half-way quaternion is simply a matter of summing the quaternions and normalizing the result, just like with vectors. However, as is also the case with vectors, the quaternions must have the same magnitude, otherwise the result will be skewed towards the quaternion with the larger magnitude.
A quaternion constructed from the dot and cross product of two vectors will have the same magnitude as those products: length(u) * length(v)
. Rather than dividing all four components by this factor, we can instead scale up the identity quaternion. And if you were wondering why the accepted answer seemingly complicates matters by using sqrt(length(u) ^ 2 * length(v) ^ 2)
, it's because the squared length of a vector is quicker to calculate than the length, so we can save one sqrt
calculation. The result is:
q.w = dot(u, v) + sqrt(length_2(u) * length_2(v))
q.xyz = cross(u, v)
And then normalize the result. Pseudo code follows:
Quaternion get_rotation_between(Vector3 u, Vector3 v)
{
float k_cos_theta = dot(u, v);
float k = sqrt(length_2(u) * length_2(v));
if (k_cos_theta / k == -1)
{
// 180 degree rotation around any orthogonal vector
return Quaternion(0, normalized(orthogonal(u)));
}
return normalized(Quaternion(k_cos_theta + k, cross(u, v)));
}
-
12
-
1Quaternion syntaxis is switched on some examples (Quaternion(xyz, w) and Quaternion(w, xyz)). Also seems that in last code block radians and degrees are mixed to express angles (180 vs. k_cos_theta + k). – Guillermo Blasco Mar 22 '14 at 20:41
-
1Quaternion(float, Vector3) is construction from scalar-vector, whereas Quaternion(Vector3, float) is construction from axis-angle. Perhaps potentially confusing, but I think it is correct. Correct me if you still think it is wrong! – Joseph Thomson May 31 '14 at 22:16
-
-
1
The problem as stated is not well-defined: there is not a unique rotation for a given pair of vectors. Consider the case, for example, where u = <1, 0, 0> and v = <0, 1, 0>. One rotation from u to v would be a pi / 2 rotation around the z-axis. Another rotation from u to v would be a pi rotation around the vector <1, 1, 0>.
-
1In fact isn't there an infinite number of possible answers? Because after you align the "from" vector with the "to" vector you can still freely spin the result around it's axis? Do you know what extra information can typically be used to constrain this choice and make the problem well defined? – Doug McClean Oct 26 '13 at 2:07
Why not represent the vector using pure quaternions? It's better if you normalize them first perhaps.
q1 = (0 ux uy uz)'
q2 = (0 vx vy vz)'
q1 qrot = q2
Pre-multiply with q1-1
qrot = q1-1 q2
where q1-1 = q1conj / qnorm
This is can be thought of as "left division".
Right division, which is not what you want is:
qrot,right = q2-1 q1
-
2I'm lost, isn't the rotation from q1 to q2 calculated as q_2 = q_rot q_1 q_rot^-1 ? – yota Apr 13 '17 at 15:03
-
I'm not much good on Quaternion. However I struggled for hours on this, and could not make Polaris878 solution work. I've tried pre-normalizing v1 and v2. Normalizing q. Normalizing q.xyz. Yet still I don't get it. The result still didn't give me the right result.
In the end though I found a solution that did. If it helps anyone else, here's my working (python) code:
def diffVectors(v1, v2):
""" Get rotation Quaternion between 2 vectors """
v1.normalize(), v2.normalize()
v = v1+v2
v.normalize()
angle = v.dot(v2)
axis = v.cross(v2)
return Quaternion( angle, *axis )
A special case must be made if v1 and v2 are paralell like v1 == v2 or v1 == -v2 (with some tolerance), where I believe the solutions should be Quaternion(1, 0,0,0) (no rotation) or Quaternion(0, *v1) (180 degree rotation)
-
I have a working implementation, but this yours is prettier, so I really wanted it to work. Unfortunately it failed all of my test cases. My tests all look something like
quat = diffVectors(v1, v2); assert quat * v1 == v2
. – sinisterchipmunk May 17 '12 at 13:09 -
It’s unlikely that this will work at all since
angle
gets its value from a dot product. – sam hocevar Feb 18 '14 at 9:37 -
Some of the answers don't seem to consider possibility that cross product could be 0. Below snippet uses angle-axis representation:
//v1, v2 are assumed to be normalized
Vector3 axis = v1.cross(v2);
if (axis == Vector3::Zero())
axis = up();
else
axis = axis.normalized();
return toQuaternion(axis, ang);
The toQuaternion
can be implemented as follows:
static Quaternion toQuaternion(const Vector3& axis, float angle)
{
auto s = std::sin(angle / 2);
auto u = axis.normalized();
return Quaternion(std::cos(angle / 2), u.x() * s, u.y() * s, u.z() * s);
}
If you are using Eigen library, you can also just do:
Quaternion::FromTwoVectors(from, to)
-
-
2nd parameter is
angle
which is part of axis-angle representation of the quaternion, measured in radians. – Shital Shah Jun 28 '19 at 1:05 -
You were asked to get quaternion to rotate from one vector to another. You don't have angle, you have to calculate it first. Your answer should contain the calculation of angle. Cheers! – Maksym Ganenko Jun 28 '19 at 12:51
-
-
Yes, this is C++. u is vector type from Eigen library (if you are using one). – Shital Shah Oct 17 '19 at 4:36
From algorithm point of view , the fastest solution looks in pseudocode
Quaternion shortest_arc(const vector3& v1, const vector3& v2 )
{
// input vectors NOT unit
Quaternion q( cross(v1, v2), dot(v1, v2) );
// reducing to half angle
q.w += q.magnitude(); // 4 multiplication instead of 6 and more numerical stable
// handling close to 180 degree case
//... code skipped
return q.normalized(); // normalize if you need UNIT quaternion
}
Be sure that you need unit quaternions (usualy, it is required for interpolation).
NOTE: Nonunit quaternions can be used with some operations faster than unit.