I’m steadily progressing through the OpenGL API and adding experiments to the test code as I go to make sure I’ve got the basics down. Here we can see the result of adding camera motion, texturing, multiple shader programs and instancing to the code.

Ok, this will go down in history as the least exciting first screenshot in the history of first screenshots, but here you go:

There’s a whole bunch of experimentation going on here:

• The window contains an NSOpenGLView subclass using CVDisplayLink to link to the drawing loop
• Everything is rendered with “modern” OpenGL (3.2 core)
• The cube is a vetex array object, with buffers bound to the array and element array buffers
• Matrices and vectors are coming from my own Matrix and Vector libraries
• Vertex and Fragment shaders are doing the positioning and lighting
• The ground is generated by a Geometry shader
• The cube has a “selected” outline: this is generated by writing to the stencil buffer while drawing the cube the usual way, and then applying the stencil and a custom vertex and fragment shader that render it again in a fixed color and at an increased size

In a previous post, I repeated a piece of code retrieved from the Internet that was intended to calculate the interval since the last frame when using CVDisplayLink. Unfortunately that code was actually incorrect, what it calculated was the frame rate.

I present the corrected code below in the hope that my answer will prove useful to others:

double frameRate = 1.0 / (outputTime->rateScalar * (double)outputTime->videoTimeScale / (double)outputTime->videoRefreshPeriod);

static int64_t lastVideoTime = 0;
double timeSinceLastUpdate = 0.0;
if (lastVideoTime) {
    int64_t videoTimeDelta = outputTime->videoTime - lastVideoTime;
    timeSinceLastUpdate = outputTime->rateScalar * (double)videoTimeDelta / (double)outputTime->videoTimeScale; 
}
lastVideoTime = outputTime->videoTime;

As if trying to drag memories of vectors and matrices out of the long-discarded parts of your brain reserved for high school mathematics wasn’t hard enough, another curve ball is thrown at you when you discover that none of your text books, DirectX or OpenGL seem to agree on exactly which way round they go.

A typical text book might make reference that DirectX uses row vectors or row-major matrices while OpenGL uses column vectors or column-major matrices, and then the text box author will pick his own favorite style, which may be neither, and proceed to rattle off the fundamentals of affine transforms leaving you unsure whether they’ll work for you or not. A particularly mean text book I have switches randomly between row and column vectors depending on how much room he has on the page.

The OpenGL FAQ, somewhere where you might hope to have the situation cleared up somewhat, is totally cagey about this too. I’ve quoted their answer to the question “Are OpenGL matrices column-major or row-major?” here:

For programming purposes, OpenGL matrices are 16-value arrays with base vectors laid out contiguously in memory. The translation components occupy the 13th, 14th, and 15th elements of the 16-element matrix, where indices are numbered from 1 to 16 as described in section 2.11.2 of the OpenGL 2.1 Specification.

Column-major versus row-major is purely a notational convention. Note that post-multiplying with column-major matrices produces the same result as pre-multiplying with row-major matrices. The OpenGL Specification and the OpenGL Reference Manual both use column-major notation. You can use any notation, as long as it’s clearly stated.

Sadly, the use of column-major format in the spec and blue book has resulted in endless confusion in the OpenGL programming community. Column-major notation suggests that matrices are not laid out in memory as a programmer would expect.

To understand what’s going on and get rid of our confusion, we need to remember how matrix multiplication works. For the purposes of this blog entry I’m just going to use 2 x 2 matrices because I don’t have enough room to do the full 3 x 3 or 4 x 4 matrices that one uses in practice. Here’s how we multiply a 2d vector by a 2 x 2 matrix:

You might recall from high school that matrix multiplication is only defined when an n x m matrix is multiplied by an m x p matrix, and that the result is an n x p matrix. So in this case we treat the 2d vector as a 1 x 2 matrix (a row vector), and can multiply it by a 2 x 2 matrix to produce a new 1 x 2 matrix, ie. another 2d vector.

We can’t use a 2 x 1 matrix (a column vector) because matrix multiplication is not defined for that way round.

So now let’s introduce transforms, which is why we’re using matrices to begin with. Because we’ve simplified to using a 2 x 2 matrix for our examples, the only standard transforms available to us are  scaling and rotation in one axis, but the same works for all other rotations and translation in the bigger matrices.

The most elegant way to think of a transform matrix is as a collection of basis vectors of a new co-ordinate space we wish to transform the co-ordinates represented by the vector into. Matrix multiplication takes the dot product of each vector co-ordinate by the appropriate basis vector. Let’s use the identity matrix as an example:

