gdalgorithms-list

Re: [Algorithms] Quaternions in IK

[Jason Z. <zi...@n-...>]

Can you convert between Quaternion and Euler without any loss of
information?  I have a routine to convert Euler->Quat but I've never seen
one that goes from Quat->Euler.  This would be most helpful for my current
project.

- Jason Zisk
- nFusion Interactive LLC


----- Original Message -----
From: "Jeff Lander" <je...@di...>
To: <gda...@li...>
Sent: Tuesday, September 05, 2000 8:06 PM
Subject: Re: [Algorithms] Quaternions in IK


> I looked into this for quite a while some time ago.  I asked quite a few
people about it as well.  The consensus is that everyone converts from
Quaternion to Euler and back to handle DOF restrictions.  Intuitively it
seems that there should be a way to restrict the motion of a quaternion to a
particular portion of the hypersphere.  It is a bit beyond my math skills
though.  I have a math grad starting work for me this month so I can put her
on the task. :) No better research tool then a graduate student.
>
> In implementation, for me the conversion isn't too severe.  I only
calculate the IK solution when needed and I classify joints that are 1 DOF
so they are not effected.
>
> -Jeff
>
> At 05:36 AM 9/3/2000 -0700, you wrote:
> >Hi all ,
> >
> >Does any one know an efficient way of constraining quaternions in IK
without factorizing them into 3 axis quaternions ?
> >Finding the required rotation quaternion in IK is pretty easy , but how
can we make sure that it doesn't violate or 3 constrains of the 3DOFs of the
joint ? what I'm doing now is factorizing the IK result quaternion of the
joint into xrotation quaternion yrotation quaternion and zrotation
quaternion , constrain them by their maximums and recombine them again ,
which is obviously a very expensive process.
> >
> >any ideas ? or maybe references ?
> >
> >Thanks
> >
> >Auday
> >
> >_______________________________________________
> >GDAlgorithms-list mailing list
> >GDA...@li...
> >http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list

Re: [Algorithms] Quaternions in IK

[<ro...@do...>]

Jason Zisk  wrote:

>Can you convert between Quaternion and Euler without any loss of
>information?  I have a routine to convert Euler->Quat but I've never seen
>one that goes from Quat->Euler.  This would be most helpful for my current
>project.
>

It is not a question of loss of information, but of absence of
information from the start.  What I mean by this is that the real
geometric thing is the rotation (or orientation) not an Euler angle
construction of it.  The rotation does not uniquely determine the
Euler angles.  If FREE rotation is allowed (think a ship on the sea or
an aircraft or spacecraft) , then a given rotation can be decomposed
into Euler components in infinitely many ways.

So if you start with an Euler construction to get a rotation matrix
(or a quaternion) then use a routine such as one that Dave Eberly
points to on his site to get Euler angles from that quaternion or
matrix, then there is no guarantee that they will be the same Euler
angles you started with....The rotation does not determine the Euler
angles.

On the other hand, for the systems at issue in IK problems, viz.,
linked structures with constrained joints, such as robots and animated
characters, the rotation of the end effectors are NOT free, but
constrained. Typically, the Euler axes DO have a mechanical reality in
the construction of your robot as a linkage of defined 1-DOF joints,
and the range of rotation of each joint is limited.  In many such
cases, no doubt, the Euler angles ARE uniquely determined by the
orientation of the end effector, and in principle one could find an
algorithm to determine them from the rotation.  But it would be
fortuitous if one of Dave's routines gave the correct decomposition in
your particular case.

These considerations lead to a question that keeps coming up for me,
but for which I have not found the answer.  I've posted it on various
forums and lists from time to time, without response.  I'm going to
ask it again here, because at least a few will understand its
statement, and maybe Dave or Jeff's grad student or someone will
remember seeing it discussd somewhere:   In the rotation group SO(3),
how can one characterize a maximal neighborhood of the identity that
has a unique analytic Euler angle parametrization?

[Algorithms] Extracting scale from matrix

[Jon A. <jan...@on...>]

Are there any good tricks for extracting the scale (x, y, z)  from a 4x4 
matrix?  It seems pretty trivial to do it for matrices that consist of 
rotations about a single axis, but I'm having problems doing it for more 
complex matrices.

Jon

Re: [Algorithms] Quaternions in IK

[Auday <au...@so...>]

Actually the main problem with Eulers is the sequence dependency , so if 
you know the sequence you want to get the Eulers in ( from a quaternion or 
a matrix )  then you will usually have only 2 solutions , for example if 
your sequence is ZYX then you will get 2 solutions for Y , one less than 
180 and the other is greater then 180 , and selecting 1 of them will give 
you 1 solution for each of X and Z .
I agree with Ron that Euler angles are not a natural representation of 
rotation, they are just like applying 3 rotations in quaternions or 
matrices, and obviously you have the same problem of dependency if you 
apply any 3 matrices or quaternions. We use the axis aligned Eulers just 
because they make sense and they give us better imagination of the rotation .
For your question Ron , sorry I didn't understand what you meant , maybe if 
you explain I can answer :)

