gdalgorithms-list

Re: [Algorithms] How to derive transformation matrices

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

Martin Gladnishki  wrote:

>Rotation transforms are easily derived when one expands the multiplication of
>a column vector A(x, y, z) by a rotation (say in the XZ plane) matrix rot( cos
>a,      0,       -sin a     0 )
>                                                                  (     0   ,
>1,              0,    0 )
>                                                                  (  sin a,
>0,       cos a,    0 ).
>
>The matrix multiplication of A' = rot3x3 * A is:
>
>| x' = x * rot(0,0) + y * rot(0,1) + z * rot(0,2)
>| y' = x * rot(1,0) + y * rot(1,1) + z * rot(1,2)
>| z' = x * rot(2,0) + y * rot(2,1) + z * rot(1,2)
>
>which is simplfied to:
>
>| x' = x * cos a  - z * sin a
>| y' = y
>| z' = x * sin a  + z * cos a
>

I agree that taking thesethree steps in the reverse order gives
essentially a derivation of the matrix for rotation about the y axis
from the formulas for rotation in a plane.  Of course, it is a pretty
trivial derivation.

>which in turn can be derived by:
>
>| x' = dist * cos ( phi + a )
>| y' = y
>| z' = dist * sin ( phi + a )
>
>where dist = sqrt( x*x + z*z ) and phi is the initial rotation angle of A.
>

Here lies the crux of the derivation of the formula for rotation in a
plane.  Of course, you leave out some essential details--if you start
out this way, then to expand on your glib "can be derived",  you need
three trigonometric identities and a mess of algebra.  And how do you
derive the three trig identities?   By diagrams involving right
triangles and the pythagorean theorem.   Actually, if you look in
virtually any textbook on plane analytic geometry you will find a
direct derivation of the plane rotation formula, not using any of
these three trig  identities, but just a single diagram involving two
right triangles and the basic definitions of the trig functions.

>As far as I remember (did it too long ago) shearing is derived in the same way
>but the equations are different.
>

You phrases  "the same way", and "the equations are different" provide
an excellent example of "whistling in the dark".   To have a
derivation, you would have to start with a definition of "shear".  

>P.S. complex rotation transformations ...
>

Whatever do you mean by "complex rotation transformations" anyway?
The fact is that  no rotation is more complex than any other rotation
(with the exception of the identity, of course).  Every rotation (not
the identity) has a unique axis and angle. 

True, when the axis of the rotation happens to be a coordinate axis in
the coordinate system you happen to be using, then the matrix of the
rotation with respect that coordinate system is easy to derive from
the plane rotation formulas, as you have done above in the case that
the axis is the y-axis.  But what about when the axis of the rotation
is not a coordinate axis in the coordinate system you happen to be
using?  Your putative derivation description

>...are obtained by expressing them as
>sequence of simple rotations in XY, XZ or YZ planes.

is another crock of whistling in the dark.  No one has ever given a
derivation of the general axis rotation in this way.  It would be
extremely difficult if not impossible. You would first have to give a
general derivation of an Euler angle decomposition of a rotation with
given (non-coordinate) axis and angle, (itself a difficult problem
with many levels of conditional branches needed to get around the
singularities inherent in Euler angles).  Then algebraically compose
those Euler rotations, then try somehow to algebraically simplify that
holy mess in all of its ramified conditional branches.

No, that won't work.  But, there are two ways to derive the matrix for
a rotation whose axis is not a coordinate axis in the system to which
the matrix refers.  

(1) If C0 is the coordinate system with respect to which you want the
matrix of the rotation, find a rotation matrix T  that maps, say, the
y-axis of C0 to the axis of the given rotation.  (Not hard, can be
done with two Euler rotations, avoiding singularities).  Then the axis
of your given rotation IS a coordinate axis in the coordinate system
C1=T C0.  Write down the matrix R for rotation about the y-axis, as
you have done above, and use the well known similarity transformation
that we all learned in elementary linear algebra, which tells how to
get the matrix of a given transformation with respect to a given
coordinate system from the matrix of the same transformation with
respect to another coordinate system.  The result for the matrix of
the general axis rotation  is T R T'  (where T' is the transpose of T)
or T' R T, depending on whether we are OperatorOnRightists or
OperatorOnLeftists. Then simplify algebraically.

But, that is still too messy for me, and far too coordinate-dependent.
I far prefer the following derivation, which does not involve anything
about similarity transformations, but just vector geometry (which I
regard as a more basic subject) and only the simplest idea about the
meaning of a transformation matrix. Namely,

(2) Let A be a unit vector along the axis of rotation and let a be the
rotation angle.  Let V be ANY given vector.  I am going to write down
a vector formula that lets you compute the result V' of rotating V
through angle a about axis A, using just the elementary vector
operations: addition, multiplication by scalars, dot and cross
products.   Then, you don't need any matrix whatsover to compute the
effect of applying the rotation to any vector, you can just use this
vector formula.  But as a bonus, I'll remind you how to get the matrix
from this vector formula, anyway.

