gdalgorithms-list

Re: [Algorithms] How to derive transformation matrices

[Martin G. <bz...@wi...>]

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

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.

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

P.S. complex rotation transformations are obtained by expressing them as
sequence of simple rotations in XY, XZ or YZ planes.

-----Original Message-----
From: Lorrimar <lor...@tr...>
To: gda...@li...
<gda...@li...>
Date: 23 Þëè 2000 ã. 13:18
Subject: [Algorithms] How to derive transformation matrices


>I'm curious on how to derive transformation matrices in 2d and 3d for things
>like shear and rotate. I've had an attempt at the maths but it didn't really
>work out. I'm wondering if anyone knows any internet resources that derive
>these matrices, and not just provide them.
>
>Cheers
>/Rodney
>
>
>_______________________________________________
>GDAlgorithms-list mailing list
>GDA...@li...
>http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
>

Re: [Algorithms] How to derive transformation matrices

[Martin G. <bz...@wi...>]

-----Original Message-----
From: Ron Levine <ro...@do...>
To: gda...@li...
<gda...@li...>
Date: 24 Þëè 2000 ã. 07:11
Subject: Re: [Algorithms] How to derive transformation matrices


Ron, I must admit, your flamethrower is impressive :)

>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?

We all have learned from elementary math how to express rotations with polar
coordinates and expressing rotation with them. Expanding the cos(a+b) and
sin(a+b) should be no trouble for you, I know ;)


>>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".

You obviously missed the words "as far as I remember". I don't know what
Lorrimar ment with 'shear'. But I did a guess 'cause I wanted to be a bit
useful. Shear (as I remember it) is a combination of rotation and scale (no,
I'm not giving an exact mathematical definition, spare me).


>
>>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

Ok, ok, mea culpa, I had in mind series of rotations around coordinate axes.
Excuse my poor English.
Of course rotating around an arbitrary axis vector does involve more math.

>
>>...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.


Wow, you won't put us all in jail if you were in charge, will you? :)))

>
>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.


Ron, if you intend to continue this crash course in expressing
rotations/shearing/etc, I will follow it with close attention. We all can
learn from you, so please be more forgiving with 'newbies' like me.


Martin

Re: [Algorithms] How to derive transformation matrices

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

Martin Gladnishki  wrote:

>
>. We all can
>learn from you, so please be more forgiving with 'newbies' like me.
>

I am never contemptuous of newbies for showing their ignorance by
posting questions--everyone was once ignorant of everything;
everyone, myself included,  remains perpetually ignornant of almost
everything. I do frequently express annoyance at newbies' seeking help
in the wrong forum.  For example, I don't think that this list is  the
right place to seek tutoring on elementary math topics for which there
exist myriad textbooks and courses that everyone ought to have taken
before setting out to do 3D applications.

What sets off my "flamethrower", as you put it, is when people post,
with an air of authority, wildly incorrect responses to the newbies'
earnest questions.  It seems to me that unless you are certain in your
heart that your answer is correct, helpful, or interesting, you should
keep quiet.  Posting  wrong answers with an air of authority makes you
fair game for chastisement.  

Re: [Algorithms] How to derive transformation matrices

[gl <gl...@nt...>]

One word Ron - 'Arrogance'.  Extremely irritating.  Insight - sure.
Corrections - of course.  Friendly? ... well, think about that one.

Also, most people here seem to be in game development.  Many of us learn as
we go, because we are driven by very different things than purists like
yourself.  Your 'approved' path to 3D development is extremely narrow.  It's
like saying that you can't play in a band and write a good song without
having been a) classically trained, b) taken a course in music production,
c) a business course etc.  All have merit, and all are useful, but
programmers have to deal with much more than math, and many/most of us learn
as we go.  Live with it.
--
gl


----- Original Message -----
From: "Ron Levine" <ro...@do...>
To: <gda...@li...>
Sent: Monday, July 24, 2000 2:56 PM
Subject: Re: [Algorithms] How to derive transformation matrices


> Martin Gladnishki  wrote:
>
> >
> >. We all can
> >learn from you, so please be more forgiving with 'newbies' like me.
> >
>
> I am never contemptuous of newbies for showing their ignorance by
> posting questions--everyone was once ignorant of everything;
> everyone, myself included,  remains perpetually ignornant of almost
> everything. I do frequently express annoyance at newbies' seeking help
> in the wrong forum.  For example, I don't think that this list is  the
> right place to seek tutoring on elementary math topics for which there
> exist myriad textbooks and courses that everyone ought to have taken
> before setting out to do 3D applications.
>
> What sets off my "flamethrower", as you put it, is when people post,
> with an air of authority, wildly incorrect responses to the newbies'
> earnest questions.  It seems to me that unless you are certain in your
> heart that your answer is correct, helpful, or interesting, you should
> keep quiet.  Posting  wrong answers with an air of authority makes you
> fair game for chastisement.
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
>

