gdalgorithms-list

[Algorithms] Rotation Matrices

[<Nik...@ao...>]

Why isn't the multiplication of rotational matrices commutative?  For example 
if I have one rotation matrix which rotates 20 degrees around the Z axis, and 
another which rotates 50 degrees around the X axis, depending on the order in 
which I multiply them, I get different results.  Why is this?  When rotating 
an object there is no visible difference when it is first rotated on one axis 
and then on another, is there?  I first looked in an elementary linear 
algebra book for the answer; however it stated that the multiplication of 
rotation matrices is commutative (although it was only covering 2D rotation 
matrices). Any help would be appreciated.

Thanks,
Nik...@ao...

Re: [Algorithms] Rotation Matrices

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

Nik...@ao... wrote

> Why isn't the multiplication of rotational matrices commutative?

Because concatenation of rotations is not commutative.  In general,
concatenation of mappings is not commutative.

>For example
> if I have one rotation matrix which rotates 20 degrees around the Z axis,
and
> another which rotates 50 degrees around the X axis, depending on the order
in
> which I multiply them, I get different results.
>Why is this?  When rotating
> an object there is no visible difference when it is first rotated on one
axis
> and then on another, is there?

Wrong. Try a simple experiment to see for yourself.

Hold in your hand a rectangular box, whose three edges have different
lengths or are otherwise easily distinguishable.  Now rotate the box 90
degrees about the x -axis, then 90 degress about the y-axis.  Notice how it
is oriented.  Now return it to its original orientation and rotate first 90
degrees about the y-axis, then 90 degrees about the x-axis.  Notice that you
end up in a different final orientation.
That's the way the world is, in 3D anyway.  Rotations are not commutative.
If matrix multiplication were commutative then matrices would not be
suitable for representing rotations.

Concatenation of mappings in general is  not commutative, even 1-dimensional
mappings.  For example consider the 1-1 mapping of the line to itself given
by
x->x^3.  Now consider another 1-1 mapping of the line to itself given by
x->x+1.  Now concatenate them in two different orders.  In one case you get
x->(x+1)^3 in the other case you get
x->x^3+1.
As functions x^3 + 1 and (x +1)^3 = x^3 + 3x^2 + 3x + 1  are quite
different.  Concatenation of mappings, in general, is not commutative.

>I first looked in an elementary linear
> algebra book for the answer; however it stated that the multiplication of
> rotation matrices is commutative (although it was only covering 2D
rotation
> matrices). Any help would be appreciated.
>

It is true that concatenation of rotations about the origin in the plane is
indeed commutative.   That's just the way the world is.

Re: [Algorithms] Rotation Matrices

[Charles B. <cb...@cb...>]

Actually, the fact that rotations in 2d are commutative
and rotations in 3d are not is quite a deep fact.  It's
why we have fermions, so that all of us are solid objects,
not collapsed in some big degenerate bose condensate.

In 2d, the rotation group is equivalent to U(1), that is
the unitary group in 1d.  This is because a rotation in 2d
about the origin has the rule :

R(a)R(b) = R(a+b)

Which obviously implies commutation :

R(a)R(b) - R(b)R(a) = R(a+b) - R(a+b) = 0

[X,Y] = XY - YX

is the commutator.  When [X,Y] = 0 it means two
variables commute.

It also means that a valid group representation is the
complex exponential :

R(a) = e^(ia) = cos(a) + isin(a)

since

R(0) = 1  (the do-nothing operator is the identity)
R(2pi) = 1

which is also true for the complex exponential, and
obviously :

R(a)R(b) = e^(ia) e^(ib) = e^(i(a+b)) = R(a+b)

Some neat notes in 2d that will get you in the right
mind-set.  A rotation by 180 is the same as multiplying
by (-1), that is, it's an inversion, which the U(1)
form e^(i pi) = -1 confirms.  Also, we can see that
rotation by 180 must be (-1), since if you do it twice
(square it) then you must get 1, the identity.  Similarly,
rotation by 90 is (i), since if you do it twice you must
get a rotation by 180, which is (-1).  If you think of the
plane as a complex plane, you can easily confirm that
multiplying by pi takes (x+iy) to (ix-y), which is indeed
the 2d matrix

0 -1
1  0

which is a rotation by 90, and is the 2d real form of "i",
it's a square-root of minus one (it's also a Pauli Spin
matrix, but now we're getting ahead of ourselves!).

Now, in 3d, we have three axes.  We'll try to write this
in the complex exponential form again.  We write

