Quaternion Extrapolation

Quaternion Extrapolation

Post by Ad » Thu, 03 Jul 2003 17:39:07



Animation in my app is based on keyframes. In a rotation key frame I
keep a quaternion value, when interpolating between rotation key
frames I do a slerp. When the last rotation keyframe is passed I would
like to give the user the option to continue the animation, to do this
I need to extrapolate a quaternion delta from the quaternions in the
last frame and the penultimate frame and add this rotation delta to
the objects current rotation ( quaternion multiply ). The way I am
extrapolating a rotation delta currently is:

D3DXQUATERNION to = pRotateToKeyFrame->GetRotation();
D3DXQUATERNION from = pRotateFromKeyFrame->GetRotation();
D3DXQUATERNION delta = ( ( to - from ) / float(
pRotateToKeyFrame->GetFrame() - pRotateFromKeyFrame->GetFrame() ) );
D3DXQuaternionNormalize( &delta, &delta );

But this is not giving the results I was expecting, not knowing too
much about quaternions I dont know if my approach is a little naive.
Any help would be great.

PS: The GetFrame call on the rotation keyframe returns the position of
that keyframe in the animation.

 
 
 

Quaternion Extrapolation

Post by Dave Eberl » Thu, 03 Jul 2003 21:31:08



Quote:> But this is not giving the results I was expecting, not knowing too
> much about quaternions I dont know if my approach is a little naive.
> Any help would be great.

Given two consecutive quaternions q0 and q1, the slerp of
them is s(t) = (sin((1-t)*A)*q0+sin(t*A)*q1)/sin(A) where
A is the angle between q0 and q1.  For the sake of argument,
let 0 < A < pi.  If you view this in 2D, q0 and q1 are points
on a unit circle centered at the origin.  The slerp s(t) is a
parameterization of the shortest arc from q0 to q1.  Moreover,
uniformly spaced samples in t lead to uniformly spaced points
on the arc.  Mathematically this property is a consequence of
the derivative s'(t) having constant length.  Specifically,
s'(t) = A*(-cos((1-t)*A)*q0 + cos(t*A)*q1)/sin(A) and has
length |s'(t)| = A for all t.

Note that s'(1) = A*[(-q0+cos(A)*q1)/sin(A)].  The quaternion
T = (-q0+cos(A)*q1)/sin(A) has unit length and, as a vector
in 4D is perpendicular to q1.  In the previous 2D analogy, T is
tangent to the circle at q1.  I believe you want to extrapolate
by "walking along the circle" starting at q1 and moving initially
in the T direction.  A parameterization of the circle using q1
and T is p(s) = cos(s)*q1 + sin(s)*T for s >= 0.  Notice that
p(0) = q1 and p'(s) = -sin(s)*q1+cos(s)*T so that p'(0) = T.
You have to decide how parameter "s" relates to the time
parameter "t" of the slerp; that is, s = c*t for some positive
constant c.

--
Dave Eberly

http://www.magic-software.com
http://www.wild-magic.com

 
 
 

Quaternion Extrapolation

Post by Just d' FAQ » Fri, 04 Jul 2003 11:10:15



Quote:>Animation in my app is based on keyframes. In a rotation key frame I
>keep a quaternion value, when interpolating between rotation key
>frames I do a slerp. When the last rotation keyframe is passed I would
>like to give the user the option to continue the animation, to do this
>I need to extrapolate a quaternion delta from the quaternions in the
>last frame and the penultimate frame and add this rotation delta to
>the objects current rotation ( quaternion multiply ). The way I am
>extrapolating a rotation delta currently is:

>D3DXQUATERNION to = pRotateToKeyFrame->GetRotation();
>D3DXQUATERNION from = pRotateFromKeyFrame->GetRotation();
>D3DXQUATERNION delta = ( ( to - from ) / float(
>pRotateToKeyFrame->GetFrame() - pRotateFromKeyFrame->GetFrame() ) );
>D3DXQuaternionNormalize( &delta, &delta );