RE: [Algorithms] How to derive transformation matrices

[Akbar A. <sye...@ea...>]

> Posting  wrong answers with an air of authority makes you
>fair game for chastisement.
very, very true.

but, actually i don't think it's a but.
but :-)
somebody once _important_ said something of the nature.
"to be a master one must learn from his teachers and the ones below him,
then one is a true master"

i think this philosophies applies to the _VAST_ field of,
yes; computer graphics. :-D
i have actually learned _quite_ a bit just observing my cousins play with
legos', interact with the "world", swimming in the pool, playing in the tub,
things of this nature. imho usually when you are doing the activities it
becomes _difficult_ to really apperciate the _technical_ point of view.

"nature is an epic beaty from a aesthetic point of veiw _as_ well as a
technical standpoint."
first time i said it 8-D
<...snip>

besides that, what ron says is very true though.
by telling people false information it becomes _manytimes_ harder to
understand the material.
but; you do learn a lot more when you challenge something.
for ex. at the opengl gamedev list before i posted about richard's wright's
first edition book OpenGL superbible, i sat for many hours trying to
_understand_ the _wrong_ code. I read through many books trying to _prove_
the code. after many hours the code was wrong. But, i didn't stop, checked
more books, sites, etc..

follow this philosphy and you will learn much more and remeber things in
general. once you get _really_ good at your _BASICS_ the rest is a breeze.
can i say albert einstein? but many people, including some on this list
don't understand that the _BASICS_ are _VERY_ important.
the next generation of programmers are going to _live_ off api's. this is
"not a good thing for humanity" :-|

a generation of mindless idiots that feel _good_ when they call a library
function properly? and a trivial one at that?
well back to philosphy.
	o Challenge EVERYTHING! -f = -ma
	o yes, books are _always_ right unless _YOU_ find otherwise. just don't
	  trust what joe schmoe says. dig up your own dirt.

in the end (book dillema) i gave up cause i could _not_ understand it (the
bad code)
It turned out it was a error and iirc, 2 people had found it since the books
first publishing.


i have been _learning_ a lot about linux and the kernel in general so please
forgive my abnormal use of underscores 8-) mucho thanks go out to steve for
showing me the light 8-)

quoting gl.
>Many of us learn as we go
the _best_ programmers do this. the linux kernel imho is the best example i
can think of, and the programmers that develop the core os.

a few of the best physists come from a poor educational background.
read, read, read! coding is the quick part (see Code Complete for diagrams)

and no,
schools like mit, cornell, berkley, yes-- rice as well are not doomed.
there are _very_ few people that write e-mails about a
mathamateical-philosphical to an algo list,
and stay up "enginerring" software all night and researching all day.


eeek. i have no idea how i wrote all thise, just about incorrect ..
advice..<snip>



peace.
akbar A.

"We want technology for the sake of the story, not for its own sake. When
you look back, say 10 years from now, current technology will seem quaint"
Pixars' Edwin Catmull.


-----Original Message-----
From: gda...@li...
[mailto:gda...@li...]On Behalf Of Ron
Levine>
Sent: Monday, July 24, 2000 8:56 AM
To: gda...@li...
Subject: Re: [Algorithms] How to derive transformation matrices


Martin Gladnishki  wrote:

>
>. We all can
>learn from you, so please be more forgiving with 'newbies' like me.
>

I am never contemptuous of newbies for showing their ignorance by
posting questions--everyone was once ignorant of everything;
everyone, myself included,  remains perpetually ignornant of almost
everything. I do frequently express annoyance at newbies' seeking help
in the wrong forum.  For example, I don't think that this list is  the
right place to seek tutoring on elementary math topics for which there
exist myriad textbooks and courses that everyone ought to have taken
before setting out to do 3D applications.

What sets off my "flamethrower", as you put it, is when people post,
with an air of authority, wildly incorrect responses to the newbies'
earnest questions.  It seems to me that unless you are certain in your
heart that your answer is correct, helpful, or interesting, you should
keep quiet.  Posting  wrong answers with an air of authority makes you
fair game for chastisement.

_______________________________________________
GDAlgorithms-list mailing list
GDA...@li...
http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list

RE: [Algorithms] How to derive transformation matrices

[Steve W. <Ste...@im...>]