Multiplying any vector by this matrix gives us the vector back. The worked equation shows us that one basis vector gives us the full amount of x and no y, while the other gives us no x and the full amount of y. We can use the vector to extract the basis vectors in the same way:

Extracting the basis vectors of the identity matrix we can get [ 1 0 ] for the basis vector of the x axis and [ 0 1 ] for the basis vector of the y axis. We can draw these vectors on a very dull graph to prove that they are indeed the unit vectors describing the axes of our untransformed co-ordinate system:

We can do the same for a scale transform:

And for a rotation transform:

So that’s the theory out of the way, if you want to know more about that kind of stuff or about 3d vectors, homogenous space, 4 x 4 matrices and all that kind of stuff go pick up a math textbook. All of the above is just to fix in our minds that we fundamentally care about the basis vectors that a matrix gives us and give us a way to translate text books later.

Let’s now get back to the fundamental question of order of the matrix. This matters because computers don’t have two-dimensional memory, memory addresses are linear and we have to pick a sensible way to lay out and address a matrix. You might choose something like this:

template <class T>
struct Matrix2 {
  T a, b, c d;
};

We flattened it down, placing the first basis vector contiguously and then the second after it. So far this matches what OpenGL claims. Vector and matrix multiplication also seems to work just fine:

Vector2<T> operator*(const Vector2<T>& v, const Matrix2<T>& m) {
  return Vector2<T>{ v.x * m.a + v.y * m.c, v.x * m.b + v.y * m.d };
}

So we’re still not any closer to figuring out what’s going on with all these text books and what they’re saying about OpenGL’s ordering. At least we have a reasonable understanding to try an experiment, let’s re-order our naming convention to match what the text books say OpenGL does:

All I’ve done is change the names of the values within the matrix, the rules of matrix multiplication still apply. That means to multiply a vector by this matrix, I have to change the names in the equation to match the names changed in my matrix:

The rules have not changed, just the names. I’m re-iterating that because it’s important. If we didn’t change the names of the values in our multiplication equation, we’d be multiplying different values from before — in fact, we’d be multiplying by the transpose of the matrix we intended.

Our basis vectors haven’t moved either, the names have changed there too:

That’s not what we wanted, and not what the books tell us about OpenGL. How do we extract the columns of the matrix instead of the rows?

The trick is to use column vectors! Now remember that we can’t multiply a 2 x 1 matrix by a 2 x 2 matrix, but we can multiply a 2 x 2 matrix by a 2 x 1 matrix and as a result get another 2 x 1 matrix:

We need to add a different function for dealing with this order of operation, but fortunately the types are different so this is pretty easy. In fact, the only difficult part is that I’ve changed my naming convention part of the way through the blog post, so the previous code uses the wrong names.

For sake of clarity here are both functions with the current naming convention, that is a column-major convention:

Vector2<T> operator*(const Vector2<T>& v, const Matrix2<T>& m) {
  return Vector2<T>{ v.x * m.a + v.y * m.b, v.x * m.c + v.y * m.d };
}
Vector2<T> operator*(const Matrix2<T>& m, const Vector2<T>& v) {
  return Vector2<T>{ v.x * m.a + v.y * m.c, v.x * m.b + v.y * m.d };
}

Now we have a matrix class that can deal with the basis vectors being in rows or columns, and multiplication by row vectors or column vectors. In fact the class doesn’t care at all, if you post-multiply a row vector by the matrix, the matrix rows are treated as the basis vectors; if you pre-multiply a column vector by the matrix, the matrix columns are treated as the basis vectors.

The rest of the functions, such as matrix/matrix multiplication, transpose, inverse, etc. remain exactly the same.

So why does it matter at all?

The first instance is when we read example transformation matrices off the Internet and want to put them into our class. We need to know the convention used; are the rows of the matrix presented the basis vectors, or the columns? Unfortunately this varies wildly, even Wikipedia arbitrarily flip/flops between the two conventions.

Here’s the example from the entry on Rotation:

If you’ve been paying attention, you’ll realize that it’s backwards from the rotation transformation I provided above. Fortunately they provided a column vector with it, so we know that the basis vectors are in the columns. If we were going to use row vectors and post-multiply in our code, we have to transpose this matrix; just like I did above in the example.

This especially comes up when you’re copying out the various projection matrices.

Another instance this matters is when copying sample code from one language and convention to your own. I used simple names a, b, c, etc. for the values but another common approach would be to use an x,y convention or two-dimensional array. At this point it’s critically important that you know whether the first dimension selects a row or a column in that particular implementation.

Remember that this is still just a naming convention from an algorithm point of view. Consider the following example of obtaining the determinant of a matrix; I’ve presented it both in a row-major and a column-major naming convention:

