100 Experience Points
An Adventure in Indie Game Development

Basis Transformations

So all day, I’ve been trying to get all of my transformations for my game working correctly. One of the big key things, that I believe I just got up and running, is building a transformation matrix from one basis to another. I thought it would be worth posting that work here. This post kind of combines together a whole slew of ideas that I’ve needed to combine together to get my transformations working, but here it is anyway.

I’ll be honest, if you don’t know much about matrices and vectors, this may be over your head. Feel free to skip ahead. Learning about matrices and vectors is good to do, but it doesn’t need to be today (and I don’t provide a lot of the little building blocks here). This is more for the people who know a bit about matrices, vectors, and transformations already, and are expanding their knowledge.

What is a Basis?

A basis is essentially a set of vectors that define the orientation of a coordinate system.

In linear algebra terms, we’d say that it’s a set of vectors that are linearly independent of each other. Which is just a fancy way of saying you can’t add multiples of some of the vectors to get the other vectors that form the basis. And also that every point in the world (the “vector space”) can be uniquely addressed by adding multiples of the basis vectors.

I know, that was ridiculously confusing. Let me try going at this from a different angle. If you’ve done much with vectors and coordinate systems, you know about the x-axis, y-axis, and z-axis. And you can define a unit vector (a vector with a length of 1) along each axis. That is, <1, 0, 0>, <0, 1, 0>, and <0, 0, 1>.

These three vectors are linearly independent. That means there is no number that you can multiply the first vector and second vectors by to get the third, there’s no number that you can multiply the first and third by to get the second, and there’s no number that you can multiply the second and third by to get the first.

And every point in the coordinate system can be reached by combining some number multiplied by each of these vectors. So these three vectors form a basis. In fact, this is the standard basis for the 3D world (a.k.a., ).

But there are lots of other bases. Basises. Bas…. You can have another basis. You just need three linearly independent vectors.

Normals, Tangents, and Binormals

In my game, I have objects that are attached to the surface of other objects. It’s a pretty common thing in physics and math to call the vector that is perpendicular to a surface a normal. The normal of a table points up (usually). The normal of the screen you’re looking at is probably pointing almost directly at your face.

Normals are extremely common, all over the place. In your game, one of the most important places it comes up is in your 3D models. The normals of your 3D model are used to determine what kind of light they’re receiving, so they can’t be lit correctly. There’s a ton more to that, but it’s for another time.

In my game, when I attach an object to another object, I know it’s normal. That’s something I get back as a part of my mouse click/picking code.

But we can take this a step further. If the normal of a surface points directly away from it, a tangent is a vector that is directly in line with the surface at a particular point. There are lots and lots of tangent vectors. Draw a line on your table, or across your screen, and you’ll see the tangent for that surface. There’s another one at 90° from that, at 45°, at 17°, and on and on.

It’s worth noting that if we were using a curve, instead of a surface, there’d only be one tangent. In fact, only having one tangent is pretty convenient. For what I did, I had to find a way to pick one of the infinite possibilities to use as the tangent vector.

Going just a little further, if we have a normal and a tangent vector, we can find a third vector that is perpendicular to both. (This can be computed with a cross product, which is, again, a topic for another day. But most systems will already have code available for you to compute a cross product.) This vector that is perpendicular to both the normal and the tangent is called the binormal. If you’re looking at a curve, this will be sticking out to the side of the curve. Interestingly, with a surface, the binormal is also tangent to the surface.

What’s interesting here, is that a normal, tangent, and binormal are all, by definition orthogonal, or perpendicular, to each other. This means that they form their own basis!

Transforms from One Basis to Another

So in my game, I need to be able to come up with a matrix that will change you from the parent’s coordinate system (the object you’re attaching to) to the child’s coordinate system (the coordinate system of the object you’re attaching). There’s a translation matrix (moving side-to-side, up/down, in/out) that’s required, and potentially a scaling matrix, but the tricky one is the rotation matrices to get things rotated correctly. This is essentially the matrix that is needed to convert from one basis to another.

And it’s pretty tricky to get right.

So let’s start here. You have your original coordinate system, with the unit X, Y, and Z vectors (<1, 0, 0>, <0, 1, 0>, and <0, 0, 1>). And then you have your normal (the new y-axis in my case), tangent (the new z-axis), and binormal (the new x-axis).

Note that in my 3D modeling, I orient objects so that they’re facing down the z-axis, with the y-axis being “up”. If you’re using something else, your normal, tangent, and binormal vectors may be arranged differently, but the concept should still work.

Our basis transformation will be a combination of two matrices. (Also note that I’m using a right-handed coordinate system, if that matters to you.)

The first matrix will rotate things that were in line with the original/parent y-axis in line with the new/child y-axis (the normal vector). To start, we calculate the angle between the original y-axis and the child y-axis/normal vector. I won’t get into calculating the angle between two vectors here, but it can be done using a dot product. This will tell us how far to rotate.

float angle = AngleBetween(Vector3.UnitY, Normal);

Then we’ll need to figure out what to rotate around. This is, not too surprisingly, the vector that is the cross product between the original y-axis and the normal (the new y-axis).

Vector3 axis = Vector3.Cross(Vector3.UnitY, Normal);
axis.Normalize(); // Don't forget this, like I did.

Now we can perform a pretty standard rotation around a specific axis. XNA has such a method, as do a lot of other Vector/Matrix libraries:

Matrix transformation = Matrix.CreateFromAxisAngle(axis, angle);

Great! At this point, our object is lined up in one direction. We just need to spin it around it’s normal to get the x and z axes(tangent and binormal) lined up correctly.

We’ll do a second CreateFromAxisAngle, using the normal as the axis, but we’ll need to calculate the angle. It’s a little harder to calculate this angle than it was last time for a couple of reasons.

One is that last time, we knew exactly what vector we needed to rotate, and what vector to rotate to. We’d like to be able to do the same thing. Rotate the z-axis to the tangent vector. But the problem is, our z-axis has been rotated to get to where we’re at. So the first step here is to figure out where the z-axis ended up with that first transformation.

We’ll use XNA’s Vector3.TransformNormal method, but again, the code for doing this yourself isn’t terribly complicated:

Vector3 transformedZ = Vector3.TransformNormal(Vector3.UnitZ, transformation);

That’s where our z-axis ended up.

Now the other tricky part. We can calculate the angle pretty easily, but we don’t know which way to rotate it. We don’t know whether the angle should be positive or negative. Rather than trying to go through all of the gory details, I’m just going to give you some code that does this transformation using pretty normal/standard methods:

double sinTheta = Vector3.Cross(transformedZ, Tangent).Length();
double cosTheta = Vector3.Dot(transformedZ, Tangent);
angle = (float)Math.Atan2(sinTheta, cosTheta);
double sign = Vector3.Dot(Normal, Vector3.Cross(transformedZ, Tangent));
if(sign < 0)
    angle = -angle;

Now we know how far to rotate (and whether to rotate backwards or not). We can now append our second and final matrix to our transform to complete it:

transformation *= Matrix.CreateFromAxisAngle(Normal, angle);

This matrix will now turn things from one basis to another!

Final Words…

But… even looking back at this page… it still seems pretty complicated. Don’t get too frustrated if you don’t understand this on your first pass. I just spent the last probably six hours getting all of this worked out, and I eat this stuff for breakfast. (Where would one buy Vector-O’s, so that I can do so, literally?) If you only get one things out of this post, it’s that you shouldn’t fear game math. Work to learn it in bits and pieces as you can, and you’ll be glad you did.