Rx(a) = e^(a Jx) 

similarly for x,y,z.  The J's are the "generators" of the
group.  The Jx is a 3x3 matrix, and the identity here is
the 3x3 identity.  We know what a rotation by X needs to
be, so we can figure out the Jx quite easily.

Jx = 
0  0  0
0  0  1
0 -1  0

Jy =
0  0 -1
0  0  0
1  0  0

Jz =
0  1  0
-1 0  0
0  0  0

So Rx(a) = = {1 in the xx, and cos(a) in the yy and zz} + sin(a) Jx

      = 1xx + cos(a) * Jx^2 + sin(a) Jx

which follows since

-Jx^2 =
0  0  0
0  1  0
0  0  1

= {1 - 1xx}

We get the cos/sin version of R by actually expanding out the exponential
using its Taylor series polynomial and doing the matrix multiplies :

e^x = 0 + x + x^2/2 + ... x^n/n!

These J's are cute; they're actually the "basis" of the
3x3 antisymmetric matrices, and you should all know that
antisymmetric matrices is what rotations are all about.
In fact, rotations are the SO(n) group or orthonormal
matrices.  What I said earlier about U(1) is the statement
that SO(2) = U(1).  The quaternion-rotation matrix
corresponds state that SO(3) = SU(2) * Z2 , where the Z2
is the damned "Gimbal Lock", which is frequently said
as "SU(2) is a double-cover of SO(3)"; eg. in SU(2),
if you rotate by 2pi, you get a minus sign in there which
wasn't there before; you have to rotate by 4pi to get
the identity; this is the double-cover; this double-cover
corresponds to the two matrices in SO(3) which give
you the same rotation : rotation by theta around n, and
rotation by (2pi-theta) around -n (confining the angles
to be in (0,2pi)).

These J's are actually a 3x3 matrix representation of the
quanternions, BTW, since :

[Jx,Jy] = JxJy - JyJx = - Jz

In fact

[Ji,Jj] = - Eijk Jk

where Eijk is the "antisymmetric tensor", 
(Eijk = 1 if ijk is a cyclic permutation of xyz,
and -1 if it's anti-cyclic, and 0 otherwise.
eg. Exyz = 1, Eyxz = -1, Exxy = 0)
Which is the multiplication rule for the quaternion
basis (in commutator form).  (The quaternion bases
are also equal to the rotations by pi times i; that
is

I = i Rx(pi)
J = i Ry(pi)
K = i Rz(pi)

so that I K = - K and so on, which you can varify by
matrix multiplication, and I^2 = -1, etc.)

Some of you may be familiar with the J's ; they're used
in going from a quaternion to a matrix.

In fact, if you have a quaternion q = {w,x,y,z} then the
matrix equivalent is M(q) with M(q) = L * R  (here M,L
and R are all 4x4), and

L = 
J*q   -x
      -y
      -z
x y z -w

R =
J*q    x
       y
       z
-x-y-z-w

Where J*q is a 3x3 matrix created by treating J as a 4-vector
of matrices and doing the 4-dot product :

J = { 1 , Jx, Jy, Jz }

(and there's a (-1) in the 4-dot product on the 0th component :
V*W = -VwWw + VxWx + VyWy + VzWz )

The generators, J, are actually the infinitesimal rotations.
That is,

Rx(a) = lim(N->infinity) { (1 + a Jx/N)^N }

Obviously,

Rx(a) ~= (1 + a Jx)

when a is very small.  This is actually a good way to derive
the rotation matrices, starting from that infinitesimal
rotation (which is easy to derive by looking at what a vector
does when you rotate it a tiny bit; a tiny rotation is just
a linear transformation).  You then just exponentiate it like
the limit above, which gives you the exponential, which then
leads the sine and cosine!

Anyway, we've seen that the generators, J, don't commute, which
means that the rotations can't commute.  We'll use a convenient
form for the rotation matrices :

Rx(a) = 1xx + cos(a) * Jx^2 + sin(a) Jx
      = (1 - cos(a)) * 1xx + cos(a) + sin(a) Jx

[Rx(a),Ry(b)] = [ sin(a) Jx , sin(b) Jy ]

All the other terms have dropped out, since they are diagonal
matrices, and a diagonal matrix commutes with all matrices.
So

[Rx(a),Ry(b)] = sin(a) sin(b) [Jx,Jy] = - sin(a) sin(b) Jz

So, for example

[Rx(pi),Ry(pi)] = 0

and

