Sign in to follow this  

Quaternion Fun!

This topic is 2626 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hey I have massive problems understanding quaternions, which is a huge problem for me as a programmer here is my problem:

I have two quaternions which represent two orientations of an object in local space:

Quaternion current_orientation
Quaternion desired_orientation

I would like to get from one to the other using something like as follows:

Quaternion offset <- some value that can be added or multiplied or anything to currrent orientation to get to desired orientation
offset_chunk <- equally divisible chunk of the offset quaternion such that adding/multiplying it to current orientation N number of times over N frames/timesteps will result in a smooth rotation from current Orientation to desired_orientation

Could someone please show me how to calculate the offset quaternion from the two provided quaternions current_orientation and desired_orientation. (represented x, y, z, w please i j k etc only if you have to) and also show me how to derive offset_chunk quaternion from that, and how you would apply the offset chunk each frame, ie a multiplication or addition and normalization etc.

Very much apprecitated.
Stu

Share this post


Link to post
Share on other sites
Okay, ive decided to work around the problem by using matrices. I figure once i have the matrix offset i can just multiply the current rotation by the offset each frame to get the final result.

I already have the full rotation i desire. If i divide each of the 9 elements in the totalRotationOffset by N would that produce the 'chunk matrix' i desire to rotate by for each of the N frames?

Stu

Share this post


Link to post
Share on other sites
You will eventually find out that linear interpolation with matrices is not going to get you the desired result. Which means you will end up having to use quaternion. My advice, learn the mathematical basis behind quaternion or any other concept before blindly using them. Once you have the foundation then its a simple as applying what you have learn. Everyone on the forum can 'show' you, but only you can absorb the knowledge ('learn' ) from what is shown.

Share this post


Link to post
Share on other sites
Dividing the matrix elements by N will simply scale the matrix by 1/N. Since matrix transformations accumulate by multiplication, you need the N:th root of the matrix, and arbitrary matrix roots are not trivial to compute in general.

I agree with cgrant, doing this with matrices is probably not the best solution. if you have a start and end quaternion, the interpolation between the rotations is trivial.

Share this post


Link to post
Share on other sites
Hehe...what is going on here!? You posted the same question in the DirectX forum, and SLERP was suggested. You ditched that thread, re-posted here, SLERP was suggested again, and you ignored it, saying you were going to linearly interpolate matrices instead (or something). Do you have something against SLERP? :-)

Remember you can ask follow-up questions - it's allowed ;) If you're not sure what SLERP is or how it relates to your problem, just ask.

Anyway, you can do what you're asking about using SLERP. However, to answer your specific question, you can compute the 'difference value' that you're asking about by multiplying one of the quaternions by the conjugate of the other. Then, you can use quaternion exp() or log() or something (I can't remember off the top of my head and I'm not going to look it up right now) to compute a 'delta' quaternion that you can then use to rotate incrementally from the first orientation to the second. (Basically what this boils down to is converting the 'difference' quaternion to axis-angle form, scaling the angle, and then converting back.) The end result will the same as with SLERP, more or less (although the means of getting there is a little different).

You can do the same sort of thing with matrices but it's both less efficient and (arguably) less elegant.

Share this post


Link to post
Share on other sites
Quote:
Original post by Brother Bob
Dividing the matrix elements by N will simply scale the matrix by 1/N. Since matrix transformations accumulate by multiplication, you need the N:th root of the matrix, and arbitrary matrix roots are not trivial to compute in general.

I agree with cgrant, doing this with matrices is probably not the best solution. if you have a start and end quaternion, the interpolation between the rotations is trivial.


Yes I should have though of that.
Surely a simpler solution would be to Get the two direction vectors from the two rotations, assuming a direction vector of (0,0,1) when no rotation applied, representing say V0. R1 and R2 would represent the two rotation matrices of orientation, then,

V1 = V0 * R1
V2 = V0 * R2

cross product of v1, v2 gets the axis of rotation
angle of rotation (theta) = acos(v1•v2) (since v1 and v2 are already normalised)