>But this is not giving the results I was expecting, not knowing too
>much about quaternions I dont know if my approach is a little naive.
>Any help would be great.

>PS: The GetFrame call on the rotation keyframe returns the position of
>that keyframe in the animation.

I'm not sure I properly understand your code, but it looks as if it
subtracts two quaternions, divides by the time interval, and then
normalizes. The problem is, Slerp should give an arc, not a line.

Remember also that we accumulate quaternions by multiplication. So you
want for the quaternion interval, not Qto-Qfrom, but Qto Qfrom^-1. And
instead of scaling that by 1/(Tto-Tfrom), you want to Slerp by it.

  delta = Slerp(Qid,Qto Qfrom^-1; 1/(Tto-Tfrom))

where Qid = [(0,0,0),1].

 
 
 

Quaternion Extrapolation

Post by Ad » Fri, 04 Jul 2003 16:36:42


I have just implemented extrapolation by performing a slerp outside of
the 0 -> 1 range and it all works fine.
 
 
 

Quaternion Extrapolation

Post by Stephen Rile » Fri, 04 Jul 2003 21:35:33




Quote:>Given two consecutive quaternions q0 and q1, the slerp of
>them is s(t) = (sin((1-t)*A)*q0+sin(t*A)*q1)/sin(A) where
>A is the angle between q0 and q1.  For the sake of argument,
>let 0 < A < pi.  If you view this in 2D, q0 and q1 are points
>on a unit circle centered at the origin.  The slerp s(t) is a
>parameterization of the shortest arc from q0 to q1.  Moreover,
>uniformly spaced samples in t lead to uniformly spaced points
>on the arc.  Mathematically this property is a consequence of
>the derivative s'(t) having constant length.  Specifically,
>s'(t) = A*(-cos((1-t)*A)*q0 + cos(t*A)*q1)/sin(A) and has
>length |s'(t)| = A for all t.

Neat!

I thought I'd implement this slerp as an applet, since I was fiddling
around getting to grips with quaternions anyway.

   http://www.sriley.co.uk/qSlerp

As you say, and the mathematics leaving little doubt, this slerp gives
uniformly spaced points. From what I see there (with quaternions
displayed in axis/angle form) the vector part giving uniformly spaced
points around a unit circle, and the angle around the vector part also
rotating/slerping uniformly.

>Note that s'(1) = A*[(-q0+cos(A)*q1)/sin(A)].  The quaternion
>T = (-q0+cos(A)*q1)/sin(A) has unit length and, as a vector
>in 4D is perpendicular to q1.  In the previous 2D analogy, T is
>tangent to the circle at q1.  I believe you want to extrapolate
>by "walking along the circle" starting at q1 and moving initially
>in the T direction.  A parameterization of the circle using q1
>and T is p(s) = cos(s)*q1 + sin(s)*T for s >= 0.  Notice that
>p(0) = q1 and p'(s) = -sin(s)*q1+cos(s)*T so that p'(0) = T.
>You have to decide how parameter "s" relates to the time
>parameter "t" of the slerp; that is, s = c*t for some positive
>constant c.

>--
>Dave Eberly

>http://www.magic-software.com
>http://www.wild-magic.com

--
Stephen Riley
 
 
 

Quaternion Extrapolation

Post by Just d' FAQ » Sat, 05 Jul 2003 06:55:19


On Thu, 3 Jul 2003 13:35:33 +0100, Stephen Riley


>I thought I'd implement this slerp as an applet, since I was fiddling
>around getting to grips with quaternions anyway.

>   http://www.sriley.co.uk/qSlerp

>As you say, and the mathematics leaving little doubt, this slerp gives
>uniformly spaced points. From what I see there (with quaternions
>displayed in axis/angle form) the vector part giving uniformly spaced
>points around a unit circle, and the angle around the vector part also
>rotating/slerping uniformly.

One good way to understand an abstraction is to make it concrete;
another is to explain it. Looks like you're well on your way with
Slerp. Examination from different points of view also can help, so
here's some relevant background.

