flipcode - Building a 3D Portal Engine

Building a 3D Portal Engine - Issue 03 - 3D Matrix Math
by (15 January 1999)

Introduction

This week in Phantom's Guide To Writing A Portal Based 3D Engine: 3D matrix mathematics. Now that we have had the nasty buffer and windows stuff, it's on to the real matter: Vector mathematics. Matrices are cool. They are also rather hard to understand fully, so if you want to know everything about them, this is the time to find a good site or book about them (preferably a site, and don't forget to submit the link to this site!).

First I want to talk about something else: Gathering knowledge. I often get e-mail from people asking me how I learned all my stuff. "What books can you recommend?" "Where did you start?", questions like that. My usual reaction to that is a chat with my wife about being 'auto-didact': You have to learn things for YOURSELF. Don't be dependant on other people's knowledge, gather your info yourself. And more important: TRY things. You won't get good by reading books, you get good by making mistakes. Gather info by browsing the web, that's the largest source of information in the world. And it's usually more up-to-date than the bookstore. Using this aproach, it's possible to develop knowledge that nobody else has: You combine gathered knowledge in a unique way, allowing you to do things that nobody else did, and trying things that nobody thought of. That's how I got my (dubious) knowledge. It's kinda hard to explain, but I hope you get the point. :)

OK, back to the matrices. A matrix can be used to define a rotation in 3D space, and a translation. Therefore I usually use a 4x4 matrix: 3x3 defines an arbitrary rotation, the last column defines the movement, a.k.a. translation. Rotated coordinates can then be calculated by tossing the coordinate (vector) into the matrix.

Suppose you defined your matrix as an array of floats: Four rows by four columns, named for example cell[4][4]. You can 'toss in' a vector using the following formulas:


     x_rotated = cell[0][0] * x + cell[1][0] * y + cell[2][0] * z + cell[3][0]
     y_rotated = cell[0][1] * x + cell[1][1] * y + cell[2][1] * z + cell[3][1]
     z_rotated = cell[0][2] * x + cell[1][2] * y + cell[2][2] * z + cell[3][2]

Note that the last row is not used, so theoretically you don't even have to store it.

So how do we create the matrix itself? We start with the unity matrix:


     1   0   0   0
     0   1   0   0
     0   0   1   0
     0   0   0   1

This matrix has the unique property that it does nothing to 3D coordinates: It leaves them perfectly intact. Then we take the desired rotation around the x-axis, wich I will call 'rx' here. The matrix for this rotation looks like this:


     1     0        0         0
     0     cos(rx)  sin(rx)   0
     0    -sin(rx)  cos(rx)   0
     0     0        0         1

So, if you just wanted to rotate your 3D coordinates around the x-axis, you could use this matrix. However, if you also want to rotate around the y and z axis, you have to 'concatenate' the x rotation matrix with the y and z rotation matrix. Here they are:


y:   cos(ry)  0    -sin(ry)   0
     0        1     0         0
     sin(ry)  0     cos(ry)   0
     0        0     0         1

 
z:   cos(rz)  sin(rz)    0    0
    -sin(rz)  cos(rz)    0    0
     0        0          1    0
     0        0          0    1

OK, so how do we concatenate matrices? Here's how: Cell [x][y] of the concatenated matrix equals the sum of the rows multiplied by the columns. Some C code explains what I mean:


for (c=0; c<4; c++) for (r=0; r<4; r++)
    conc[c][r] = m1[0][r] * m2[c][0] +
                 m1[1][r] * m2[c][1] +
                 m1[2][r] * m2[c][2] +
                 m1[3][r] * m2[c][3];

Note that the order in which you concatenate matrices is important! That's logical: If you first rotate 90 degrees around the x axis, then 45 degrees around the z axis, you get a different rotation than if you would have done these rotations in the opposite order.

That's the basic stuff. Here's how to put it in practice. Imagine you have a cube. It's located at (100,100,100) in 3D space, and should revolt around that coordinate. It's rotation is (rx, ry, rz), and of course we alter rx, ry and rz in a nice loop to have a spinning cube. The vertices of the cube can be defined as follows:


     1:    -50, -50, -50
     2:     50, -50, -50
     3:     50,  50, -50
     4:    -50,  50, -50
     5:    -50, -50,  50
     6:     50, -50,  50
     7:     50,  50,  50
     8:    -50,  50,  50

Note that the cube is initially defined at the 3D origin. That's because we wish to rotate it: If you would rotate a cube that was defined with it's center at (100,100,100) it would revolt around the 3D origin also, causing a huge sweep through 3D space. The center of the cube, a.k.a. it's translation, should be the (100,100,100). So, we construct a matrix, by starting with rx. We construct another matrix, for ry, and concatenate the two. Then we construct another matrix for rz, and concatenate it. Finally the translation is added, this can be done by directly altering the relevant matrix elements, cell[3][0], cell[3][1] and cell[3][2] (for x, y and z respectively). Then we toss the vertices in the final matrix, and voila! The rotated coordinates need to be processed of course to display them on the screen. You could use the following formula for that:


     screen_x = rot_x * 500 / rot_z + 160;
     screen_y = rot_y * 500 / rot_z + 100;

Note that I used 160 and 100 here as the centre of a 320x200 buffer. The resulting 2D coordinates can directly be plotted on your display, providing that they are NOT offscreen.

OK, that's the basic stuff. Here's some more stuff to wet your appetite: You don't have to stop when you've concatenated rx, ry and rz. For example, if you have two cubes, with one circling around the other, you could define a rotation matrix with only a rotation around the x axis for the second cube. If you concatenate that matrix to the matrix of the 'parent' object, the circling cube will be rotated by the matrix of the first cube PLUS it's own matrix. This makes it possible to have a 'hierarchical' system of objects: For example a robot, with arms that rotate relatively to the body of the robot (concatenate arm matrix to robot matrix), and hands rotating relative to the arm (concatenate again).

You can do other nifty things with matrices too, like inverting them. This can be used in quick surface culling, I'll talk more about that later, this article is getting a bit lengthy already.

That's all for now, experiment a bit with it, try to get your dot cube on the screen, and if it doesn't work for you just send me an e-mail explaining where it goes wrong. If you're nice enough I might even answer. :)

Article Series:

Building a 3D Portal Engine - Issue 01 - Introduction
Building a 3D Portal Engine - Issue 02 - Graphics Output Under Windows
Building a 3D Portal Engine - Issue 03 - 3D Matrix Math
Building a 3D Portal Engine - Issue 04 - Data Structures For 3D Graphics
Building a 3D Portal Engine - Issue 05 - Coding A Wireframe Cube
Building a 3D Portal Engine - Issue 06 - Hidden Surface Removal
Building a 3D Portal Engine - Issue 07 - 2D & 3D Clipping: Sutherland-Hodgeman
Building a 3D Portal Engine - Issue 08 - Polygon Filling
Building a 3D Portal Engine - Issue 09 - 2D Portal Rendering
Building a 3D Portal Engine - Issue 10 - Intermezzo - 8/15/16/32 Bit Color Mixing
Building a 3D Portal Engine - Issue 11 - 3D Portal Rendering
Building a 3D Portal Engine - Issue 12 - Collision Detection (Guest Writer)
Building a 3D Portal Engine - Issue 13 - More Portal Features
Building a 3D Portal Engine - Issue 14 - 3D Engine Architecture
Building a 3D Portal Engine - Issue 15 - Space Partitioning, Octrees, And BSPs
Building a 3D Portal Engine - Issue 16 - More On Portals
Building a 3D Portal Engine - Issue 17 - End Of Transmission