You get the vector formula by resolving V into two components, one
parallel to A and one perpendicular to A.  Because the rotation, like
all linear transformations,  preserves vector sums, we only need to
compute the effect of the rotation on the two components, then
recombine the rotated components. Happily, the component parallel to A
is clearly mapped to itself, and the rotation of the perpendicular
component is easy to get, because it remains in the plane
perpendicular to A.   When you carry this out and combine the terms
appropriately you get

 V' = cos(a)V + (A dot V)( 1- cos(a)) A + sin(a) A cross V

(To carry out the details of this derivation, you do need one nice
vector identity, namely the identity
 A cross (B cross C) = (A dot B) C - (A dot C) B, 
whose derivation is a little messy algebraically, but which you will
find in the same chapter in your elementary calculus book in which the
vector cross product is first introduced.) 

Note that this formula expresses the rotated vector V' as a linear
combination of V , A , and the most natural vector that you can
construct from V and A but is linearly independent of V and A, ,
namely A cross V.

Actually, this formula is the basis for the formalism of representing
rotations by quaternion conjugation, but I digress, let's leave
quaternions out of this.  

Now, what about the matrix?  Well, whenever you are able to compute
the effect of a linear transformation on any given vector, you can get
the matrix of that transformation with respect to any given coordinate
system by applying it to the basis vectors of that coordinate system.
THAT is fundamental to the very  concept of using matrices to
represent linear transformations.  So, supposing that you have the
components of A with respect to some coordinate system of which A is
not necessarily an axis vector,  just apply that formula to the basis
vectors (1,0,0), (0,1,0), and (0,0,1) and the resulting nine numbers
are just the elements of the matrix you seek. Again, whether these are
arranged in rows or columns depends on whether you are
OperatorOnRightist or OperatorOnLeftist.

What I am trying to stress here is an idea that is foreign to most
graphics people, but which is extremely important to understanding
what is going on geometrically, an idea that has been mentioned
recently in another thread in this list. It is the idea that, however
much you need them in the end for computing, coordinate systems are an
enormous hindrance to understanding intrinsic geometry.

God did not attach a canonical coordinate system to the universe for
us all to use.  And that's good,  because we are free to use whatever
coordinate system we find most convenient in any problem, and
frequently we find it convenient to work in several different
coordinate systems in a single problem!  The only formulas that are an
aid to understanding, as opposed to  coding, are those that are
manifestly coordinate invariant.  My vector rotation formula above is
manfestly coordinate invariant.  Transformation matrices are highly
coordinate dependent, the opposite of  coordinate invariant.  A given
transformation, with definite intrinsic geometric meaning, has many
different matrix representations, one for each different coordinate
system you might wish to use in any problem.  My manifestly invariant
vector formula given above contains within it all possible different
coordinate-dependent matrix representations of the rotation in
question.

Therefore, all these "tutorials" in graphics API manuals and game
development web sites,  which present the matrices for coordinate-axis
rotations and, leaving it at that,  claim to have dealt with
rotations, are perpetrating a serious crime upon the 
eager newbie who seeks to understand what is a rotation. 

Having dealt with rotations, what about shear?  I'll leave that aside
until someone asks the question using an intrinsic geometric
definition of "shear" (And it does exist).  

P.S. Quaternions, in their role representing rotations, are just as
coordinate dependent as matrices are.

Re: [Algorithms] How to derive transformation matrices

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

I wrote

>  The only formulas that are an
>aid to understanding, ...  are those that are
>manifestly coordinate invariant. 

Albert Einstein took this principle, or rather its extension to
generalized curvilinear coordinates for space-time, which he called 
"The Principle of General Covariance", as his guiding light in
deriving the gravitational field equations of General Relativity.  The
entire framework of classical physics suggests that they must be
second-order partial differential equations.  Einstein arrives at them
as the simplest possible system of second-order PDEs that can be
expressed in a manifestly coordinate invariant way.

Aid to understanding? 85 years of increasingly precise observational
data (mostly astronomical) confirms them in every way.

Re: [Algorithms] How to derive transformation matrices

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

I wrote

>What I am trying to stress here is an idea that is foreign to most
>graphics people, but which is extremely important to understanding
>what is going on geometrically, an idea that has been mentioned
>recently in another thread in this list. It is the idea that, however
>much you need them in the end for computing, coordinate systems are an
>enormous hindrance to understanding intrinsic geometry.
>

Well, maybe the light is beginning to dawn on some graphics people in
some quarters.  I don't have time to go to Siggraph this year, but I
see in the program a description of a course called "Geometric
algebra".  This is from the description:

"Geometric algebra is a new fundamental language for the mathematics
of computer graphics, modeling, and interactive techniques. It is
especially useful for handling geometric problems, since it allows for
intrinsic (coordinate-free) and dimensionally seamless descriptions of
geometry..."

Note the use of the term "intrinsic....geometry".  Further, one of the
best ways to make a discussion manifestly coordinate invariant is to
make it  "coordinate-free".

Further, in IEEE Computer Graphics and Applications, May/June 1999,
there is a good tutorial by James R. Miller, entitled "Vector Geometry
for Computer Graphics".  It broaches some of the same ideas of using
coordinate-free vector representations as an aid to understanding.

These ideas are just beginning to dawn on the vanguard of theorists of
computer graphics. They were at the essential core of the training I
received in math grad school a couple of decades ago.