LinuxQuestions.org
Download your favorite Linux distribution at LQ ISO.
Home Forums Tutorials Articles Register
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
Password
Programming This forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.

Notices


Reply
  Search this Thread
Old 07-17-2004, 03:10 PM   #1
The_Nerd
Member
 
Registered: Aug 2002
Distribution: Debian
Posts: 540

Rep: Reputation: 32
Math, Skellitons, and OpenGL


I am making a 3D game engine, and I have decided that I want Skellital Animation. The only problem is that I don't know my math very well, so I need some of your guys help. Check this link out about S.A.

http://nehe.gamedev.net/data/article...asp?article=03

I don't understand the last picture. What is a Matrix? Whats it used for? And what the heck to all those numbers mean that are at each joint?

I have also relized that I could easily accomplish S.A. by use of OpenGL. Just think:
B
O-------
|
| A
|

O is the joint, with the two bones connected to it and are 90˚, well, all I have to do is rotate all the vertecies on bone A 090˚ to get:
A B
-------O--------

Right? Well, is it possible in OpenGL to do a transform on just a set a vertices?

Please help me here. References, explaining, etc...

Last edited by The_Nerd; 07-17-2004 at 03:12 PM.
 
Old 07-17-2004, 04:17 PM   #2
R00ts
Member
 
Registered: Mar 2004
Location: Austin TX, USA
Distribution: Ubuntu 11.10, Fedora 16
Posts: 547

Rep: Reputation: 30
Re: Math, Skellitons, and OpenGL

Quote:
Originally posted by The_Nerd
I don't understand the last picture. What is a Matrix? Whats it used for? And what the heck to all those numbers mean that are at each joint?
[/B]
Have you taken any courses on linear algebra? Google for 'linear algebra matrix' and you should find some good sources. I'll attempt to give an explanation here:

Basically linear algebra deals with when you have a set of equations that represent a system. For example, in that triangle there are three vertices of the triangle right? So we can represent their coordinates with three variables and we can have multiple positions like:

Position #1) (c1) x + (c2) y + (c3) z = c
Position #2) (c4) x + (c5) y + (c6) z = c
Position #3) (c7) x + (c8) y + (c9) z = c

Where all the c# represent constants. Notice that each of the 3 equations add up to the same number, c. We can form a matrix out of these equations:

[c1 c2 c3]
[c4 c5 c6]
[c7 c8 c9]

Where each row represents an equation, the first column represents the x constants, 2nd column = y constants, 3rd column = z constants. Still with me?


Now looking at that NeHe tutorial, those matrices are representing the position of the joints. Those matrices describe the position of the joint in terms of x, y, z, and some other coordinate (I don't know much about openGL yet, so I have no idea what that 4th coordinate is for).


Yeah that wasn't the best explanation, sorry I tried. I think that article needs to go into detail more, its more like just a summary of skeletal animation rather than a HOW TO. Try finding another source that better explains the code behind it. Oh and you might want to pick up some linear algebra while you're at it too. 3D animators need a lot of math skills, and besides linear algebra is awesome! I use it everyday! Well.... almost everyday
 
Old 07-17-2004, 06:24 PM   #3
kev82
Senior Member
 
Registered: Apr 2003
Location: Lancaster, England
Distribution: Debian Etch, OS X 10.4
Posts: 1,263

Rep: Reputation: 51
ok ive never done skeletal animation before but i think from his very brief explanation ive kinda figured something out

this post has a few prerequisites because it'd take me ages to explain them

a) you can multiply matricies and understand how they do linear transformations
b) you know that an nth dimensional translation can be done by (n+1)th dimensional rotation or just accept we use n+1 dimension matricies
c) you know what the modelview matrix is

lets look at a nice simple 2d system with 3 joints sort of like an arm - see diagram

now imagine we are in opengl and the current modelview matrix is sitting us on top of J1 facing the theta=0 direction. so to be properly aligned with this joint you have to perform the transformation rotate by theta anticlockwise ie multiply by the matrix

Code:
(cos(theta)  sin(theta)  0)
(-sin(theta) cos(theta)  0)
(0           0           1)
so this is the matrix that gets us to J1 from our starting position.