In elementary trigonometry we learn to draw a unit circle:

  x = cos(t)
  y = sin(t)

The xy coordinate system is arbitrary. Given any two perpendicular
unit vectors U and V we could just as well write a unit circle as

  C(t) = cos(t)*U + *sin(t)*V

One nice feature of this form is that the same formula works in any
dimension, whether 2D or 3D or 4D or whatever. The circle will be in
the plane spanned by U and V.

More suggestively, let t run from 0 to 1 in

  C(t) = cos(t*pi/2)*U + sin(t*pi/2)*V

to draw a quarter-circle arc from U to V. Because cosine is an even
function, cos(x) = cos(-x), and a shifted sine, we can rewrite the
first term.

  cos(t*pi/2) = cos(-t*pi/2)
              = sin(pi/2 - t*pi/2)
              = sin((1-t)*pi/2)

Now suppose U and V are unit vectors but at an angle of A instead of
perpendicular. Then the portion of V perpendicular to U does not have
unit magnitude, but is diminished to sin(A). Likewise for U to V. By
compensating for that we arrive at the general Slerp formula.

                 sin((1-t)*A)*U + sin(t*A)*V
  Slerp(U,V;t) = ---------------------------
                           sin(A)

This derivation makes absolutely no use of quaternion properties.
Slerp is no more nor less than a flexible way to draw a circular arc!

The fact that drawing an arc is the appropriate way to interpolate
unit quaternions is a different, deeper, discussion.

 
 
 

Quaternion Extrapolation

Post by Stephen Rile » Sun, 06 Jul 2003 03:42:27




Quote:>One good way to understand an abstraction is to make it concrete;
>another is to explain it. Looks like you're well on your way with
>Slerp. Examination from different points of view also can help, so
>here's some relevant background.

>In elementary trigonometry we learn to draw a unit circle:

>  x = cos(t)
>  y = sin(t)

>The xy coordinate system is arbitrary. Given any two perpendicular
>unit vectors U and V we could just as well write a unit circle as

>  C(t) = cos(t)*U + *sin(t)*V

>One nice feature of this form is that the same formula works in any
>dimension, whether 2D or 3D or 4D or whatever. The circle will be in
>the plane spanned by U and V.

>More suggestively, let t run from 0 to 1 in

>  C(t) = cos(t*pi/2)*U + sin(t*pi/2)*V

>to draw a quarter-circle arc from U to V. Because cosine is an even
>function, cos(x) = cos(-x), and a shifted sine, we can rewrite the
>first term.

>  cos(t*pi/2) = cos(-t*pi/2)
>              = sin(pi/2 - t*pi/2)
>              = sin((1-t)*pi/2)

>Now suppose U and V are unit vectors but at an angle of A instead of
>perpendicular. Then the portion of V perpendicular to U does not have
>unit magnitude, but is diminished to sin(A). Likewise for U to V. By
>compensating for that we arrive at the general Slerp formula.

>                 sin((1-t)*A)*U + sin(t*A)*V
>  Slerp(U,V;t) = ---------------------------
>                           sin(A)

>This derivation makes absolutely no use of quaternion properties.
>Slerp is no more nor less than a flexible way to draw a circular arc!

Excellent. Having not seen or derived the general case above before, I
didn't connect the general slerp you give above to the aforementioned
quaternion slerp. Thanks for the background info!

Quote:

>The fact that drawing an arc is the appropriate way to interpolate
>unit quaternions is a different, deeper, discussion.

