On Saturday, I finally had a chance to dig into the 3D math part of this project – and then it’s taken me until tonight to write about it. But you can see the results in the picture – ooh! It’s a cube! And it rotates! Exciting!
I will point out that this cube is, as they say in the demos, entirely dynamically computed in real time! Of course, it’s still not up to snuff with what you’d see in a good demo for the Amiga 500. Those demoscene coders can do filled-polygon cubes and still get a better framerate than I’ve got so far. But it’s a start.
Writing the code for the math was actually a lot of fun. I’m using the standard approach from computer graphics where the entire problem of converting a 3D scene into a 2D projection in screen coordinates is handled by a bunch of linear algebra. I’ll describe the broad strokes of what I did below, but it’s a lot to discuss and I’ll probably do it badly. There are lots of books on the topic; the one I used when I needed a refresher on some of the details was an older edition of Edward Angel’s Interactive Computer Graphics.
The basic idea is that you represent each point in the geometry by a 4-element vector like [x, y, z, w]. Then you create a bunch of 4×4 matrices to do all your translations, rotations, scaling, and perspective transformation. You then multiply all these transformations together into a final transformation matrix. When you multiply the transformation matrix and point, you get a vector [x’, y’, z’, w’]. In the transformed vector, x’ and y’ are the screen coordinates of the point (with an important caveat involving that w’ term that I’ll get to later). Whew!
And yes, this means that to figure out the two-dimensional projection of a three-dimensional object, we’re using four-dimensional math. Makes you appreciate your graphics card a little more, doesn’t it?
For my first test, I wanted to keep things simple. A cube has 8 vertices, and my transformation was built from three matrixes:
- Rotation matrix. I wanted to spin the cube around the X axis. I increment the amount of rotation every frame to provide the animation.
- Projection matrix. The projection matrix maps an object in 3D space to a 2D projection. The simplest kind is an orthographic projection, where objects don’t get smaller when they’re farther away, and parallel lines don’t converge in the distance. Using this for the first test also let me fudge a little with my “camera positioning”.
- Viewport matrix. The projection matrix gave me (x,y) coordinates on a scale from (-1,-1) to (1,1). The viewport matrix transforms that into screen coordinates that we can use to draw lines on the Amiga’s display. It’s basically scaling the x and y coordinates and adding offsets so that we get numbers that will fit on a 320×200 screen. The tricky part is that I wanted +Y to be “up” in my world coordinates, but the +Y axis goes down in Amiga screen coordinates. I was able to flip the Y coordinates by adding a negative scale factor.
Matrix multiplication is not commutative, so these matrices had to be multiplied together in the correct order to have the desired effect. The intuitive way to understand it is that the “rightmost” matrix is applied to the geometry first. With that in mind, my final transformation matrix T ends up as:
T = viewport matrix * projection matrix * rotation matrix
Now, the viewport and projection matrices are constant, so I was able to multiply them together once at the start of the program and save the result. Then, for every frame I had to calculate the rotation matrix and recreate T. (It’s safe to save the result of V * P because matrix multiplication is associative).
I had fun writing and testing the matrix code. Doing it in C felt a little weird, because my first instinct as a C++ programmer is to create classes for matrices and vertices. Even without the language support, I tried to implement those data structures in a relatively object-oriented way, as a set of well-defined C functions to operate on matrix structs.
I tried to do as much of it as I could without looking up references, including working out on paper the format of the rotation matrices (I couldn’t remember off the top of my head exactly where the sine and cosine terms go to rotate around various axes). I did refer to the book when it came time to do the projection matrix functions, since those involve more complicated shear and nonuniform scale operations. With that refresher, I was able to come up with the viewport transform on my own (with a little trial and error).
This code went together quickly. The trickiest problem turned out to be a sneaky typo in the code to generate the orthographic projection. The most time-consuming part was getting the viewport matrix to position the drawing area correctly. My failed attempts usually result in lines drawing partly or entirely off the edges of the screen. On a shared-memory system like the Amiga, “drawing off the edges of the screen” is another way to say “scribbling on a random chunk of memory”, with usually catastrophic results.
Once I got a cube that was spinning, instead of a computer that was crashing and rebooting, I wanted to do something a little more complicated. I added some more rotations around the other axes, so that the cube would spin and wobble in a more interesting pattern. I also wanted to switch the orthographic matrix out in favor of a proper perspective view (where objects get smaller in the distance and lines converge toward a vanishing point).
Using a perspective view also meant I had to think a little more about my camera position. I added a translation matrix to move the camera (or, alternately, move the world relative to the camera) away from the cube, so that the cube would be entirely within the viewing volume specified by the perspective transform. So it looked something like this:
T = viewport * perspective * translation * X rotation * Y rotation * Z rotation
And again, I could calculate (viewport * perspective * translation) just once, and multiply in the rotation matrices with each frame.
The immediate results of trying this were a fine-looking set of lines scribbled all over my drawing screen. And over some unrelated windows. And then the dreaded Guru Meditation error. Obviously, I’d forgotten something.
Remember how I said a point was defined by four numbers – x, y, z, and w? And that we were doing four-dimensional math? 3D graphics uses something called homogeneous coordinates to represent points (I dare you to read the Wikipedia page in the link). That w parameter is always a 1, and as long as you’re only performing affine transformations (translations, rotations, etc.), w’ will also always be 1.
But a perspective transform is not affine (it doesn’t preserve parallel lines, for one thing), and as a result w’ after a perspective transform is not 1. In order to get our coordinates back down into a regular 2D space, we have to calculate x’/w’ and y’/w’. Once I added those divisions to my code, my cube looked much more like a cube. I just wish I’d remembered to get some screen shots of the more interesting, um, attempts.
There’s a couple more places I could go with this, including hidden line removal and filled polygon surfaces, but the first thing I want to do is take some measurements and see if I can speed it up at least a little.