if we now want to get to J2 from J1 we need to procede 1 unit along the x-axis(remember we've rotated theta anticlockwise) and then rotate phi anticlockwise which is represented by the matrix

Code:
(cos(phi)   sin(phi)   0) (1 0 0)
(-sin(phi)  cos(phi)   0)*(0 1 0)
(0          0          1) (1 0 1)
or

Code:
(cos(phi)   sin(phi)   0)
(-sin(phi)  cos(phi)   0)
(cos(phi)   sin(phi)   1)
then to get to J3 from J2 you need to procede 1 unit along the x-axis

given by

Code:
(1 0 0)
(0 1 0)
(1 0 1)
so basically we have these matrices and we multiply with the modelview matrix to get where we wanna go

hopefully the following psuedcode will help

Code:
//assume modelview at J1 pointing at theta=0
multiply_modelview_by(J1) //align with joint
draw_sphere() //for joint
draw_cyliner() //for bone
multiply_modelview_by(J2) //move and align with joint 2
draw_sphere() //for joint
draw_cyliner() //for bone
multiply_modelview_by(J3) //move and align with joint 
draw_sphere() //for joint
if your happy to be facing the same direction at each joint then your matrices will have the form

Code:
(1 0 0)
(0 1 0)
(a b 1)
so you can do some serious optimisation on the multiplication hence why the guy in the tutorial says its very fast

as ive just made this up from reading the tutorial i might be talking rubbish but it makes sense to me. anyone who knows what there talking about please correct me if im wrong.

Last edited by kev82; 07-17-2004 at 06:40 PM.
 
Old 07-18-2004, 01:44 PM   #4
The_Nerd
Member
 
Registered: Aug 2002
Distribution: Debian
Posts: 540

Original Poster
Rep: Reputation: 32
Ok! This is WAY over my head! I think I'll go do some reading on linear algebra and matrecies.

Btw, I have one qestion. Are matracies just a way of looking at things, and in code they are different? Or are they actually arrays of values in real world and in code?

Wait one more question!
I don't understand why there is constants in the vertex equations r00ts? Why constants? What do they do?
 
Old 07-18-2004, 01:56 PM   #5
The_Nerd
Member
 
Registered: Aug 2002
Distribution: Debian
Posts: 540

Original Poster
Rep: Reputation: 32
Ok! This post is about 5 seconds after my last one! That is because I think I may have figured out the constant thing in those eq r00ts. Tell me if I am right. (Thinking outloud here)

Lets say you have a 2D grid, I won't waste my time drawing it here, because we all know what a 2d grid looks like with the center at (0,0)

So, if we say our vertex (1, 0), then it would be one to the left of center.
Then we could say:
Vertex=(C1)x + (C2)y = c

x=1
y=0
C1=?
C2=?
c=?
Vertex=?
(remember I am thinking outloud)

....
....



....


ummm.....

Thinking isn't working...

I was thinking that the Constants C1 and C2 where the grid space, wich is constant. But I don't see how this works. I relise we can't just say a vertex in space = x+y, because that wouldn't work. Wait!!!! I might understand!

Its like a times table chart isn't it!

Pretend the times table chart is a 12x12 chart, or grid.

If we had constants, then we could find our place on the chart really easy, right? Lemme try it out:

(C1)x + (C2)y

x=3
y=0

hmmm....

something is still wrong... what is C1 and C2?

Are they transforms? Such as rotation, scale, translate? I can understand that. But then shouldn't the eq be:

(C1)x(C2)y?

Why +? Help! This thinking out loud isn't working!!!
 
Old 07-18-2004, 02:31 PM   #6
kev82
Senior Member
 
Registered: Apr 2003
Location: Lancaster, England
Distribution: Debian Etch, OS X 10.4
Posts: 1,263

Rep: Reputation: 51
by The_Nerd
Btw, I have one qestion. Are matracies just a way of looking at things, and in code they are different? Or are they actually arrays of values in real world and in code?

they are nothing more than a big array of numbers both in the real world and when you code them

I don't understand why there is constants in the vertex equations r00ts? Why constants? What do they do?

roots appears to be talking about solving a set of simultaneous equations which is one of the many applications of linear algebra but not much to do with transformations so dont worry about it.

i'll try to explain where the authors J4 matrix comes from. if im at J1 and my spatial coordinates are (x y z 1) then if i multiply by J4 i get to (x y+1 z 1) so J4 is the matrix that translates vectors by (0 1 0 0)

you cant really do much 3d at all without knowing a good amount of matrix math so i found you this link.

hth
 
Old 07-18-2004, 03:28 PM   #7
R00ts
Member
 
Registered: Mar 2004
Location: Austin TX, USA
Distribution: Ubuntu 11.10, Fedora 16
Posts: 547

Rep: Reputation: 30
Quote:
Originally posted by kev82
by The_Nerd
Btw, I have one qestion. Are matracies just a way of looking at things, and in code they are different? Or are they actually arrays of values in real world and in code?

they are nothing more than a big array of numbers both in the real world and when you code them

I don't understand why there is constants in the vertex equations r00ts? Why constants? What do they do?

roots appears to be talking about solving a set of simultaneous equations which is one of the many applications of linear algebra but not much to do with transformations so dont worry about it.

i'll try to explain where the authors J4 matrix comes from. if im at J1 and my spatial coordinates are (x y z 1) then if i multiply by J4 i get to (x y+1 z 1) so J4 is the matrix that translates vectors by (0 1 0 0)

you cant really do much 3d at all without knowing a good amount of matrix math so i found you this link.

hth
1) Just think of matrices like two dimensional arrays. That's how they are most often represented.


