Logo
RuTh's  RuThLEss  HomEpAgE

 

sTaRt
 
 
 
 
 
 
 
 
FuN
 
 
 
 
fAcTs
 
 
>
3D Game DesignEnglish
>
PlanetrisEnglishDeutschCesky
>
PHP-SkripteDeutsch
>
Programming Links
 
 
 
 
 
 
* INDEX * 3D game to-do list * 3D Engine to-do list ( chapter 1, 2, 3, 4, 5, 6, 7 ) *
* projection formula * transformation matrices * Bresenham algorithm * Scanline Polygonfill algorithm *
* Spieldesign / game design * Troubleshooting 3D * Irrlicht 3D engine * Blender for Beginners *

3D Matrix Formulas

3D Transformation With Matrices

It's one thing to define and project static 3D entities onto the screen, and another to transform them. When I say transformation I mean common tasks: You want your 3D entities to change their position (translation), or you want them to turn around (rotation), or you want them to shrink or grow (scaling). Remember that vectors are used to define the vertices of our 3D-entitities? For a transformation, you have to recalculate each of those vectors of each polygon of an entity. For example, you have to substract 5 from each vector's x-value if you want the entity to move left 5 units.

1.00.00.00.0
0.01.00.00.0
0.00.01.00.0
0.00.00.01.0
{ 1.0 , 0.0 , 0.0 , 0.0 ,
  0.0 , 1.0 , 0.0 , 0.0 ,
  0.0 , 0.0 , 1.0 , 0.0 ,
  0.0 , 0.0 , 0.0 , 1.0 }
Doing that kind of calculation for each and every polygon takes a lot of CPU time, so it's essential to start optimizing right here. If there was some way to add up several transformations and apply them to the entity in one step, we would save a lot of CPU time... And, luckily, there is one: matrix arithmetics.

Matrix arithmetics is less scary than it might sound: Matrices are actually just lists of numbers that are multiplied with each other. For instance, I implement a 4x4 matrix like the one shown here with a simple 16-field NSMutableArray of floating point numbers. I'm not going to go into depths how matrices work: Just think of matrices as clever shortcuts to move vertices (and thus the whole 3D-entity) around in an efficient and controlled fashion.

Combining the effects of many transformation matrices into one is called concatenation of matrices. Mathematically this it done by multiplation. You'll see there are rules how to pick numbers for a 4x4-matrix that will cause a precise effect on a vector when they are multiplied with each other. Hold on to your hat, you are now about to be let in on the secret of 3D animation: The translation matrix for moving entities, the scaling matrix for resizing entities, and 3 rotation matrices to turn entities around three axes...

The Five 3D Transformation Matrices

Translation Matrix

Multiplying a vector with the translation matrix will move it xTrans units along the x-axis, yTrans units along the y-axis, and zTrans units along the z-axis. This is what you would use when you want an entity to fall, fly, drive or walk around.

1.00.00.00.0
0.01.00.00.0
0.00.01.00.0
xTransyTranszTrans1.0

Scaling Matrix

Multiplying a vector with the scaling matrix will scale it xScale units along the x-axis, yScale units along the y-axis, and zScale units along the z-axis. This is what you would use when you want an entity to grow smaller/higher or wider/narrower. If you want an entity to grow or shrink proportionally, simply make sure that xScale = yScale = zScale.

xScale0.00.00.0
0.0yScale0.00.0
0.00.0zScale0.0
0.00.00.01.0

Matrix for Rotation Around the X-Axis (Pitch)

Multiplying a vector with this rotation matrix will rotate it xRot units around the x-axis. It's the same movement than nodding you head. This is what you would use when you want a plane to pitch nose-down.

1.00.00.00.0
0.0cos(xRot)sin(xRot)0.0
0.0-sin(xRot)cos(xRot)0.0
0.00.00.01.0

Matrix for Rotation Around the Y-Axis (Yaw)

Multiplying a vector with this rotation matrix will rotate it yRot units around the y-axis. It's the same movement than shaking your head. This is what you would use when you want a plane to yaw parallely to the ground.

cos(yRot)0.0-sin(yRot)0.0
0.01.00.00.0
sin(yRot)0.0cos(yRot)0.0
0.00.00.01.0