[Rx(pi/2),Ry(pi/2)] = - Jz

In fact, it should be obvious that this commutator is equal to
zero, because it obviously must be zero whenever a or b is an
integer multiple of pi, and it must increase and decrease
smoothly around those points, so naturally we should have guessed
that form.

Anyway, the point is that if I rotate a vector in x then y, and I
rotate it in y then x, and take the difference, that difference is
"like" a rotation in Z.

Note Rx(pi/2) = 1xx + Jx
so Jz = (Rz(pi/2) - 1zz)
A rotation in Z by 90, projected onto the XY plane, that is,
the perpendicular of the projection of the vector in the XY plane.

For more jazz like this, see

http://math.ucr.edu/home/baez/README.html

or

http://www-physics.lbl.gov/~rncahn/book.html

and search the net for Lie Algebras and Rotations Groups such.

--------------------------------------
Charles Bloom           www.cbloom.com

Re: [Algorithms] Rotation Matrices

[<dav...@hu...>]

    Imagine rotating a cylinder in 3 dimensions about the 2 of the 3
principle axis.  This works best if you pick up a cylindrical medicine
bottle or something similiar (it helps to visualize).  Let's assume y is up,
x is left to right and z is towards and away from you.    Hold the cylinder
such that the "length" of the object points in the direction of y axis and
the "flat" section parallels the x axis.   Now perform these rotations:

a)
      - rotate 45 degrees around the y axis.  (you should notice the
cylinder just spins "in place", and does perceptually move if its a perfect
cylinder).
      - rotate 45 degrees about the x axis.  (it now leans toward or away
from you depending on the direction of rotation).

b)
      - rotate 45 degrees about the x axis. (it now leans toward or away
from you depending on the direction of rotation).
      - rotate 45 degrees around the y axis.  ( the cylinder now is at an
angle in more than one axis.)


As you can hopefully see, the order of rotations in 3 dimensions makes a
difference.


----- Original Message -----
From: <Nik...@ao...>
To: <gda...@li...>
Sent: Wednesday, August 02, 2000 1:25 PM
Subject: [Algorithms] Rotation Matrices


> Why isn't the multiplication of rotational matrices commutative?  For
example
> if I have one rotation matrix which rotates 20 degrees around the Z axis,
and
> another which rotates 50 degrees around the X axis, depending on the order
in
> which I multiply them, I get different results.  Why is this?  When
rotating
> an object there is no visible difference when it is first rotated on one
axis
> and then on another, is there?  I first looked in an elementary linear
> algebra book for the answer; however it stated that the multiplication of
> rotation matrices is commutative (although it was only covering 2D
rotation
> matrices). Any help would be appreciated.
>
> Thanks,
> Nik...@ao...
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
>

[Algorithms] On 2D and 3D Sprites

[Doug C. <dc...@d-...>]

I thought of an easy way to do 2D and 3D sprites but as of yet I cant get it
to work well. The method involves simply grabbing the current world and view
matrices and simply cancelling out the rotational components so the object
can translate in world/view space but is always facing the camera. It works
great if the object is just sitting there at the origin, moving the camera
in any direction still appears as the object is facing right at you
 whether its a 2D sprite or a 3D complex object ). Billboards are easy
because you can just allow rotations on one or more of the axes and it
appears correct also. The weird thing is when you transform the object so it
is no longer centered at the origin. The object still faces you perfectly,
but it moves in relation to the camera - i.e. if you translate it along -x
it moves along the -x axis with respect to the camera, not the world. For
instance it would always move to the left with a -x translation matrix
applied no matter what direction the camera faces it from. I cant figure out
why it would do this since I am still passing though the world translation
as well as the view, just not their rotations. Any ideas on this, has or
anyone else tried doing 2D and 3D sprites in a similar fashon successfully?
Our old method involved transforming the coordinate center of the object
into view space and then reconstructing the object there ( slow - especially
for 3D objects ).

Doug Chism

Re: [Algorithms] On 2D and 3D Sprites

[Stephen J B. <sj...@li...>]

On Thu, 3 Aug 2000, Doug Chism wrote:

> I thought of an easy way to do 2D and 3D sprites but as of yet I cant get it
> to work well. The method involves simply grabbing the current world and view
> matrices and simply cancelling out the rotational components so the object
> can translate in world/view space but is always facing the camera.

That's certainly what most people do.

It's not *perfect* though because it keeps the object parallel to the
screen - which is not the same thing as "facing the camera".

The difference is usually unimportant unless you have a wide field-of-view.