2) Yes sets of simulatenous equations were what I'm talking about. Like I said I don't know anything about 3D animation but I know my linear algebra and that's what I most often used it for. The link kev82 provided just covers the fundamental identities of matrix math, but it doesn't even touch on the fun stuff like eigenvector matrices Ahh I kinda miss math right now for some reason...
 
Old 07-19-2004, 05:48 AM   #8
dakensta
Member
 
Registered: Jun 2003
Location: SEUK
Distribution: Debian & OS X
Posts: 194

Rep: Reputation: 35
If I can offer another €0.02,

For learning about transformations, OpenGL could potentially be a source of confusion because there are different sets of transformations that have different effects and there are different ways to mentally visualise the results.


Using your 2D grid analogy will simplifiy things substantially. Hopefully this will not duplicate any information in the previous posts and doesn't come over too simplistic.

Imagine your (x,y) coordinate point at (1,0).
Now add a circle of radius 1, centre (0,0). Your point sits where this circle crosses the x-axis.

You want to rotate this point 45 degrees about the origin. The resulting point will also lie on the edge of the circle but no longer on the x-axis.
If you were to draw a line through the origin (0,0) and the point (1,1), you point would sit where this diagonal line crosses the edge of the circle (often called a unit-circle).

The question is, how do you calculate the new coordinates.

You use matrix multiplication:

new_point = rotation_matrix * old_point

Code:
(x)  = old_point
(y)

