gdalgorithms-list

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] Tris intersection

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

Yup, thats what that suggestion from someone else does, in coplanar cases -
in fact its quite neat, I wish I'd thought of it.  Just test for
intersection (total of 9 intersection tests any one of which can return true
- very nice if you expect most cases to intersect) and then if still not
determined just test if any point of one is in the other, which because
there are now no intersections means you only have to test one point of each
against the other.

Rob

-----Original Message-----
From: Steve Wood [mailto:Ste...@im...]
Sent: 24 July 2000 17:52
To: 'gda...@li...'
Subject: RE: [Algorithms] Tris intersection


Oh...your right...checking to see if any of the line segments intersect
would be a better test.

R&R

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] Tris intersection

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

Oh...your right...checking to see if any of the line segments intersect
would be a better test.

R&R

> From: Robert Dibley [mailto:RD...@ac...]
> 
> This is not valid for all cases, since it is possible to have two
> intersecting triangles where none of the vertices of either 
> triangle are in
> the other one ... like this
> 
>        a
>        |\
>        | \
>    x---+--\------y
>    |   |   \    /
>    |   |    \  /
>    |   |     \/
>    |   |     /\
>    |   |    /  \
>    |   |   /    \
>    |   |  /      \
>    |   | /        \
>    |   |/          \
>    |   /            \
>    |  /|             \
>    | / |              \
>    |/  b---------------c
>    z
> 
> in which case no point will give you the same area when used 
> to make three
> more triangles.
> 
> The only guaranteed way I know is to test each edge to see if 
> the other
> triangle is completely 'outside' it, which simply requires three
> cross-products for each case, and you must test all six edges 
> to be certain
> that you haven't missed one.  I'm sure there must be an 
> easier way, but I've
> never bothered to figure one out.
> 
> Robert
> 
> -----Original Message-----
> From: Steve Wood [mailto:Ste...@im...]
> Sent: 24 July 2000 03:59
> To: 'gda...@li...'
> Subject: RE: [Algorithms] Tris intersection
> 
> 
> I think the best way to find if the triangles intersect is to 
> take the 3
> vertexes from each triangle one at a time and use it to 
> divide the other
> triangle up into three separate triangles (geometry now not 
> math).  If the
> sum of the area of the three triangles is equal to the area 
> of the whole
> triangle then the triangles intersect (OK, put away your 
> thought compass and
> do the math).  You will need to do this 6 times, 3 times for each
> triangle...  Once you find a vertex where the areas are equal 
> then they
> intersect and you won't have to do the rest of them.
> 
> It's impossible to illustrate with ansii characters so in 
> your mind draw a
> line from point p which represents one of the vertices from the other
> triangle to each vertex a, b, and c to divide the triangle into 3
> triangles...add up the sum of the three triangles, apc, bpa, 
> cpb and compare
> it to the area of abc.  If They are equal then the point is 
> inside, or on
> the triangle (be sure to allow some margin of error for 
> rounding).  Sound
> like a plan?
> 
> a        intersects                    a       does not intersect
> |\                                     |\
> | \                                    | \
> |  \                                   |  \
> |   \                                  |   \
> |    \                                 |    \
> |     \                                |     \
> |      \                               |      \
> |       \                              |       \
> |    .   \                             |        \     .
> |    p    \                            |         \    p
> |          \                           |          \
> |___________\                          |___________\
> c            b                         c            b
> 
> 
> If it solves analytic geometry problems to relax after 10 
> hours of straight
> TFC and Q3A-CTF then it's,
> Rockn-Roll
> 
> 
> > -----Original Message-----
> > From: Jeffrey C [mailto:pl...@as...]
> > Sent: Sunday, July 23, 2000 5:54 PM
> > To: gda...@li...
> > Subject: [Algorithms] Tris intersection
> > 
> > 
> > Hi,
> > 
> > Anyone could tell me a quick way to know whether 2 triangle 
> > that lie on the same plane
> > intersect each other?
> > Let say that I have triangle A(a0,a1,a2) and B(b0,b1,b2), 
> > here is some example that the
> > triangles intersect each other.
> > 
> > |\  /|
> > | / B|
> > | -\--
> > |___\
> >  A
> > 
> >      /|
> >     / |
> >    / B|
> >   /   |
> >  / |\ |
> > /--| \-
> >    |A \
> >    ----
> > 
> > 
> > 
> > 
> > 
> > _______________________________________________
> > GDAlgorithms-list mailing list
> > GDA...@li...
> > http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
> > 
> 
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
> 
> _______________________________________________
> 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] Where is the enemy?

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