Matrix for Rotation Around the Z-Axis (Roll)

Multiplying a vector with this rotation matrix will rotate it zRot units around the z-axis. It's the same movement than cocking your head. This is what you would use when you want a plane to make a barrel roll.

cos(zRot)sin(zRot)0.00.0
-sin(zRot)cos(zRot)0.00.0
0.00.01.00.0
0.00.00.01.0

Matrix Concatenation (Multiplication)

I've been talking about "multiplying" matrices and vectors -- but, you interject, they are not numbers, but arrays of numbers: A 4x4-matrix is an array of 16 floating point numbers, and a 3D vector is an array of 3 floating point numbers. How do I "multiply" two arrays which, into the bargain, even have different lengths? Well, there is a special rule for that:

( a b c d )
( e f g h ) * (x y z u) = ( nx ny nz nu ) 
( i j k l )
( m n o p )
where
nx = x*a + y*b + z*c + u*d
ny = x*e + y*f + z*g + u*h
nz = x*i + y*j + z*k + u*l
nu = x*m + y*n + z*o + u*p

Now you might interject again, why do I show an example where the vector has four fields (x|y|z|u) instead of three (x|y|z), hmm? Well, unfortunately, the tranformation matrices need 4x4 fields, and all the matrices and vectors you want to multiply must have the same width in order for the multiplication rule to work... To be honest, it's actually only the translation matrix which really cannot do without the fourth row; the other four translation matrices could be represented with 3x3-matrices...

But instead of dropping translation (we do need that!), we go the other way: We cave in and extend all the matrices to 4x4 and the vector to 1x4. This is mathematiclally possible, as long as we make sure the vector's useless fourth 'coordinate' u is always set to 1.0 and therfore does not influence the outcome of the calculations. (I know, it's a wild hack, but hey, just think of the nice 3D game you'll get of it!)

Implementation

Now that you have learnt the mathematical background, we sit down and implement. I put all the matrix arithmetics in one C object called MYMatrix. How will this object be employed in the 3D game engine?

  • Each time you want to transform a 3D entity, you first create a new 'empty' concatenation matrix object and apply to it all the transformations that you need to make your entity act out its role. For optimal results apply transformations matrices in this order: rotate-z, rotate-x, rotate-y, scale, translate. By multiplying your empty concatenation matrix with these transformation matrices, their effects are combined in the concatenation matrix -- this is what matrix concatenation is all about.
  • Then you multiply your prepared concatenation matrix with the local coordinates of your entity. *Poof* All the combined transformations stored in it will now be applied to your entity in one step. The result is stored in the entity's transformed coordinate variables.
  • Those transformed coordinates are then converted to world coordinates and projected to the screen the way I showed it to you in the previous chapter about projection. This is the step we skipped because I though it was kinda lengthy to explain, remember? :-)
So now, here are the actual methods from the MYMatrix source code:

Matrix Concatenation (Multiplication)

This is the implementation of the weird matrix multiplication rule I just showed you. Looks much better in Objective C, doesn't it.

/* Multiplies matrix1 (self) with the argument matrix2 
 * returns the result in matrix3 */
- (MYMatrix*) multiply:(MYMatrix*)matrix2
{
    MYMatrix* matrix3 = [[MYMatrix alloc] init];
    int	i,j;
    for (i = 0; i < 4; i++) {
	for (j = 0; j < 4; j++) {
	    [matrix3 setRow:i column:j 
                     to:( [self valueRow:i column:0] 
                        * [matrix2 valueRow:0 column:j])];
	    [matrix3 addValue:( [self valueRow:i column:1] 
                              * [matrix2 valueRow:1 column:j]) 
                     toRow:i column:j];
	    [matrix3 addValue:( [self valueRow:i column:2] 
                              * [matrix2 valueRow:2 column:j]) 
                     toRow:i column:j];
	    [matrix3 addValue:( [self valueRow:i column:3] 
                              * [matrix2 valueRow:3 column:j]) 
                     toRow:i column:j];
	}
    }
    [matrix3 retain];
    return matrix3;
}

Matrix Copy

This is a very simple method just copying the data to a new matrix. (= clone?)

