Archived

This topic is now archived and is closed to further replies.

x19er

Quaternion Integration

Recommended Posts

x19er    122
It appears that NASA has a quaternion integration method that does not require normalization between integration steps. Does anyone have any information on this technique? Their webpage (http://ettc.usc.edu/dryden/tos/closedform.html) states: "NASA''s technology represents a substantial improvement over traditional methods of integrating 4-D kinematics equations. Those methods solve the quaternion kinematic equations in a way that does not automatically preserve the unit normalization of the quaternion. These methods are therefore inherently prone to error and difficult to correct. Such traditional methods are computation-intensive because of the substantial amount of error correction needed to compensate for analytical drift. NASA''s integration method preserves the mathematics of the quaternion space that it creates and therefore introduces no error associated specifically with non-preservation of the quaternion norm. As a result, error correction associated with normalization is not needed in the NASA method"

Share this post


Link to post
Share on other sites
v71    100
Since quaternions are 4-d complex number , just transform a quaternion with Laplace integration from a+jb to a-jb using dt as differential term , integrate the quaternion and revert back to 3d at lest this is what i would do , correct me if i''m wrong :-)

Share this post


Link to post
Share on other sites
grhodes_at_work    1385
quote:
Original post by v71
Since quaternions are 4-d complex number , just transform a quaternion with Laplace integration from a+jb to a-jb using dt as differential term , integrate the quaternion and revert back to 3d at lest this is what i would do , correct me if i''m wrong :-)


Do you know what the date of that patent is? If it is very recent, there may very well be prior art that invalidates the patent.

What you suggest is true, but that doesn''t seem to be what NASA has done. But what NASA seems to have done is to transform the kinematic equations, originally developed based on Euler angle rotations, into quaternion space. The entire equation set not just the rotation itself. They may have used a higher-dimensional form of the Laplace transform to get there. My head hurts thinking about the algebra involved. But the work basically should be just a bunch of ugly algebraic manipulations with perhaps something like Laplace transforms thrown in.

Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.

Share this post


Link to post
Share on other sites
sQuid    149
The US patents office has a lengthy description here.

It describes prior art as solving quaternion kinematices equation using numerical integration schemes that "violate the mathematics of quaternion space" requiring the renormalisation of quaternions after each (integration) time step. This renormalisation "introduces error into the integration in the form of analytical drift."

The new and improved method "constructs 4-D quaternion kinematics equations and integrates them while preserving the norm of the quaternion." Basically it sounds like he has found some integrating factor that enables a closed form solution to the quaternion kinematics equation.

Unfortunately the details are buried in bad formatting and extraneous junk related to including this in some navigation system. I might try to decipher it tonight, or you might immediately be able to tell by looking at the patent.

Share this post


Link to post
Share on other sites
Vlion    151
Patenting math ?
Pardon me, but that sounds really cheesy and bad form and all that.
Sorry, but in science you shouldn`t patent things like that.

Share this post


Link to post
Share on other sites
Palidine    1315
no need to get all freaked out over patents of math. from what i read the patent is specific to the integration of this method into "INS of flight vehicles. The NASA method and device performs three functions.."

device + math = patent.

that''s pretty much as fitting to the ideology of the patent system as you can get. idea + specific implementation.

-me

Share this post


Link to post
Share on other sites
Chappa    122
Excuse me, but why would one want to integrate quaternions anyway? I figured it must have something to do with kinematics but where exactly comes quaternion integration into play?

Sorry if the question might sound a little stupid but I''m just curious.

Share this post


Link to post
Share on other sites
x19er    122
I have to integrate quaternions for my physics engine. The problem is that I have to normalize after each integration step which induces errors. I found the patent doing a google search for quaternion integration. Unfortunately I do not, at present, know how to solve the error problem when integrating quaternions. If anyone has an algorithm for this it would be appreciated.

Share this post


Link to post
Share on other sites
thelamberto    122
quote:
Excuse me, but why would one want to integrate quaternions anyway? I figured it must have something to do with kinematics but where exactly comes quaternion integration into play?

If your simulating the dynamics of something then you can calculate the forces and moments acting on it. Using these you calculate the translational and angular rate accelerations (ie rate of change of movement) which you can integrate to get the new velocities and angular rates. These in turn allow you to calculate the rate of change of the quarternion parameters. So you integrate over a time step to get the new ones.


  (*----------Linear accelerations-------------*)

UDot := XForce/Mass - Q*W + R*V;
VDot := YForce/Mass - R*U + P*W;
WDot := ZForce/Mass - P*V + Q*U;

(*-----------Linear velocities---------------*)

Integrate(U, UDot);
Integrate(V, VDot);
Integrate(W, WDot);

(*---------- Angular accelerations ----------*)

PDot := (Rmt + (Iyy - Izz)*Q*R + Ixz*(RDot + P*Q))/Ixx;
QDot := (Pmt + (Izz - Ixx)*R*P + Ixz*(R*R - P*P))/Iyy;
RDot := (Ymt + (Ixx - Iyy)*P*Q + Ixz*(PDot - Q*R))/Izz;

(*---------------Angular rates---------------*)

Integrate(P, PDot);
Integrate(Q, QDot);
Integrate(R, RDot);

(*--------------Quarternions-----------------*)

Lambda_e := 25.0 * (1.0 - (e0*e0 + e1*e1 + e2*e2 + e3*e3));
e0Dot := -0.5 * (e1*P + e2*Q + e3*R) + Lambda_e*e0;
e1Dot := 0.5 * (e0*P + e2*R - e3*Q) + Lambda_e*e1;
e2Dot := 0.5 * (e0*Q + e3*P - e1*R) + Lambda_e*e2;
e3Dot := 0.5 * (e0*R + e1*Q - e2*P) + Lambda_e*e3;

Integrate(e0, e0Dot);
Integrate(e1, e1Dot);
Integrate(e2, e2Dot);
Integrate(e3, e3Dot);

That's how I did it anyway (and the code's in Modula-2, yuck, Pascal-esk). All in the axis system of the body in question.


[edited by - thelamberto on October 23, 2002 7:39:36 AM]

Share this post


Link to post
Share on other sites
grhodes_at_work    1385
quote:
Original post by Vlion
Patenting math ?
Pardon me, but that sounds really cheesy and bad form and all that.
Sorry, but in science you shouldn`t patent things like that.


Sadly, its quite common, and can be a major headache for game developers who do this for a living. Patents can be a major source of revenue for some companies, and from a business point-of-view they can make sense. And in some cases, it can be beneficial for a developer to pay license fees in order to use a patented technology. But there are so many patents out there that its becoming such a large issue that the International Game Developer''s Association (IGDA) is forming a committee to assist development studios in dealing with patents.

http://www.igda.org/Committees/patents.htm




Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.

Share this post


Link to post
Share on other sites
a2k    124
i''m having the same problem with numerical error. even when i normalize, the quaternions can get kind of inaccurate. i''ve been trying to implement runge-kutta integration to hopefully improve the integration steps. anyone that has successfully gotten stable quaternions, is this the most probable/only way to do it?

a2k

Share this post


Link to post
Share on other sites