Come to think of it...the vector can be eliminated since it's in both
equations...just this test need be done:

if Px + Py + Pz > P1x + P1y + P1z then it's to the right
if Px + Py + Pz < P1x + P1y + P1z then it's to the left
if Px + Py + Pz = P1x + P1y + P1z then it's straight ahead

R&R

> From: Aldo . [mailto:al...@ho...]
> How can I decide wich side must I turn?
> 
> I've tried cross product, but it doesn't worked fine.
> 
> Any sugestions?
> 

Hmm, how about using the equation of a plane which has at it's normal a
vector V pointing at a right angle to the up and forward vectors and
positive to the right:

VxP1x + VyP1y + VzP1z = C1

Where C1 would be an index to compare with C in

VxPx + VyPy + VzPz = C

that tells you if point P is to the right (C>C1) or left (C<C1).

R&R

RE: [Algorithms] Rendering (a portion of) a Plane

[Jeremy B. <Jer...@in...>]

thanks Angel Popov exactly what I was 
looking for

and just to clarify...
the extraction of clipping planes I was 
referring to was the code that's been 
going around (posts I remember are from
Gil Grib) where you get the final
transformation matrix then

row[3] + row[0]
row[3] - row[0]
row[3] + row[1]
row[3] - row[1]
row[3] + row[2]
row[3] - row[2]

each of these resulting 4Vectors
represent normalX, normalY, normalZ, dist
and seem to work great I just wanted 
to visualize them externally.

Jeremy Bake
RtroActiv 

RE: [Algorithms] Where is the enemy?

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

> From: Aldo . [mailto:al...@ho...]
> How can I decide wich side must I turn?
> 
> I've tried cross product, but it doesn't worked fine.
> 
> Any sugestions?
> 

Hmm, how about using the equation of a plane which has at it's normal a
vector V pointing at a right angle to the up and forward vectors and
positive to the right:

VxP1x + VyP1y + VzP1z = C1

Where C1 would be an index to compare with C in

VxPx + VyPy + VzPz = C

that tells you if point P is to the right (C>C1) or left (C<C1).

R&R

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] Where is the enemy?

[Ray <ra...@gu...>]

"Aldo ." wrote:
> 
> I'm building the AI module of my game, but I have a problem.
> 
> Imagine you as a space ship pilot in the deep space. Your enemy apears on
> the radar screen. You are at the "p1" position, "d" is your direction and
> "u" is your up vector. Your enemy is at the position "p2".
> How can I decide wich side must I turn?
>
...clip...
> 
> Any sugestions?
> 
> Thanks in advance.
> 
> Aldo

Hi,
Do you want your ship's up vector to match the enemy ship's up vector?
in outerspace that's not really necessary since there is no true up.

Ok, so what I would do is to use a quaternion to define a rotation from
your orientation to the enemy's orientation.
Get the direction of the enemy relative to you and your forward
direction.
Do a cross product and that's the axis around which you rotate.
Do a dot product and that's the cosine of the angle which you rotate
around that rotation axis.

Then the rest is simple algebra to make a quaternion.
Then you use that quaternion and turn it into a rotation matrix and appy
it to your ship.
Or
if you have stored your current orientation as a quaternion, and with
the new quaternion you can SLERP from one quaternion to the other over
time. To do this though you must calc the new quaternion as an absolute
quaternion as opposed to one that is applied to your current
orientation.

I hope this helps a little.