In the example, m2,1 and n1,2 are alternate names for the same matrix value and the only thing that changes in either side are the names used; m just happens to use row-major notation and n column-major notation in the naming.

This is important when copying code because for optimisation reasons, the code you’re writing will be laid out so that your basis vectors are always contiguous in memory. If you’re using row vectors, this means you’d be using a row-major convention; if you’re using column vectors you’d be using a column-major convention.

Annoyingly it’s often harder to figure out which convention code is actually using, and as we’ve seen above, it’s important to get it right so as not to accidentally transpose matrices in the code. When in doubt, look at the functions in the code that perform transformations, if there are such things.

The third instance where things get confusing is matrix multiplication. This isn’t specifically a naming and layout convention issue, but the convention you pick does matter because matrix multiplication is not commutativeTo understand why this matters, go back to the geometry examples above and consider the cases of a rotation and a translation. If we first apply a rotation transformation to a co-ordinate, and then a translation, the translation applies to the rotated co-ordinate. But if we first apply the translation, and then the rotation, the rotation applies to the translated co-ordinate.

This matters when we come to putting together our model, view, projection matrix.

Fortunately there’s an easy rule of thumb to remember here. Transformations apply from the vector outwards:

In other words, if we’re using row vectors we know they go on the left, so the left-most transformation is applied first; if we’re using column vectors on the right, the right-most transformation is applied first.

Thus for each vertex of a model, we first apply the model matrix to relocate the co-ordinate of the vertex from model space to world space, then the view matrix to relocate the world space co-ordinates into camera space, and finally the projection matrix to bundle it all into homogenous clip space

So finally, does OpenGL really require we use column-major matrices and column vectors? The answer is not really. That may have been true in the older fixed-function pipeline OpenGL implementations, which provided their own matrix classes and functions, but in the modern shader pipeline it’s largely up to you. GLSL supports post-multiplication and pre-multiplication, in your shader code you just place the vector on the left or the right depending on which convention the matrices you passed in use.

However GLSL does use a column-major naming convention for its matrix types; performing an array subscript operation on a mat3 or mat4 type returns a vec3 or vec4 of the named column, not row.

For consistency between your shaders and your engine code, you may want to use column-major to stop yourself going mad. Since all the books and references assume OpenGL requires column-major, you may want to just accept that to stop yourself going mad. And since the vast majority of example shader code out there does assume you post-multiply column vectors, it’s probably a good idea to stick with that otherwise your lighting might look funny.

While the kinds of games I like to play have traditionally used isometric graphics, and those do have a certain retro appeal, I wouldn’t be happy as a player today with that. Even playing OpenTTD today I miss being able to arbitrarily zoom and reorient the camera as I play.

Plus learning 3D programming has been something I’ve wanted to do since I first played Elite, and I even remember working out the math to do perspective when I was supposed to have been studying German in class at school.

So this project will be using OpenGL. I actually started playing around with this a year or so ago on iOS, but got distracted by the removal of Google Maps from the iPhone and wrote Embarcadero instead, so I’ve been revisiting some of the code I wrote back then.

I’m not going to use iOS for this project though, at least not at first. The extra overhead to dealing with the different platform, the simulator, or devices, would get in the way of the learning and experimenting. I’m going to use OS X instead, since that’s what’s running natively on my laptop. Of course OpenGL means the game should be easier to port to other platforms later if it gets that far.

There’s more than a few differences between iOS and OS X to get to grips with; for a start, iOS uses OpenGL ES 2.0 while OS X uses OpenGL 3.2. They are similar enough though:

On iOS, the most useful drawing surface is the GLKView, which we combine with a GLKViewController subclass that we implement that also serves as the view’s delegate. When that view is loaded we create an EAGLContext and assign it to the view, and this is made to be the current OpenGL context when each frame is needed to be drawn. To draw each frame we implement the glkView:drawRect: method and fill it with appropriate GLyness.

OS X’s approach is similar, but the names and roles are different. The convenient drawing surface is the NSOpenGLView which takes care of some of the setup for us, in particular the creation of the NSOpenGLContext for drawing. Rather than implement a delegate model, we subclass the view and override its methods such as drawRect: to draw a frame.

In either case, the core of any game is going to be the rendering loop. But then comes the question, how often do you redraw the screen? There’s several different answers to this, each with their own benefits and weaknesses.

The least effort approach would be to only redraw the screen when there’s something that’s changed. If the program is largely made of static, unchanging, content this should be a huge win since the CPU and thus power requirements would be much lower. But for a game, something should be always changing on the screen; nobody likes looking at a static image, so everything has little subtle animations.