then just divide theta by N (the number of frames desired)

Now just derive the rotationOffsetMatrix chunk from the axis of rotation and the new theta

This is EXACTLY the same as Part III: Spherical Linear Interpolations (SLERPS) in this gamedev article: 'Do We Really Need Quaternions?' http://www.gamedev.net/reference/articles/article1199.asp

Share this post


Link to post
Share on other sites
Yes, that is probably the preferred solution if you have a start and end direction you want to rotate between. As I said, if you start with quaternions though, interpolation with quaternions is probably more convenient. So chose the tool that fits the job.

As the saying goes; if all you have is a hammer, then all problems look like a nail. Don't focus only on solving it with matrices. You said you had quaternions, so solve it with quaternions.

Share this post


Link to post
Share on other sites
Quote:
Original post by jyk
Hehe...what is going on here!? You posted the same question in the DirectX forum, and SLERP was suggested. You ditched that thread, re-posted here, SLERP was suggested again, and you ignored it, saying you were going to linearly interpolate matrices instead (or something). Do you have something against SLERP? :-)

Remember you can ask follow-up questions - it's allowed ;) If you're not sure what SLERP is or how it relates to your problem, just ask.

Anyway, you can do what you're asking about using SLERP. However, to answer your specific question, you can compute the 'difference value' that you're asking about by multiplying one of the quaternions by the conjugate of the other. Then, you can use quaternion exp() or log() or something (I can't remember off the top of my head and I'm not going to look it up right now) to compute a 'delta' quaternion that you can then use to rotate incrementally from the first orientation to the second. (Basically what this boils down to is converting the 'difference' quaternion to axis-angle form, scaling the angle, and then converting back.) The end result will the same as with SLERP, more or less (although the means of getting there is a little different).

You can do the same sort of thing with matrices but it's both less efficient and (arguably) less elegant.


Yes thx for that. I didn't deliberately 'ditch' it. I posted the question, left the forum, and I'd forgotten to put up 'email when someone responds' and then couldnt find it again. Since i had run a search and nothing came up, i had assumed my browser hadn't posted before i had closed the tab window. Many apologies. Dont know why i posted in the DirectX section.

Share this post


Link to post
Share on other sites
Quote:
Original post by Brother Bob
Yes, that is probably the preferred solution if you have a start and end direction you want to rotate between. As I said, if you start with quaternions though, interpolation with quaternions is probably more convenient. So chose the tool that fits the job.

As the saying goes; if all you have is a hammer, then all problems look like a nail. Don't focus only on solving it with matrices. You said you had quaternions, so solve it with quaternions.


Really I have both. Quaternions only pop up because send and receive them over net instead of matrices as it costs less bandwidth, but most of the time dealing with matrices, as all the rotations I get and set in the code are in terms of 3d or 4d Matrix

In terms of speed, isn't performing one matrix multiplication (9 multiplications on 3x3 matrix) cheaper than performing a Slerp every frame? I only have to calculate the offset matrix once roughly every 6.25 frames at worst performance. ie probably more frames pass by than just 6.25 .

Share this post


Link to post
Share on other sites
The question is not which one is cheaper, but whether the difference will be significant enough for you to notice and spend time wondering about. If not, then that's not the reason to pick one or the other. Consider how much work a modern computer can do, and how little work a quaternion slerp or matrix multiplication needs.

Share this post


Link to post
Share on other sites
Slerp can be incremental as well and the best solution I know requires 4 multiplication and 4 addition (it is therefore a lot cheaper than a single matrix multiplication).

I will not derive this algorithm, but you can find it in

Barrera, Tony, et. al. "Incremental Spherical Linear interpolation", Proceedings of SIGRAD, vol. 13 2004.

Li, Xin. "To slerp or not to slerp?", Game Developer Magazine, August 2006, Volume 13, Number 7.

I discovered it in the second article, where other incremental versions are presented (pseudo-code listings from the article).

