Kuro5hin.org: technology and culture, from the trenches
create account | help/FAQ | contact | links | search | IRC | site news
[ Everything | Diaries | Technology | Science | Culture | Politics | Media | News | Internet | Op-Ed | Fiction | Meta | MLP ]
We need your support: buy an ad | premium membership

[P]
Introductory Basic 3D Transformations 101 Made Easy for Dummies in 30 Days

By spcmanspiff in Technology
Mon Dec 09, 2002 at 04:31:18 AM EST
Tags: Software (all tags)
Software

The problem:

You have a bunch of 3D data. This data describes an object -- usually by a big list of coordinate points.

So how do you get it onto the screen?

This very informal article assumes rudimentary familiarity with vector geometry.


Transformation the First

Well, first of all, our data (say it's a cube, with its center at the origin and width,height,length of 1,1,1) exists someplace. The box is placed somewhere in the world. For example, say that the point (0,0,0) in your coordinate list -- object space -- is really at (13,-10,0) in world space.

Before we start worrying about getting it in the right place on the screen, first we should move it to the proper place in the universe. So we add (13,-10,0) to every data point.

Our box is now transformed to world space!

Transformation the First: Redux

But wait! not only is the box moved somewhere, but it's been turned some, too. Horrors! Obviously, we can't deal with this simply by adding...

So, we break out some high school trig. Say the box was rotated by 45 degrees around the Y axis. So, for every data point we do a bit of math:

  • newx = x * cos(45) - z * sin(45)
  • newy = y
  • newz = x * sin(45) + z * cos(45)
Once we've done that, the box is rotated and all we need to do is add the translation and move the box to its place in the world.

Transformation the First: But isn't that slow?

Yes, it is. And to make matters worse, it gets much more complicated if, say, you wanted your box rotated around some arbitrary vector instead of an euler axis. And if you stick to axes, then you'll feel the pain of gimbal lock sooner or later.

Let's take a different approach. Imagine what happens to the coordinate system of the box as it's rotated: What was once directly to the right (along the x axis) becomes 45 degrees back and to the right. What was directly back becomes back and to the left. And so on --- for any rotation, you can come up with a new vectors A, B, and C so that whatever was once n units along the X axis from the origin is now n units along A; whatever was n units along Y is now n units along B, etc.

With this idea in hand, we can rotate things by replacing every point as follows:

(nx,ny,nz) = (x * A) + (y * B) + (z * C)

We can turn it into coordinate form:

  • nx = (x * Ax) + (y * Bx) + (z * Cx)
  • ny = (x * Ay) + (y * By) + (z * Cy)
  • nz = (x * Az) + (y * Bz) + (z * Cz)
This is pretty good, as far as rotating stuff. But wait! That particular result looks somehow familiar.

| Ax Bx Cx |   |x|   |nx|
| Ay By Cy | * |y| = |ny|
| Az Bz Cz |   |z|   |nz|

If we multiply this out, we get:

  • nx = (x * Ax) + (y * Bx) + (z * Cx)
  • ny = (x * Ay) + (y * By) + (z * Cy)
  • nz = (x * Az) + (y * Bz) + (z * Cz)
What a coincidence! It looks like 3x3 matrices are perfect for 3D rotation.

Furthermore, they're also useful for scaling: For example, to make something twice as large along the x axis, all we need to do is use an A of (2,0,0) instead of the boring Euler axis of (1,0,0). You can build the matrix using A, and keeping B and C at (0,1,0) and (0,0,1) respectively, and see how every x gets replaced with 2x.

Neat, huh?

Yet More Transformation the First
But I want to rotate around something other than the origin!

Easy. Just translate your object to the point you want to rotate around (newpoint = point - rotation_center) and do your rotation (newerpoint = newpoint * rotation_matrix), then translate it back (newestpoint = newerpoint + rotation_center).

So how do I come up with A,B, and C for my rotation?

Well, you plug your rotation u around an axis Q into this formula. If you're smart, you've already derived it, haven't you?

Ax = (1-cos(u)) * Qx^2 + cos(u)
Ay = (1-cos(u)) * Qx * Qy + sin(u) * Qz
Az = (1-cos(u)) * Qx * Qz - sin(u) * Qy
Bx = (1-cos(u)) * Qx * Qy - sin(u) * Qz
By = (1-cos(u)) * Qy^2 + cos(u)
Bz = (1-cos(u)) * Qy * Qz + sin(u) * Qx
Cx = (1-cos(u)) * Qx * Qz + sin(u) * Qy
Cy = (1-cos(u)) * Qy * Qz - sin(u) * Qx
Cz = (1-cos(u)) * Qz^2 + cos(u)

Please note that, personally, I'm far too lazy to derive anything, so I looked this up and typed it in. I probably made mistakes. Also, if Q isn't unit length, interesting things will happen. Enjoy the troubleshooting!

The First Transformation: Object -> World

So now we know how to take a bunch of objects, rotate them appropiately and place them in the world:

  • Translate to the center of its rotation
  • Rotate around its axis of rotation
  • Translate back to its origin
  • Translate to its position in world-space
Cake!

So how do we get "the world" onto the screen, then?

The Camera Transformation

Not being all-knowing and all-seeing, only part of the world will be visible. Since we're not dealing with perspective yet, that part will be shaped like a box.

We could start by trying to figure out where that box should be in the world, given the camera position and orientation:

  • Scale a 1x1x1 cube so its dimensions are equal to the width, height, and depth of the area that the camera can see.
  • Rotate it to point in the camera's direction
  • Move it to the camera's position in the world
But this is backwards: We're trying to put the world into the camera, not the camera into the world!

So that's what we'll do -- transform world space into camera space:

  • Move the world to the camera origin. (Subtract the camera's position from every point in the world.)
  • Rotate the world until the camera isn't rotated at all. (This is the opposite rotation from the one to orient the camera above)
  • Scale the world by the inverse of the visible rectangle's dimensions
Now the entirety of the visible world is within a 1x1x1 cube!

Getting It To the Screen

But the screen doesn't use coordinates like that -- we need X's and Y's from 640 to 480, not zero to one. The solution? Transform it again, into viewport space.

This is a simple matter of scaling X values by 640, and Y by 480 (or whatever the viewport's width and height are.)

Or is it? If your world space is like most world, then positive Y values are "up." But on the screen, increasing Y values are "down." Everything is upside-down! To fix this, we need to make all Y values negative: Scale by (0,-1,0) first.

Thus, the final steps before actually drawing our data:

  • Flip the world upside-down by scaling Y values by -1
  • Scale X and Y by the size of your scene in pixels.
Pheew!

Finally, you have your data in screen coordinates that can be displayed directly, for pretty 3D goodness. It might be a good idea to sort your data by z and draw from back-to-front, so objects only get drawn over the top of other ones if they're in front, and to clip things to your viewport so you aren't spending a lot of time drawing items that are off the screen, etc etc etc ... (this is a whole 'nother series).

That's it for now, but watch for...

Next time: Homogenous coordinate systems and more matrices! Adding a bit of perspective to the picture! The glory and joy that is OpenGL!

 

Sponsors

Voxel dot net
o Managed Hosting
o VoxCAST Content Delivery
o Raw Infrastructure

Login

Poll
What kind of poll would fit best here?
o One asking whether the material made sense 7%
o Name your favorite first-person shooter 8%
o Ask about the chance of people ever using the information presented 23%
o K5 diary regulars popularity contest 10%
o Stream of thought dissassociated postmodern goodness 16%
o Favorite Axis: (1,0,0) (0,1,0), (0,0,1) or (0,0,0,1)? 33%

Votes: 104
Results | Other Polls

Related Links
o gimbal lock
o Also by spcmanspiff


Display: Sort:
Introductory Basic 3D Transformations 101 Made Easy for Dummies in 30 Days | 45 comments (25 topical, 20 editorial, 0 hidden)
Hartenburg Parameters? (3.00 / 1) (#4)
by zaphod46 on Sun Dec 08, 2002 at 08:20:04 PM EST

I may have screwed the spelling up on that...

Anyway, if you know anything about these, I could really have used a nice reference two years ago. Though I am now a firm believer in Screw Theory, I'd like to get these things explained to me at some point. I could never find a book referencing them in detail, and the one web reference I found was apalling.

If I weren't so lazy, maybe I would do a companion piece to this about robotics and controlling mechanisms using this stuff. Of course, I am lazy, so that's not gonna happen. Good job on your end, though.

Jeff

Screw coordinates ... (3.00 / 1) (#14)
by spcmanspiff on Sun Dec 08, 2002 at 11:13:53 PM EST

I tried once to understand them, since my perpetual hobby project (that isn't even started yet, really) is a good general dynamics engine, and as you probably know, matrices don't really cut it...

Unfortunately, I didn't have the formal math background, plus I only had one .pdf to work with.

Now I'm working through a few "Introduction to Geometric Algebra for Programmers" papers to get a bit more perspective on it ... but do you happen to have any good references? Thanks!

 

[ Parent ]

Screw References (5.00 / 1) (#24)
by zaphod46 on Mon Dec 09, 2002 at 09:11:53 AM EST

There's always the original: A treatise on the theory of screws by Robert Ball.

But that might be a bit overwhelming (I sure think it is). I learned all about screws from A Mathematical Introduction to Robotic Manipulation by Richard Murray (my old academic advisor). It covers other stuff too, like homogenous coords, etc. It does leave out some of the details, so I would suggest keeping a good linear algebra reference handy when you read it.

Good Luck!
Jeff

[ Parent ]

Some things to note (3.75 / 4) (#5)
by xriso on Sun Dec 08, 2002 at 08:20:51 PM EST

In 2D world, we rotate around points. In 3D world, we rotate around lines.

In 2D world, there is only 1 angle needed to represent an amount of rotation. In 3D world, we need 3 angles (eg. pitch yaw roll).

Furthermore, if anybody has is interested in the subject after reading this article, I highly suggest that you learn matrix and vector algebra, and read an in-depth article about this stuff. Your programs will be faster and have less bugs.
--
*** Quits: xriso:#kuro5hin (Forever)

If I were being pedantic, I'd say ... (4.75 / 4) (#15)
by spcmanspiff on Sun Dec 08, 2002 at 11:30:22 PM EST

In any dimension, rotations always happen with respect to a plane. Not a point, not a line, but a plane. This is because, very loosely, rotation is an operation that requires to be constrained to two degrees of freedom to carry out, and planes have the necessary dimension.

... But I'm not feeling very pedantic, so I'll just make a quiet correction:

In 3D, you can represent rotation by 3 angles (Rotation around X axis - yaw, rotation around the Y axis - pitch, and rotation around the Z - roll.) However, this will lead to Big Trouble, as explained in the gimbal lock link. In this article, I suggest axis-angle (any vector for the axis, not just X,Y, or Z) format. There are quite a few others others... quaternions have had their praises widely sung for representing rotation, and deserve it -- but are a bit much for a "For Dummies" article.

Completely agreed on the matrix and vector algebra stuff, by the way. And not just an article if you're serious -- a whole book, or a college course, would be nice.

 

[ Parent ]

Multiple planes, not just one (5.00 / 1) (#26)
by the on Mon Dec 09, 2002 at 09:57:20 AM EST

In any dimension, rotations always happen with respect to a plane
No. For example consider rotations in 4D. If you were to perform a rotation in the 1-2 plane followed by one around the 3-4 plane you'd end up with, well, a 1-2 rotation followed by a 3-4 rotation. All 4D rotations can be generated by rotations in a plane but almost all 4D rotations can't be described by a single rotation in a plane. Some discussion here.

--
The Definite Article
[ Parent ]
Hm. (none / 0) (#28)
by spcmanspiff on Mon Dec 09, 2002 at 11:24:28 AM EST

Now I'm confused .... is there a way to do rotation aside from choosing a plane, then rotating wrt the chosen plane?

I completely see the point about orientation in higher dimensions being irreducible to a single rotation, but I thought rotation as an operation was inextricably tied to planes.

 

[ Parent ]

Rotations are tied to bivectors (5.00 / 1) (#29)
by the on Mon Dec 09, 2002 at 12:50:36 PM EST

Given a pair of vectors a=(ai) and b=(bj) you can form the antisymmetric matrix 'product' a/\b=def(aibj-biaj) . Basically generalized rotation 'axes' can be described by antisymmetric matrices (otherwise known as bivectors) and all bivectors can be constructed as sums of terms of the form a/\b, but not every bivector can be written as exactly one such product. When the bivector is of the form a/\b then the rotation can be thought of as being in the plane containing a and b.

In 3D an antisymmetric matrix has 6 non-zero terms, each of which appears twice. So there are 3 parameters that define a rotation. By strange coincidence this is the dimensionality of the space so, as you point out, 3D rotations can be described by vectors, as well as by bivectors. (And in fact the bivector product can be seen to be the cross product in disguise.)

You're in good company when you claim rotations are defined by planes. It's a popular error and I've made it myself.

--
The Definite Article
[ Parent ]

One more question... (none / 0) (#31)
by spcmanspiff on Mon Dec 09, 2002 at 01:24:46 PM EST

You're in good company when you claim rotations are defined by planes. It's a popular error and I've made it myself.

I'm not convinced that's "good" company.  ;)

-------

I'm quite sure I didn't understood all that, so I'm going to ask a for clarification in my own non-rigorous way.

Rotation: "Turning" an object. Done by choosing two orthogonal unit vectors A and B and transforming the object so that all components parallel to A are replaced by components parallel to a new vector Q, and B with R. Q and R must lie in the same plane as A and B. (That is, Q and R must be expressible in terms of xA + yB with no other components necessary). Because of this, all aspects of the object which are orthogonal to A and B are unchanged. (In 2D: none; in 3D: our axis of rotation; in 4D: a plane; in 5D: a space, etc.)

Orientation: The way an object is currently pointing -- that is, an entity that sums up all the rotations that it has undergone. This our bivector. A single rotation is insufficient in spaces of more than three dimensions to describe the orientation of an object. For example, in four dimensions we can rotate using the x and y axes, then the z and w axes, which, since they're orthogonal, cannot be combined.

Now, I'm there's an operation (I'm going to call it Operation X) that can change any orientation of an object into any other orientation in one step. Rotation as I've described it can't do this.

So, here's my question: Is Operation X the real canonical rotation, and what I'm calling "rotation" is just some bastardized subset?

Or, and I intuitively like this much better, should I leave leave my notion of rotation as is and explore the properties of Operation X independently?

 

[ Parent ]

Yes, I meant to say something about this (none / 0) (#33)
by the on Mon Dec 09, 2002 at 05:27:47 PM EST

You could use rotations in the limited way you suggest, but then we have the problem that the product of two rotations doesn't make a rotation. That's kind of an ugly concept. If you were studying rotations you'd be forced to study "Operation X" as well. So why not study "Operation X" right from the beginning and call them all rotations?

--
The Definite Article
[ Parent ]
Like in 3D? (none / 0) (#30)
by Arkaein on Mon Dec 09, 2002 at 01:19:21 PM EST


If you were to perform a rotation in the 1-2 plane followed by one around the 3-4 plane you'd end up with, well, a 1-2 rotation followed by a 3-4 rotation.

Is this not the same in 3D? If we rotate around X, then Y, are we guaranteed to have a rotation expressible as a rotation around a single vector? That is, can every 3D rotation be represented in angle-axis form?

----
The ultimate plays for Madden 2003-2006
[ Parent ]

The way I understand it... (none / 0) (#32)
by spcmanspiff on Mon Dec 09, 2002 at 01:36:07 PM EST

If you rotate around X, then what you're really doing is changing the Y and Z components of your object. Hence, it's a rotation in the Y-Z plane.

Around Y is a rotation in the X-Z plane.

Because the XZ and YZ have a component in common (Z), we can come up with a new plane, formed by two vectors, that represents both rotations at once:

Z is the first vector -- the component in common -- and the second takes the form (aX + bY). The normal of this plane is the axis of rotation for the new, combined rotation.

However, in 4D we can rotate using the XY plane, then rotate again using the ZW plane, and they cannot be combined.

 

[ Parent ]

Yup (none / 0) (#37)
by the on Mon Dec 09, 2002 at 08:46:17 PM EST

Sounds like you have a pretty good idea of what's going on.

--
The Definite Article
[ Parent ]
How to get axis and angle from matrix (none / 0) (#44)
by Arkaein on Tue Dec 10, 2002 at 10:31:40 AM EST

Hmmm, I've always dealt with converting an angle and axis in 3D to a matrix as so (copied from the Matrix and Quaternion FAQ)

rcos = cos(phi);
rsin = sin(phi);
matrix[0][0] = rcos + u*u*(1-rcos);
matrix[1][0] = w * rsin + v*u*(1-rcos);
matrix[2][0] = -v * rsin + w*u*(1-rcos);
matrix[0][1] = -w * rsin + u*v*(1-rcos);
matrix[1][1] = rcos + v*v*(1-rcos);
matrix[2][1] = u * rsin + w*v*(1-rcos);
matrix[0][2] = v * rsin + u*w*(1-rcos);
matrix[1][2] = -u * rsin + v*w*(1-rcos);
matrix[2][2] = rcos + w*w*(1-rcos);

but I've never done the reverse. I thought about deriving the equations for extracting the axis and angle from the matrix, but decided I would ask if anyone has used direct formulas (I'm sure it can be done using quaternions, but simplified equations are always nice). Not sure if there is a lot of practical value, but it may be a nice addition to a 3D transformation library I've mostly developed.

----
The ultimate plays for Madden 2003-2006
[ Parent ]

To get the axis from a matrix (none / 0) (#45)
by the on Tue Dec 10, 2002 at 01:56:35 PM EST

Suppose you have the rotation matrix R. Then if x is the axis you know Rx = x (that's what axis means, right?). I don't know how your mathematics is but basically when you solve Rx = ax, where a is a scalar, then a is known as an eigenvalue of the matrix and x is an eigenvector. There are many standard algorithms for extracting eigenvalue-eigenvector pairs and you just need the eigenvector corresponding to 1. (There will be two other complex eigenvalues.)

Actually, last time I did this I used a slightly different method. Define S = R-13. Then Sx = 0. So S has a zero eigenvalue and you need to find the corresponding eigenvector. There are many algorithms for finding eigenvectors corresponding to zero (ie. solving Sx = 0 for x). Two that come to mind are SVD and QR decomposition. See Numerical Recipes for algorithms but elementary row operations will also do the trick.

Getting the angle of rotation is easier. The trace of a matrix, tr(R), is the sum of the diagonal elements. So, for example, tr(13)=1+1+1=3. Well If R is a rotation then tr(R)=1+2*cos(angle). It's an interesting exercise to prove this.

--
The Definite Article
[ Parent ]

you've got to be kidding. (1.00 / 13) (#18)
by rev ine on Mon Dec 09, 2002 at 01:31:50 AM EST

-1 horrible.

Well, I did say it was: (4.00 / 1) (#19)
by spcmanspiff on Mon Dec 09, 2002 at 01:44:14 AM EST

  • Introductory
  • Basic
  • Made Simple
  • and, last but not least, For Dummies
What do you expect, Euclid's friggin' elements?

More seriously -- what sucked about it? Is it just my abhorrent writing style, or did you have problems with the actual content?

 

[ Parent ]

Hey, buddy (none / 0) (#20)
by carbon on Mon Dec 09, 2002 at 01:54:31 AM EST

Make it editorial. And while you're at it, write something helpful, or at least constructively critical.


Wasn't Dr. Claus the bad guy on Inspector Gadget? - dirvish
[ Parent ]
Matrix and Quaterion FAQ (5.00 / 1) (#25)
by jck2000 on Mon Dec 09, 2002 at 09:28:53 AM EST

When I was first interested in 3D graphics, I found the Matrix and Quaternions FAQ to be very helpful.

missing (2.25 / 4) (#27)
by turmeric on Mon Dec 09, 2002 at 10:57:30 AM EST

polar coordinate systems. (or... why open GL and the 3d gamer subsystem ruined all creativity in computer graphics)

He'll get around to quaternions... (4.00 / 1) (#35)
by John Miles on Mon Dec 09, 2002 at 07:31:08 PM EST

... soon enough, I expect. Are they polar enough for you?

For so long as men do as they are told, there will be war.
[ Parent ]
gotchas for learning 3D transformations (5.00 / 2) (#34)
by NickW on Mon Dec 09, 2002 at 06:50:53 PM EST

There are a two different notations for working with vectors. These make it difficult when trying to teach yourself from multiple sources.

The first in row vectors vs. column vectors. spcmanspiff uses column vectors such as
|x|
|y|
|z|
|1|

a row vector looks like

|x y z 1|

Different vector notation leads to different transformation matrices. The translation matrix for a row vector looks like:

|1 0 0 0|
|0 1 0 0|
|0 0 1 0|
|tx ty tz 1|

but for a column vector it is flipped on it's diagonal axis:

|1 0 0 tx|
|0 1 0 ty|
|0 0 1 tz|
|0 0 0 1 |

Another difference between references (and APIs) is the direction of the axis of coordinate system. See Left handed vs. Right handed coordinate systems.

--
Cult - A sociotype of an auto-toxic meme-complex, composed of membots and/or memeoids.
Memetic Lexicon

... you're giving it all away! (5.00 / 1) (#36)
by spcmanspiff on Mon Dec 09, 2002 at 08:27:21 PM EST

This article didn't have any homogenous coordinates... That was for next time, which will be a bit more rigorous and less touchy-feely.

Still, those are very good things to keep in mind. Sucks to debug them, especially for the 1st time.

 

[ Parent ]

Slower (more explaining) tutor (4.00 / 1) (#40)
by e8johan on Tue Dec 10, 2002 at 04:43:01 AM EST

You can find a slower tutorial here. It covers all the topics from this story, but more in depth and in greater detail. It also has sample code to prove the concepts introduced.

That's a really good one (3.00 / 1) (#41)
by hulver on Tue Dec 10, 2002 at 05:01:03 AM EST

Thanks. It explained the mapping of 3d -> 2d space really well.

--
HuSi!
[ Parent ]
Introductory Basic 3D Transformations 101 Made Easy for Dummies in 30 Days | 45 comments (25 topical, 20 editorial, 0 hidden)
Display: Sort:

kuro5hin.org

[XML]
All trademarks and copyrights on this page are owned by their respective companies. The Rest 2000 - Present Kuro5hin.org Inc.
See our legalese page for copyright policies. Please also read our Privacy Policy.
Kuro5hin.org is powered by Free Software, including Apache, Perl, and Linux, The Scoop Engine that runs this site is freely available, under the terms of the GPL.
Need some help? Email help@kuro5hin.org.
My heart's the long stairs.

Powered by Scoop create account | help/FAQ | mission | links | search | IRC | YOU choose the stories!