Thanks

Auday




>It is not a question of loss of information, but of absence of
>information from the start.  What I mean by this is that the real
>geometric thing is the rotation (or orientation) not an Euler angle
>construction of it.  The rotation does not uniquely determine the
>Euler angles.  If FREE rotation is allowed (think a ship on the sea or
>an aircraft or spacecraft) , then a given rotation can be decomposed
>into Euler components in infinitely many ways.
>
>So if you start with an Euler construction to get a rotation matrix
>(or a quaternion) then use a routine such as one that Dave Eberly
>points to on his site to get Euler angles from that quaternion or
>matrix, then there is no guarantee that they will be the same Euler
>angles you started with....The rotation does not determine the Euler
>angles.
>
>On the other hand, for the systems at issue in IK problems, viz.,
>linked structures with constrained joints, such as robots and animated
>characters, the rotation of the end effectors are NOT free, but
>constrained. Typically, the Euler axes DO have a mechanical reality in
>the construction of your robot as a linkage of defined 1-DOF joints,
>and the range of rotation of each joint is limited.  In many such
>cases, no doubt, the Euler angles ARE uniquely determined by the
>orientation of the end effector, and in principle one could find an
>algorithm to determine them from the rotation.  But it would be
>fortuitous if one of Dave's routines gave the correct decomposition in
>your particular case.
>
>These considerations lead to a question that keeps coming up for me,
>but for which I have not found the answer.  I've posted it on various
>forums and lists from time to time, without response.  I'm going to
>ask it again here, because at least a few will understand its
>statement, and maybe Dave or Jeff's grad student or someone will
>remember seeing it discussd somewhere:   In the rotation group SO(3),
>how can one characterize a maximal neighborhood of the identity that
>has a unique analytic Euler angle parametrization?
>
>_______________________________________________
>GDAlgorithms-list mailing list
>GDA...@li...
>http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list

Re: [Algorithms] Quaternions in IK

[Jeff L. <je...@di...>]

The process is really Quat->Matrix->Euler.  Since Quat->Matrix is a pretty easy operation, you can use it as basically Quat->Euler.

I am sure others here have more robust or flexible routines like this but this is what I use.
Since the Matrix->Euler solution has a dependency on order of rotations, a general solution would handle any order.  I typically only use either XYZ or YXZ (HPB) so I have just two versions.  This returns the XYZ decomposition of a Quaternion (x,y,z,w)

You can run this into a EulerToQuat routine to check the results and as long as the EulerToQuat is XYZ order, it should be equal.  The HPB version can be calculated from this easily but if you need it, you can email me.

void QuatToEuler(const tQuaternion *quat, tVector *euler)
{
/// Local Variables ///////////////////////////////////////////////////////////
         float matrix[3][3];
         float cx,sx,x;
         float cy,sy,y,yr;
         float cz,sz,z;
///////////////////////////////////////////////////////////////////////////////
         // CONVERT QUATERNION TO MATRIX - I DON'T REALLY NEED ALL OF IT
         matrix[0][0] = 1.0f - (2.0f * quat->y * quat->y) - (2.0f * quat->z * quat->z);
//      matrix[0][1] = (2.0f * quat->x * quat->y) - (2.0f * quat->w * quat->z);
//      matrix[0][2] = (2.0f * quat->x * quat->z) + (2.0f * quat->w * quat->y);
         matrix[1][0] = (2.0f * quat->x * quat->y) + (2.0f * quat->w * quat->z);
//      matrix[1][1] = 1.0f - (2.0f * quat->x * quat->x) - (2.0f * quat->z * quat->z);
//      matrix[1][2] = (2.0f * quat->y * quat->z) - (2.0f * quat->w * quat->x);
         matrix[2][0] = (2.0f * quat->x * quat->z) - (2.0f * quat->w * quat->y);
         matrix[2][1] = (2.0f * quat->y * quat->z) + (2.0f * quat->w * quat->x);
         matrix[2][2] = 1.0f - (2.0f * quat->x * quat->x) - (2.0f * quat->y * quat->y);

         sy = -matrix[2][0];
         cy = sqrt(1 - (sy * sy));
         yr = (float)atan2(sy,cy);
         euler->y = (yr * 180.0f) / (float)M_PI;

         // AVOID DIVIDE BY ZERO ERROR ONLY WHERE Y= +-90 or +-270 
         // NOT CHECKING cy BECAUSE OF PRECISION ERRORS
         if (sy != 1.0f && sy != -1.0f)  
         {
                 cx = matrix[2][2] / cy;
                 sx = matrix[2][1] / cy;
                 euler->x = ((float)atan2(sx,cx) * 180.0f) / (float)M_PI;        // RAD TO DEG

                 cz = matrix[0][0] / cy;
                 sz = matrix[1][0] / cy;
                 euler->z = ((float)atan2(sz,cz) * 180.0f) / (float)M_PI;        // RAD TO DEG
         }
         else
         {
                 // SINCE Cos(Y) IS 0, I AM SCREWED.  ADOPT THE STANDARD Z = 0
                 // NEED SOME MORE OF THE MATRIX TERMS NOW
                 matrix[1][1] = 1.0f - (2.0f * quat->x * quat->x) - (2.0f * quat->z * quat->z);
                 matrix[1][2] = (2.0f * quat->y * quat->z) - (2.0f * quat->w * quat->x);
                 cx = matrix[1][1];
                 sx = -matrix[1][2];
                 euler->x = ((float)atan2(sx,cx) * 180.0f) / (float)M_PI;        // RAD TO DEG

                 cz = 1.0f;
                 sz = 0.0f;
                 euler->z = ((float)atan2(sz,cz) * 180.0f) / (float)M_PI;        // RAD TO DEG
         }
}
// QuatToEuler  ///////////////////////////////////////////////////////////////