I suppose if unit quaternions represent points on a 4-dimensional unit
hypersphere, it might be hoped (I'd better not say expected!) that a
slerp on a great circle in that space would also be a minimum distance
in 2 and 3-dimensions (or rather follow a minimum energy curve/gradient
or whatever the mathematical term) in lower dimensions, especially since
the vector part only moves in 2D. Is that right? Are geodesics in higher
dimensions just 2 dimensional? In any case, I've no doubt coming to the
correct conclusion rigorously would be a much deeper issue!

Is there a way of visualising a 4-dimensional sphere btw?

--
Stephen Riley

 
 
 

Quaternion Extrapolation

Post by Just d' FAQ » Sun, 06 Jul 2003 09:58:57


On Fri, 4 Jul 2003 19:42:27 +0100, Stephen Riley


>I suppose if unit quaternions represent points on a 4-dimensional unit
>hypersphere, it might be hoped (I'd better not say expected!) that a
>slerp on a great circle in that space would also be a minimum distance
>in 2 and 3-dimensions (or rather follow a minimum energy curve/gradient
>or whatever the mathematical term) in lower dimensions, especially since
>the vector part only moves in 2D. Is that right? Are geodesics in higher
>dimensions just 2 dimensional? In any case, I've no doubt coming to the
>correct conclusion rigorously would be a much deeper issue!

On a sphere in of any positive dimension a Slerp gives a uniform speed
great circle arc, which is both planar and a geodesic. Different ways
to characterize the quaternion Slerps are: straightest path, shortest
path, and constant angular velocity. In Lie group terms, that last one
is called "one-parameter-subgroup", multiplying the same infinitesimal
rotation times itself over and over. An ordinary sphere in 3D is not a
group, so we can't use this last idea, but the first two still work.
Now try drawing on a cylinder, which is a rolled up plane; most of the
geodesics look like coiled springs.

Quote:>Is there a way of visualising a 4-dimensional sphere btw?

Yes, but not without distortion. Stereographic projection is a purely
geometric way. Plant a lighthouse at the "south pole", (0,0,-1), and
place a sheet of paper opposite; now trace rays to establish a map
between points on the sphere and points on the paper. This procedure
for the ordinary sphere puts the north pole at the center and circles
of longitude become radiating lines. It works in 2D and 4D as well.

While that has the advantage of mapping circles to circles (counting
those radial lines as really big circles!), it puts the south pole at
infinity. A more compact depiction uses geodesics. Start at the north
pole and walk straight measuring distance. Transfer the measurements
to a flat piece of paper. The ordinary sphere becomes a disk, with all
points on the rim of the disk corresponding to the south pole. When we
apply the same idea in 2D we get a line segment from -pi to pi; in 4D,
we get a solid 3D ball of radius pi.

Since it's boring and unhelpful to draw a picture of a ball, we often
see pictures of the sphere in 4D dissected into circular fibers, the
beautiful Hopf fibration of S3 over S2.

  <http://www.theory.org/geotopo/3-sphere/html/>
  <http://hopf.math.purdue.edu/new-html/hopflogo.html>
  <http://www.math.uni-bonn.de/people/weber/research/tori/>

 
 
 

Quaternion Extrapolation

Post by John Blackbur » Tue, 08 Jul 2003 05:08:50




> Is there a way of visualising a 4-dimensional sphere btw?

One way of visualising 4D is reportedly Hinton's Cubes. They are described
in Martin Gardener's book "Mathematical Carnival", from 1977, as being
invented by Charles Howard Hinton in his book "The Fourth Dimension", from
1904. I've not tried experiementing with them myself: the first book has a
cautionaly note about their effect on users.

John

--
John Blackburne; programmer, The Pitbull Syndicate
<http://www.hk.super.net/~johnb>

 
 
 

1. Quaternion extrapolation

Hello,

I have come across a fair amount of information on quaternion
interpolation using spherical linear interpolation.

Does anyone know of a method for performing quaternion extrapolation? If
so, can you please direct me towards any useful references/web pages,
etc. that might contain relevant information?

Thanks,

Scott.

Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.

2. PSP8 patch available

3. Java Morph with Slider & Extrapolation

4. gallery open..

5. wavelet extrapolation

6. Channels vs Layers

7. Polynomial Interpolation and/or Extrapolation

8. BASKETTBALL mesh/texture..

9. 3DS angle-axis quaternions => normal quaternions

10. Extrapolation(?) and image differencing

11. How to avoid extrapolation ?

12. Need help with Quaternions!

13. Still need some help with Quaternions!