> From: ro...@do... [mailto:ro...@do...]
> 
> 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).  
> 

Which begs the question to Lorrimar...What did you mean by shear?  I'm not a
matrix guy at all (well, except for the movie which rules) but I do know a
few things about shear forces.  If that is what you meant then a shear is
the perpendicular component of force on a surface.  In engineering we need
material that can withstand shear forces so things won't rip apart.  In 3D
graphics I'm assuming that it will create a moment in the object receiving
the force and instead of determining the deflection and deformation of the
material or illustrating the breakage of the material I also assume you will
use shear to cause the object to move or spin.

R&R

Re: [Algorithms] How to derive transformation matrices

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

Steve Wood  wrote:

>> From: ro...@do... [mailto:ro...@do...]
>> 
>> 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).  
>> 
>
>Which begs the question to Lorrimar...What did you mean by shear? 

Guilty of begging the question,  not because I didn't know the answer,
but because it was getting late.  I can't necessarily answer every
question in onepost or one evening.

> I'm not a
>matrix guy at all (well, except for the movie which rules) but I do know a
>few things about shear forces. 

There is no question of forces here, but just of affine mappings.
True, a shear force on a deformable object tends to produce a
deformation that would be described by a shear mapping.  I think the
engineers say "Stress is proportional to strain".  The stress is the
shear force, the strain is the deformation.  

But on a rigid body a shear just produces a force couple, which
results in rotation, not a shear deformation, so not a shear
transformation..  But all this is a digression from the issue of
transformations, i.e. mappings.
   
> If that is what you meant then a shear is
>the perpendicular component of force on a surface. 

Although incompletely stated,  I believe you have this wrong.  The
shear comes from the force component parallel to the surface, not
perpendicular.

> In engineering we need
>material that can withstand shear forces so things won't rip apart.  In 3D
>graphics I'm assuming that it will create a moment in the object receiving
>the force and instead of determining the deflection and deformation of the
>material or illustrating the breakage of the material I also assume you will
>use shear to cause the object to move or spin.
>

See above the comment on the difference between shear qua force and
shear qua mapping.

Re: [Algorithms] How to derive transformation matrices

[Andrew H. <an...@co...>]

From: "Ron Levine" <ro...@do...>
Subject: Re: [Algorithms] How to derive transformation matrices

> Guilty of begging the question,  not because I didn't know the answer,
> but because it was getting late.  I can't necessarily answer every
> question in onepost or one evening.

"begging the question" is a logical fallacy, also known as circular
reasoning.
(See http://www.nizkor.org/features/fallacies/begging-the-question.html).

I can't continue to parse your post because you seem to have used incorrect
terms.

etc. ;)

Re: [Algorithms] How to derive transformation matrices

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

Andrew Howe  wrote:

>From: "Ron Levine" <ro...@do...>
>Subject: Re: [Algorithms] How to derive transformation matrices
>
>> Guilty of begging the question,  not because I didn't know the answer,
>> but because it was getting late.  I can't necessarily answer every
>> question in onepost or one evening.
>
>"begging the question" is a logical fallacy, also known as circular
>reasoning.
>(See http://www.nizkor.org/features/fallacies/begging-the-question.html).
>
>I can't continue to parse your post because you seem to have used incorrect
>terms.
>
>etc. ;)
>

Right.  I was confusing the term with "begging off".  I am actually
proud of unbegging the question by insisting that a derivation has to
begin with a definition.  

Re: [Algorithms] How to derive transformation matrices

[Martin G. <bz...@wi...>]

Ron,

I'll try to be polite. Uncounted posts from this very list have been a great
help and inspiration for me. The reason I'm posting in here is that I __may__
be a tiny bit helpful to someone. This is not my primary goal, though.
Exchanging thoughts and experience is what has greater value for me. So things
like 'ignorance' and 'air of authority' exist only in _your_ mind. I was
neither trying to be ignorant or authoritative, nor did I want it. Think about
the narrow path Gl spoke about.

P.S. I will not continue this thread. You should do the same, for the sake of
the list.

Martin

RE: [Algorithms] How to derive transformation matrices

[Robert D. <RD...@ac...>]

I think most people in this case take shear to mean a transformation in
which there is an invariant plane, but everything outside that plane is
moved within its own parallel plane, so viewing through the said invariant
plane, you would see this :


  pre-shear            post-shear

  +------+             +------+
  |      |            /      /
--+------+----- -----+------+-------- invariant plane
  |      |          /      /
  +------+         +------+

Useful for certain effects, but in general not a good thing because unlike a
rotation matrix it doesn't preserve your normals.