> It works
> great if the object is just sitting there at the origin, moving the camera
> in any direction still appears as the object is facing right at you
>  whether its a 2D sprite or a 3D complex object ). Billboards are easy
> because you can just allow rotations on one or more of the axes and it
> appears correct also. The weird thing is when you transform the object so it
> is no longer centered at the origin. The object still faces you perfectly,
> but it moves in relation to the camera - i.e. if you translate it along -x
> it moves along the -x axis with respect to the camera, not the world. For
> instance it would always move to the left with a -x translation matrix
> applied no matter what direction the camera faces it from.

The model will always rotate about its local origin.  If you move it away
from there (by changing the vertex coordinates) it's still going to rotate
around the origin - I suppose that might *look* like a translation if
it's sufficiently far from the origin.

You have to position it billboards using the matrix and THEN nuke the
rotation parts.

> I cant figure out
> why it would do this since I am still passing though the world translation
> as well as the view, just not their rotations. Any ideas on this, has or
> anyone else tried doing 2D and 3D sprites in a similar fashon successfully?

I don't quite understand your explanation of the bug - but I can tell you that
I've done this successfully *many* times in the past and if you have it
implemented right, it will work.

Steve Baker                      (817)619-2657 (Vox/Vox-Mail)
L3Com/Link Simulation & Training (817)619-2466 (Fax)
Work: sj...@li...           http://www.link.com
Home: sjb...@ai...       http://web2.airmail.net/sjbaker1

Re: [Algorithms] On 2D and 3D Sprites

[Doug C. <dc...@d-...>]

Thanks for the response, what I did to solve it was leave the view alone and
stick the view transpose into the worlds rotation components and it works
fine now. I was setting both of the rotational components ( in world and
view ) to identity to cancel out all rotations in both coordinate spaces but
thats not what I wanted to do ( obviously ).

Doug Chism
----- Original Message -----
From: "Stephen J Baker" <sj...@li...>
To: <gda...@li...>
Sent: Thursday, August 03, 2000 1:51 PM
Subject: Re: [Algorithms] On 2D and 3D Sprites


> On Thu, 3 Aug 2000, Doug Chism wrote:
>
> > I thought of an easy way to do 2D and 3D sprites but as of yet I cant
get it
> > to work well. The method involves simply grabbing the current world and
view
> > matrices and simply cancelling out the rotational components so the
object
> > can translate in world/view space but is always facing the camera.
>
> That's certainly what most people do.
>
> It's not *perfect* though because it keeps the object parallel to the
> screen - which is not the same thing as "facing the camera".
>
> The difference is usually unimportant unless you have a wide
field-of-view.
>
> > It works
> > great if the object is just sitting there at the origin, moving the
camera
> > in any direction still appears as the object is facing right at you
> >  whether its a 2D sprite or a 3D complex object ). Billboards are easy
> > because you can just allow rotations on one or more of the axes and it
> > appears correct also. The weird thing is when you transform the object
so it
> > is no longer centered at the origin. The object still faces you
perfectly,
> > but it moves in relation to the camera - i.e. if you translate it
along -x
> > it moves along the -x axis with respect to the camera, not the world.
For
> > instance it would always move to the left with a -x translation matrix
> > applied no matter what direction the camera faces it from.
>
> The model will always rotate about its local origin.  If you move it away
> from there (by changing the vertex coordinates) it's still going to rotate
> around the origin - I suppose that might *look* like a translation if
> it's sufficiently far from the origin.
>
> You have to position it billboards using the matrix and THEN nuke the
> rotation parts.
>
> > I cant figure out
> > why it would do this since I am still passing though the world
translation
> > as well as the view, just not their rotations. Any ideas on this, has or
> > anyone else tried doing 2D and 3D sprites in a similar fashon
successfully?
>
> I don't quite understand your explanation of the bug - but I can tell you
that
> I've done this successfully *many* times in the past and if you have it
> implemented right, it will work.
>
> Steve Baker                      (817)619-2657 (Vox/Vox-Mail)
> L3Com/Link Simulation & Training (817)619-2466 (Fax)
> Work: sj...@li...           http://www.link.com
> Home: sjb...@ai...       http://web2.airmail.net/sjbaker1
>
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
>
>

[Algorithms] Single mesh vs segments

[Leigh M. <lei...@ro...>]

 I have a engine that uses segmented models.  I am thinking of switching it
to a single skinned mesh but I am ignorant in this area.  If  the same human
character was modeled using segments and then modeled with a single skin
would one be faster then the other?  Do they take about the same memory
space?  Which looks better?

