Where is my playable Riven X?

Update: Part II is now available.

If one reads the Riven X project page, one can read “but I expect something barely playable in November”. Obviously, that’s not going to happen. Without going into boring details, let’s just say it’s been one hell of a semester.

So I thought I’d discuss a particular issue that’s been annoying me with Riven X: how to render a card. Specifically, how to efficiently render what needs to be rendered in a way that will yield the proper display order while allowing reasonably fast object rendering activation and deactivation.

Background theory

Essentially, Riven is made of stacks and cards. Just like in real-life, a stack contains multiple cards. But what does a card contain? Essentially, renderable objects: pictures, movies, sound effects. Obviously, sound effects are completely different from pictures and movies because they are strictly acoustic in nature. That leaves us to deal with pictures and movies as far as graphics are concerned. The biggest problem by far is to respect the display order. You see, initially a card is blank: it has no active renderable objects. But as scripts are executed in reaction to game state changes or user events, renderable objects start getting activated and deactivated. The rule of the game is then simple: whatever gets activated last is drawn on top of everything. In other words, you “pile things up” as you activate them. Deactivating an item means removing it from the stack while preserving the order of the other elements. We can make a simple diagram to illustrate this:

This seemingly simple problem has caused me more than one headache, and I’m still unsure the solution I settled upon will be satisfactory. Only sampling will tell, and I’m far from being able to do that. At this point, you may continue reading for details about potential solutions, or wait for my next entry which should be concerned with the solution I have chosen and the unavoidable reasons supporting that choice.

How are card objects stored?

This may not be final, but the current organization of data in cards is presently as follows:

1. A single vertex buffer object (VBO) for all the picture coordinates. This includes 4 vertex coordinates (one for every vertex defining the region of a picture, or the quad in OpenGL parlance) and 4 texture coordinates (essentially, a texture coordinate is a 2 component vector (for 2D textures anyways) that maps a particular point in a texture (in normalized coordinates – -1 to 1) to a particular vertex) for each picture.
2. An array of texture objects, one for each picture. The order of this array matches the order in the coordinates VBO.
3. An array of GLMovie objects, each of them using one VBO for vertex coordinates, one VBO for texture coordinates and one texture object.

How does storage affect rendering?

There are quite a large number of factors we could enumerate here, but the principal one has to do with minimizing state changes. OpenGL is essentially a large state machine (this is somewhat less true with the OpenGL Shading Language, but we’ll overlook that), and everytime you change the state, there is an associated cost. Some operations are more costly than others, but the general rule is to render such that state changes are minimized. Of course, one must also get accurate rendering, so not only must you respect the former rule, you need to do so in a way that preserves display order.

With that in mind, it should be relatively clear that in the case of a card, we’d like to bind (make current, activate, select) the picture VBO, render all enabled pictures (one at a time unfortunately, since we need to bind the correct texture object for each picture), then render all the movies. The next logical step is therefore to analyze how OpenGL renders a scene.

From commands to images

Without anything fancy added to it, OpenGL will display or draw primitives as they are submitted to it. In other words, OpenGL’s display order is OpenGL’s render order. However, to minimize state changes, it is often necessary to change the render order to group primitives that share some amount of state information. For example, if you have a red quad below a green quad below a second red quad, you’d normally render the first red quad first, then the green quad and finally the second red quad. However, it would be more efficient if you could render both red quads together, then change the front color and render the green quad. Unfortunately, if you do that, you’ll mess up your scene. OpenGL’s solution to this problem is called the depth buffer.

Give me depth

The depth buffer is essentially a two dimensional grayscale texture the same size as the OpenGL viewport (the area of the screen or window OpenGL is rendering into), which means there is one pixel in the depth buffer for every pixel in the viewport. Normally, a value of 0 means closest to the viewer and a value of 1 means as far away from the viewer as possible. Usually, the depth buffer is cleared with 1 at the beginning of every frame, in the same fashion as the color buffer.

With the depth buffer made writable and depth testing enabled, you can start specify a depth coordinate (also known as a z coordinate) for your primitives. That depth coordinate, once it is properly modified by applicable transform matrices and extrapolated for every fragment generated by rasterizing a given primitive, will be compared to the corresponding value already found in the depth buffer. If the new depth value passes the depth test, which usually means if it is closer to the viewer than the previous value, the fragment continues to be processed. Otherwise, the fragment is altogether dismissed, with the final effect of preserving whatever was already there in the final image that will be displayed on your screen.

In short, depth testing allows us to control display order while optimizing render order! It seems we have found our solution, but unfortunately things are not quite so straightforward. As will be made clear in an upcoming entry, depth testing has problems of its own. Stay tuned!