Robert

-----Original Message-----
From: Steve Wood [mailto:Ste...@im...]
Sent: 24 July 2000 17:49
To: 'gda...@li...'
Subject: RE: [Algorithms] How to derive transformation matrices


> From: ro...@do... [mailto:ro...@do...]
> 
> 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).  
> 

Which begs the question to Lorrimar...What did you mean by shear?  I'm not a
matrix guy at all (well, except for the movie which rules) but I do know a
few things about shear forces.  If that is what you meant then a shear is
the perpendicular component of force on a surface.  In engineering we need
material that can withstand shear forces so things won't rip apart.  In 3D
graphics I'm assuming that it will create a moment in the object receiving
the force and instead of determining the deflection and deformation of the
material or illustrating the breakage of the material I also assume you will
use shear to cause the object to move or spin.

R&R

_______________________________________________
GDAlgorithms-list mailing list
GDA...@li...
http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list

Re: [Algorithms] How to derive transformation matrices

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

Robert Dibley  wrote:

>I think most people in this case take shear to mean a transformation in
>which there is an invariant plane, but everything outside that plane is
>moved within its own parallel plane, so viewing through the said invariant
>plane, you would see this :
>
>
>  pre-shear            post-shear
>
>  +------+             +------+
>  |      |            /      /
>--+------+----- -----+------+-------- invariant plane
>  |      |          /      /
>  +------+         +------+
>

That's pretty close to the way a mathematician would define it, but
your statement  needs a little sharpening  and a nomenclature
adjustment.   The sharpening: it's understood that "transformation"
implies "linear" of "affine", so that the displacements in all the
parallel planes are mutually parallel (or antiparallel) and are
proportional to the signed distance from the fixed plane. Your ASCII
art suggest the mutually parallel property  but does not in fact imply
it in the 3D case, because the artwork lacks one dimension.  Your art
does give a pretty solid indication of the displacement
proportionality property (at least in the font in which I am viewing
it), but again, art is not math.

The point of nomenclature:  What you are calling the "invariant"
plane, would be called the "fixed plane" by most math authors. Each
point of the fixed plane is mapped to itself by the transformation, so
it consists entirely of fixed points of the mapping.   Then each of
the planes parallel to it would be called "invariant" under the
transformation, because each is mapped to itself, that is each point
in such a plane is mapped to another point in the same plane..

OK, as promised, given the intrinsic definition I'll show you how to
get the matrix.  Again, the matrix depends on the coordinate system.
It's straightforward to write down the matrix in the case that the
mapping is nicely aligned with the coordinate system, i.e the case
that the fixed plane is a coordinate plane and the mutually parallel
displacement direction is in the direction of one of the coordinate
axes in that plane. Just as Martin indicated, you write down the
linear equations that express what we have just described in words,
and pick off the coefficients to get the matrix.  So it would be, for
the case that the fixed plane is the xy plane and the translation
direction is in the direction of the x axis

	1  0   c
                0  1   0
                0  0   1 

where c is a non-zero constant giving the amount of shear, the
proportionality constant relating the displacement in the invariant
plane to its z coordinate.  A lot simpler than for the axis-aligned
rotation, isn't it?.   
   
But of course, we want to be able to express the matrix  in ANY
coordinate system, not just a system aligned with the intrinsic
parameters of the mapping.  Just as with rotations, there are two
ways.  The first, for which it is messy to write down a general
formula but not hard to derive in a particular case: 

(1)  Find a transformation T that maps the xy plane of the coordinate
system to the fixed plane of the shear and the x axis to the
displacement direction of the shear, try to make it simple, e.g. (a
rotation, if the origin is in the fixed plane, a rotation and
translation if it is not), and work out the  similarity transformation
T^-1 S T, where S is the above matrix for the axis-aligned shear (or
its obvious extension to a 4x4).

The second, which I prefer because of its manifest coordinate
invariance

(2) Go back to the verbal description of the mapping and write it as a
vector geometric  equation.  Intrinsically, the shear mapping is
described by
	 a fixed plane, which is described by a point with position
vector P0 and a unit normal vector N,
	 a unit displacement vector U which is parallel to that plane,
so perpendicular to N, 
	and a scalar shear constant c, which gives the rate at which
the displacement grows as you move  perpendicular to the fixed plane.

Let V be the position vector of any point.  Writing down the vector
equation described by the above verbal description is fairly direct.
The result is that  V is mapped to a point with position vector V'
given by 

	V' = V +  c ((V - P0) dot N) U 