- Ray

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.  

RE: [Algorithms] Where is the enemy?

[Ignacio C. <i6...@ho...>]

Aldo wrote:
> Any sugestions?

Try using quaternions to interpolate the direction vectors and then get back the euler angles.


Ignacio Castano
ca...@cr...

[Algorithms] Where is the enemy?

[Aldo . <al...@ho...>]

Hi!

I'm building the AI module of my game, but I have a problem.

Imagine you as a space ship pilot in the deep space. Your enemy apears on 
the radar screen. You are at the "p1" position, "d" is your direction and 
"u" is your up vector. Your enemy is at the position "p2".
How can I decide wich side must I turn?

Something like this:

auxVect = p2 - p1;

Calculate relative position based on auxVect, d and u;


if ( enemy at left )
  yaw += turnSpeed;
else
  yaw -= turnSpeed;


if ( enemy is above )
  pitch += tunSpeed;
else
  pitch -= tunSpeed;



I've tried cross product, but it doesn't worked fine.

Any sugestions?

Thanks in advance.

Aldo

________________________________________________________________________
Get Your Private, Free E-mail from MSN Hotmail at http://www.hotmail.com

RE: [Algorithms] Tris intersection

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

This is not valid for all cases, since it is possible to have two
intersecting triangles where none of the vertices of either triangle are in
the other one ... like this

       a
       |\
       | \
   x---+--\------y
   |   |   \    /
   |   |    \  /
   |   |     \/
   |   |     /\
   |   |    /  \
   |   |   /    \
   |   |  /      \
   |   | /        \
   |   |/          \
   |   /            \
   |  /|             \
   | / |              \
   |/  b---------------c
   z

in which case no point will give you the same area when used to make three
more triangles.

The only guaranteed way I know is to test each edge to see if the other
triangle is completely 'outside' it, which simply requires three
cross-products for each case, and you must test all six edges to be certain
that you haven't missed one.  I'm sure there must be an easier way, but I've
never bothered to figure one out.

Robert

-----Original Message-----
From: Steve Wood [mailto:Ste...@im...]
Sent: 24 July 2000 03:59
To: 'gda...@li...'
Subject: RE: [Algorithms] Tris intersection


I think the best way to find if the triangles intersect is to take the 3
vertexes from each triangle one at a time and use it to divide the other
triangle up into three separate triangles (geometry now not math).  If the
sum of the area of the three triangles is equal to the area of the whole
triangle then the triangles intersect (OK, put away your thought compass and
do the math).  You will need to do this 6 times, 3 times for each
triangle...  Once you find a vertex where the areas are equal then they
intersect and you won't have to do the rest of them.

It's impossible to illustrate with ansii characters so in your mind draw a
line from point p which represents one of the vertices from the other
triangle to each vertex a, b, and c to divide the triangle into 3
triangles...add up the sum of the three triangles, apc, bpa, cpb and compare
it to the area of abc.  If They are equal then the point is inside, or on
the triangle (be sure to allow some margin of error for rounding).  Sound
like a plan?

a        intersects                    a       does not intersect
|\                                     |\
| \                                    | \
|  \                                   |  \
|   \                                  |   \
|    \                                 |    \
|     \                                |     \
|      \                               |      \
|       \                              |       \
|    .   \                             |        \     .
|    p    \                            |         \    p
|          \                           |          \
|___________\                          |___________\
c            b                         c            b


If it solves analytic geometry problems to relax after 10 hours of straight
TFC and Q3A-CTF then it's,
Rockn-Roll


> -----Original Message-----
> From: Jeffrey C [mailto:pl...@as...]
> Sent: Sunday, July 23, 2000 5:54 PM
> To: gda...@li...
> Subject: [Algorithms] Tris intersection
> 
> 
> Hi,
> 
> Anyone could tell me a quick way to know whether 2 triangle 
> that lie on the same plane
> intersect each other?
> Let say that I have triangle A(a0,a1,a2) and B(b0,b1,b2), 
> here is some example that the
> triangles intersect each other.
> 
> |\  /|
> | / B|
> | -\--
> |___\
>  A
> 
>      /|
>     / |
>    / B|
>   /   |
>  / |\ |
> /--| \-
>    |A \
>    ----
> 
> 
> 
> 
> 
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
> 

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

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

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] Tris intersection