At 10:45 PM 9/5/2000 -0400, you wrote:
>Can you convert between Quaternion and Euler without any loss of
>information?  I have a routine to convert Euler->Quat but I've never seen
>one that goes from Quat->Euler.  This would be most helpful for my current
>project.
>
>- Jason Zisk
>- nFusion Interactive LLC

Re: [Algorithms] Quaternions in IK

[Dave E. <eb...@ma...>]

From: "Jeff Lander" <je...@di...>
> Since the Matrix->Euler solution has a dependency
> on order of rotations, a general solution would handle
> any order.  I typically only use either XYZ or YXZ (HPB)
> so I have just two versions.

I have all six converters (XYZ, XZY, YXZ, YZX, ZXY, ZYX)
at my MgcCore.html page (MgcMatrix3.*), among other
conversions to/from various forms.

--
Dave Eberly
eb...@ma...
http://www.magic-software.com

RE: [Algorithms] decompose onto non-orthogonal vectors

[Tom F. <to...@mu...>]

True - I did take a few short-cuts when describing the solution. :-)

Tom Forsyth - Muckyfoot bloke.
Whizzing and pasting and pooting through the day.

> -----Original Message-----
> From: ro...@do... [mailto:ro...@do...]
> Sent: 15 July 2000 18:22
> To: gda...@li...
> Subject: Re: [Algorithms] decompose onto non-orthogonal vectors
> 
> 
> I  wrote:
> 
> >Tom Forsyth  wrote:
> >
> >>Throw one of the dimensions away (any one) - then you have only two
> >>equations. NOW can you solve it? :-)
> >>
> >>The third dimension will just give the same answer if p 
> lies in the plane of
> >>a and b. If it isn't, then it's not a well-formed question, 
> and you'll need
> >>another axis (c) to define a suitable basis. 
> >
> >Not true.  p can very well lie in the plane of a and b without that
> >plane being a coordinate plane.  In that case, the problem is well
> >formed and your solution will give the wrong answer.
> 
>  Ooops, you are indeed correct.   But your solution does not detect
> the ill-formed case.  And moreover, you do have to be careful about
> which dimension to throw away.  If the thing does lie in one of the
> coordinate planes then you can't throw away that dimension.  And you
> can also use some intellegence about which coordiate plane to throw
> away to minimize the errors.
> 
> 
> 
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
> 

Re: [Algorithms] decompose onto non-orthogonal vectors

[<ro...@do...>]

Reprise:

In the 3D case:

If  you are certain that p lies in the plane spanned by a and b, then
Peter Dimov's solution is the best.  (assuming you understand dot
products and 2x2 linear systems).

And, in fact,  that is exactly what I use in my code to find the
intersection of a ray with a triangle with given vertices V0, V1, V2:
First find the intersection P of the ray with the plane of the
triangle.  Refer everything, i.e. the intersection point and two of
the vertices, to any one vertex V0, so that, to cast it into Ben's
notation, p = P - V0, a=V1-V0 and b=V2-V0, and we are certain that p
lies in the plane through V0 spanned by a and b.  Form the dot
products as Peter indicates, and solve the resulting 2x2 system for u
and v.  The result V0 + ua + vb will lie in the triangle if and only
if 0<=u, 0<=v and u+v<=1.

But if you do not know a priori that p is a linear combination of a
and b, then the only way to determine that (finding u and v in the
process) is by Gaussian elimination on the underdetermined system as I
described. Of course, you can organize the Gaussian elimination
efficiently by thinking of it as row operations on the matrix of the
system, rather than elementary operations on the equations.  The
matrix approach is simply a tabular organization of the manipulation
of the equations themselves.