Voila.  A manifestly coordinate invariant vector expression for the
shear mapping.  You get the 4x4 matrix  with respect to ANY coordinate
system as follows.  Express P0, N and U in their components with
respect to the given coordinate system.  For the translation part of
the 4x4  matrix, substitute (0,0,0) for V. The resulting components of
V' = -c(P0 dot N)U give the first three elements of the last row or
column of the 4x4 affine matrix.  For the upper left 3x3 linear part,
successively substitute the basis vectors (1,0,0), (0,1,0), (0,0,1)
for V.  Then the rows or columns of the upper left 3x3 part are formed
by the respective resulting components of V'.

>Useful for certain effects, but in general not a good thing because unlike a
>rotation matrix it doesn't preserve your normals.
>

True.  Also, the inverse is no longer the transpose (of the 3x3 linear
part), and other nice properties of orthogonal matrices are also lost.
But you can still  recover the normal of a transformed surface by
applying the inverse of the transpose of the 3x3 linear part to the
corresponding normal of the untransformed surface.

Re: [Algorithms] How to derive transformation matrices

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

I  wrote:

>The point of nomenclature:  What you are calling the "invariant"
>plane, would be called the "fixed plane" by most math authors. Each
>point of the fixed plane is mapped to itself by the transformation, so
>it consists entirely of fixed points of the mapping.   Then each of
>the planes parallel to it would be called "invariant" under the
>transformation, because each is mapped to itself, that is each point
>in such a plane is mapped to another point in the same plane..
>

By way of clarifciation:  The fixed plane of the shear is also an
invariant plane of the shear.  But in standard mathematical
nomenclature, the other non-fixed planes which are mapped to
themselves are called "invariant" 

RE: [Algorithms] How to derive transformation matrices

[Steve W. <Ste...@im...>]

> From: ro...@do... [mailto:ro...@do...]

[snip]
>    
> > If that is what you meant then a shear is
> >the perpendicular component of force on a surface. 
> 
> Although incompletely stated,  I believe you have this wrong.  The
> shear comes from the force component parallel to the surface, not
> perpendicular.
> 

uh...no, it's the perpendicular.  Forces parallel to a surface do not
interact with the surface (actually, there would be no resulting force for
any actions parallel to a surface) unless the perpendicular force causes
penetration so the parallel component then has something to "grab onto".

Re: [Algorithms] How to derive transformation matrices

[Klaus H. <k_h...@os...>]

----- Original Message -----
From: Steve Wood <Ste...@im...>
To: <gda...@li...>
Sent: Tuesday, July 25, 2000 7:58 PM
Subject: RE: [Algorithms] How to derive transformation matrices
>
> uh...no, it's the perpendicular.  Forces parallel to a surface do not
> interact with the surface (actually, there would be no resulting force for
> any actions parallel to a surface) unless the perpendicular force causes
> penetration so the parallel component then has something to "grab onto".

Steve,
I'm not native to the English language, but I think it's possible that you
are confusing "shear" with "sheer"!?

According to my English dictionary, "sheer" can be used as an adverb:
B.1 Completely, absolutely, directly,
B.2 Perpendicularly, very steeply, straight up or down

The English dictionary uses the term "shear" mostly for 'parallel' things,
like:
1. The bar, or either of the two parallel bars, forming the bed of a lathe
2. "shear plane". [Geol.] a boundary surface between bodies of rock or ice
which have experienced relative motion parallel to the surface.
3. and a lot more samples, that include the term "parallel".

Niki

Re: [Algorithms] How to derive transformation matrices

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

----- Original Message -----
From: "Steve Wood" <Ste...@im...>
To: <gda...@li...>
Sent: Tuesday, July 25, 2000 10:58 AM
Subject: RE: [Algorithms] How to derive transformation matrices


> > From: ro...@do... [mailto:ro...@do...]
>
> [snip]
> >
> > > If that is what you meant then a shear is
> > >the perpendicular component of force on a surface.
> >
> > Although incompletely stated,  I believe you have this wrong.  The
> > shear comes from the force component parallel to the surface, not
> > perpendicular.
> >
>
> uh...no, it's the perpendicular.  Forces parallel to a surface do not
> interact with the surface (actually, there would be no resulting force for
> any actions parallel to a surface) unless the perpendicular force causes
> penetration so the parallel component then has something to "grab onto".
>

Not in the classical picture (as opposed to the quantum mechanical picture).
Consider the force of friction of a flat table on a rectangular block being
pushed along it.  That frictional force is parallel to the interface, not
perpendicular.  True, in the quantum mechanical detail of the intersurface
forces at the molecular level , there is some interpenetration of the outer
layers of the electromagnetic fields of the surface molecules of the two
interacting materials, but at that level of detail, the notion of "surface"
becomes fuzzy.  Also true that, in the classical picture,  the magnitude of
that frictional force (parallel to the interface) does depend on the normal
force.

