Today I came across a video in YouTube featuring the history of Ken Silverman’s Build Engine.
I remember spending countless hours, when I was young, using the Build tools for designing and scripting levels for games such as Duke Nukem 3D and Shadow Warrior, as well as creating new artwork and even editing the game configuration files (CON files).
Build Engine’s CON files were my first approach to programming, way before I learned how to program using C++. They used to have a weird syntax, but you could do all sorts of changes to the game. Even defining new monsters and items was possible thanks to CON files.
Here’s the video. It’s about 10 minutes long, but completely worth it.
In my last article, I provided some overall details on how to load Quake 2 model files (also known as md2 files) and described how these models would store its animations in their so called keyframes.
By the end of the post I discussed the fact that (as you could see on video) the model animation looks rather “choppy”. In this post I will explain what we can do to improve the animation rendering process for models animated through keyframes.
What we are going to do in order to smooth the animation is, instead of just rendering the keyframe data directly, take advantage of a factor that we haven’t completely explored yet: time.
If by the end of the last post you started working on rendering md2 models, chances are so far you have some sort of time control that allows you to determine which keyframe to render.
The rendering problem that we face is characterized by the fact that sometimes, for a given elapsed time, we determine that the actual keyframe we have to draw lays between two keyframes. Let’s call these the nth and nth+1 keyframes.
In order to draw the mode to the screen, we face two choices: select the nth keyframe or the nth+1 keyframe. What’s important to know here is that in either case our choice will be wrong. This is because the actual data that we need does not exist, and so, it’s impossible to render the model correctly. Forcing the choice to the nth or n+1 keyframe is what makes our model animation look choppy.
Not everything is lost though. Even if we don’t have the data we need, we can infer it.
Should our needed keyframe actually exist, we know it would lay between two other keyframes. Now, as we have some sort of time control mechanism, we can determine which ones these two actually are. Under these conditions, something we can do is determine the “distance” from the current time mark to each keyframe’s.
Using this information, we can guess the keyframe that’s supposed to lay in between by interpolating both keyframes in time. The idea is to perform a convex sum. The following C++ pseudocode depicts the concept:
Here, guess holds our guessed keyframe, Vertex is a struct composed of three floats and t is a parameter dependent on the elapsed time that has been adjusted to the [0,1] interval. When t=0, it means the keyframe to render is actually the nth keyframe. Conversely, t=1 indicates the keyframe to render is nth+1. Finally, notice that when t=0.5, the guessed frame will be halfway between keyframes n and n+1.
The following video shows the improved rendering process in action:
Notice how smooth the animation actually looks. This video was generated by running the animation at just 2 frames per second.
Interpolating between keyframes is certainly possible and, in our conducted tests, it really helped smooth the animation process.
This added visual quality does come at a cost, though. Every time we have to animate the model, we will have to iterate over the keyframe array, interpolating the values corresponding to two consecutive keyframes. The additional CPU overhead is well worth it nevertheless, dramatically improving the quality of our animation.
Many factors have been left out of this post. In particular, time control, elapsed time calculation and how to determine which keyframe should be rendered at a given time were all omitted. I believe these features are dependent on the kind of application being written and different formulae will or will not work in different situations. The best thing to do is to design a model that works for your application and produce a simple way to obtain the data needed to apply these concepts.
By mid June 2010 I worked on a personal project that consisted in rendering models from the classic Quake 2 game by Id Software. Here’s a video of the renderer.
Quake 2 was one of my favorite games when I was young and researching how to load and render its 3D models instantly sent me down the nostalgia path.
For those who might be interested in developing their own loader, Quake 2 models are very easy to read and parse from languages such as C and C++. This is mostly because .md2 files consist in a binary file format that we can easily read into C structs.
David Henry does a great job at explaining how the bytes are stored internally, so I’m not going to reproduce his work here. Nonetheless, here’s the md2 file header:
Quake 2 model files organize vertices and triangles into keyframes: a series of poses that enable us to draw the model animated. The texture to use when rendering the model is referenced by the file too. Each file might point to zero or more textures in the PCX format. Textures are called the model’s “skin” in Quake 2’s terminology.
The video above were generated using the custom renderer that I wrote. It is using OpenGL and GLUT to create the window and draw the model.
Now, you’ve probably noticed that the animation in the video above looks rather “choppy”. It’s definitely not smooth. The reason is that keyframes provide a base for animating the model, but not enough frames are provided as to produce a “continuous” animation.
In my next post I’m going to show you how we can improve this situation. Stay tuned!
C++ is a great language when it comes to extensibility. I used to think most customizations were possible only because of the famous C preprocessor, however, other features such as operator overloading open the door for a whole new degree of extensibility too.
Operator overloading is a mechanism built right into C++ that allows classical operators such as +, *, /, – to be “overloaded” to operate on our objects. In some scenarios, operator overloading can greatly improve program readability, as it provides an infix notation for denoting operations on two objects.
This post is not about operator overloading in general, however (at least not about overloading the typical operators), but rather, about overloading the special operators we have in C++. In particular, and as you may have guessed from the post’s title, I’m interesting in talking about the “operator bool“.
operator bool is the operator that allows us to define if and how our objects can be implicitly cast into a boolean value. Why would you want to define an implicit conversion from an object into a boolean value? Well, it turns out there are a couple of cases where it can really help improve program readability.
Let’s consider the following example. Here, I want to write a program that reads a text file.
Now, there are a number of things that can go wrong when reading a file. The file might not exist. We might have read past it’s end. An error could’ve occurred. Etc. Wouldn’t it be great if we could test whether everything was OK without having to ask for each single possible error? Enter operator bool.
Notice the loop condition. ifstream instances can be implicitly cast into a boolean value to test for non-existing files, EOF, and other read errors.
Overloading operator bool is really easy. In the next snippet I’ll show you how. Imagine we have a data provider class that, er, provides some data. We want to be able to test whether the stream is valid and has data just by dropping the object reference into a conditional.
Easy, huh? One area where operator bool really shines is writing a custom smart pointer implementation. Operator bool can allow your library’s users to test whether a smart pointer is null just by implicitly casting the smart pointer instance to bool.
Have a look at the following example. This is something we’re doing today with Algorithmia’s Vortex-Engine.
In conclusion, C++ operator overloading is a powerful feature that adds a great deal of flexibility to the language. Nothing prevents you from redefining and completely changing the meaning of the operators that work on your objects. It’s the programmer’s responsibility to determine whether overloading an operator makes sense and actually improves readability, instead of tampering with it.
In general, use common sense and remember that with great power comes great responsibility.