[Andrew S. <as...@di...>]

You could just use Moller's (excellent) triangle/triangle intersection code
- no point in re-inventing the wheel

- andrew

http://www.ce.chalmers.se/staff/tomasm/code/

> -----Original Message-----
> From: Steve Wood [mailto:Ste...@im...]
> Sent: Sunday, July 23, 2000 9:59 PM
> To: 'gda...@li...'
> Subject: RE: [Algorithms] Tris intersection
> 
> 
> I think the best way to find if the triangles intersect is to 
> take the 3
> vertexes from each triangle one at a time and use it to 
> divide the other
> triangle up into three separate triangles (geometry now not 
> math).  If the
> sum of the area of the three triangles is equal to the area 
> of the whole
> triangle then the triangles intersect (OK, put away your 
> thought compass and
> do the math).  You will need to do this 6 times, 3 times for each
> triangle...  Once you find a vertex where the areas are equal 
> then they
> intersect and you won't have to do the rest of them.
> 
> It's impossible to illustrate with ansii characters so in 
> your mind draw a
> line from point p which represents one of the vertices from the other
> triangle to each vertex a, b, and c to divide the triangle into 3
> triangles...add up the sum of the three triangles, apc, bpa, 
> cpb and compare
> it to the area of abc.  If They are equal then the point is 
> inside, or on
> the triangle (be sure to allow some margin of error for 
> rounding).  Sound
> like a plan?
> 
> a        intersects                    a       does not intersect
> |\                                     |\
> | \                                    | \
> |  \                                   |  \
> |   \                                  |   \
> |    \                                 |    \
> |     \                                |     \
> |      \                               |      \
> |       \                              |       \
> |    .   \                             |        \     .
> |    p    \                            |         \    p
> |          \                           |          \
> |___________\                          |___________\
> c            b                         c            b
> 
> 
> If it solves analytic geometry problems to relax after 10 
> hours of straight
> TFC and Q3A-CTF then it's,
> Rockn-Roll
> 
> 
> > -----Original Message-----
> > From: Jeffrey C [mailto:pl...@as...]
> > Sent: Sunday, July 23, 2000 5:54 PM
> > To: gda...@li...
> > Subject: [Algorithms] Tris intersection
> > 
> > 
> > Hi,
> > 
> > Anyone could tell me a quick way to know whether 2 triangle 
> > that lie on the same plane
> > intersect each other?
> > Let say that I have triangle A(a0,a1,a2) and B(b0,b1,b2), 
> > here is some example that the
> > triangles intersect each other.
> > 
> > |\  /|
> > | / B|
> > | -\--
> > |___\
> >  A
> > 
> >      /|
> >     / |
> >    / B|
> >   /   |
> >  / |\ |
> > /--| \-
> >    |A \
> >    ----
> > 
> > 
> > 
> > 
> > 
> > _______________________________________________
> > GDAlgorithms-list mailing list
> > GDA...@li...
> > http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
> > 
> 
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
> 

RE: [Algorithms] Tris intersection

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

I think the best way to find if the triangles intersect is to take the 3
vertexes from each triangle one at a time and use it to divide the other
triangle up into three separate triangles (geometry now not math).  If the
sum of the area of the three triangles is equal to the area of the whole
triangle then the triangles intersect (OK, put away your thought compass and
do the math).  You will need to do this 6 times, 3 times for each
triangle...  Once you find a vertex where the areas are equal then they
intersect and you won't have to do the rest of them.

It's impossible to illustrate with ansii characters so in your mind draw a
line from point p which represents one of the vertices from the other
triangle to each vertex a, b, and c to divide the triangle into 3
triangles...add up the sum of the three triangles, apc, bpa, cpb and compare
it to the area of abc.  If They are equal then the point is inside, or on
the triangle (be sure to allow some margin of error for rounding).  Sound
like a plan?