Let
α = angle between q_0 and q_1 as 4D vectors = cos^{-1}(dot(q_0, q_N))
β = incremental angle = α/N
A = 2cos(β)
p_0 = (q_n - cos(α)q_0)/sin(α)
q_1 = cos(β)q_0 + sin(β)p_0

then the k-th (k > 1) quaternion is

q_k = A q_{k-1} - q_{k-2}

Since A is a real number, you have only 4 multiplications and 4 subtraction (the other quantities are computed once).

Share this post


Link to post
Share on other sites
Interpolating between two matrix states is neither easy or efficient. But interpolating between two quaternions is both, so you should do that.
Given quaternions representing the initial and final orientations of the object, you interpolate (typically every timestep) with a factor between 0 and 1. For example, interpolating with 0.333... will produce a quaternion that rotates the object 1/3 of the way to it's desired orientation.
Your API probably provides the interpolation function for you. In directX, it's D3DXQuaternionSlerp.

For simplicity, start with an object whose world space transform is the identity matrix.
Now you create a quaternion that will rotate it into it's initial orientation. And a second quaternion representing it's final orientation.
Every timestep you determine what the factor is (between 0 and 1) and use D3DXQuaternionSlerp to get the quaternion representing the object's current orientation. Then you call D3DXMatrixRotationQuaternion to convert the current orientation to a matrix, which you can use as the object's world transformation.

Share this post


Link to post
Share on other sites
Once again thank you for all your interest and input. I tried implementing the quaternion iteration idea. I didnt get very far before i realised that there is a crucial bit of information that is important and so far makes it impractical to use quaternions, at least to my knowledge.

I am not just making one interpolation but two at the same time which results in the effect of one. I am interpolating the last set of frames worth of error as well as the next set of frames predicted rotation. This still results in an interpolation between where I am and where i want to be in the future, unfortunately it only works with matrices because I can combine the two rotations into one. I believe the quaternions give me two orientations instead of amount of rotation (maybe im wrong) and so cannot be then interpolated between or combined.

You may ask why I am doing this as the behaviour should be exactly the same as if i just interpolated between where am and where will be in future. The reason is that I need to be able to drop one orientation interpolation and just set the orientation to where it currently should be.

Sorry if that's confusing.

Share this post


Link to post
Share on other sites
your explanation is definitely confusing but anyways,

if you have multiple rotations acting on an object, that should result in ONE quaternion. you should really only ever interpolate one quaternion pair (begin and end). just to be clear, a matrix has a rotation about X,Y, and Z axes, where a quaternion is the combined rotation about those axes. one matrix, 3 rotations => 1 quaternion, 1 rotation.

Share this post


Link to post
Share on other sites
Quote:
Yes thx for that. I didn't deliberately 'ditch' it. I posted the question, left the forum, and I'd forgotten to put up 'email when someone responds' and then couldnt find it again. Since i had run a search and nothing came up, i had assumed my browser hadn't posted before i had closed the tab window. Many apologies. Dont know why i posted in the DirectX section.
Ok, sorry about that - I was just puzzled :) For future reference though, you can find your older threads by going to your profile and looking at the 'previous threads started' section.

Share this post


Link to post
Share on other sites
Quote:
Original post by stu2000
Once again thank you for all your interest and input. I tried implementing the quaternion iteration idea. I didnt get very far before i realised that there is a crucial bit of information that is important and so far makes it impractical to use quaternions, at least to my knowledge.

I am not just making one interpolation but two at the same time which results in the effect of one. I am interpolating the last set of frames worth of error as well as the next set of frames predicted rotation. This still results in an interpolation between where I am and where i want to be in the future, unfortunately it only works with matrices because I can combine the two rotations into one. I believe the quaternions give me two orientations instead of amount of rotation (maybe im wrong) and so cannot be then interpolated between or combined.

You may ask why I am doing this as the behaviour should be exactly the same as if i just interpolated between where am and where will be in future. The reason is that I need to be able to drop one orientation interpolation and just set the orientation to where it currently should be.