/* Copy: Just sets 'self' to srcMatrix. */
- (void) copy:(MYMatrix*)srcMatrix
{
    short i, j;
    for (i = 0; i < 4; i++) {
	for (j = 0; j < 4; j++) {
	    [srcMatrix retain];
	    [self setRow:i column:j 
                  to:[srcMatrix valueRow:i column:j]];
	}
    }
}

Applying Transformation

Translation

This is how to implement translation. The method takes three arguments, xTrans, yTrans, and zTrans; they signify how many units you want to move a vector. The method creates a translation matrix and sets the three special fields to the argument values.

/* Applies a translation to the input matrix (self). */
- (void) moveX:(float)xTrans y:(float)yTrans z:(float)zTrans
{
    MYMatrix* transMatrix = [[MYMatrix alloc] init];
    MYMatrix* tempMatrix = [[MYMatrix alloc] init];

    /* Set transMatrix to a translation matrix */
    [transMatrix setRow:0 column:0 to:1.0];
    [transMatrix setRow:0 column:1 to:0.0];
    [transMatrix setRow:0 column:2 to:0.0];
    [transMatrix setRow:0 column:3 to:0.0];
    [transMatrix setRow:1 column:0 to:0.0];
    [transMatrix setRow:1 column:1 to:1.0];
    [transMatrix setRow:1 column:2 to:0.0];
    [transMatrix setRow:1 column:3 to:0.0];
    [transMatrix setRow:2 column:0 to:0.0];
    [transMatrix setRow:2 column:1 to:0.0];
    [transMatrix setRow:2 column:2 to:1.0];
    [transMatrix setRow:2 column:3 to:0.0];
    [transMatrix setRow:3 column:0 to:xTrans];
    [transMatrix setRow:3 column:1 to:yTrans];
    [transMatrix setRow:3 column:2 to:zTrans];
    [transMatrix setRow:3 column:3 to:1.0];
    /* Concatenate the translation matrix with the input matrix. */
    tempMatrix = [self multiplizieren:transMatrix];
    /* Copy the temp matrix back into the input matrix */
    [self kopieren:tempMatrix];
}

Proportional Scaling

This is how to implement proportional scaling. The method takes one argument, the scalingFactor; it signifies how many units you want to grow or shrink a vector. The method creates a scaling matrix and sets the three special fields to the argument value. If you need unproportional scaling, copy and rewrite it to accept three arguments and change this proportional method to just call the unproportional scale: with three equal arguments.

/*  Applies proportional scaling to the input matrix. */
- (void) scale:(float)scalingFactor
{
    MYMatrix* scaleMatrix = [[MYMatrix alloc] init];
    MYMatrix* tempMatrix = [[MYMatrix alloc] init];
    /* Set scaleMatrix to a scaling matrix */
    [scaleMatrix setRow:0 column:0 to:scalingFactor];
    [scaleMatrix setRow:0 column:1 to:0.0];
    [scaleMatrix setRow:0 column:2 to:0.0];
    [scaleMatrix setRow:0 column:3 to:0.0];
    [scaleMatrix setRow:1 column:0 to:0.0];
    [scaleMatrix setRow:1 column:1 to:scalingFactor];
    [scaleMatrix setRow:1 column:2 to:0.0];
    [scaleMatrix setRow:1 column:3 to:0.0];
    [scaleMatrix setRow:2 column:0 to:0.0];
    [scaleMatrix setRow:2 column:1 to:0.0];
    [scaleMatrix setRow:2 column:2 to:scalingFactor];
    [scaleMatrix setRow:2 column:3 to:0.0];
    [scaleMatrix setRow:3 column:0 to:0.0];
    [scaleMatrix setRow:3 column:1 to:0.0];
    [scaleMatrix setRow:3 column:2 to:0.0];
    [scaleMatrix setRow:3 column:3 to:1.0];
    /* Concatenate the scaling matrix with the input matrix. */
    tempMatrix=[self multiplizieren:scaleMatrix];
    /* Copy the temp matrix back into the input matrix */
    [self kopieren:tempMatrix];
}

Rotation

This is how to implement rotation. The method takes three arguments, the rotation factors; they signify how many units you want to rotate a vector around each of the three axes. The method creates three rotation matrices out of the three argument values you gave it.