a        intersects                    a       does not intersect
|\                                     |\
| \                                    | \
|  \                                   |  \
|   \                                  |   \
|    \                                 |    \
|     \                                |     \
|      \                               |      \
|       \                              |       \
|    .   \                             |        \     .
|    p    \                            |         \    p
|          \                           |          \
|___________\                          |___________\
c            b                         c            b


If it solves analytic geometry problems to relax after 10 hours of straight
TFC and Q3A-CTF then it's,
Rockn-Roll


> -----Original Message-----
> From: Jeffrey C [mailto:pl...@as...]
> Sent: Sunday, July 23, 2000 5:54 PM
> To: gda...@li...
> Subject: [Algorithms] Tris intersection
> 
> 
> Hi,
> 
> Anyone could tell me a quick way to know whether 2 triangle 
> that lie on the same plane
> intersect each other?
> Let say that I have triangle A(a0,a1,a2) and B(b0,b1,b2), 
> here is some example that the
> triangles intersect each other.
> 
> |\  /|
> | / B|
> | -\--
> |___\
>  A
> 
>      /|
>     / |
>    / B|
>   /   |
>  / |\ |
> /--| \-
>    |A \
>    ----
> 
> 
> 
> 
> 
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
> 

Re: [Algorithms] How to derive transformation matrices

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

Lorrimar  wrote:

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

Right.  The internet is not a good place to look for such elementary
derivations.  Fortunately, there are tons of math textbooks that give
them.  Check you  local library.

[Algorithms] Tris intersection

[Jeffrey C <pl...@as...>]

Hi,

Anyone could tell me a quick way to know whether 2 triangle that lie on the same plane
intersect each other?
Let say that I have triangle A(a0,a1,a2) and B(b0,b1,b2), here is some example that the
triangles intersect each other.

|\  /|
| / B|
| -\--
|___\
 A

     /|
    / |
   / B|
  /   |
 / |\ |
/--| \-
   |A \
   ----

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] Bullets on walls

[Tom F. <to...@mu...>]

If you are using a small texture with clamp-to-edge mode, the scanline
conversion still has to be done (consuming pipeline clocks), but it will
just read the same texels over and over again (the edge ones) for most of
the drawing. So it won't compete for memory bandwidth.