Sorry if that's confusing.



I decided to try and expand this with some simple diagrams:

The current states in an EXTREME case of bad error.
Click here to view full size

What I do with matrices
Click here to view full size

What happens with quaternions, unless someone can improve.
Click here to view full size




I realise that for quaternions, i could just have a bool that switches to false IF i snap the orientation to where currently should be, which when true, interpolate between where should-currently-be and where should-be-in-future and whenever false, just interpolate between where-currently-am and where should-be-in-future. However this would also result in needing to keep track of T for the slerp, performing the full slerp instead of faster iteration version someone provided earlier. (because can happen at any time point and wont have previous quaternion to carry on from).

With matrices I just set the rotation offset representing the error interpolation to an identity matrix at the point of snapping the orientation and it just carries on correctly. The other rotation offset matrix that interpolates between where should be and where should be in future remains the same.

Hope that's clearer.


--------------
In terms of speed implementing that IF switch and performing one full slerp is probably faster than performing the two rotation matrix accumulations (18 mults) every frame. Now just gotta find out which of the two methods supervisor wants based on how easy they will be for others to understand, and neatness of code.

Share this post


Link to post
Share on other sites
Sorry, but I do not understand your problem. To combine two rotations with quaternions you simply have to multiply the two quaternions representing the rotations together in the correct order. What are you exactly trying to do?

Share this post


Link to post
Share on other sites
ok so if i do perform two slerp iterations for the two offsets with quaternions as shown in the diagram below, they should combine like this? The dashed line represents the previous orientation and the solid one represents the new orientation by adding the offset. Both are in world space.

Click here to view full size

If so then that's all i need. I just thought you couldn't multiply them together to combine rotations like with matrices, the main reason being the matrices in this case are rotations to be combined with the current orientation, and are not a rotation representing the actual orientation. Im pretty sure doing a slerp will get me a quaternion representing the orientation from 0 when what i need is a rotation from the current position which i can constantly combine each frame. Does that make sense?


--------------
Imagine youve got a clock. You know its second hand turns 1/360 degrees every second clockwise. Thats the offset1. Every frame you apply that offset to the orientation to get the new orientation. You dont need to know the orientation at any time to have a fully working clock. Now say that that clock was ahead by 10 seconds and you want to correct that over 10 seconds. You calculate a second offset that makes it turn counter-clockwise by 1/360th of a degree every second. The result is that the clock does not change for those 10 seconds. If you forget to take away that second offset it will be wrong again and you will have to re-calculate and apply the second offset again. Im pretty sure with slerp, what i will get is an orientation i desire at any point in time given t, when really what i want is to find out the quaternion to apply an offset each frame. But I really want to apply two quaternion offsets, one for the error, and one for the normal change of rotation in time.

The trick is calculating a quaternion offset from two quaternion orientations and you want that offset to be applied N times to get from one to the other quaternion. Now do that twice to get the error and the normal movement so that you can apply both to the current orientation every time frame.

--
this thread looks similar http://www.blitzmax.com/Community/posts.php?topic=51812

Quaternions P, Q.