Depending on how your sine/cosine functions are implemented, xRot, yRot, and zRot must be expressed in either degrees (0 - 259) or radians (0.0 - 2*pi)! If you take the wrong units either way, you'll get very strange results!

/* Applies x,y, and z rotations to the input matrix. 
 */
- (void) rotierenX:(float)xRot Y:(float)yRot Z:(float)zRot
{
    MYMatrix* rotMatrix = [[MYMatrix alloc] init];
    MYMatrix* tempMatrix1 = [[MYMatrix alloc] init];
    MYMatrix* tempMatrix2 = [[MYMatrix alloc] init];
    float xSin, xCos, ySin, yCos, zSin, zCos;
    
    xSin = [MYMatrix sinus:xRot];
    xCos = [MYMatrix cosinus:xRot];
    ySin = [MYMatrix sinus:yRot];
    yCos = [MYMatrix cosinus:yRot];
    zSin = [MYMatrix sinus:zRot];
    zCos = [MYMatrix cosinus:zRot];
    
    /* We want to apply all three rotations to the inputMatrix,
     * in the order of y, x, and z. In order to accomplish all of
     * these transformations, we have to use two temporary matrices
     * and copy between them. */
    
    /* Set rotMatrix to the y rotation matrix */
    [rotMatrix setRow:0 column:0 to:yCos];
    [rotMatrix setRow:0 column:1 to:0.0];
    [rotMatrix setRow:0 column:2 to:-ySin];
    [rotMatrix setRow:0 column:3 to:0.0];
    [rotMatrix setRow:1 column:0 to:0.0];
    [rotMatrix setRow:1 column:1 to:1.0];
    [rotMatrix setRow:1 column:2 to:0.0];
    [rotMatrix setRow:1 column:3 to:0.0];
    [rotMatrix setRow:2 column:0 to:ySin];
    [rotMatrix setRow:2 column:1 to:0.0];
    [rotMatrix setRow:2 column:2 to:yCos];
    [rotMatrix setRow:2 column:3 to:0.0];
    [rotMatrix setRow:3 column:0 to:0.0];
    [rotMatrix setRow:3 column:1 to:0.0];
    [rotMatrix setRow:3 column:2 to:0.0];
    [rotMatrix setRow:3 column:3 to:1.0];
    /* Concatenate rotMatrix with inputMatrix */
    tempMatrix1=[self multiplizieren:rotMatrix];
    
    /* Set rotMatrix to the x rotation matrix */
    [rotMatrix setRow:0 column:0 to:1.0];
    [rotMatrix setRow:0 column:1 to:0.0];
    [rotMatrix setRow:0 column:2 to:0.0];
    [rotMatrix setRow:0 column:3 to:0.0];
    [rotMatrix setRow:1 column:0 to:0.0];
    [rotMatrix setRow:1 column:1 to:xCos];
    [rotMatrix setRow:1 column:2 to:xSin];
    [rotMatrix setRow:1 column:3 to:0.0];
    [rotMatrix setRow:2 column:0 to:0.0];
    [rotMatrix setRow:2 column:1 to:-xSin];
    [rotMatrix setRow:2 column:2 to:xCos];
    [rotMatrix setRow:2 column:3 to:0.0];
    [rotMatrix setRow:3 column:0 to:0.0];
    [rotMatrix setRow:3 column:1 to:0.0];
    [rotMatrix setRow:3 column:2 to:0.0];
    [rotMatrix setRow:3 column:3 to:1.0];
    /* Concatenate rotMatrix with tempMatrix1 */
    tempMatrix2=[tempMatrix1 multiplizieren:rotMatrix];

    /* Set rotMatrix to the z rotation matrix */
    [rotMatrix setRow:0 column:0 to:zCos];
    [rotMatrix setRow:0 column:1 to:zSin];
    [rotMatrix setRow:0 column:2 to:0.0];
    [rotMatrix setRow:0 column:3 to:0.0];
    [rotMatrix setRow:1 column:0 to:-zSin];
    [rotMatrix setRow:1 column:1 to:zCos];
    [rotMatrix setRow:1 column:2 to:0.0];
    [rotMatrix setRow:1 column:3 to:0.0];
    [rotMatrix setRow:2 column:0 to:0.0];
    [rotMatrix setRow:2 column:1 to:0.0];
    [rotMatrix setRow:2 column:2 to:1.0];
    [rotMatrix setRow:2 column:3 to:0.0];
    [rotMatrix setRow:3 column:0 to:0.0];
    [rotMatrix setRow:3 column:1 to:0.0];
    [rotMatrix setRow:3 column:2 to:0.0];
    [rotMatrix setRow:3 column:3 to:1.0];
    /* Concatenate rotMatrix with tempMatrix2 */
    tempMatrix1=[tempMatrix2 multiplizieren:rotMatrix];
    
    /* Copy the temp matrix back into the input matrix */
    [self kopieren:tempMatrix1];
}