Older chips won't see much benefit - they were indeed core-bound most of the
time, not memory-bound (or at least the core wasn't far behind the memory),
but newer chips will love you silly, especially in 32bpp modes.

Tom Forsyth - Muckyfoot bloke.
Whizzing and pasting and pooting through the day.

> -----Original Message-----
> From: Stephen J Baker [mailto:sj...@li...]
> Sent: 21 July 2000 18:38
> To: gda...@li...
> Cc: ma...@ci...
> Subject: RE: [Algorithms] Bullets on walls
> 
> 
> On Fri, 21 Jul 2000, Mark Atkinson wrote:
> 
> > We do it this way:
> > 
> > If the decal does not cross a polygon boundary with a high 
> enough crease 
> > angle, draw it as a quad.  Use ZBIAS if supported and/or 
> move it along the 
> > normal to lift it off the surface.
> > 
> > Otherwise draw it as decal, as per Jaimi's method.  
> Remember to enable 
> > ALPHATEST so there's no overdraw or fill-rate hit even if 
> the base triangle 
> > is large and has several decals.
>  
> Eh?
> 
> Alpha Test (presuming it's the same mechanism as glAlphaFunc 
> in OpenGL)
> won't eliminate (all of) the overdraw/fillrate issues.  The renderer
> still has to scan-convert all those pixels, do the texture calculation
> on each one and compare the alpha value against the threshold.
> 
> * On some hardware, that'll be no cheaper than drawing the 
> entire polygon.
> 
> * On other hardware, you'll only pay *some* per pixel cost 
> (maybe half).
> 
> * It'll never be zero though - that's impossible - it has to consume
>   some texture bandwidth per-pixel of the entire polygon.
> 
> 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

[Algorithms] How to derive transformation matrices

[Lorrimar <lor...@tr...>]

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

RE: [Algorithms] Bullets on walls

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

	The N64 supports this op. It was used for the bullet holes in Perfect Dark
(and Goldeneye.). It still doesn't give a glitch free result. It does 'clip'
to the edges on polygons when the decal goes over the edge of the polygon
its sat on, but its really just scissoring with Z to do that.
	One thing to remember is that the error in the z slope calculations on the
small decal polygon is higher than that on a larger (in screen space)
polygon. So you are always going to have some accuracy worries. Using one
decal polygon the same size as the surface it's resting on may work very
well. With individual decals someone will always get them all on one wall if
you let them - which is a big hit with individual decals, small with one big
decal.
	Unless you can use precisely the same polygon for generating Z values you
will need to add Z-bias to minimize glitching.

-Brian.
> -----Original Message-----
> From: gda...@li...
> [mailto:gda...@li...]On Behalf Of Tom
> Forsyth
> Sent: Friday, July 21, 2000 2:35 PM
> To: gda...@li...
> Subject: RE: [Algorithms] Bullets on walls
>
>
> We know. Nothing on the planet supports something like
> ALPMOST_EQUAL as far
> as I know (and even if it did, that still has problems when things walk
> beside the walls).
>
> You will have to either clip the decals to the wall
> geometrically; draw the
> wall poly with clamp texture mode & the right UVs; or composite the decals
> onto a wall-shaped poly, as suggested. If drawing individual decals, which
> seems a popular method, then you will need some sort of Z-bias
> functionality, which is what glPolygonOffset and moving the clip planes
> gives you.
>
> Tom Forsyth - Muckyfoot bloke.
> Whizzing and pasting and pooting through the day.
>
> > -----Original Message-----
> > From: Angel Popov [mailto:ju...@bi...]
> > Sent: 21 July 2000 15:50
> > To: gda...@li...
> > Subject: Re: [Algorithms] Bullets on walls
> >
> >
> > No, neither glPolygonOffset or moving the near clipplane will
> > have the same
> > functionality as the non-existent glDepthFunc( GL_ALMOST_EQUAL )
> > because these two approaches will not fix the problem with
> > the wallmark
> > not getting clipped at wall corners.
> >
> >
> > > For D3D (and probably OpenGL), a good alternative is to
> > move the near &
> > far
> > > clip planes a bit further away for those tris. You only
> > need to move the
> > > near clip plane if using Z-buffering. If using W-buffering,
> > you'll need to
> > > move both.
> > >
> > > Tom Forsyth - Muckyfoot bloke.
> > > Whizzing and pasting and pooting through the day.
> > >
> > > > -----Original Message-----
> > > > From: Neal Tringham [mailto:ne...@ps...]
> > > > Sent: 21 July 2000 10:56
> > > > To: gda...@li...
> > > > Subject: Re: [Algorithms] Bullets on walls
> > > >
> > > >
> > > >
> > > > Giovanni Bajo <ba...@pr...> writes:
> > > > > In DirectX, there is a ZBIAS stuff that let you set a
> > priority order
> > > > > (integer) when Z matches. It is a renderstate. But looking
> > > > at the caps, it
> > > > > is not supported in every boards I have tried. I heard
> > it is an old
> > > > thingie
> > > > > of first Voodoo boards.
> > > >
> > > > Yes, the support for zbias seems to be rather inconsistent.
> > > >
> > > > > I had not found something similiar in OpenGL.
> > > >
> > > > You may want to look at the 1.1 glPolygonOffset function.
> > > >
> > > >
> > > > Neal Tringham (Sick Puppies)
> > > >
> > > > ne...@ps...
> > > > ne...@em...
> >
> >
> > _______________________________________________
> > GDAlgorithms-list mailing list
> > GDA...@li...
> > http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
> >
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
>