(x') = new_point
(y') 

(a  b) = rotation_matrix
(c  d)
To multiply these and calculate (x', y') we apply the formula in ROOts' first post:

x' = a * x + b * y
y' = c * x + d * y

From the linear algebra / simultaneous equations point of view, we often know (x, y) and (x', y') and we want to FIND a, b, c and d. This is more complicated because there is no guarantee that you will a solution exists and I would suggest that you don't worry about this side of things.

From a computer graphics / geometry point of view, we often know a, b, c, and d because we know what transformation we want to apply and we want to FIND (x', y').

For the angle 45 degrees,
a = cos(45)
b = -sin(45)
c = sin(45)
d = cos(45)
(NB the signs of b,c can swap depending on the direction of rotation)

If you want to rotate a square, you simply apply the same transformation to all 4 points or vertices that define the square.

The identity matrix is one that performs no transformation:
If a=1, b=0, c=0 and d=1 then you find :
x' = 1 * x + 0 * y = x
y' = 0 * x + 1 * y = y
i.e. the point is not transformed : (x,y) == (x', y')

For different transformations, you use different matrices, commonly you will use rotation and scaling (transforms a square into a bigger, or smaller square). You might also want to be familiar with the terms "similarity" (transforms a square into a rectangle, preserves angles in a geometric shape) and "affine" (transforms a square into a parallelogram, preserves parallel lines).

So far I have avoided translations, the most simple transformation.
The reason for this is that we have to change out coordinate system slightly.
A translated point (x', y') is described like this:
x' = x + u
y' = y + v
where u and v are values in the 2D grid. Now this is a separate addition to our transformation matrix multiplication.

BUT, it is possible to combine the transformation into a single multiplication.
Instead of writing (x,y) we call the original point (x, y, 1) and the transformed point (x', y', 1)

A three dimensional matrix multiplication with these points goes like this:
Code:
(a  b  u)     (x)     (x')
(c  d  v)  *  (y)  =  (y')
(0  0  1)     (1)     (1 )
with
x' = a* x + b * y + 1 * u
y' = c * x + d * y + 1 * v
1 = 0 * x + 0 * y + 1 * 1
so we now incorporate u and v as out translation parameters into a single matrix.
Note that a,b,c and d stay in the matrix in the same place, simply embedding a 2x2 matrix in a 3x3.
We just have to fill the appropriate spaces in the matrix with some suitable 0's and 1's.
To perform only a translation, you would set a,b,c,d to the identity matrix.

Extending this to 3D, gives us 4D vertices to represent 3D postions.
Adding the extra coordinate opens up a whole other can of worms though due to the way opengl uses it.

You have also be using matrix multiplication through the functions glRotate*, glScale* and glTranslate* which save the overhead of creating a matrix.

Seeing as you have obviously managed thus far, I would highly recommend, as a visual aid, drawing a couple of unit cubes on screen and then experimenting with glMultMatrix to see how different matrix change the cube. The compilcations in OpenGL are that you are no longer sticking to a fixed 2D coordinate system. You can change the origin, and relative coordinate systems so that it is easy to get confused about which transformations you are applying.

Check Chapter 3 and Appendix G of The Red Book too.

Anyway, I hope this helps fill in some of the gaps ... I think it is very difficult to learn the maths without active help because you will find everyone (computer bods, mathematicians of a hundred different flavours, physicists, economists and so on) has their own little (or large) subset of an enormous topic and describes it in their own way in there own terms. Lots of aspects are related (fancy describing transformations in terms of eigenvectors and values?) and crop up all over the place under different topics.

Good Luck

[BIG EDIT]
Ok, just noticed this and I don't want to cause confusion:

Quote:
then to get to J3 from J2 you need to procede 1 unit along the x-axis given by
Code:
(1 0 0)
(0 1 0)
(1 0 1)
so basically we have these matrices and we multiply with the modelview matrix to get where we wanna go
Here, kev82 has expressed the translation:
Code:
(1 0 0)
(0 1 0)
(u v 1)
This is the same as my explantion, except he is performing calculations like this:
Code:
(x  y  1) * (a  c  0)  =  (x'  y'  1)
            (b  d  0)
            (u  v  1)
where as I would write it differently. They are the same calculation, except that the transformation matrix and vertices have been transposed (column swapped with rows).

Last edited by dakensta; 07-19-2004 at 11:09 AM.
 
Old 07-19-2004, 08:32 AM   #9
deiussum
Member
 
Registered: Aug 2003
Location: Santa Clara, CA
Distribution: Slackware
Posts: 895

Rep: Reputation: 32
I don't have much to add to what's already been said, but thought I might try to take a higher level view in describing matrices from OpenGL's perspective. You may already realize that OpenGL has a few different matrices defined. The ones that are mostly used are GL_PROJECTION and GL_MODELVIEW. There is also GL_TEXTURE for transforming texture coordinates, and I've seen specs for a GL_COLOR matrix, for transforming color, though I'm not sure I've ever seen an OpenGL implementation that actually supports this one...

The GL_PROJECTION matrix is used to define the viewing volume. It can either be an orthographic projection, a perspective projection, or some custom projection if you know what you are doing... Think of this matrix as defining the properties of your camera such as field of view, depth of field, etc. It basically represents the shape of the area that is viewable.

GL_MODELVIEW is usually used to represent the transformations of the camera and objects within your scene. Camera transformations are generally done first, which I will explain a bit more below. Camera transformations are actually done as if you were moving the world the opposite of the way you move the camera, so in this regard, OpenGL doesn't have a real "camera" per se. (e.g. Moving the world back 5 spaces is the same as moving the camera forward 5 spaces, etc.)

Now, when you use functions like glMatrixMode, you are setting which of OpenGL's matrices you will be performing operations on. You can think of it as though OpenGL has state variables with the contents of each of the matrices that it knows about. Much the same way it has state variables of most other things. That is why OpenGL is considered a state machine.

The glLoadIdentity basically sets the current matrix to a value that, when multiplied by another matrix, you will get the result of that other matrix. It is much like 1 in simple multiplication. 5*1 = 5, SomeMatrix * Identity = SomeMatrix, etc.

Functions like glRotate, glTranslate, glScale all create a matrix representing the transformation that they do and multiply it to the current matrix.

So, if you think of the following bit of code:

glLoadIdentity();
glTranslate(...)
glRotate(...)

You can think of OpenGL as doing the following:

currentMatrix = Identity
currentMatrix *= translationMatrix
currentMatrix *= rotationMatrix

You now have a single matrix that represents both a translation and a rotation. You should note that if you have 2 different matrices, M1 and M2, that M1 * M2 is NOT necessarily equal to M2 * M1!

Because of the way OpenGL does it's matrix multiplication, if you think in terms of world coordinates, the last matrix you multiplied is actually the one that appears to be done first. (Although, underneath it is all still just a vertex being multiplied by a single matrix) If you take a piece of paper and draw an origin, you can visualize this a bit better. if you translate along the X-axis, then rotate around the origin, you get a totally different position than if you do this in the reverse order. This is why camera transformations are done first. If you did camera transformations last, you wouldn't get the effect you would expect. It takes a little bit of thinking to get this right sometimes.

There are also functions like glLoadMatrix and glMultMatrix that basically lets you do all the matrix multiplication yourself if you wish.

OpenGL also has a matrix stack, which can be useful for skeletal animation. This basically pushes the current matrix onto the top of the stack, saving it to be restored later. Usually you do this if you want to preserve the matrix for other objects, but make modifications to it for the current object you want to draw.

For instance, for a simple solar system animation, you might do something like so:

Code:
glLoadIdentity();
doCameraTransformation();

drawSun();

for(each planet)
{
   glPushMatrix();
   glRotate(planet orbit around sun)
   glTranslate(planet distance from sun);
   glPushMatrix();
   glRotate(planet rotation about it's axis); 
   drawPlanet();   
   glPushMatrix();
   for (each moon of planet)
   {
       glPushMatrix();
       glRotate(moon's orbit around planet);
       glTranslate(moon's distance from planet);
       glRotate(moon's rotation about it's axis);
       DrawMoon();
       glPopMatrix();
    }
    glPopMatrix();
}
You can extend this to thinking of ways to move the appendages of a skeleton in a similar fasion...

Anyway, hope that clears up matrices a bit from an OpenGL perspective, w/o having to go too far into the details of matrix math.

As you can possibly see now, some of the fun details are in OpenGL itself, and the windowing system you use to create the window (SDL vs. Glut vs. GLFW vs. OS dependent calls) is all just a boring argument on how you can get to start using OpenGL.

Last edited by deiussum; 07-19-2004 at 08:53 AM.
 
Old 07-19-2004, 11:33 AM   #10
The_Nerd
Member
 
Registered: Aug 2002
Distribution: Debian
Posts: 540

Original Poster
Rep: Reputation: 32
Cool guys. I don't have time to read all those pages and stuff but they look great! I thank you all, and I promis I will read all this when I find time. I think I am starting to understand all this a little more. I also want to tell you guys that I DO understand simultaneous equations. Matrecies are still out there for me, but I think I may be starting to understand them as well.

Again thank you for all your help.


So your saying if I make my own matrecies for transform, scale, and rotate in OpenGL then it will be allot faster then using glRotate*, glScale*, and glTranslate*?
 
Old 07-19-2004, 12:47 PM   #11
dakensta
Member
 
Registered: Jun 2003
Location: SEUK
Distribution: Debian & OS X
Posts: 194

Rep: Reputation: 35
Quote:
So your saying if I make my own matrecies for transform, scale, and rotate in OpenGL then it will be allot faster then using glRotate*, glScale*, and glTranslate*?
Yikes! No! The opposite!
glRotate etc. are given because they are specific examples of transformations and have been implemented in a highly optimised form.

Where you need a more general matrix (or want to experiment as part of learning) then you can create your own matrix. There are more transformation types available than Scale, Rotate and Translate but these form the most common subset and can be applied through fewer calculations than the generic 4x4 matrix multiplication.

People have contributed an explanation of the skeletal geomtery tutorial, basic linear transformations and OpenGL's application of transformations,

Understanding these basics enables you to design things like the skeletal animation yourself. Leave the implementation of the calculations to OpenGL except where you really, really, REALLY need to do it yourself.
 
  


Reply



Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off



Similar Threads
Thread Thread Starter Forum Replies Last Post
math.h Damicles Programming 9 12-04-2010 05:51 AM
Overwrite Mesa OpenGL with ATI OpenGL Carl-Fredrik Slackware 12 10-01-2004 03:33 PM
c math calculation alaios Programming 3 06-01-2004 01:46 AM
Changing from MESA OpenGL to ATI OpenGL tillyoubreakit Linux - Hardware 19 10-07-2003 07:32 PM
OpenGL is needed by plib-1.7.0- but i have opengl ! qwijibow Linux - Newbie 0 08-05-2003 07:12 AM

LinuxQuestions.org > Forums > Non-*NIX Forums > Programming

All times are GMT -5. The time now is 08:45 PM.

Main Menu
Advertisement
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
Open Source Consulting | Domain Registration