Now,  if the force pushing the block along is applied above the level of the
interface, then it is the couple of the pushing force and the frictional
resistance, both parallel to the table, that produces the shear force, and
the shear deformation if the body is deformable.  The perpendicular force is
simply equal and opposite to the weight of the block and produces no shear
deformation.

But again, this is a huge digression from the issue of deriving
transformation matrices. although the ideas are certainly important in the
sort of physical modeling that people are now doing in games.  In those
models, frictional force is parallel to the interface.

RE: [Algorithms] How to derive transformation matrices

[Steve W. <Ste...@im...>]

> From: Andrew Howe [mailto:an...@co...]
> 
> "begging the question" is a logical fallacy, also known as circular
> reasoning.
> (See 
> http://www.nizkor.org/features/fallacies/begging-the-question.html).
> 
> I can't continue to parse your post because you seem to have 
> used incorrect
> terms.
> 
> etc. ;)
> 

I hope my sincere appologies are accepted for any ill feelings I caused.
Apparently I should not use the phrase "begging the question" since many
people now consider it to be something other than it's intended
construction, sorry.  I use the phrase "begging the question" to mean that
the subject matter of a solution includes a topic that raises another
question...the solution is said to "beg the question".  Rons answer brought
up the question in my mind that he might be asking about shear forces.

At first I thought the web site you gave was loonie tooney, however, I also
found some of the same info on the phrase at:
http://search.britannica.com/frm_redir.jsp?query=begging+the+question&redir=
http://www.drury.edu/faculty/Ess/Logic/Informal/Overview.html


R&R

RE: [Algorithms] How to derive transformation matrices

[Steve W. <Ste...@im...>]

> From: Ron Levine [mailto:ro...@do...]
> 
> But again, this is a huge digression from the issue of deriving
> transformation matrices. although the ideas are certainly 
> important in the sort of physical modeling that people are now doing in
games. 
> 

Roger that...I show the shear force is perpendicular to the surface of the
object, then I get shown that it's parallel to the shear plane...both
correct, but doesn't help solve the problem of deforming a 3D object using
transformation matrices...which I know nothing about.

R&R

RE: [Algorithms] How to derive transformation matrices

[Steve W. <Ste...@im...>]

> -----Original Message-----
> From: Klaus Hartmann [mailto:k_h...@os...]
> Steve,
> I'm not native to the English language, but I think it's 
> possible that you
> are confusing "shear" with "sheer"!?
> 

No...I mean shear.

> According to my English dictionary, "sheer" can be used as an adverb:
> B.1 Completely, absolutely, directly,
> B.2 Perpendicularly, very steeply, straight up or down
> 
> The English dictionary uses the term "shear" mostly for 
> 'parallel' things,
> like:
> 1. The bar, or either of the two parallel bars, forming the 
> bed of a lathe
> 2. "shear plane". [Geol.] a boundary surface between bodies 
> of rock or ice
> which have experienced relative motion parallel to the surface.
> 3. and a lot more samples, that include the term "parallel".
> 
> Niki
> 

Yes, a "shear plane" describes the plane where two surfaces move by each
other.  A force causing these surfaces to move is called a shear force and
is parallel to the shear plane, however it is perpendicular to the surface
of contact.  A dictionary sometimes doesn't provide what you might learn in
an engineering textbook.

Consider the following box and a force acting on it perpendicular to the
surface of contact:

                                         -------------------------
                   shear force --------> |                       |
                                         |                       |
                                         |                       |
                                         -------------------------

This is what happens if the box breaks apart with the top half moving and
the bottom half staying:

                                         -------------------------
                   shear force --------> |                       |
                                        -------------------------  this is
the shear plane
                                        |                       |
                                        -------------------------

That is what I learned in engineering about shear forces...I could be wrong,
but I think the physics is correct. I have a friend that went to the same
class and he argued for hours that the force was parallel, with the same
argument that you gave...that the text used the word parallel.  It's not
always the definition that counts, it's mostly the application of the
knowledge that makes the money.  If you want to handle shear planes, then
you need to use only the component of a force that is perpendicular to the
surface of contact to determine if shear occurs...afterwards if it does
occur then you will need to use the parallel component to determine the
resultant forces on the separated portion.

But, again I don't think the original poster (OP) has an object box breaking
apart and just wants to deform it, like turning a box into a trapezoid...in
other words a geometry solution and not a physics solution...so my bringing
up shear forces has gotten this thread off track.