inverse of P (P') when combined with Q gets you from P to Q. ie P'Q is the total offset looking for.

Now can i somehow divide that offset into little chunks so that i dont go from P to Q in one go but in N timesteps like i have done with matrices by getting to the angle and dividing that by N before deriving the matrix.

[Edited by - stu2000 on September 28, 2010 4:25:39 AM]

Share this post


Link to post
Share on other sites
Ok i think Ive finally done it. Also i havent seen this done anywhere yet. I took how it works in matrices and cut out as much as i could and kept it all in quaternions. This is a way you can have two quaternions, Q1 Q2 and you can get from q1 to q2 in N timesteps. Ive used it and it seems to work perfectly.

Direction_vector_from_quaternion(Quaternion q)
{
v.x = 2 * (q.x) * (q.z) - 2 * (q.w)*(q.y);
v.y = 2*(q.y) * (q.z) + 2 * (q.w)*(q.x);
v.z = 1 - 2 * q.x * q.x - 2 * q.y * q.y;
return v;
}

Quaternion_from_axisangle(Vector v, float angle)
{
angle *= 0.5;
float s = Sin(angle);
x = v.x * s;
y = v.y * s;
z = v.z * s;
w = Cos(angle);
}

v1 = Direction_vector_from_quaternion(q1);
v2 = Direction_vector_from_quaternion(q2);

axis_of_rotation = Cross(v1, v2);
float angle = acos(dot product v1 v2) or written as acos(v1 . v2)

//This is where you divide by n timesteps, in my case i multiply by 1/N which is set to factor;
angle *= factor;

Quaternion offset = Quaternion_from_axisangle(axis_of_rotation, angle);

Share this post


Link to post
Share on other sites
I'll admit I still don't fully understand the problem, but:
Quote:
The trick is calculating a quaternion offset from two quaternion orientations and you want that offset to be applied N times to get from one to the other quaternion. Now do that twice to get the error and the normal movement so that you can apply both to the current orientation every time frame.

--
this thread looks similar http://www.blitzmax.com/Community/posts.php?topic=51812

Quaternions P, Q.

inverse of P (P') when combined with Q gets you from P to Q. ie P'Q is the total offset looking for.

Now can i somehow divide that offset into little chunks so that i dont go from P to Q in one go but in N timesteps like i have done with matrices by getting to the angle and dividing that by N before deriving the matrix.
Did you read my earlier reply? I'll quote it here for convenience:
Quote:
Original post by jyk
However, to answer your specific question, you can compute the 'difference value' that you're asking about by multiplying one of the quaternions by the conjugate of the other. Then, you can use quaternion exp() or log() or something (I can't remember off the top of my head and I'm not going to look it up right now) to compute a 'delta' quaternion that you can then use to rotate incrementally from the first orientation to the second. (Basically what this boils down to is converting the 'difference' quaternion to axis-angle form, scaling the angle, and then converting back.) The end result will the same as with SLERP, more or less (although the means of getting there is a little different). [Emphasis added.]
I described finding the 'difference' quaternion by multiplying by the inverse (conjugate, actually - since the quaternions are unit-length, it's not necessary to use the inverse). I also described how to 'break the quaternion into little chunks' that you can then 'add' incrementally over time (or at least I provided a pretty good hint).

If there's anything about my explanation that isn't clear, please let me know and I'll be happy to elaborate.

Share this post


Link to post
Share on other sites
Quote:
Original post by stu2000
Ok i think Ive finally done it. Also i havent seen this done anywhere yet. I took how it works in matrices and cut out as much as i could and kept it all in quaternions. This is a way you can have two quaternions, Q1 Q2 and you can get from q1 to q2 in N timesteps. Ive used it and it seems to work perfectly.

Direction_vector_from_quaternion(Quaternion q)
{
v.x = 2 * (q.x) * (q.z) - 2 * (q.w)*(q.y);
v.y = 2*(q.y) * (q.z) + 2 * (q.w)*(q.x);
v.z = 1 - 2 * q.x * q.x - 2 * q.y * q.y;
return v;
}

Quaternion_from_axisangle(Vector v, float angle)
{
angle *= 0.5;
float s = Sin(angle);
x = v.x * s;
y = v.y * s;
z = v.z * s;
w = Cos(angle);
}

v1 = Direction_vector_from_quaternion(q1);
v2 = Direction_vector_from_quaternion(q2);

axis_of_rotation = Cross(v1, v2);
float angle = acos(dot product v1 v2) or written as acos(v1 . v2)

//This is where you divide by n timesteps, in my case i multiply by 1/N which is set to factor;
angle *= factor;

Quaternion offset = Quaternion_from_axisangle(axis_of_rotation, angle);
If that's working for you, that's good, but you've solved a different problem than originally stated, more or less.

The code you posted computes a rotation that will rotate the forward vector of one coordinate basis onto the forward vector of another. In the general case, this method will *not* actually interpolate between the orientations; that is, once you've 'incremented' the rotation the desired number of times, the resulting orientation won't necessarily be the same as the target orientation (even taking rounding error into account).

Although I don't fully understand the problem you're trying to solve, your mention of clock hands suggests that you might only be dealing with a single rotation axis; if so, the above method may appear to work (deceptively), but I don't think it's actually doing what you think it's doing.

Also, the 'shortest arc' rotation you refer to is a solved problem, more or less, and there are actually nicer, more robust methods than what you've posted. In order to be robust, the method you're using needs to account for the input vectors being nearly parallel, and also for the argument to acos() going outside of the range [-1, 1] due to rounding error.

Fortunately, there's a couple of very nice quaternion-specific algorithms for computing the 'shortest arc' rotation that don't suffer from the same problems. (The only case that requires special handling is when the input vectors are oppositely aligned or nearly oppositely aligned, but that's unavoidable.) One of these methods is documented in one of the first two GPG books, I believe.

Share this post


Link to post
Share on other sites
This seems to work:

#include <boost/math/quaternion.hpp>

typedef boost::math::quaternion<double> Q;

// This version of log only works on unit quaternions
Q log(Q q) {
double a = std::acos(boost::math::real(q));
return a * boost::math::unreal(q);
}

Q interpolate(Q q1, Q q2, double t) {
Q ratio = q2 * boost::math::conj(q1);
Q step = boost::math::exp(log(ratio) * t);
return q1 * step;
}




[Edited by - alvaro on September 28, 2010 7:36:28 AM]

Share this post


Link to post
Share on other sites
Quote:
Original post by jyk
I'll admit I still don't fully understand the problem, but:
Quote:
The trick is calculating a quaternion offset from two quaternion orientations and you want that offset to be applied N times to get from one to the other quaternion. Now do that twice to get the error and the normal movement so that you can apply both to the current orientation every time frame.

--
this thread looks similar http://www.blitzmax.com/Community/posts.php?topic=51812

Quaternions P, Q.

inverse of P (P') when combined with Q gets you from P to Q. ie P'Q is the total offset looking for.

Now can i somehow divide that offset into little chunks so that i dont go from P to Q in one go but in N timesteps like i have done with matrices by getting to the angle and dividing that by N before deriving the matrix.
Did you read my earlier reply? I'll quote it here for convenience:
Quote:
Original post by jyk
However, to answer your specific question, you can compute the 'difference value' that you're asking about by multiplying one of the quaternions by the conjugate of the other. Then, you can use quaternion exp() or log() or something (I can't remember off the top of my head and I'm not going to look it up right now) to compute a 'delta' quaternion that you can then use to rotate incrementally from the first orientation to the second. (Basically what this boils down to is converting the 'difference' quaternion to axis-angle form, scaling the angle, and then converting back.) The end result will the same as with SLERP, more or less (although the means of getting there is a little different). [Emphasis added.]
I described finding the 'difference' quaternion by multiplying by the inverse (conjugate, actually - since the quaternions are unit-length, it's not necessary to use the inverse). I also described how to 'break the quaternion into little chunks' that you can then 'add' incrementally over time (or at least I provided a pretty good hint).

If there's anything about my explanation that isn't clear, please let me know and I'll be happy to elaborate.


Thanks yah i realise now im pretty much doing exactly what you stated, just dividing theta instead of using quaternion exp() or log(). I hope this has the same effect. Bit worried about someone else stating that this may look like its working but it wont necessarily have the same orientation after the N steps. I would have thought when you take rounding error into account it should.

Im imagining quaternion as a straight line that passes through the center of a sphere (axis of rot) and then rotating round that sphere theta number of degrees. Surely even if you use a smaller theta (by factor N) but do it N times, when you apply this to the starting quaternion orientation, you will end up at the final quaternion orientation?

Share this post


Link to post
Share on other sites

This topic is 2626 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this