If we’re going to do animations, we know that there will be some amount of time to calculate the animation and, especially if we’re moving the camera, the next frame in general. We could use this calculation time as the delay between redraws, and then immediately begin the calculation for the next frame once redrawing has completed. In other words, a tight loop, updating and rendering as quickly as possible.

That approach consumes more resource than we really need. On a low-powered device it probably makes no difference, but on a high powered device we could end up redrawing a hundred times a second, consuming far more power than necessary.

A middle-ground would be to use a timer fixed at the desired frame-rate, say 30 or 60 frames per second. Each timer fire would update the scene, and then redraw it, and sleep again until the next timer fire. If we took longer than 1/30th or 1/60th or a second then we’d have to be careful to ensure that we don’t queue up timer firings, perhaps by only setting the timer at the conclusion of the redraw based on the amount of time the redraw took.

All of those approaches, even the latter one, suffer from another problem though: screen tearing. This is because the screen itself is being redrawn at a fixed rate. What we really want is to have our game redraw the screen as often as the screen itself is being redrawn, with our rendered content presented along with the rest of the screen.

If we take longer than the screen refresh cycle to render a frame then it’s saved in the buffer we were using until the next screen redraw and used then, and drawing function skips however many intermediate frames we missed because we were busy.

Core Video on OS X and iOS provides is this feature via CVDisplayLink. In fact, on iOS it’s completely free because that’s what GLKit already uses and how it decides when to call the glkView:drawRect: method you implement.

On OS X we can use this too, but it requires a little more setup work to hook into the view. Fortunately Apple provide a Technical Q&A for this; with this in place the view’s drawRect: method will be called once, but we can ignore it and instead just implement the getFrameForTime: method suggested in the article.

For animation we need to know the time since the last frame, the outputTime object passed in can be used to calculate that:

double timeSinceLastFrame = 1.0 / (outputTime->rateScalar * (double)outputTime->videoTimeScale / (double)outputTime->videoRefreshPeriod);

We also need to do a little work in the getFrameForTime: method to set the context and deal with any threading issues that might come up.

NSOpenGLContext *currentContext = [self openGLContext];

// Display Link is threaded, so GL context must be locked.
CGLLockContext((CGLContextObj)[currentContext CGLContextObj]);
[currentContext makeCurrentContext];

renderer->renderFrame(timeSinceLastFrame);

[currentContext flushBuffer];
CGLUnlockContext((CGLContextObj)[currentContext CGLContextObj]);

Now we just need something to render!

When I was a boy, the first programs I ever wrote for a computer were computer games. They weren’t particularly good, but the sense of achievement of turning endless typing of BASIC code into a game I could actually play was immense. So what if you could get the Atlantis all the way back to Earth without visiting the Daedalus for oxygen? I knew you had to do that, so that’s what I did every time I played the game after writing it.

I even wrote games in high school. We weren’t allowed to play games in the computer labs, even at break or lunch, but the loophole was that if you wrote the game yourself then you were allowed to test it. And your friends could obviously help you test it too.

But then I discovered IRC, and Linux, and somehow got distracted writing IRC bots, IRC proxy servers, RSS news aggregators, init daemons and web browsers for a living. Even my personal projects ended up more utilitarian, such as iOS apps to let me order coffee from my favorite shop before I got there and to figure out what time the next Muni train leaves.

For my next project, I’m going back to my roots, and am going to write a computer game.

The kinds of games I love to play are the ones that have gotten lost in the rush for the “Triple AAA” quality that everyone seems to aspire to these days. Don’t get me wrong, my love for the Assassin’s Creed series is evident to anyone who sees my motorbike on the road, but I still yearn for a simpler kind of game.

Games like the original Sim City, Populous, Civilization, Railroad Tycoon and Transport Tycoon. You can probably even name the author of these games, it used to be possible for one person to write immensely playable games, so why should that have changed now? In fact, we’re seeing with the mobile revolution, that it hasn’t.

I’m not just going to write the game myself, I’m going to write the game engine too. Firstly because the kind of games I want to play just don’t fit into the FPS-centric engines out there today. But also because I really want the challenge of a complex software project, with many facets. I want to learn 3D programming, modeling, map generation, etc. And fortunately I don’t really have any goal in mind for how long it should take to write, just that I should enjoy doing it.

I’ll be blogging as I write mostly as an aid to myself. I find that trying to write down an explanation of concepts to a third party has proved a useful technique in learning those concepts myself. Since I’ll be learning a huge number of new things, that aid, along with the ability to go back and read my own explanations will be hugely useful.