R&R

R&R

Re: [Algorithms] How to derive transformation matrices

[Klaus H. <k_h...@os...>]

----- Original Message -----
From: Steve Wood <Ste...@im...>
To: <gda...@li...>
Sent: Tuesday, July 25, 2000 11:10 PM
Subject: RE: [Algorithms] How to derive transformation matrices


> Yes, a "shear plane" describes the plane where two surfaces move by each
> other.  A force causing these surfaces to move is called a shear force and
> is parallel to the shear plane,

I agree here.

> however it is perpendicular to the surface
> of contact.

With this I don't agree. Certainly, in the case of your box, the shear force
is perpendicular to the surface of contact. But that's not necessarily true
for other primitives. What about spheres for example? Imagine a sphere that
is centered at the origin. The fixed plane is the x/z plane of the world
coordinate system, and we shear along the x-axis (y, and z are fixed). So
our shear force could be represented as a vector H = <h 0 0>, where h is the
magnitude of the force in x-direction. Would you still say, that the shear
force if perpendicular to the surface of contact? Maybe I just misunderstand
you, but for me it's not perpendicular to the surface of contact.

> A dictionary sometimes doesn't provide what you might learn in
> an engineering textbook.

Yeah, forget that dictionary thing. I don't even know why I posted this :(

> But, again I don't think the original poster (OP) has an object box
breaking
> apart and just wants to deform it, like turning a box into a trapezoid

I think that's a parallelepiped, but I'm not 100% sure.

But you are right... this really doesn't help the OP author. So I'll just
exit the thread here, unless I decide to provide something more useful.

Niki

Re: [Algorithms] How to derive transformation matrices

[Klaus H. <k_h...@os...>]

Okay, I know... I said I would exit the thread, but I did a mistake in my
last post.

> With this I don't agree. Certainly, in the case of your box, the shear
force
> is perpendicular to the surface of contact. But that's not necessarily
true
> for other primitives. What about spheres for example? Imagine a sphere
that
> is centered at the origin. The fixed plane is the x/z plane of the world
> coordinate system, and we shear along the x-axis (y, and z are fixed). So
> our shear force could be represented as a vector H = <h 0 0>, where h is
the
> magnitude of the force in x-direction. Would you still say, that the shear
> force if perpendicular to the surface of contact? Maybe I just
misunderstand
> you, but for me it's not perpendicular to the surface of contact.

Forget the vector H thing, which is quite incorrect, because shearing
depends on another coordinate. Examples:

Hxy is a shear matrix that changes x depending on y.
Hxz is a shear matrix that changes x depending on z.
Hyx is a shear matrix that changes y depending on x.
Hyz is a shear matrix that changes y depending on z.
Hzx is a shear matrix that changes z depending on x.
Hzy is a shear matrix that changes z depending on y.

I hope that at least this time I was faster to correct myself than others ;)
Niki

[Algorithms] Polygon clipping

[Klaus H. <k_h...@os...>]

Hi all,

Even though this is not an API-specific question, I'd like to use an
API-specific example to explain my problem.

In Direct3D, when using *vertex buffer* with pre-transformed and pre-lit
vertices, then Direct3D does not perform any clipping. So I have to do this
myself. I could probably go ahead an clip single triangles with a Sutherland
Hodgman algorithm, but...

How do you people clip triangle strips and triangle fans? Is it possible to
clip them so, that strips remain strips, and fans remain fans, or is this
impossible?

Also, which is the prefered clipping algorithm? Is it Sutherland Hodgman?

When you answer, please keep in mind that I also need to clip texture
coordinates and the diffuse/specular colors.

Any help is greatly appreciated,
Niki

RE: [Algorithms] Polygon clipping

[Brian M. <bma...@ra...>]

A triangle fan will remain a triangle fan after clipping to a convex clip
boundary. So if you're clipping to a normal 6 plane view frustrum the fan
stays a fan, though it may have more or less vertices afterwards.

As to triangle strips check out:

	'Three Dimensional Homogenous Clipping of Triangle Strips' Patrick-Gilles
Maillot, Graphics Gems II

If you don't have the book the code is on the net.

When you clip a strip you can get zero or more strips out, or output at most
one strip with degenerate triangles. (The degenerate triangles are used for
jumping along a clip boundary when a hole section of the strip is outside
the clip volume.)

The strip clipping code uses the clip against one plane at a time approach
of Sutherland-Hodgman, but exploits the strip structure to improve
performance.