Create a new Matrix

This is the Matrix init method. A newly initialized Matrix is not empty: For 'security reasons', you want it to be initialized to the so-called identity matrix. An identity matrix is to a vector what the number "1" is to another number: When you multiply them, the number remains the same -- like 1*823476=823476.

/*  Initializes a matrix to the identity matrix. */
- (MYMatrix*) init
{
    if( self=[super init] )
    {
    matrix = [[NSMutableArray alloc] init];
    NSNumber* A1 = [[NSNumber alloc] initWithFloat:1.0];
    NSNumber* A2 = [[NSNumber alloc] initWithFloat:0.0];
    NSNumber* A3 = [[NSNumber alloc] initWithFloat:0.0];
    NSNumber* A4 = [[NSNumber alloc] initWithFloat:0.0];
    NSNumber* B1 = [[NSNumber alloc] initWithFloat:0.0];
    NSNumber* B2 = [[NSNumber alloc] initWithFloat:1.0];
    NSNumber* B3 = [[NSNumber alloc] initWithFloat:0.0];
    NSNumber* B4 = [[NSNumber alloc] initWithFloat:0.0];
    NSNumber* C1 = [[NSNumber alloc] initWithFloat:0.0];
    NSNumber* C2 = [[NSNumber alloc] initWithFloat:0.0];
    NSNumber* C3 = [[NSNumber alloc] initWithFloat:1.0];
    NSNumber* C4 = [[NSNumber alloc] initWithFloat:0.0];
    NSNumber* D1 = [[NSNumber alloc] initWithFloat:0.0];
    NSNumber* D2 = [[NSNumber alloc] initWithFloat:0.0];
    NSNumber* D3 = [[NSNumber alloc] initWithFloat:0.0];
    NSNumber* D4 = [[NSNumber alloc] initWithFloat:1.0];
    matrix = [NSMutableArray arrayWithEntitys:
                             A1,A2,A3,A4,
                             B1,B2,B3,B4,
                             C1,C2,C3,C4,
                             D1,D2,D3,D4,nil];
    [matrix retain];
    }
    return self;
}

Accessors and Destructors

Don't forget the dealloc destructor that releases an unused matrix. You also will need accessor methods that take a row and a colum of the matrix as input and return the value from that matrix field, and same thing for setting a value in a matrix field.

For convenience, I also wrote me a method that adds a value to a matrix field. Just a reminder: For a 4x4-matrix represented by a 16-item array, you need to access the array field number ((r*4)+c) if you want to access the matrix field in row r and column c (counting rows/columns starts with zero).

Completing MYEntity

A Working Transformation Method for MYEntity

This is the transform method in MYEntity that I skipped while explaining static projection -- don't forget to upate it, otherwise you won't get any transformation and you're stuck with the fake static version! It takes a matrix as argument and applies it to the entity triggering the transformations stored in the matrix.