Leigh McRae

Re: [Algorithms] Rotation Matrices

[Steve B. <st...@li...>]

On Wed, 2 Aug 2000 Nik...@ao... wrote:

> Why isn't the multiplication of rotational matrices commutative?

Well, look at the top-left corner element and see how it's computed:

    dst[0][0] = m2[0][0] * m1[0][0] +
                m2[0][1] * m1[1][0] +
                m2[0][2] * m1[2][0] +
                m2[0][3] * m1[3][0] ;                                                        

Clearly, in general: m2[0][1]*m1[1][0] != m1[0][1]*m2[1][0] ...and so on,
so from the definition of how you multiply them, it's clearly not
commutative.

>  For example 
> if I have one rotation matrix which rotates 20 degrees around the Z axis, and 
> another which rotates 50 degrees around the X axis, depending on the order in 
> which I multiply them, I get different results.  Why is this?

Because that's how rotation works in the real world.

>  When rotating 
> an object there is no visible difference when it is first rotated on one axis 
> and then on another, is there?

Yes there is - you need a concrete example!

Do this - *really* do it - I MEAN NOW!

  1) Fold yourself a paper airplane.

...OK - finished?  Now do this:

[ Roll ==Rotation about Z axis,
  Pitch==Rotation about X axis ... for the sake of this example ]

  2) Hold the paper plane level, right side up with it's nose
     pointing away from you.
  3) Roll it 90 degrees so the left wing is pointing at the
     floor and the right wing is pointing up towards the ceiling.
  4) Now pitch the plane 90 degrees so the nose is pointing at
     the floor and the left wing is pointing towards your chest
     and the right wing is pointing away from you.
  5) Remember how it looks.

That was 90 roll followed by 90 pitch.  Now let's do the reverse:

  2) Hold the paper plane level, right side up with it's nose
     pointing away from you.
  3) Pitch it 90 degrees so the nose is pointing at the
     floor and the tail is pointing up towards the ceiling.
  4) Now roll the plane 90 degrees so the nose is pointing to
     your right and the tail to your left.
  5) Notice that your paper plane is in a different position now.

So, you can clearly see that rotations in the real world are definitely *not*
commutative.

>  I first looked in an elementary linear 
> algebra book for the answer; however it stated that the multiplication of 
> rotation matrices is commutative (although it was only covering 2D rotation 
> matrices). Any help would be appreciated.
 
Well, that's only true for 2x2 *rotation* matrices - if you do something
like:

   Take a square.
   Rotate 90 degrees.               (Still a square)
   Scale by 0.5 in the X direction. (Now a tall, thin rectangle)

...you get something different than:

   Take a square
   Scale by 0.5 in the X direction. (Now a tall, thin rectangle)
   Rotate 90 degrees.               (Now a short, fat rectangle)

...so arbitary 2x2 matrix multiplication *certainly* isn't commutative.

The math book was strictly correct - hopefully it didn't imply
that arbitary 2x2's could be multiplied commutatively.

The deal is that 2D rotations always happen about the same axis
(there IS only one after all) - so multiplication of rotation
matrices is just like adding the angles - and addition is
commutative.

If you do multiple 3D rotations that are all about the same axis
then they commute too.  The problem is when you have a pair
of rotations about DIFFERENT axes - that can't happen in 2D
so the non-commutative nature of arbitary axis rotations
doesn't show up.

Steve Baker                      (817)619-2657 (Vox/Vox-Mail)
L3Com/Link Simulation & Training (817)619-2466 (Fax)
Work: sj...@li...           http://www.link.com
Home: sjb...@ai...       http://web2.airmail.net/sjbaker1

Re: [Algorithms] Rotation Matrices

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

> The deal is that 2D rotations always happen about the same axis
> (there IS only one after all) - so multiplication of rotation
> matrices is just like adding the angles - and addition is
> commutative.
>
Indeed, when you consider rotations about a common center in the plane, say
the origin, then concatenating rotations is isomorphic to adding angles
modulo 2pi.
Since addition of numbers is commutative you can conclude that concatenation
of plane rotations about a common center is also commutative.

However, it is worth mentioning that when you are considering affine
mappings of the plane, you need to consider the problem of concatenating
rotations about different centers (or, considered as 3D rotations, about
different but parallel axes).
These plane rotations about different centers, of course, do not have to
commute. But of course, you cannot represent them by 2x2 rotation matrices,
either.