As to the choice of clipping algorithm - I think that belongs more on a D3D
list for your example, but it may well be worth seeing how quick D3D is at
doing the clipping itself.

-Brian.

> -----Original Message-----
> From: gda...@li...
> [mailto:gda...@li...]On Behalf Of Klaus
> Hartmann
> Sent: Tuesday, July 25, 2000 11:49 PM
> To: gda...@li...
> Subject: [Algorithms] Polygon clipping
>
>
> Hi all,
>
> Even though this is not an API-specific question, I'd like to use an
> API-specific example to explain my problem.
>
> In Direct3D, when using *vertex buffer* with pre-transformed and pre-lit
> vertices, then Direct3D does not perform any clipping. So I have
> to do this
> myself. I could probably go ahead an clip single triangles with a
> Sutherland
> Hodgman algorithm, but...
>
> How do you people clip triangle strips and triangle fans? Is it
> possible to
> clip them so, that strips remain strips, and fans remain fans, or is this
> impossible?
>
> Also, which is the prefered clipping algorithm? Is it Sutherland Hodgman?
>
> When you answer, please keep in mind that I also need to clip texture
> coordinates and the diffuse/specular colors.
>
> Any help is greatly appreciated,
> Niki
>
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
>

Re: [Algorithms] How to derive transformation matrices

[Klaus H. <k_h...@os...>]

Okay, I know... I said I would exit the thread, but I did a mistake in my
last post.

> With this I don't agree. Certainly, in the case of your box, the shear
force
> is perpendicular to the surface of contact. But that's not necessarily
true
> for other primitives. What about spheres for example? Imagine a sphere
that
> is centered at the origin. The fixed plane is the x/z plane of the world
> coordinate system, and we shear along the x-axis (y, and z are fixed). So
> our shear force could be represented as a vector H = <h 0 0>, where h is
the
> magnitude of the force in x-direction. Would you still say, that the shear
> force if perpendicular to the surface of contact? Maybe I just
misunderstand
> you, but for me it's not perpendicular to the surface of contact.

Forget the vector H thing, which is quite incorrect, because shearing
depends on another coordinate. Examples:

Hxy is a shear matrix that changes x depending on y.
Hxz is a shear matrix that changes x depending on z.
Hyx is a shear matrix that changes y depending on x.
Hyz is a shear matrix that changes y depending on z.
Hzx is a shear matrix that changes z depending on x.
Hzy is a shear matrix that changes z depending on y.

I hope that at least this time I was faster to correct myself than others ;)
Niki

RE: [Algorithms] How to derive transformation matrices

[Steve W. <Ste...@im...>]

> -----Original Message-----
> From: Klaus Hartmann [mailto:k_h...@os...]
> 
> Okay, I know... I said I would exit the thread, but I did a 
> mistake in my last post.
> 

OMG!  :O

> > With this I don't agree. Certainly, in the case of your box, the shear
force
> > is perpendicular to the surface of contact. But that's not necessarily
true
> > for other primitives. What about spheres for example? Imagine a sphere
that
> > is centered at the origin. The fixed plane is the x/z plane of the world
> > coordinate system, and we shear along the x-axis (y, and z are fixed).
So
> > our shear force could be represented as a vector H = <h 0 0>, where h is
the
> > magnitude of the force in x-direction. Would you still say, that the
shear
> > force if perpendicular to the surface of contact? Maybe I just
misunderstand
> > you, but for me it's not perpendicular to the surface of contact.
> 

I see your point and agree with you...I think it has finally dawned on me
why shear forces are described with reference to the shear plane.  Thanks.
Mostly what I remember about my statics class was the endless repository for
laughter called Mohr's circle, just barely edging out the slide rule...which
believe it or not was a required lesson the year before I took geometry (we
were the lucky class to be first to use a calculator), and our instructor's
slide show of when he was called off during 2 weeks of the class to help in
the assesment of the Loma Prieta earthquake of '89.

> Forget the vector H thing, which is quite incorrect, because shearing
> depends on another coordinate. Examples:
> 
> Hxy is a shear matrix that changes x depending on y.
> Hxz is a shear matrix that changes x depending on z.
> Hyx is a shear matrix that changes y depending on x.
> Hyz is a shear matrix that changes y depending on z.
> Hzx is a shear matrix that changes z depending on x.
> Hzy is a shear matrix that changes z depending on y.
> 

I found the vector thing intuitive for me...I don't use matrices but that
might help others understand.

> I hope that at least this time I was faster to correct myself 
> than others ;)
> Niki
> 

Well, I think we'll let it go this time...but one more time and...! ;)

R&R