After restructuring my graphics program, one of the first features I wanted to add was back-face culling. That’s a basic graphics technique where you only draw a polygon if it’s actually facing towards the camera. For example, pick up a Rubik’s Cube (you do have a Rubik’s Cube within reach, don’t you?). No matter how you rotate the Cube, you can’t see more than three sides of it at once. As long as the shape you’re drawing is a convex hull, you can cull the back-facing polygons without any visible effect. And if you’re rendering in line mode, like I’ve been doing so far, you can get a sort of hidden-line removal out of it.

In principal, back-face culling is really simple. Let’s take one side of the Rubik’s Cube, which is a square polygon. You can think of each of its edges as a vector. If you take the cross product of two of those edges, you get a vector that’s perpendicular to the polygon and facing out from the “front”.

Next, you figure out a vector that goes from the camera to one of the vertices of the polygon. Then you calculate the dot product of those two vectors. If the dot product is positive, the polygon is facing away from the camera and you don’t have to draw it.

I figured it was a nice simple problem that I could hack out quickly. How could I mess up something that simple?

*Ah.* Let me count the ways…

First, I needed to change my data structure. So far, I’d only used vertices and edges (where an edge was just a pair of indices into the array of vertices). Now I needed to keep track of faces, which are polygons composed of multiple edges. Since each edge can be shared by two faces, I added a boolean to the edge to check whether it’d already been drawn each frame. So far, nice and easy.

There is one problem with using the cross-product of two edges to figure out the normal vector of a face: something called polygon winding. In order to make sure the normal is pointing outward, instead of inward, you have to pick your edge vectors so that they’re going counter-clockwise around the edge of the polygon (looking down from whichever side you want to be the “top”). My shared edge structs didn’t quite solve the problem – there was no way to define them so that they’d be counter-clockwise for every face referencing them. I could make it work, but it was easier to add a list of vertex indices in the correct order to each shape. It’s a little redundant, but right now speed is more important to me than memory efficiency, and it got the job done:

typedef struct Edge { int p1; // index to points int p2; // index to points int drawn; // 1 if already drawn } Edge; typedef struct Face { // vertex indices, in CCW winding order int mPoints[5]; // edges, so we can keep track of which ones are // already drawn. int mEdges[5]; int mNumEdges; // also number of points. Convenient, huh? } Face;

Of course, now that I had all that data structure to work with, I had to get it all filled in correctly, which was a real pain. I want to do other objects, but I may have to figure out how to define them programmatically.

With all those pieces in place, I could test my back-face culling routine and see it *fail miserably*. Um, yay?

Knuth writes somewhere about the dangers of premature optimization, but I ran into optimizations I added a year and a half ago and promptly forgot about. I only rediscovered them when they blew up in my face.

For example, during the Retrochallenge 2014 WW, I took a shortcut when multiplying vertices by my transformation matrix: I only computed the X and Y values. I didn’t have a depth buffer or anything, so I didn’t need to compute Z. Cue me, last night, looking baffled when every point of a cube had Z == 0. Oops.

The biggest optimization I did last year was my fixed-point math macros, which let me compute real number values using only integer math operations, which are much faster than any of the Amiga’s floating-point libraries. The downside is that the fixed-point numbers have a limited range – plus or minus about 32,000, in this case. For a while, I though I had a problem where I was overflowing those values. I probably was, but that was just a sign of a bigger, dumber mistake.

It’s important, when working in 3D, to always know what coordinate system you’re working in, and what set of transformations you’re applying to your data. I got this wrong at the outset, and when I tried to fix it the first time I was different, but *still wrong*, so it cost me a long time, and I had to go back to basics and look at the actual numbers in a very simple situation before I ever understood what was going on.

In my first implementation, I would create a single transformation matrix for each frame that was applied to my input data. A fixed set of vertices went in one end, and a set of screen coordinates came out the other. So this matrix looked something like this:

Screen × Projection × Camera_Translation × Model_Transform

Now, screen coordinates were never going to be the right frame of reference for the culling calculations (I realized after staring at results for an hour). I needed to see my vertices somewhere in the middle of that pipeline, which unfortunately meant that each vertex would have to be transformed twice. Oh, my poor framerate!

Unfortunately, for some reason I decided to compute the vertices with Projection × Camera_Translation × Model_Transform. This was the wrong choice because of the way the perspective projection interacts with the Z values of the vertices. But I couldn’t figure out that that was my problem until, in a desperate bid to simplify the situation, I replaced the perspective projection with an orthographic projection – and things started working the way they were supposed to.

By the way, in the course of this process I discovered that my camera translation had been wrong *the whole time*, and the shape was actually being rendered *behind the camera!* The only reason I was seeing anything at all was that, to save time, I never bothered testing the front or back clipping planes(!) This also meant that the shapes were all being drawn flipped along the Z axis, adding to my consternation. I swear I actually do know how this stuff is supposed to work. Please believe me!

To finally get things working, I ran the back-face culling routine on the polygon vertices after they were multiplied by the Camera_Translation and Model_Transform matrices, but not the Projection or Screen transforms. At long last, bingo! A cube that you can’t see through to the other side!

It’s not a perfect victory, though. It’s slower than it was. The extra calculations I’m doing cost more than the time i’m saving by not drawing the lines for the back-facing polygons. Now that the math’s right, we can fix some of that up – for example, it might be faster to calculate the normals once and then just transform them each frame. After that, we’ll see.