- (void) transformation:(MYMatrix*)transformMatrix
{
    /* Transforms the local coordinates by the transformMatrix.
     * Stores results in the vertices' temporary variables tx,ty,tz,tt.
     */

    int p,v;
    MYVertex* theVertex;
    MYPolygon* thePolygon;
    int numOfPolygons=[self size];

    for(p=0;p < numOfPolygons;p++)
    {
	thePolygon = [self polygon:p];
	int numOfVertices=[thePolygon size];
	for(v=0; v < numOfVertices; v++)
	{
	    float tmp0, tmp1, tmp2, tmp3; 
	    theVertex=[thePolygon vertex:v];

	tmp0 = [theVertex lx] * [transformMatrix valueRow:0 column:0]
	     + [theVertex ly] * [transformMatrix valueRow:1 column:0]
	     + [theVertex lz] * [transformMatrix valueRow:2 column:0]
	                      + [transformMatrix valueRow:3 column:0];

	tmp1 = [theVertex lx] * [transformMatrix valueRow:0 column:1]
	     + [theVertex ly] * [transformMatrix valueRow:1 column:1]
	     + [theVertex lz] * [transformMatrix valueRow:2 column:1]
	                      + [transformMatrix valueRow:3 column:1];

	tmp2 = [theVertex lx] * [transformMatrix valueRow:0 column:2]
	     + [theVertex ly] * [transformMatrix valueRow:1 column:2]
	     + [theVertex lz] * [transformMatrix valueRow:2 column:2]
	                      + [transformMatrix valueRow:3 column:2];

	tmp3 = [theVertex lx] * [transformMatrix valueRow:0 column:3]
	     + [theVertex ly] * [transformMatrix valueRow:1 column:3]
	     + [theVertex lz] * [transformMatrix valueRow:2 column:3]
	                      + [transformMatrix valueRow:3 column:3];

	[theVertex setTX:tmp0];
	[theVertex setTY:tmp1];
	[theVertex setTZ:tmp2];
	[theVertex setTT:tmp3];
	}
    }
}

Tying in The New Methods

Probably you're ready for some action after all that typing and reading. For testing purposes, you can first implement a simpler global transformation. Global transformation means that the same transformation is applied to each object in the game world (MYGameWorld).

  • Add five global translation variables to your game world object, one for scaling, one for moving, and three for rotation.
  • MYGameWorld gets its own draw function, which performs the steps I just described above:
    • The draw:-method initializes an empty concatenation matrix, applies to it rotation, scaling and translation. For now, it uses the global transformation variables as arguments to create the concatenation matrix.
    • Then it loops through the array containing the game world entities and applies to each first transformation, second conversion to world coordinates, and third projection. Finally, it calls each entity's draw:-method.
  • By manipulating the global transformation variables, you can either hardcode a series of transformations to your drawRect:-method and watch it repeat over and over again -- or you can link their manipulation to trigger keys on your keyboard.

If you want to do the latter, you can catch signals from keys with the NSResponder class in your custom NSView object.

- (void)keyDown:(NSEvent *)theEvent
{
    if( [theEvent keyCode]== 78  ) 
    {
	// trigger something...
    }
    [self setNeedsDisplay:YES];
}

Optimization

You can save a bit of time by precalculating sine and cosine values for 360 degrees and storing them in an array. Then you use your own sine/cosine function that returns the corresponding field from the array, which is faster than calculating the same values over and over.

/* this is in degrees between 0 and 259! */

static NSMutableArray* gSinTable=nil;
static NSMutableArray* gCosTable=nil;

+ (void) initSinCosTable
{
    int		i;
    float	radians;
    float	sinResult, cosResult;
    gSinTable = [[NSMutableArray alloc] init];
    gCosTable = [[NSMutableArray alloc] init];

    for (i = 0; i < 360; i++) {
	radians = i * degToRad;
	sinResult = sin(radians);
	cosResult = cos(radians);
	[gSinTable insertEntity:
           [[NSNumber alloc] initWithFloat:(sinResult)] atIndex:i];
	[gCosTable insertEntity:
           [[NSNumber alloc] initWithFloat:(cosResult)] atIndex:i];
    }
}
+ (float) sinus:(float)z
{
    if(gSinTable==nil){
	[MYMatrix initSinCosTable];
    }
    z=(int)roundf(z);
    return [[gSinTable objectAtIndex:z] floatValue];
}
+ (float) cosinus:(float)z
{
    if(gCosTable==nil){
	[MYMatrix initSinCosTable];
    }
    z=(int)roundf(z);
    return [[gCosTable objectAtIndex:z] floatValue];
}
 
   
2008.08.26

http://www.ruthless.zathras.de/