The Developer's Cry

FTGL font rendering in multiple colors

2012-01-23T14:53:00.000+01:00

In my last post, I was talking about font rendering in OpenGL by using the FTGL library. What I really wanted to have, however, was displaying a font with multiple colors. That is something FTGL can not do directly out of the box, but you can use a trick. Here's a short description of two methods to display text using multiple colors per character.

Method 1: Use a texture

The GLPolygonFont can be textured. Just bind your texture and call ftglRenderFont(). It really is as simple as that. The texture will stretch over the entire text drawn; if you want a texture per character then you will have to render the characters one by one. Mind that texture is laid over the bounds of the text. The bounds are usually a bit wider than you may expect. This example image was created using an image of a gradient as texture:

A drawback of using GLPolygonFont is that it has lower performance than for example the GLBufferFont. Also, at low resolutions you will see jagged edges.

Method 2: Using the stencil buffer

OpenGL's stencil buffer can be used for masking. You can tell OpenGL to draw where the stencil buffer is empty, or where the stencil is black. So to draw text in two colors, first draw one color, then draw a shape in the stencil buffer, and then draw the second color. It works a bit like woodcut printing in multiple colors. This example image was created using a GLBufferFont and the stencil buffer:

A drawback of the stencil buffer is that you will see jagged edges if you make a slanted line in the buffer. (It doesn't really show in this image, but they are there. The stencil buffer creates "hard" pixels.)

The stencil buffer is easy to use. The code for creating the image above is like this:

glColor4f(1, 0, 0, 1);
    ftglRenderFont(font, "World", FTGL_RENDER_ALL);

    glEnable(GL_STENCIL_TEST);
    glClear(GL_STENCIL_BUFFER_BIT);
    glStencilFunc(GL_NEVER, 0, 0);
    glStencilOp(GL_INCR, GL_INCR, GL_INCR);

    ... draw triangle (in stencil buffer) ...

    glStencilFunc(GL_EQUAL, 1, 1);
    glStencilOp(GL_KEEP, GL_KEEP, GL_KEEP);

    glColor4f(1, 1, 0, 1);
    ftglRenderFont(font, "World", FTGL_RENDER_ALL);
glDisable(GL_STENCIL_TEST);

The stencil buffer can also be used to other cool stuff like making holes in your text, or drawing text as a mask. [By the way, mind that masking using blending is near impossible using FTGL — ftglRenderFont() sets the glBlendFunc() for its own purposes.]

Concluding

I've shown two ways of rendering text in multiple colors. Both have pros and cons. Of course, there is a third method; use textures. If your text is static then you might as well use a single texture for the text. If your text is not static, you can still use one texture per character (glyph) but you lose the benefits that FTGL gives you.

OpenGL font rendering with FTGL

2012-01-15T18:06:00.000+01:00

OpenGL is a wonderful library for rendering graphics, but there is one thing it can not do: render text. It wasn't exactly made for this purpose. Graphics and text are two different things. However, at some point you are going to want to display text in your rendered scene. Then you will encounter the terribly missing feature of OpenGL, its inability to render text. There is no such thing as a glPrintf() function.

Drawing text with OpenGL
OpenGL is a graphics library and it can draw anything you like, even characters. But OpenGL is a very low level library and leaves drawing characters as an exercise to the programmer. There are a number of approaches you can use to draw text:

make a "stick font" in which all characters are made up out of lines. This looks really crappy but might be OK for an eighties style 3D vector game.
make an outline font in which all the outline of characters are drawn as lines. This looks fun but again, for an eighties style 3D vector game. Not only that, it also takes a lot of work to define the vertices for all characters.
load a bitmap font and use glBitmap() to render the characters. This is acceptable but mind that bitmap fonts do not scale well to today's high resolution displays. The characters will look pixelated and blocky when scaled up.
use textures; every character is a rendered texture of an image of a character. This works well but it takes a lot of effort to correctly create the textures for every character. Again, mind the scale. If you scale too high, it will look pixelated and blocky.

So, drawing text is hard. Or you can use an external font rendering library, such as FTGL. FTGL is great. FTGL does the tricks mentioned above for TrueType fonts. Unfortunately, using FTGL can be frustrating because the documentation forgets to mention a some very essential points. Hence the reason for writing this blog entry.

Pitfall #1: Getting FTGL to work
To use FTGL, you should #include "FTGL/ftgl.h". If that produces an error about ft2build.h, you should also install the Freetype development package. Point your include path (gcc -I) and linker path (gcc -L) at the right places.

Pitfall #2: Using orthogonal mode correctly

FTGL can render text on a plane in 3D space, but in general you switch to orthogonal mode using glOrtho() before rendering text. The origin should be set to the lower left or you may get strange results like text appearing upside down. Also, set the current pen color before drawing. That's easy.

Pitfall #3: Using glTranslate*() with raster fonts
FTGL supports two "raster" fonts: GLBitmapFont and GLPixmapFont. GLBitmapFont looks terrible and I would never want to use it, but GLPixmapFont looks nice. One reason to prefer GLPixmapFont over GLTextureFont is performance, another reason might be that it doesn't use texture memory. However, since it is a raster font, you can not scale nor rotate it. You must position using glRasterPos*(). The fact that you can't scale the font makes it less useful because it doesn't give nice results at small sizes. Which brings us to the next point.

Pitfall #4: Font sizes

You might be inclined to think that with ftglSetFontSize() you could set a font's size to 12 points and then get a good result on screen. If only it were that simple. In practice, you might see a blurry mess or even nothing at all. Why is this?
Fonts are rendered using dots per inch. OpenGL, however, has its own coordinate system. You initialized it by calling glOrtho(). Personally, I tend to set glOrtho() to pixel coordinates. Pixel coordinates have no relation to dots per inch, so it doesn't fit. [In theory, you should be able to set OpenGL's coordinate system to dots per inch and get good results right away, but haven't tried this. My guess is that this won't work either because of the following.]
When loading a texture font, FTGL creates textures for every character (or glyph) using the size and resolution parameters passed to ftglSetFontSize(). If you choose the parameters too small, the texture will be small and the result will be ugly. The key is to use fairly high values like 72 or simply one hundred. This may well cause the displayed text to appear huge; scale the result down again with glScale*() one tenth times or whatever works for you.
Since OpenGL is very good at scaling textured images, the end result will be good looking. Isn't it kind of dumb to use a large font size and then scale it down again? Yes, but if you don't, chances are that it won't be good looking.

Pitfall #5: Font scaling

This is pitfall is a consequence of scaling. When you scale the FTGL font, you must take the scale into account when working with bounding boxes and string widths.

Wrapping up
FTGL is a very nice OpenGL font rendering library with good performance. It has an easy to use C++ API and good standard C interface. The documentation is a bit lacking though. For example, to get the string width in standard C, use ftglGetFontAdvance() * scale.
Let me end with a link into the FTGL User Guide at SourceForge.

NSTabView tutorial

2012-01-02T13:14:00.000+01:00

Let's kick off the new year with some nice MacOS X Cocoa programming. I made a small music player in which you can switch views by pushing buttons. So on the click of a button, it replaces the content of the window with a new view. It is an interface that you now often see on phones and tablets, but I liked choosing this interface for my MacOS X desktop music player program.

There are different ways to accomplish the desired effect. I started out by replacing the window content, but the code turned out much cleaner when I opted for NSTabView. I didn't find many good examples of using NSTabView online, hence the reason for writing this blog entry. Cocoa programming is not very hard, just very confusing if you don't know how to use its components.

Start out by dragging an NSTabView control to your window in Interface Builder (IB). If you want, you can make the tabview encompass the whole window. By default, a tabview has a row of buttons with which the user can select tabs. In my case, I want to have a single button that controls the tabview. You can disable the row of buttons by selecting Style:Tabless in the Attributes Inspector, but it is best to leave it on while still developing.
The NSTabView has a number of Tabs you can set in the Attribute Inspector. This sets the size of the internal array that point to the views. Also, set the Initial Tab to the tab that you want it to display first.

Now open the Assistent editor and Ctrl-drag the NSTabView into the source AppDelegate.h. This will create the IBOutlet for this tabview. You can now use [self tabview] to programmatically address the control in AppDelegate.m.

You would think there is a way to hook up NSViews to the NSTabView from within IB ... I have not found out how to do this. So to make it display your custom views, you will have to tell it from code.

Oddly enough, NSTabView doesn't directly deal with views. It deals with NSTabViewItems. We don't have to deal a lot with NSTabViewItems to accomplish what we want, but you should be aware that NSTabView uses tab view items that hold the views for us.

Now, you can either add a new custom view in MainMenu.xib or create a new NSViewController class. The first option sounds easier but your application will have to contain code to control all these views. It makes more sense to give each view its own controller. Especially if your project is large you will want to have separate views and view controllers. It keeps the code cleaner and even makes the views reusable.

Let's create a new NSViewController class. Choose from the File menu New File and select Cocoa Objective-C class. Next, choose your class name "FirstViewController" and choose Subclass of NSViewController. This creates three new files: a header, a .m source, and a FirstViewController.xib. The XIB contains your new custom view. Start out simple; draw a label saying "View 1".
Repeat this step for view 2 and any other views you may have.

Now we have a NSTabView in the main window and a bunch of NSViewControllers with associated custom views. We want to put the views into the tabview.
First we have to tell the application that it has these custom views. The easiest way to do this is to instantiate them in IB. Open the MainMenu.xib and drag an NSViewController object from the Object library into the area where the other objects (like File's Owner, First Responder, and AppDelegate) are. Select the NSViewController and in the Identitity Inspector, set the custom class to FirstViewController. In the Attribute Inspector, set the Nib Name to FirstViewController.
Open the Assistent editor and Ctrl-drag the view controller icon into AppDelegate.h. Name it firstViewController. This should create a line like:

@property (assign) IBOutlet FirstViewController * firstViewController;

This will create a compiler problem that is easy to solve; in the top of AppDelegate.h put:

#import "FirstViewController.h"

Now we can finally go tell NSTabView to use this view. Open AppDelegate.m and implement this code:

- (void)applicationDidFinishLaunching:(NSNotification *)aNotification {
    // Insert code here to initialize your application

    // put the views into the tabview
    NSTabViewItem *item;
    item = [[self tabview] tabViewItemAtIndex:0];
    [item setView:[[self firstViewController] view]];

    item = [[self tabview] tabViewItemAtIndex:1];
    [item setView:[[self secondViewController] view]];
}

Build and run the application. The tabview should be working now.
For code cleanliness, I numbered my tabs using an enum so I can address them using symbolic constants. It is also possible to give each tab an identifier and select them by identifier.

Originally I wanted to have a single button control the tabview, so Ctrl-drag the button right into AppDelegate.m to create an IBAction for the button. What's really lame is that you can't ask an NSTabView what the index of its currently selected item is. You get an NSTabViewItem instead but I find working with indexes much more convenient. Here's a simple example of a button that cycles through all tabs:

- (IBAction)buttonPressed:(id)sender {
    static int cycle = 0; // assume initial tab was first

    cycle++;
    if (cycle >= [[self tabview] numberOfTabViewItems])
        cycle = 0;

    [[self tabview] selectTabViewItemAtIndex:cycle];
}

Now that the tabview is finally working, change the style of the NSTabView control in IB to Tabless.

This concludes my NSTabView tutorial. As said, Cocoa is not very hard, just confusing if you don't have a clue, and it can be tedious to get seemingly simple things done.

libobjects++ : A Python-esque library for C++

2011-12-04T18:57:00.002+01:00

Nearly exactly a year ago, I wrote about C+Objects: A Python-esque library for C/C++. The goal of this library was to ease programming in C/C++ in such a way that the code would resemble Python (to a certain extent) and that it would make programming in C/C++ as easy as it is in Python. I implemented the library in C++, which wasn't very successful, and last summer I implemented a version of it in standard C. The standard C version handles very much like Objective-C (rather than like Python); all objects are pointers. All objects are manually reference counted using retain() and release() calls. There is a print() function that prints any Object. It has runtime typing information and even features inheritance (in standard C!).

After a while I did get a bit tired of the interface though. Standard C has no this pointer for objects so you have to pass a pointer along as first argument to the method functions. Secondly, there is no operator overloading. For example, for the Array class you would call arrayItemAt(arr, idx) rather than just arr[idx]. This was particularly bothersome because in C++ you can overload the subscript operator and make it accept this syntax. Furthermore, standard C has no references like C++ has, so you can't address an array item and modify it on the spot.

So even though C++ is not my favorite language (C++ is too complicated to get any work done quickly), it does have some neat features that I needed for libobjects to work the way I wanted. A recap of the would-like-to-haves:

everything is an Object
objects can be stored into containers: arrays, lists, dictionaries
containers are also Objects (see first bullet)
container classes like arrays should only store pointers
objects are automatically reference counted
strings should be copy-on-write
number objects should be copied, not referenced
adding new user-defined classes should be made easy

For libobjects++ (the all new and shiny C++ rewrite of libobjects) I made a couple of design decisions that changed the game for the better.

One of the problems I was wrestling with was this: in C++ you can have an instance go out of scope, and it will self-destruct. If you wish to retain this object, you would have to make a copy using new and keep that pointer around somehow. For this reason, in the old C++ implementation, every Object was a proxy that had a pointer to a reference counted backend. It didn't work very nicely because it required you to add two classes for every newly defined class: one for the proxy and one for the backend.

The solution to this problem has multiple aspects. Firstly, the new implementation has the convention that the backend is only a struct. From this follows that all the method code that fiddles with the structure fields is present in the proxy class. Secondly, the Object proxy class itself has no real data fields; it only has a pointer to the data structure. Thirdly, the data structure has been encapsulated in a reference counting back end object. This encapsulation has been realized by means of a C++ template. Templates can be hard to write but they ensure correct typing, which is a good thing when you are building robust code. The Object class acts much like a smart pointer to the original data structure. The user of the Object class sees only the data structure without ever knowing that it is automatically being reference counted. I said it acts much like a smart pointer because it isn't really one, the user of the class doesn't bother with pointers at all. The user mostly uses the Integer number class, the String class, the Array class, which are derived from Object.

A note about reference counting; in my opinion it is best implemented using intrusive reference counting. Intrusive means the counter itself is part of the data structure; the object that is being reference counted. The most non-intrusive way of adding intrusive reference counting is to wrap the whole data structure by a new class that includes the reference count. Note how this is different from having a reference counted base class that the object must be derived from (see NSObject in Objective-C — which doesn't have templates, and thus solved it this way). Another note, I started out with a non-intrusive reference counting design, in which the reference count lives in a smart pointer that points at the referenced object. This costs another “hop” and therefore (a little) performance.

Although the internals of libobjects++ were kind of hard to write, it is a joy to use and see in action. I'd post a snippet of demo code, but libobjects++ is not fully finished at this point and not available for download yet either. The first things to be added next are the Array and Dictionary classes. After that I would like to add a File, Buffer, Thread, and maybe Socket. These would be simply re-implementations of older code I have lying around. Adding multi-threading to a reference counting library is another problematic topic I won't go into deeper right now.

Best way to think of libobjects++ is as a useful replacement for STL. All this basic functionality is available in STL and boost, but somehow those never quite did it for me. Their interfaces simply do not handle as easily as Python's or libobjects++'s.

I'd like to add that although libobjects++ is really nice (and fully type safe), Python does handle things differently quite fundamentally. In Python, a variable is a pointer to a backend of any type. When you for example address the pointer as if it were an array, Python will try to treat it as an array. If you then address the variable like it's a string, Python will treat it like a string. A runtime type check is made whether the object really supports a given method or operator, and if it doesn't, it will throw an exception. Think for a moment about how different that approach is compared to C++'s compile time type checking and my (now seemingly straightforward) implementation of libobjects++.
I generally consider the loose typing nature of Python one of its great strengths, but sometimes all this runtime checking can be a major nuisance. Other than a basic syntax check there appears to be hardly any compile time checking performed at all.

I could go on ranting about this topic for days, but to conclude this blog entry, I would like to give you something to ponder: C++ is becoming a language of the past decades, while it seems Python stays overshadowed by Java and JavaScript.

(Not that it matters much, every language has its uses).

Update: I ran into a problem with the templated back end. C++ has strict typing, so it became near impossible to create a generic container class that can hold any kind of item. There are ways around this ... I actually started over yet again with a design that is a compromise between the old and the new way: it has two classes, a front end and a back end. By convention, the back end does not implement many methods. The back end is friends with the front end, which can manipulate the back end directly. This works pretty good so far ...

Thread safety and thread specific data

2011-11-14T12:39:00.009+01:00

Every once in a while I work again on my Pythonesque / Objective-Cish library for standard C. One of the goals of this library is simplicity; ease of use. One of the ways of coming to an interface that is easy to use is the use of static variables. Statics keep the state and save it for later. A negative side-effect of statics is, however, that they break thread safety. In a multi-threaded program you can not have static variables because every thread works on the same memory.

Thread safety is an important issue. A library that is not thread-safe can only work correctly when used in serial codes. Today's computers have multiple cores, and tomorrow's computers will have many (and I mean many) cores. Although in some cases it is alright to use a forking model, it is generally not a bad thing to use threading whenever and wherever you can.

For synchronized access to global variables there are mutexes, semaphores and condition variables. For access to static variables we need something totally different. Each thread should have its own copy of the static variable, because the static keeps state and the state may be different for each thread. This is called thread-specific data. The creators of the POSIX thread library recognized the need for an interface to handle thread-specific data, so they included some functions for this in their API.

The answer to the problem of converting static variables into thread-specific data lies in using the functions pthread_key_create(), pthread_getspecific() and pthread_setspecific().

#include <pthread.h>

pthread_key_t key_buf = (pthread_key_t)0L;

void func(void) {
/* static char buf[64]; old code; not thread-safe */

    char *buf = pthread_getspecific(key_buf);
    if (buf == NULL) {
        if ((buf = (char *)malloc(64)) == NULL)
            error();

        if (pthread_setspecific(key_buf, buf) != 0)
            error();
    }
    ... do something ...
    ... save state into buf ...
}

void initialize(void) {
    if (key_buf != (pthread_key_t)0L)
        return;

    if (pthread_key_create(&key_buf, free) != 0)
        error();
}

In the code example above, key_buf is a key that is used to get access to the thread-specific data. The key must first be created (or initialized). This can be done in a serial part of the code, or you can put a mutex lock around the code that creates the key. Once the key has been created, it exists for all threads, even for threads that will be created later.
In func() we obtain the thread-specific buffer using the key for that thread-specific data. If this thread did not have its own allocated buffer yet, allocate it and assign it to this thread's specific data.
What if the thread exits? We allocated a buffer for this thread, so would it leak memory? The answer is no; when we created the key, we passed free() as second argument to pthread_key_create(). The second argument is the destructor, it gets called when the thread exits. Note that the destructor is bound to the key, so you must use each unique key in the same way for every thread. (Which makes perfect sense, but I'm just tellin' ya).

Concluding, thread-specific data is the perfect mechanism for keeping state in threads, where you would normally – in purely serial code – use static variables.

Portal rendering engine (or not)

2011-11-06T12:30:00.002+01:00

All this thinking and writing about the id Tech 5 engine in my last post brought back a lot of memories of DOOM and Quake. It sparked an old desire in me to develop a 3D engine for a first person game. As computers have become faster over the years, making a DOOM like game now is a lot easier than it was in 1993. On the other hand, people also expect to see more in a game now than back then. It shouldn't be your goal to be better than Rage or write the next Crysis. As an amateur, you can not set the bar that high for yourself, or you will fail. Yet it is still a challenge to create an engine that will allow you to walk smoothly through fairly large data sets.

The odd thing about DOOM is that it's hard to comprehend how its internals work because it's not really 3D and uses complex trickery rather than straightforward OpenGL to draw the scene. In 1993 there were no hardware 3D graphics cards for PC and even worse, the strongest CPUs in that day had a hard time doing 3D math. Therefore, DOOM employs techniques that you would not use nowadays.

I find DOOM interesting though for thought experiments. It works with a 2D map, which simplifies things greatly. The map may be 2D, but it is all vector based and it does include height. Starting out in 3D from nothing with little experience at all is a daunting task. Therefore I say it is a-okay to start out in a vector based 2D world and work up from there.

Imagine a floor plan of a building and having to visualize a first person view, walking through that building. Note that I start out by considering only a single floor and not a full apartment tower block.

Suppose the player is looking down a corridor. Left and right are closed doors to offices. Further on, an office door is open on the left side. At the end, the corridor continues to the right.

The engine may have loaded the entire map into memory, but there is no reason to calculate nor draw any geometry for rooms that are not visible. So, you want to take some scissors and clip away the parts of the map that can not be seen from the current player's position. It's easy to do when you look at it, but how can we do this in a computer program?

The hardest part of the whole rendering engine is determining what walls are visible and what walls are not, from any position on the map, looking into any direction.

The answer lies in dividing the map up into sectors. It is not based on a rectangular grid, a sector is merely a collection of walls. The corridor itself is such a sector. The office room that is on the left is a sector. The part at the end, where the corridor takes a right turn, that's a new sector. These sectors are connected through doors, but also through invisible doors that are always open. They are just lines on the map. These are portals. You can see through them and you can walk through them. Portals can also be small windows with bars, if you like.

Back to our rendering engine. The player is in sector 1. The engine considers drawing the walls in sector 1. During this process, it also encounters a portal to sector 2 (office room) and a portal to sector 3 (corridor takes a right turn). The player can see inside these sectors so the engine has to take sector 2 and 3 into consideration as well.

Only small parts of sector 2 and 3 should be visible (as we are standing in the corridor), so optimizations can be made. Before drawing the geometry at all, the engine performs view frustum culling. Since you can only see what is inside the portal, the viewing frustum for the sector is adjusted to the portal itself. The line of sight from the viewpoint (of the player) to the boundaries of the portal now form the new viewing frustum for looking from one sector into the other; from the corridor into the next room. This will cull any walls in sector 2 that are not visible and only draw walls that are visible from the player's point of view.

Sector 3 is another corridor which connects to more rooms and more portals. The other portals will be culled as described above. Hence it doesn't matter how much geometry is beyond sector 3, it will not be considered.

In a game engine, you can put this to other use as well. For example, to activate monsters: an enemy soldier in the next area might be walking in circles while whistling a tune, so that the player can hear him while he's not seeing him yet. This kind of games ties enemies down to the areas where they live on the map, if the player rushes past them on to the next sector, they are typically literally out of view and not being considered (or controlled) by the game engine any more.

Now for the real bonus. The geometry of a building is static, so unless you have moving walls there is no further computation involved. Simply send the geometry to the video hardware and the scene is being rendered.

So, is everything great? Not really. In theory you can adjust the view frustum to the portal to see into the other sector, but in practice it's not super easy to do in 3D. The portal may have an irregular shape which complicates matters.

Another practical issue is where to put portals on the map. It's easy for a human level designer to draw them into a 2D map, but it gets hard for 3D maps. Moreover, it's incredibly hard to develop a program that does this automatically. You can use a binary space partitioning (BSP) method but it tends to cut up a map into many more pieces than a human would, creating many more portals. Although not incorrect, but having many portals in a scene means having to do more calculations on the CPU, which is something we were trying to avoid.

You will find no references to the term portal in technical descriptions of how the Quake engine works. Quake maps are partitioned into clusters (sectors) and each cluster carries onboard a potentially visible set (PVS) in the form of a bit array that tells the engine what other clusters are visible from this cluster. It then proceeds to do coarse grained view frustum culling using bounding boxes, and finally rendering the geometry. OpenGL will take care of backface culling.

The PVS are precomputed and the maps have been optimally segmented so that Quake never has to bother with portals. It is well possible that portals are used in the preprocessing step, although they might as well use a costly brute force method like casting rays of light and see what walls are lit.

For id's latest game Rage, I realized that it's largely based on the same engine. Rage's texturing is awesome (read my previous post) but the way the corridors and halls work are still the same as before. DOOM3 and Rage feature very high polygon count environments but the trick is, they are still simple blocky corridors. A player can never climb on or crawl under pipes that run along the walls, revealing the fact that the player is in reality walking through a crude maze of invisible walls with some very detailed visuals situated behind those plexiglass walls.

The game's rendering engine deals with a small collection of flat walls per sector and selects which walls to render. Each flat wall has a property that points to the complex geometry that the player is about to see. The engine then sends that geometry to the GPU and the result is a highly detailed 3D scene for a very low cost of CPU power.

For further reading on portal engines I recommend flipcode's articles on Building a 3D Portal Engine. I have to say it is doubtful that any modern game today uses a true portal renderer. That aside, it is an interesting way of looking at the problem and flipcode's articles are a fun and educational read.

RAGE, MegaTexture, clipmapping

2011-10-25T22:41:00.009+02:00

Recently, id software (of DOOM and Quake fame) released their highly anticipated new title named RAGE. I don't normally write game reviews on this blog, but since I wrote about this game before way back in 2008 – three ... years ... ago! – and because I played through the game I felt like writing some more about how its new "Tech 5" engine works. The game's release was a bit of a disaster on PC (lead developer John Carmack raged out on twitter) because both NVidia and ATI did not deliver promised updates to their video drivers in time, but hey, I play the PlayStation 3 version.

One of the most impressive aspects of the game are its visuals. The outdoor scenes were described as "a moving painting". And indeed, it does look painted, which has mostly to do with the artists that did the graphics. Aside from that, this game is known for the fact that the graphics show no repeating textures. Every location, every object and every little detail has a unique look. The terrain in the game world is composed from a single gigantic and highly detailed texture. This is very special as this is usually not the case with traditional texture mapping, and id software is probably the first to show this off in a game. (Note: RAGE is not their first game to use this technique; in 2007 Quake Wars: Enemy Territory used an earlier version of the same code).

MegaTextures
Carmack uses a texture mapping technique in his rendering engine that he calls "mega textures" and "virtual textures". This is not just marketing hype first of all because Carmack is a geeky programmer and not a marketing guy, and secondly because it looks too good to be just marketing hype. I think I have a good impression now of how it works, it's something along these lines.

Traditionally if you want to texture map a cube, you'd have six faces of the cube and you would choose to texture it using six textures, one for each face. Or you could choose to have just one texture, and have it repeat. In games, if you wanted to texture map a large area, you would repeat the texture over and again. When you use a different texture for each face, not only will you be using up texture ids quickly, it will also cost performance. So what Carmack did since the beginning (already in Quake 1) was making a texture map like a sheet of paper, and wrapping it around an object. This way you get a fully textured model, with just one texture per model.

Terrain data is like a gaint object. Using geomipmapping you can have a single highly detailed mesh for the terrain, while still being able to render it efficiently and having level of detail (LOD) with respect to viewing distance. (NB. What is also possible is that they tricked the level of detail using multiple terrain maps, each with a little less detail, but this doesn't matter in respect to texturing the terrain).
To texture the terrain, a giant texture map with a resolution of something like 64000x64000 is used. It is impossible to load this texture into memory all at once, so it loads only tiles. Each tile is 4096x4096 pixels. For geometry that is further in the distance, a lower resolution texture is chosen (like mipmapping).
I don't know if RAGE employs this, but it is possible to do a dynamic in-between level of detail by blending the higher resolution texture with a lower res texture. My guess is that this would cost too much performance, but I really don't know.

Carmack mentions using tiles of 4096x4096 on the PS3. Note that the PS3 has five year old hardware by now, but also note that 4096x4096 is still a lot. For example, 1080p "full HD" is only a fraction of that.
Modern PCs have larger video memory than the PS3 so RAGE should look even better on PC, but there is a bandwidth problem with loading the data from disk that gets in the way, so not everything is sunshine on the PC.
4K by 4K amounts to 16 megapixels per texture. Take 24 bits per pixel and you're up to 48 megabytes of memory per texture. This may not sound like a lot of data, but it takes more than half a second to load 48 megabytes from a hard drive.
Now compare the 5 year old PS3 hardware to a modern PC, and notice how the PC has much more memory, much more graphics memory and much more processing power, but both are limited in maximum performance by the same speed of the hard drive.

To speed up loading times, textures are compressed. Compression has the disadvantage that it takes processing power to decompress the textures when they are loaded. You can choose to use hardware compression, in which case the GPU has to decompress the texture. The problem with this is that the GPU will be busy, while it already was busy doing renderings. Another thing is that there are better and faster compression codes available for CPU ... in RAGE, a CPU thread is used to decompress the texture data.

In addition to mega textures, Carmack uses a technique he calls "virtual textures". I guess it works like a demand paging system; whenever a texture is needed because it is going to be displayed on screen, it needs to be loaded into the video texture memory.
The texture may be loaded from a core memory buffer (cache), or from a memory mapped file (disk cache), or lastly from the source media, the BluRay DVD player. Of course, loading off DVD is slow and that's when you see "texture pop-in" artifacts.
This technique is also called texture streaming because it is constantly loading texture data as you move around and look around the world.

60 Hertz refresh rate
The game is promoted for its 60 Hz refresh rate. Many games use 30 Hz. Experienced gamers say they can easily tell the difference, as 60 Hz games feel a lot faster and snappier. Just try to remember Quake 3 Arena when it ran an yer ole 100 MHz 486, as opposed to Quake 3 Arena on modern hardware — the game is much more action packed now because everything reacts faster on a higher frame rate.
RAGE feels fast at times indeed. It is an achievement to write a game that leans so heavily on graphics and have a frame rate of 60 Hz. Where does all this speed come from? For one thing, RAGE doesn't do multi-texturing. Why would it, if all textured space looks unique anyway? All the graffiti on the walls have already been "burned in" by the artists. All that hard work was already done during preprocessing. Other things that are known to have been tricked are lighting and shadows. It's a game, as long as it looks good, it is good enough — no need to pull off compute-intensive raytracing-style mathematics for no apparent reason.

Clipmapping
Carmack is a very good 3D graphics programmer but he sure did not come up with these ideas all by himself. He does do his homework very good, apparently.

In the legendary game DOOM he popularized the use of BSP trees to efficiently render indoor environments. Use of BSP trees in computer graphics had been researched for many years by then, but it was a research paper published in 1991 that first described how gain lots of performance by using the BSP trees to draw a scene in a (then) unusual way: from the front to the back.

The mega texturing technique sounds an awful lot, no, exactly like clipmapping, a technique thought up by SGI researchers and published in 1998 in their paper titled “The Clipmap: A Virtual Mipmap”. You can read the full paper here.
Another term for clipmapping is the use of cliptextures.

Surprisingly, the paper also mentions a frame rate of 60 Hz. The 60 Hz frame rate is tied to the hardware limits of a high end graphics machine from around 1998, which does make you wonder if modern hardware could pull this off at 30 Hz too.

Carmack is not a bad guy and he knows where he came from; every now and then id software release the source code to their old engines for the sake of teaching students how to create 3D game engines.

The Game
RAGE is a fun game, but I have the feeling that they tried to make a game more in the likes of Red Dead Redemption, and too bad for them, Rockstar beat them. Unlike RAGE, Red Dead is a truly open world game and it is very different from the shooter genre. RAGE is a good shooter when compared to Quake, but it's not as frantic as shooters like Crysis or Killzone.

Maybe id software should give a shot at going back to their underground roots and produce a fairly simple, but large enough game that is pure brute and blunt fun rather than working for ages on producing a Hollywood blockbuster type of game. Take the Super Turbo Turkey Puncher for example. That was cool, and not because it was a mini game. It was simple and it was fun, and I wish I had it as a separate game. It would be killer on iPhone, I'm sure.

Remember DOOM and how it would get your adrenaline pumping. Halls full of imps to slaughter. The clicking sound as you picked up the shotguns left behind by enemies was so addictive. The monsters would moan and howl in pain as you were gunning them down.
Trent Reznor of NIN once phrased it like this: “the we don't give a shit attitude, it really struck a chord”.

Exceptional conditions: adding exceptions in standard C

2011-10-23T12:15:00.008+02:00

An important aspect of programming is error handling. A program is running, all is well, and then ... oh no! All of a sudden a condition occurs that was not supposed to happen, or at least the programmer wished it would not happen. A program usually checks the most common errors and may retry, work around, or simply abort the operation depending on how hard to resolve this error is.

There are software error conditions and there are hardware errors. Hardware errors are represented by software error codes. There are different ways in which an error condition is given to an application when it comes to programming:

error return value from a function
library reports error: in standard C, check errno
UNIX signal received
an exception was thrown or raised

Easiest to understand and use is the first one; if the return value of a function has a certain value (error code), then it signifies an error and the application should act accordingly. The application programmer himself must choose what error codes to use for error conditions.

The second case describes how the standard C library reports errors; the library functions return zero on success and -1 on error. To get more information about what error occurred, examine the error code in errno. Note, errno is not a normal variable but a function that returns a thread-safe errno value. All errno values are predefined by the operating system. The errno values are (either translated or directly propagated) return codes from the operating system's system calls.

UNIX signals may be sent by the (UNIX) operating system to signify certain conditions. These conditions vary from SIGALRM (a timer expired) to hard errors like SIGSEGV (segment violation, which is illegal memory access) and SIGBUS (bus error). Signals are handled by the process itself, but the signal handler is run in a different context. This means that the normal program flow is interrupted and continues after the signal handler has finished executing. A signal can even interrupt a system call, after which the system call will report the errno value EINTR (system call was interrupted). Signal handlers may be hooked by the application, but an application can not define its own signal numbers. The signal numbers are predefined by the operating system.

Exceptions are exceptional conditions that may be thrown or raised. An application may catch an exception, in which it will resume operation at the point where it first tried to do the operation. Because it involves stack unwinding and jumping through code, exceptions generally require special language support. Moreover, exceptions generally have a specific syntax in the form of try { ... } catch(Exception) { ... } or try: ... except Exception: .... Exceptions are a key aspect of the Java and Python programming languages, in which it is common use to throw exceptions for error conditions. In C++ exceptions exist but it is more left to the programmer whether to use them extensively or stick with error codes. In Objective-C exceptions exist but they are not commonly used.

Exceptions do not exist in standard C, but I thought it would be fun to add them. How do you add a language feature that is completely absent from C? Well, you can emulate them. In fact, I stole this neat idea from Objective-C; in Objective-C the NSException is implemented using setjmp()/longjmp(). Without using any macros to define try and catch, I came up with the following:

if (!catchException(exception_number)) {
... try some code ...

throwException(exception_number, "descriptive message");

} else {
printf("caught exception! %s\n", caughtExceptionMsg());
}
endException();

In this code, catchException() really sets up a try block. What it does behind the screens is creating an Exception object containing a jmp_buf and pushing it onto an exception watching stack. The code that actually catches the Exception is really in throwException(), which examines the stack to see if we want to catch the thrown exception at all. When it finds the corresponding Exception object, it cleans up the stack and jumps back to the initial starting point of the try block. If the exception is not being caught, print a message about the uncaught exception and abort the program.
If the exception does not occur, you are left with an object on the exception watching stack, which is why you need to explicitly call endException() to clean up the stack. Other languages do this implicitly.

This way we have added exceptions to standard C. There is a huge caveat to using exceptions correctly: as your program is able to jump back and forth through large pieces of code, you have to be extra careful not to leak memory. You can't have everything, but if you have something like an AutoReleasePool then this may help a great deal.

Bytecode interpreters, virtual machines, emulators

2011-09-04T13:44:00.020+02:00

Lately I've been working on programming a utility that translates more or less natural text to more cryptic firewall statements. In the translation process, I use two passes: the first pass translates to bytecode, and the second pass translates from bytecode to the final output. A huge advantage of using the intermediate bytecode stage is that this makes it possible to easily support multiple kinds of firewalls while having only one syntax for the input. The code for the output generator is completely decoupled from the input parser code. Cross compilers work in the same way. Modern compilers like gcc also work in a different way; they support multiple frontends for compiling different programming languages.

When I was still a student, I once wrote an assembler/disassembler for a nonexistent architecture. While a nonexistent architecture may seem an odd choice, I was inspired by the Java bytecode that executes in a virtual machine rather than on a real CPU. The professor did not give me a straight A only because I had not actually written the virtual machine that would run the code. The instruction set was rather extensive and implementing the full virtual machine would have been too much work for the limited time of the assignment. The feeling of what if always stuck with me however.

An emulated CPU has the following properties:

a bunch of general purpose registers
a program counter (this is just an address; the instruction pointer)
a stack pointer
a flags register (with a zero, sign, carry, overflow flag)
optionally: interrupt flag or current interrupt level
optionally: supervisor mode flag or current privilege level

Emulated interrupts enable you to let the system interact with I/O devices much like it happens in real computers. Whenever an I/O device is ready, it will interrupt the CPU, which will then automatically jump to the Interrupt Service Routine (ISR). The address of the ISR is read from an interrupt vector table that typically resides at a low memory address.
The supervisor mode or privilege levels offer the possibilities of implementing a sturdy “operating system” in the virtual machine, adding a hypervisor, and ultimately having virtual machines running in virtual machines.

The instruction set needs to have load, store, arithmetic operations like add, subtract, multiply and divide, logical operations like and, or, exclusive or, and bitwise operations like bit shifting and possibly bit rotation. Furthermore you need a jump (goto) instruction and a set of instructions for conditional branching, and push/pop to work with the stack. Lastly you could add some privileged instructions like loading the flags register or resetting the machine. At the bare minimum, there are about 25 instructions to be implemented. By comparison, the 8086 CPU has about 75 different instructions.

For a memory model, 64K ought to be enough for anybody ... Or you could give the system very little real memory and implement paging and swapping. Implementation wise, the virtual memory management could take place in either the guest or the host ... (when implemented in the host, the guest OS would never know its memory was being swapped in and out!)
A related issue is protected memory: can the current process write to a given address or not? Early micro-computers did not have support for paging, but they did have read-only memory in the form of ROM. You probably want to have memory mapped I/O, an interrupt vector table and some display memory representing the screen.

One of the problems I've always had with this model is that programming for such an emulated system is hell as you would need to write everything in its assembly language. To overcome this problem, you would really need to make a high level compiler generate the code. Nowadays we have gcc and if you're handy it should be possible to have it generate code for platform X.

Now let us take a step back and get back to bytecode interpreters. Java, Perl, PHP, Python, various kinds of BASIC and even some MUD codes all use a stack machine at the heart of their bytecode interpreters. The stack machine is the simplest kind of processor: it has no registers and its instructions only manipulate a stack. The lack of registers make both compilation and execution (or emulation) easy. Interpreted languages benefit from bytecode because interpreting bytecode is faster than having to go through the language parsing procedures all the time.

A bytecode interpreter for a scripting language is quite different from a full blown system emulator. For a bytecode interpreter, you can make up your own opcodes for any common operation you like. There is no need for an opcode to perform only low level operations; they can be high level operations just the same. For example, Python has opcodes for slicing strings. Until Python 3, print was a statement with an opcode equivalent rather than being a function. It's not cheating, it increases performance.

It's good fun designing your own bytecode interpreting virtual machine. There are a lot design of choices to be made beforehand. Do you want to fully emulate a CPU or not? Maybe you want to emulate any other hardware components? Will you write anything like a system BIOS in bytecode? Are you going to develop a self-hosting system? How far are you willing to take it?

Lion: Yet Another Review

2011-08-03T01:03:00.008+02:00

Cheerios, finally a new blog post after a long while. Haven't I been programming a lot lately? Well, yes and no. I've been working real hard on synctool, which is a sysadmin tool written in Python for doing software configuration management on clusters of computers. In github the development branch is now something like 180 commits ahead of the stable branch. After which I got the flu and after that I was on a well deserved long vacation. Just when I got back home, Apple released Mac OS X Lion so I had some interesting upgrading to do. In the past, I sometimes blogged about Ubuntu (Linux) upgrades, nowadays “I'm a mac” (sorry — btw, still doing lots of things with Linux at work) so I'll write about my experiences with the Lion.

Surprise surprise
Upgrading to Lion is a breeze. Just buy it from the App Store, download the program and off you go. After an hour or so you are now running Mac OS X Lion. It's as easy as that. But wait, as a sysadmin, there are a few things here that are making me feel uneasy.

I got Lion from the App Store, so I have no CD-ROM to install the system from if my system ever breaks. Apple solved this partially by including a system restore partition on your hard drive. Eww. Uhm. Well ... OK. I guess..?

Apparently there is a way to create a Lion install CD-ROM but Apple does not tell you how. It is (apparently) reserved to “power users” (or should I say “hackers”?). Doing so is not easy especially because the Lion installer magically disappears from your hard drive after the upgrade is done. After downloading the 4 gig or so installer I had to download it again to upgrade my laptop. This is not such a nice thing for Apple to do.

Upgrading my laptop took a bit more work. It's an older model white macbook with only 1 gig of memory. Lion only works on systems with 2 gigs of memory or more, so I had to do a small hardware upgrade first. I can't really explain, but Lion uses a ton of memory even though the running apps do not show big memory footprints in Activity Monitor.

Gimme gimme new features
Lion offers a number of new things. There isn't an awful lot, but then again, it was only 29 dollars or something. Some of those things were good, and some of those were bad. I love my Mac enough to blog about it and I do like Lion but grrrrrowls ... I'll give you the bad first.

Ironically most of Lion's biggest selling points were pretty useless to me. Honestly, it's mostly marketing hype. Here's why: my main system is a 27 inch iMac. Gimmicks like Launchpad and fullscreen Mail are nice on a laptop, but they are not useful (just plain awful) on a 27 inch screen. Lion's features are mostly ideal for laptops but not for desktop Macs.

new UI. Really? Yeah, but you have to look super hard to notice. And then when you do notice, it annoys the crap out of you because it does not look better than Leopard. Except for the squared buttons, which looks more like Microsoft Windows?
full screen apps. Great feature, but on large displays it is not useful. You just drown in this amazingly large screen. Which is kind of fun actually, because a regular PC never does that to me.
3 column layout for Mail. Oh wow. I hate it. It's a cheap Outlook imitation if you ask me. And it's ugly.
Launchpad. A big screen full of icons. Great. Sigh. I will never use it.
new trackpad gestures. Yeah, I do have a trackpad with my iMac. I'm just not comfortable with four and five finger gestures, rotating your hand, etc. For photo editing, I use a mouse (!)
Mission Control. Where did Expose go??
Dashboard is awful on a large display. It was nice in Leopard, the screen would fade out to darkness and your widgets would appear. You would click next to a widget in the void and the whole thing would zoom out and you would return to your desktop. In Lion, the whole desktop slides offscreen to the right (a dazzling animation that gives you a headache) and you are presented with a million (really, a million!) tiny knobs that are some kind of Lego base plate, and you can't even change that annoying background without hacking into your system library folder (!!!)
AirDrop. Maybe Lion's coolest feature, but it doesn't work with my old macbook. I don't even blame Apple for this because it is an older model and the WiFi chip in this macbook does not have the needed functionality, but as said, AirDrop is unfortunately useless to me.
FileVault now has whole disk encryption. To a lot of people, this feature came like five years too late. On the other hand, this feature is arguably useless to everyone. It enables you to encrypt even your system files, files that are identical on any Lion installation. Moreover, even though Apple denies it, FileVault makes your system noticeably slower.

Apps that broke:

PowerPC apps simply don't work anymore. Apple removed the brilliant Rosetta software. I say brilliant because it allowed me to play WarCraft 3 (for PowerMac) on my intel Leopard system flawlessly.
TrueCrypt / MacFUSE. I found a website that offered up-to-date MacFUSE software that fixed the problem. But it was not on the official MacFUSE website. Odd. Very odd. But it really does work now.
Some folks say that Spaces is broken in Lion because Apple changed it. I don't use Spaces but looking at Mission Control, I believe them.
Printing from Google Chrome crashes the app. Of course, it's all Google's fault and you should use Safari. But I'm pretty sure that I could print from the Chrome browser before.
Lion removed my compilers and did so even without asking. gcc, clang, make, all gone. Insane! Apple decided that thou shalt use Xcode 4 on a Lion system. It's free, and thou shalt download the 4 gig Xcode 4 installer from the App Store and you are not given any option to install only the command-line tools. So I spent some additional hours to get my programming environment back in order again.

The Good Stuff
So, is Lion all useless? No, here's what I do like about it:

More system programs are 64-bits binaries.
The OS kernel runs in 64-bits mode now, which is faster than 32-bits mode on modern CPUs.
ASLR has now been implemented properly or so they say. Address randomization is important for security; it helps prevent system crackers to gain root access by smashing the stack. I find this to be a very important feature because I do online banking with my system, and who doesn't, nowadays.
The price is fair, even for a guy like me who has been spoiled rotten for years with Linux and GNU where software is typically free (as in beer — yes, RMS says you can make money from it but everyone is getting it for free anyway. But wait, isn't that exactly the same in the Windows world? Hmmm).
The arrows on the scroll bars are gone. I'm not too crazy about the new scroll bars, but you have to admit that no one was seriously clicking those arrows anymore and removing them is a bold move. No doubt Ubuntu and other Linuxes will follow this example, as will Microsoft.

I Still Love You
Despite my criticism on Lion I have to say that I'm still very much in love with the Mac OS. It just works. I can't put it any other way. I love working with it. I love programming for it. I love its strangely brilliant Objective-C. I love digging in the docs of its Objective-C API. I love its brilliant BSD UNIX that is its core. I love that you can sit down and get some work done rather than having to click away popup after popup as your system is begging for attention because it needs you to be a sysadmin night after night. I love that OS upgrades do not totally break your system and that you do not have to spend a full weekend on hacking away in it in a futile attempt to fix it. I love how you can copy gigabyte files around and the whole desktop remains responsive. I love how my old white macbook runs the latest Mac OS X smoothly and without feeling sluggish at all. I love the finger scroll with inertia on the Magic Mouse that seems to ‘just know’ where you want to scroll to. I love the beautiful screen fonts. They are not ugly like on other platforms. And I love how the Dashboard worked in Leopard. No other OS in the world implemented widgets in this way and it was done exactly right. And I love Spotlight. Spotlight has to be the only desktop search tool that does not grind on your hard drive as it is rebuilding an index every single day from a daily cron job.

I could go on and on. There are few things in Mac OS that I do not like. The Finder does not behave like Windows Explorer — but then again, it is not a Windows application. The default settings for PageUp and PageDown in the Terminal and Xcode editor appear broken as they do not react intuitively. Launchpad is rubbish. They messed with my favorite app, the Dashboard.
Other than that, the Mac is still insanely great.

Update: In System Preferences|Mission Control, uncheck “Show Dashboard as a space” to get the old Dashboard behavior back.

Quaternion versus Matrix performance

2011-05-08T17:50:00.006+02:00

When doing 3D graphics programming, you will be dealing with vertices, vectors, translations and rotations. OpenGL will happily do the translations and rotations for you, but in some cases you will want to do the math by yourself anyway. For example, I like keeping the orientation of an object around so I can rotate it whenever I like (like in an animation or game loop or heartbeat routine). At that point, OpenGL is not involved. Later, a drawing routine is invoked that calls OpenGL to do the necessary rendering to display.

OpenGL uses matrices to represent 3D space in memory, so it makes sense to store the orientation of the object in a matrix as well. The 3D space is actually represented in a 4x4 matrix, which is generally written as an array of 16 floats. Now, there are some gotchas like the column major format to layout the matrix in memory and the right-handedness rule, but once you got that right, all the drawing routine really has to do call glMultMatrix() on your 'matrix' array of float values, and the object will (hopefully, if you got everything else right as well) appear under the desired angles. That's easy.
Multiplying matrices together to make combined rotations is not an easy task and takes 4x16 = 64 floating point multiply operations! There are 4x12 = 48 add/subtract operations as well, but I assume that the multiplications have the worst impact on performance. If you want to do a rotate in a glRotate-style you will have to setup the matrix first, which adds another 24 multiply operations in the worst case, without counting the multiplications and the sqrt() call needed to normalize the vector.

There is another way of storing orientation, and it's the quaternion. This is something like a vector in complex 4D space and consists of "something like" a <x,y,z> vector and an additional w component. What, only 4 values? Yup, that's all. The memory footprint of a quaternion is really small compared to that of a matrix. (By the way, this is a non-issue to me because modern computers have plenty of memory — even the mobile devices do. But maybe you have some whack project in which you want keep tons of different orientations and memory becomes a problem). Because there are only 4 values, initializing a quaternion is dirt cheap in terms of CPU usage. Multiplying quaternions is also relatively cheap with only 16 floating point multiply operations. There are 12 add/subtract operations as well, but I assume that the multiplications have the worst impact on performance. Again, not counting the operations needed to normalize the rotation vector.
So, are quaternions the golden egg? Well, yes and no. Yes, they are great, but the main drawback is that OpenGL works with matrices. Converting the quaternion back to a matrix costs 27 multiplies.

In my book (I keep a little black book to pen down these kinds of numbers) 16+27 = 43 is still less than the 88 that matrices cost. However, there is a special case where matrices will still be faster. The trick is that when working with matrices, initially, you will have the identity matrix. Since multiplying the identity matrix with another matrix equals that other matrix (check this yourself, it's fun ...), you can greatly optimize the first matrix rotation, as it requires no multiply at all. This requires that you keep a flag on the matrix saying that it is identity. Or you can make a separate routine that simply initializes the matrix in its first rotated state. It makes for an embarrassingly fast rotate call, especially if you were going to do just one rotation of the object.
Of course, this is cheating. You can cheat in a similar way with quaternions, saving an extracted copy of its corresponding matrix and flagging it as dirty whenever it needs to be updated. Just keep in mind that if you rotate the object all the time, you will have to extract the matrix for use with OpenGL all the time.

I want to end this post with a couple of remarks:

Quaternions are apparently terrific for combined rotations. If you hardly do combined rotations, matrices will be faster. If you do combined rotations all the time (like for animating skeletons and such) then you probably already knew that quaternions are the way to go.
Quaternions produce less floating point drift than matrices, because they do less multiply operations than when multiplying matrices. They do drift however, and don't let anybody tell you that they don't.
In my post I made a remark about modern computers having enough memory ("640K ought be enough for anybody ..."). The same goes for CPU power, really. However, on mobile devices it probably does pay off to investigate app performance not only because of the less powerful CPU, but also because of battery power consumption.
I got to writing this blog entry because I spent a day wondering why my matrix rotation around an arbitrary axis gave weird results. The quaternion code did work, until I passed in a vector that was not normalized and it displayed the exact same weird result! That was an eye-opener. After normalizing said vector, the matrix code gave just as good results.
Over a year ago, when I wrote in my blog about quaternions for the first time, I made a remark that NeHe's code has a sign wrong somehow. To my surprise, my model was rotating clockwise using my own quaternion code. I fixed it to have it rotate anti-clockwise. Either I got the matrix column major layout wrong before, or my other project was working with different axis. Anyway, NeHe's quaternion code is probably alright after all. I didn't use it. By the way, I saw wikipedia too now shows code examples for quaternions.

Database performance in practice

2011-03-06T12:19:00.009+01:00

For a project at work, I wanted to put some syslog messages into a database so you would be able to query the dataset easily and most importantly, quickly. To my surprise, this was not as easy as I thought it would be. Database engines are not the magic tools they promise to be.

The main problem with syslog data is its volume. The relevant logging lines of several machines combined, gathered over three years time was about 50 million records. You would think a database would be able to hold 50 million records ...

MongoDB

MongoDB is a fairly recent new high performance database engine. MongoDB is "web-scale" meaning that you can spread load over multiple servers. I have only one server so web-scale doesn't apply in this case. MongoDB doesn't understand SQL, but instead it uses a Javascript interface. I don't like SQL much so initially I was quite happy with MongoDB. There is some controverse around MongoDB because it defers commits to disk (which means undetected data loss in case of a power outage) in order to gain performance but in this case I could live with it and this wasn't a show stopper.

It comes with nice Python bindings so developing the app was quickly done. MongoDB doesn't require you to define any schemas or anything at all so it's very easy to get something working quickly.

Tests with a months worth of syslog data were satisfactory so I decided to load up all the data, with records dating back as long as three years. This took a while so I let it run overnight.

Queries now took a long time to complete. Unacceptably long. To cut down on query time, I took the extreme measure to make a subset of the data that contained only three months worth of data.

I read that querying on datetime objects was slow, so I broke it down to year/month/day numbers and used that instead. When adding these columns, the database files on disk blew up from 50 gigs to 120 gigs. Disk space was not really an issue on this system, but really, 120 gigabytes?

Memory usage was much worse though, to the point it became unbearable. MongoDB uses the mmap() system call to map on-disk files into memory, with the unfortunate consequence that when you do a costly query, it will consume all system memory. Linux has a-OK memory management so your system won't die on the spot, but it was clearly having a hard time. Since I didn't want to dedicate the full box to MongoDB, this was a no-go and Mongo had to go.

MySQL

MySQL is a famous free relational database and would have been many a person's first choice anyway, so I decided to give it a go. One of the reasons I don't like SQL databases is that you have sit down and take the time to set it up. Create the database, the user(s), set passwords, write the schema etcetera before you can start. What you get in return for this investment is that you can give certain users or apps read-only rights to the database (which is kind of important when dealing with logging data) and you can easily review what attributes and data types you used to create the tables with.

Tests with a months worth of syslog data were satisfactory so I decided to load up all the data, with records dating back as long as a year. This was practically impossible. Inserting rows into MySQL goes alright for a while and then it slows down, and slows down more and more until the point were it takes minutes to insert data into the database! I tried improving this with transactions (do multiple inserts and commit) and it didn't help!

Fifty M records is too much for MySQL. MySQL's on-disk and in-memory footprint were formidable, but who cares when you can't even put some data in your database. You can do tricks with partitioning in MySQL but I didn't try it because it creates new issues to consider. Someone said I should use PostgreSQL, but I was already too tired to try.

'Proprietary' solution

I was convinced that a modern PC should be able to handle 50 million records, so I decided to do it the hardcoded way using a packed struct and dump that into a binary file. Database lovers cringed and called me an idiot but I let them. Using some shortcuts, it was possible to cram a syslog line into just 48 bytes — and this includes two magic bytes to detect possible data corruption. The total amounts to 2.5 gigabytes which takes about half a minute to read through from disk, but the subset is only a few hundred megs and is processed much quicker.

Because the data can be packed so small, it's no problem doing a linear search to find what you are looking for. A linear scan through memory may be an inefficient way of searching but it finishes in a split second so no further optimisations are necessary at this point. Mind you, there is no indexing going on because I'm not trying to imitate a database engine.

What's also cool about this data is that when you are searching by date, you can skip through the data using a binary partitioning method (just like bsearch() does). Moreover, data can be easily partitioned by writing to a new data file every month.

The major drawback of this solution is of course development time. It's written in C for performance reasons and as a consequence the program is not yet fully featured, and it will take considerable effort before it is.

Conclusion

Databases are generic tools that keep you from writing lots of code that have to do with storing and searching through data. In that respect, databases are like what scripting languages are compared to low-level programming languages. You can outperform (or maybe in this case I should say, outmaneuver) them but whether it's a smart thing to go that way depends.

The given problem can probably be solved using MySQL by dynamically creating a new partition each month and adapting the application to work with that. I'm pretty confident that it will work but this too will require some more work to get done.

What bothers me is that database engines are overkill for the small data store problems (where you would typically use some ASCII flat format file to put all records in), while at the same time these heavyweight tools cripple under the load when you put a lot of records into them. All of a sudden you have to be a database expert for solving a seemingly simple problem.

Update (March 14, 2011)
I set up a MySQL db with the archive storage engine and partitioned it by month. It's currently loaded with 150 million records (!) and counting ... It's holding up nicely. We will get some more experience with it in the coming weeks, but so far, I'm quite impressed with it especially because it is running on a rather cheap and simple PC server.

C+Objects: A Python-esque Library for C/C++

2010-12-12T20:30:00.006+01:00

Not so long ago, I wrote a rather large Python code, which turned out to be a very useful tool. It was thousands of lines of Python, but I wrote it in only a couple of weeks. I wrote it "with my eyes closed", churning out the code at a high rate, and yet the number of bugs was small and they were always easy to resolve whenever problems did occur. This is the power of Python. The ease at which you can produce useful, working code is simply amazing. Writing such a program in C or C++ would take much longer, months, maybe as long as a year. Skill has little to do with it. The language simply is easy on the developer. It makes things easy.

Python is a fine language, and while its performance is quite alright, when compared to the raw power of C or C++ it just doesn't compare. Neither would I be comfortable creating something like a game in Python. While this is perfectly possible, my personal experience directs me to libraries like SDL, OpenGL, OpenAL, and what not.

At the same time, a language like C++ is perfectly suited for creating games, except that the language itself is the cause of lots of stress. C++ is not an easy language. It is overly politically type-safe correct, to the point where a little word like 'const' or a wrongly placed & sign has a completely different meaning and makes your program do weird unintended things. C++ pros may laugh at me, but consider the fact that I'm actually using C++ professionally, too.

In C++, I can almost philosophically ponder all day long whether a certain class should be implemented this way or another. While the beauty of the design is worth investing precious time in, are you getting any work done? And time is precious indeed. If I had to choose between easily writing a working program in Python, or struggling with C++ just to make the compiler happy, I'd choose Python any day. If only I could bend C++ to make it play nice, make it see things my way ... and you actually can. C++ is a very odd (but cool) language, which lets you redefine operators to make it behave the way you want. Insanity, it even lets you redefine the "()" parens and the "->" deference 'operator' ! (gasp!)

The past weeks I've been working on this library which implements some basic objects like a Number, a String, an Array, a List, and a Dictionary. These exist in the STL, but are not quite like how I would like them to be -- like Python. Anyway, what an adventure..! The undertaking was heavier than anticipated. Each class is derived from a base class named Object, which is the base of everything.

C++ has this cool feature that when a local instance goes out of scope, it calls the destructor. So you have some kind of automatic memory management. But wait, it's much more complicated than this. What if we added our String to a List and the String goes out of scope? Boom, the program would break. Oddly, when you use new to allocate an Object, it remains in existence and the destructor is not being called. Of course, you say, this is basic C++. Now, we use this feature to allocate a backend for our String 'proxy' object. The proxy may go out of scope, but the backend remains. The backend is not deallocated until a reference count drops to zero. Yes, adding it to the List increments the reference count in the backend of the added Object.

Using this library, we can now write code that looks a lot like Python code, but is really compiled by a C++ compiler. The performance is less than optimal, but surely better than Python's. Is everything ideal now? Umm no, I ran into a problem where the compiler lost track what type of object it was really dealing with, and I had to resort to static_cast<>()ing the thing to the correct type. C++'s type-correctness is really annoying. One other thing is that adding a new class is hell. You need to implement both a proxy and a backend class, and you need to implement lots of methods (low-level stuff like operator=(const Object&)) to make it work. Of course, your new class will have new methods, and you will have to use dynamic_cast<>() on the pointer to the derived backend a lot, which is coding hell.

Although I succeeded (more or less) in implementing a Python-esque library to ease writing C++ code, I'm now considering dropping the idea of mimicking Python and moving away from a copy-by-value paradigm to a more efficient pointer-oriented solution, much like Objective-C has. In Objective-C, everything is a pointer to an instance -- you just hardly realize it due to its syntax. Objective-C code is not as easy to write as Python, but I really dig its nice API and its convention of having really long descriptive names for members.

In Objective-C, everything is an Object, and it has 'manual' reference counting via two calls: retain and release. Retain/release is not super-easy but it does help a lot when compared to old-fashioned C memory management. This may be combined with an autorelease pool to easily deallocate unused objects. Objective-C has another feature that is extremely useful: calling a non-existant method in an instance (because the var is nil, for example) results in nothing being done. No program crash, it simply ignores the fact. I yet have to think about how one could mimic this behavior efficiently. This time my weapon of choice would be standard C. Ah, the joys of good old plain C.

Work, stress, and management

2010-10-09T17:31:00.007+02:00

Now that we have entered the multi-core age, we should all be writing multi-threaded code. Even though it's nothing new, I'd still like to devote a (another) blog post to it. I came up with an extremely generic model that applies in most cases. It is based on the producer-consumer model, but with a twist. The standard producer-consumer is often a bit too simplistic in practice.

The Worker

Suppose we have a main thread that has a bunch of work to do. The work must be a number of tasks that are all the same, like for instance scaling a number of images. It doesn't really matter what kind of work it is, as long as you have a number of units that must be processed.

A single work unit is abstracted into a work object. This single work object will be processed by a process function. The process will be executed by a worker thread, who handles the work units. The work will be given to the worker by the main thread; the main thread acts like a manager.

This is a standard producer-consumer paradigm where the producer injects work, while the consumer takes work.

The Stressful Worker

Now imagine that processing a work unit takes some time, and the main thread doesn't have much else to do. This will mean that the main thread will be quick to hand out more work, piling it up for the worker as it is processing each unit one by one. This is overburdening the worker.

A solution to this problem is to have the manager wait until the worker is finished. You can optimize this and hand out a number of work units to a worker before waiting until the workload drops below a certain threshold. Note that the workload is really the length of the work queue (in the case where all work units are alike).

Another solution is to have the manager co-operate and let him do some work himself. This changes the model (and the code!) a lot since in this case, it's better to have the worker take on work by itself rather than being a slave.

Another solution is to have the manager manage multiple worker threads, one for each available core in the system of course. Depending on the type of work, it may or may not be easily possible to make use of multiple threads.

Some pseudo-code

Here's some pseudo-code to illustrate what I've been talking about.

1. The naive implementation, which causes overburdening the worker:

# the manager (producer)

for work in pile_of_work {
worker.give_work(work)
}
worker.time_to_go_home = 1

# the worker (consumer)

forever {
work = get_work()
if not work {
if time_to_go_home {
exit
}
continue
}
process(work)
}

2. The stressful worker, with a kind manager:

# the manager (producer)

for work in pile_of_work {
while worker.workload >= max_load {
sleep a bit or do something else
}
worker.give_work(work)
}
worker.time_to_go_home = 1

# the worker (consumer)

forever {
work = get_work()
if not work {
if time_to_go_home {
exit
}
continue
}
workload += 1
process(work)
workload -= 1
}

Clever people will note that sleeping is ugly and the manager should block instead until it is notified by the worker that it is done doing its job. This is best implemented using condition variables:

# the manager (producer)

for work in pile_of_work {
worker.give_work(work)
manager_condition.wait()
}
worker.time_to_go_home = 1

# the worker (consumer)

forever {
work = get_work()
if not work {
if time_to_go_home {
exit
}
continue
}
workload += 1
process(work)
workload -= 1

if workload < maxload {
# signal I'm ready for more
manager_condition.signal()
}
}

In this last case, I let the worker decide if he's ready to take on more work.

Python programmers get away easy: there happens to be a standard Queue class that implements the above workqueue, complete with a maximum workload that blocks the producer when the worker is being overburdened.

tutorial: Key Value Coding done right

2010-09-15T10:59:00.011+02:00

In MacOS X / Cocoa, there is this concept of "Key Value Coding". It allows you to loosely couple objects together in a flexible way. For example, this is used by NSCollectionView to glue the interface (the GUI) of the program to the actual code of the program.

Key Value Coding means that you can get the value of a property by its key (which is a string). Note that this is exactly what a NSDictionary does, so making your custom class work with KVC, is a lot like making it look like a NSDictionary.

If you are still confused about what KVC is and want to know more, you may read the excellent page on KVC at MacResearch.

Turning a class into a KVC class

To make a class KVC compliant, it has to respond to the -valueForKey: method. The quick and dirty way is to implement this by checking the string and returning nil if it's an unknown key. In many cases this will actually work. There are some little extras that you should know, though. They are best explained by example:

@interface Album : NSObject {
NSString *artist, *title;
}

@property (retain) NSString *artist, *title;

// in Album.m

@synthesize artist, title;

-(id)valueForKey:(NSString *)key {
if ([key isEqualToString:@"artist"]) {
if (artist == nil)
return [NSNull null];
return artist;
}
if ([key isEqualToString:@"title"]) {
if (title == nil)
return [NSNull null];
return title;
}
@throw [NSException exceptionWithName:NSUndefinedKeyException reason:[NSString stringWithFormat:@"key '%@' not found", key] userInfo:nil];
return nil;
}

-(NSArray *)allKeys {
return [NSArray arrayWithObjects:@"artist", @"title", nil];
}

-(NSArray *)allValues {
return [NSArray arrayWithObjects:artist, title, nil];
}

Concluding

When making your class KVC compliant, take care of the following:

implement -valueForKey: and check the name of every property
if the property is nil, return [NSNull null] to indicate that the value is nil
throw an NSUndefinedKeyException if the key is not found
implement -allKeys, returning an array containing all valid keys
implement -allValues, returning an array containing all values

flocking boids

2010-06-13T20:49:00.006+02:00

Hi ... I got a bit stuck with my 3D space game when trying to get real-time impostors right. Impostors are dynamic billboards for rendering hundreds of distant asteroids. After a three week holiday, it was hard getting back into the code, so I put it on hold for now. On the bright side, I started working on a new arcade game that is really 2D, but with a 3D twist. It is inspired by Geometry Wars / |g|ridwars, GridRunner, and another old Jeff Minter game that features four cannons along the screen edges.

An intern that I'm currently working with, pointed out flocking to me. The guy is studying game technolology — you can actually get a master's degree in game technology nowadays, how great is that?

Anyway, flocking, also known as swarming, is a technique reminiscent of particle systems. While particle systems simulate physics models like fireworks, smoke, or fountains (water drops), flocking is an AI system that is great for simulating groups of animals. An impressive YouTube video shows such a simulation of a flock of birds that is under attack by two birds of prey.

On first thought, you might think that group behaviour is programmatically implemented by controlling the group as a whole. This is not true. Every bird (or boid, as the bots are called) in the flock is an autonomous entity sporting its own artificial intelligence.

How is this implemented? Each boid has an area of sight. If it sees it is going to collide with another boid (or object), it will adjust its heading to avoid collision.

At the same time, the boid wants to stay with the group. It does this by adjusting its heading, to get close to others, while trying to match the heading of a boid that is near. As a consequence, the boid will follow others.

Coming from an age when computers were slow, I first thought that this would be too slow to do in real-time. As it turns out, a modern cpu has no problems whatsoever with the little bit of math required for directing each boid. A pitfall is to have a boid influence another, and recursing because this action influences another, and ... You should not try to solve a mathematical puzzle here. Instead, focus on only one boid at a time and have it make the decision of how to adjust its heading. Do this for every boid, every discrete time step.

I implemented the AI rules in 2D in a game, and while the result is not as impressive as the flock of birds video, it is kind of cool. I started out by making sure that the monsters (or boids) would no longer pass through each other. This is done with a simple circle collision test. When a monster collides, it chooses another direction to move in. Once this was working, changing the code to get flocking behaviour was rather easy: increase the collision radius (area of sight) and adjust the direction only slightly rather than choosing an entirely different direction.

One problem I ran into was that the play area in this game is small and I don't want monsters to fly off the screen. So, the monster had to turn at the edges. Again, increase the area of sight, and have it adjust the direction.

In the game, the gliders (paper airplane models) flock together, while the magenta thargoids are going around like bumper cars, and are disturbing the gliders. The yellow cubes are stationary obstacles in the arena.

Note that it is possible to extend the AI with more rules, but flocking is a technique that already yields quite amazing results with just a few simple rules.

Vertex Buffer Objects - what you can and can not do with them

2010-04-04T12:10:00.005+02:00

In 3D games, models consisting of thousands of vertices and polygons, are rendered to screen at least at 30 frames per second. For every frame, these vertices are transmitted from the memory to the GPU over the bus. For static models, this is a huge waste of time and bus bandwidth, because the vertices are the same for every frame. Why not cache the data in graphics memory and tell the GPU to get it there? This is what vertex buffer objects (VBOs) are all about.

In my 3D space game, I added the 3D model of an asteroid. The model has ~2700 vertices, which is not much at all (by modern standards), but I decided it should be a VBO and enable the code for even higher detailed models.

Never having used VBOs before, I took the safe route and implemented the asteroid first without any VBO code, and rewrote it later to use a VBO. This was a lot of extra work, but there were some lessons learned.

I found the following:

use GL_TRIANGLE_STRIP for the most efficient way of rendering shapes. However, for most meshes from 3D modelers you would use GL_TRIANGLES. For the asteroid, I use GL_TRIANGLE_STRIP.
Use glDrawElements() rather than glDrawArrays(). Making an extra array with indices seems more work but is very worthwhile the extra effort.
I had to include degenerate triangles to stitch multiple triangle strips together. Degenerate triangles are 'fake' triangles that refer to the first vertex in the next triangle strip. (Consider triangle ABC, and degenerate triangle DEE to refer to EFG).
ARB extensions for VBOs are old-fashioned by now. VBOs have been included in OpenGL for a long time and you can use the functions without the need for meddling with ARB extensions.
Allocating a new VBO for every type of coordinate is wasteful. Instead, allocate a single VBO to store vertices, texture coordinates, normals, colors, etc. and use glBufferSubData() to place the data into the vertex buffer object.
If you use glDrawElements(), you must buffer the indices using a separate VBO. The reason for this is that the indices have target GL_ELEMENT_ARRAY_BUFFER. I tried mixing indices into subbuffers (GL_ARRAY_BUFFERs) and it did not work for me.
If you do not have an array at hand, but generate coordinates on the fly, use glMapBuffer() to get a pointer to memory. Mind that you are not directly writing into graphics memory; the buffer will be copied to graphics memory by glUnmapBuffer().

So, are VBOs the golden egg? Well, no. They are a great way of speeding up the rendering of high poly-count meshes. There are things that VBOs are simply not suited for. This has to do with both the limitations of OpenGL and what it is that you're trying to achieve. For example, I tried loading the stars into a VBO. This turned out not to work very well, because in my code, stars are point sprites, and each star has a specific point size. Since you can not set the point size in a vertex array, it also makes no sense to use a VBO. I sorted the stars by size to draw them as a vertex array nevertheless, but this resulted in a low vertex count per call so it still makes no sense to use a VBO here.

I also noticed that 1D textures do not work in vertex arrays. Maybe I'm using them for the wrong purpose (texturing GL_LINEs) but considering that glBegin/glEnd is practically deprecated there may be a problem here.

Another problem I had was with face culling. This is not the VBOs fault, but I suspect that when you drape a triangle strip into a convex shape, it may show artifacts. Enabling depth testing did not help me here, but disabling face culling did.

Although VBOs are an add-on to vertex arrays, it seems like OpenGL always requires you to turn your code inside out when you want to change something. I stuck to static meshes for now and decided to abstract a VBO class from it, which wasn't exactly easy either. Anyway, here is a link to a site that I used to implement VBOs:

http://www.ozone3d.net/tutorials/opengl_vbo_p2.php

Real-time rendering a lens flare

2010-03-07T10:54:00.009+01:00

After adding a sun to my 3D space flyer, the only thing missing was a cool lens flare special effect. Making a lens flare is not very hard, and the effect looks great. It makes your environment look more realistic, it comes to life.

Oh sunny boy

The sun is by itself worth a paragraph in this blog. When rendering a sun, don't fall into the trap of texturing a sphere with a "sun" texture — this looks very unrealistic. Instead, use a textured quad to display an image of a sun. Photos by NASA are practically unusable here, but the photos do show that the sun as seen from space, is a white ball with a yellowish glow, and has streaks. You can make a sun texture using the GIMP (or Photoshop) and choose Light effects: Nova. Apply radial gradient to fade away to the edges of the image.

When displaying the textured quad in-game, I did not want the sun to visibly rotate as we're rotating the spaceship. The perfect way to do this is to do "cheating spherical billboarding". This ensures that the sun with its streaks remains stationary even when we are rolling the spaceship (and thus, the view). Cheating spherical billboarding works like this:

glPushMatrix();
glTranslatef(position.x, position.y, position.z);

// reset submatrix to identity: do cheating spherical billboarding
glGetFloatv(GL_MODELVIEW_MATRIX, matrix);
matrix[1] = matrix[2] = matrix[4] = matrix[6] = matrix[8] = matrix[9] = 0.0f;
matrix[0] = matrix[5] = matrix[10] = 1.0f;
glLoadMatrixf(matrix);

... draw 2D textured quad here ...

glPopMatrix();

Use additive blending to give the sun the bright intensity that it has.

Shine a light on me

Now that we have a sun, let's get to the lens flare part. A lens flare is a series of rings or circles in the line of sight to a bright flash (like the sun). This line always cuts through the center of the camera. So, knowing the position of the sun and the position of the camera, we can calculate the positions of the flare elements. How many elements you want and what size they should be is up to you.

Note that when looking directly into the sun, the lens flare will be larger than when the sun is off to the side. So, you can use the distance as a measure for scaling the lens flare elements.

When searching the net, you will find that NeHe's tutorial renders a 3D lens flare even though a lens flare is really a 2D special effect, as it occurs in the lens of the camera.

The math for a 3D lens flare is less intuitive than for a 2D lens flare and drawing the flare is easier in 2D, so I implemented it as a 2D image post-processing effect.

The following needs to be taken into consideration:

when the sun is visible, a lens flare effect should be drawn
use gluProject() to find the 2D onscreen position of the sun
gluProject() returns pixel values; scale these to fit your viewport
the distance between the sun's 2D position and the center of the screen is a measure for the scale of the lens flare elements
vary color and size of the flare elements
use additive blending because we are working with light effects
the sun may be occluded by another object in which case a flare should not be drawn

If there is an object in front of the sun, no lens flare should be drawn. NeHe's tutorial shows that it's easy to do a depth test here by reading a single pixel from the depth buffer using glReadPixel(). The fun part is that in my code the sun is drawn infinitely far away with depth testing disabled, so if the depth buffer contains a value here, there must be an object in front of it.

The easiest way to draw the flare elements evenly spaced over the line of the flare, is to make a vector from it, normalize it, and "travel along" this vector to place the elements.

The code looks just like this:

GLfloat center_x = SCREEN_WIDTH * 0.5f;
GLfloat center_y = SCREEN_HEIGHT * 0.5f;

// screenPos is the onscreen position of the sun
// mind that the pixel coordinates have been scaled
// to fit our viewport
GLfloat dx = center_x - screenPos_x;
GLfloat dy = center_y - screenPos_y;

GLfloat len = sqrt(dx * dx + dy * dy);

// normalize the vector
GLfloat vx = dx / len;
GLfloat vy = dy / len;

// choose a spacing between elements
dx = vx * len * 0.4f;
dy = vy * len * 0.4f;

// note that we already are in 2D (orthogonal)
// mode here

glPushMatrix();
glTranslatef(screenPos.x, screenPos.y, 0);

// travel down the line and draw the elements
for(int i = 0; i < numElements; i++) {
glTranslatef(dx, dy, 0);
draw_flare_element();
}
glPopMatrix();

The result is quite nice. You can make things crazier by adding more circles, starbursts, hexagonal elements, and horizontal blue anamorphic streaks.

Rendering glow

2010-02-15T20:49:00.005+01:00

Hi, in the space game that I'm working on lately, I added a gyroscope-like object to help the player orientate him/herself in 3D. This gyroscope is presented as a wireframe sphere with a ring around it. To this gyroscope, I wanted to add a "glow" effect to it so that it looks ultramega cool.

Rendering glow is nothing new, and with some googling you can quickly find descriptions on how to do it. As always, it's easier said than done, especially when you've never rendered glow in your life before — so I like to write a little blog entry about this.

So, how does it work? In essence, just render a blurred copy of all glowing parts in the image, and then do an additive blend of the object. So the steps to take are:

render glowing parts of scene
copy rendered image data to a pixel buffer
apply blur filter
put blurred image into a texture
draw texture
set blending to additive blending
render scene

I tried reading the pixel data with glReadPixels(), which didn't work for me for some reason (in hindsight, maybe the back buffer was not selected, or maybe some other problem). I read that glReadPixels() is slow and you should use glCopyTexImage2D() anyway. One caveat with glCopyTexImage2D() is that you must call glTexParameter() or it will not work.

Since the image is blurred anyway, it is usually OK to work with a low-res texture (that gets stretched when drawn).

The code for making the texture looks like this (note how I use the home-made PixelBuffer class):

/*
...
start by rendering the glowing parts of your object here

...
*/

// put rendered image into a texture
glEnable(GL_TEXTURE_2D);
glBindTexture(GL_TEXTURE_2D, texture_id);

glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_MIN_FILTER, GL_LINEAR);
glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_MAG_FILTER, GL_LINEAR);

glCopyTexImage2D(GL_TEXTURE_2D, 0, GL_RGBA, 0, 0, 64, 64, 0);

// get the pixel data from texture and blur it
PixelBuffer *pixbuf = [[[PixelBuffer alloc] initWithWidth:64 andHeight:64] autorelease];

glGetTexImage(GL_TEXTURE_2D, 0, GL_RGBA, GL_UNSIGNED_BYTE, [pixbuf pixels]);
[pixbuf renderFilter:blur];

// put the blurred image back into the texture
glTexSubImage2D(GL_TEXTURE_2D, 0, 0, 0, 64, 64, GL_RGBA, GL_UNSIGNED_BYTE, [pixbuf pixels]);

Now simply render a quad and texture the blurred image on it. Use alpha blending to make it look better. For the second part, enable additive blending and render the scene again.

glBlendFunc(GL_SRC_ALPHA, GL_ONE);
glEnable(GL_BLEND);

I use GL_SRC_ALPHA rather than GL_ONE, but you really have to try and see whether it makes a difference or not.

For making the blurred texture, I first set the glClearColor() to 0, 0, 0, 0 (even zero alpha). This was needed to get the desired result. You may not need to do this, depending on what it is you're doing, but I mention it here because it was one of those gotchas.

Lastly, many say you need to reset your viewport temporarily to the size of the texture. In this case, I did not need to do this. However, as you add more glowing objects to your scene, it's wise to render all glowing objects in a scene to a single blur-texture in one go. Then draw a fullscreen quad with the blur texture, and off you go.

Rendering random nebulae (part 3)

2010-01-27T17:36:00.006+01:00

My brother, who is a hobbyist programmer himself, had the constructive comment that my nebulae were overall too dark. Real nebula have dark and bright areas, he said. And he is right, I guess. So I decided to give it a go and tweak the nebula a bit more.

Shaping up nicely

One problem was that when the shape of the nebula was determined, the cloud was pretty much flattened out. This happens because the heights of the bubbles that define the shape are all added up and clamped to 255, which is the maximum alpha value. A consequence of this is, that the nice height map that was created using a plasma renderer, is all flattened. I changed the shaping algorithm so that the inner height map in the cloud is mostly preserved (by taking averages), while still fading at the edges. This gives the cloud a fluffy, three dimensional look.

Previously, I would render a plasma, blend in colors, and finally determine the shape of the nebula. This time, each layer has its own shape. The result is that the colors are more coherent and staying together in their own little "sub cloud".

A Blurred Vision

It seemed like a good idea to blur the image to make it a vague cloud. This turned out not so well; blurring the image takes all detail out of the image. (Sounds kinda obvious, doesn't it?)

I also did some trickery with the alpha channel previously, to fade the entire image. This was totally unnecessary, as you can set the alpha factor with glColor4f() when the final texture is being drawn — so I took out this code, simplifying things. Since the background is the black void of space, this only controls the brightness of the nebula.

Blending In

Previously, I used alpha blending to blend in colors into the nebula. Alpha blending is real nice, but for rendering clouds it's better to use additive blending. The formula used is:

result = alpha * srcPixel + destPixel

In OpenGL, you would call this:

glBlendFunc(GL_SRC_ALPHA, GL_ONE);
glEnable(GL_BLEND);

What's cool about additive blending, is that blue and red make magenta, and blue and yellow make green. This may sound obvious, but note that this is not true for alpha blending.

I also use additive blending for making some extra bright stars. Experiments with additive blending in layers multiple times into the nebula were not exactly successful, as it looks funny when you make it super bright.

On one hand, I'm very happy with this result, while on another ... it shows the plasma algorithm. It's almost as if blobs of paint have been splatted onto the screen in a pseudo-random way. Ever heard of the Holi festival? I think it may be a good way to generate clouds too. But for now, I'll leave it at this.

Rendering random nebulae (part 2)

2010-01-20T17:06:00.007+01:00

Last time, I talked about how to render a random nebula. As a final remark, I stated that the nebula had no shape; the plasma simply fills the entire image to its boundaries. The result is that you end up with a texture that is unusable; you can not have a nebula in the starry sky that is shaped perfectly like a square. So, we need to give it a random shape.

I tried fading out at the edges, and I tried a simple circular fade. It doesn't work. In the first case, you end up with a perfect square, that perfectly fades out to the edges. In the second case, you end up with a perfect circle. Both look like crap, we really need a random shape.

I decided the alpha channel of the nebula should be like a height map, with height zero around the edges. I tried out the diamond-square algorithm, which seems ideally suited for this (by the way, the plasma of the nebula is generated using a diamond-square algorithm), but it's hard to control around the edges. I thought about leveling the edges by 'pushing a pyramid' down over the image, but I'm sure it wouldn't look nice.

How do you generate random shapes? The answer: with a fractal. The word 'fractal' sounds very mathematical and difficult, but its not. See wikipedia for some info.

Algorithm used to generate a fractal shape:

draw a circle;
choose a random point on the edge of the circle;
divide the radius by two;
recurse; draw smaller circle at the newly chosen point.

Using a circle as a brush is not a bad choice, but if the edges have to fade, then the brush should be a radial gradient. I had a little trouble in drawing a radial gradient and did not find the right solution online, so I'll share my formula with you. It's actually easier than you might think:

float d = sqrt(dx * dx + dy * dy);
pixel = gradient - (int)(d / radius * gradient);

d is the distance of the pixel to the center of the circle.
gradient is the difference between the low end and the high end of the gradient; usually 255 for a full spectrum.

I work with overlapping circles in the alpha channel, so I use:

new_alpha = old_alpha + the gradient formula

When you do this, you will get a lot of high values in the alpha channel as they add up quickly, and that doesn't look good for nebulae. Therefore I chose a small value for the gradient variable, and then the results get quite nice.

Here are some small screenshots:

Rendering random nebulae (part 1)

2010-01-17T11:02:00.007+01:00

As I wrote in my previous post, I'm playing with a random 3D star field lately. To this star field, I like to add some nebulae to fill the black void of space. Previously, I worked with dozens of photos of existing nebulae from NASA. This time, I decided I want the scene to be entirely fictional, so there is no place for real nebulae.

Bring Out The Gimp

There is a way to draw nebulae by hand. Fire up the GIMP (or Photoshop, or alike), and select Filter : Render Clouds : Plasma. You now get a colorful mix onscreen which is probably not quite like what you had in mind. Now select Colors : Desaturate to make it look like a grayscaled image. Now select Colors : Colorize and drag the Hue slider to select the desired color for the nebula. To make the nebula look nicer than this, we probably have to mess with transparent layers, but this is the basic idea.

Programmatically speaking

A way to go would have been to use ImageMagick's library to do the described operations. Well, it seems that MagickWand (ImageMagick's C API), does not include a plasma renderer. The C++ counterpart, ImageMagick++, does, but being mostly a standard C programmer, I'm quite intimidated by its use of templates and references. And to be honest, I could not even get any decent looking nebula by trying to use ImageMagick from the command-line.

I got some neat plasma rendering code in standard C from the source code of the GIMP. Well, puting it like this makes it sound easier than it was, but I adapted it to work with an RGBA pixel buffer. I also wrote filters for desaturating (grayscaling), blurring, colorizing, alpha blending, and something that I dubbed "fadebuffer", but it's really "gray color to alpha" as it puts the gray value into the alpha channel.

All filters work an RGBA pixel buffer and all have the form:

void render_filter_name(unsigned char *pixels, int width, int height);

My Objective-C PixelBuffer class has a method named renderFilter that allows me to use any implemented filter on that image.

@implementation PixelBuffer

-(void)renderFilter:(void(*)(unsigned char *, int, int))filter_func {
filter_func(pixels, width, height);
}

@end

This renderFilter method can be used as follows:

PixelBuffer *pixbuf = [[PixelBuffer alloc] initWithWidth:128 andHeight:128];

[pixbuf renderFilter:plasma];
[pixbuf renderFilter:blur];
[pixbuf renderFilter:grayscale];
fadebuffer_factor(1.5f);
[pixbuf renderFilter:fadebuffer];
colorize_color4f(r, g, b, a);
[pixbuf renderFilter:colorize];

Which is both readable and powerful code.

In pure Objective-C, you would have used a selector and maybe filter classes derived from PixelBuffer, but I like this way of doing things as it allows you to plug in quite standard code easily.

Formula's

I want to share two formula's that I used. One is for computing the desaturation of a fully colored plasma cloud:

gray = (int)(0.3f * red + 0.59f * green + 0.11f * blue);
if (gray > 0xff)
gray = 0xff;

if (gray < 0)
gray = 0;

This works well if the image has lots of color. I experimented a bit with the plasma renderer and adapted it to generate only blue-tones, which results in this formula not working so well, as it takes only 11% of the blue component. So for monotone pictures, do not use this formula but simply take the active color component and put it into the new values for R, G, and B.

Note that this code is floating point and therefore relatively slow. It's easy to change this to integer only arithmetic. If you need more speed, use lookup tables (it costs only 3 x 256 bytes!). I didn't bother because this code is only used for preprocessing.

The second formula is for alpha bending. When you search the net you will find more than one formula to do this. Also, many focus on speed for doing realtime alpha blending in 16-bit pixel formats — this is all old stuff from the late 1990s when computers weren't as powerful.

Anyway, the formula I used is:

result = (alpha * (srcPixel - destPixel)) / 256 + destPixel

Do this for every R, G, B component. Note that in blending terminology you have a 'source pixel' and a 'dest pixel', but they mean to say that you combine the R, G, and B components of source image 1 with the R, G, and B components of source image 2, and that forms the result.

There are many optimizations possible here, like treating the RGBA bytes like one 32-bit integer and using bit masking to take out the components. This is faster because you do less fetching from memory.

Note: If you want to do really good and fast alpha blending, you should probably use OpenGL. The glBlendFunc() is excellent for all kinds of blending, but in this case it involves some hassle; you have to make some textures first and render them to a resulting texture. Since I'm just using this for preprocessing and I'm not interested in doing realtime blending, I decided to implement the blending 'by hand'.

The results

For making the nebula, the above procedure is repeated a few times for different colors, and these images are blended together. The pixel buffer is then turned into an OpenGL texture and textured onto a quad (made up from a triangle strip).

Although it's just a boring gas cloud, I'm quite happy with it. Not everything is well though; the plasma renders into a square and therefore, there is a square nebula in the sky. To make it perfect, the nebula must be given a random shape and fade away near the edges of the texturing square.

(Simple) Flight Mechanics and quaternions

2010-01-02T15:36:00.005+01:00

I've been playing with a 3D star field lately, and what it needs, of course, is a little space ship so that you can fly around. Sounds easy enough, but it's actually quite confusing.

The controls are confusing, but this is actually caused by the camera view. Our eyes and head can move independently from our bodies (well, at least for the most of us) so we can look around without having the feeling of explicitly having to turn. We are accustomed to our Earthly environment, where we think to know which way is up, down, and expect to come back down when we jump up.
Try this:

stand in the center of the room and look straight ahead
shuffle your feet to spin around, keep staring straight ahead

Now, do this:

stand in the center of the room, and look straight up to the ceiling
shuffle your to spin around again, keep staring straight up

Feeling dizzy yet? In the first experiment, you were yawing, going around the Y axis. In the second experiment, you made the exact same movement, but you were rolling, only because you were looking in another direction (down the Z axis).
Rolling happens when you see the horizon spinning in flight sims. Rolling usually isn't present in first person shooters because it's not a very natural movement for a person to make.

Now think about relativity. What if you were standing still, then the room would have moved around you in the opposite direction. People who have a film camera know that there are two ways of filming all sides of an object; one is to walk around the object, while filming it, and the other is to hold the camera steady, while spinning the object. In computer graphics, the camera is typically held in the same spot, while the world is rotated around it. This even holds true when you'd swear there was a camera hovering above and around you, as you were blasting aliens and flying corkscrew formations to avoid missiles.

I observed there are three different ways of controlling 3D movement:

FPS or racing game style movement;
Space sim like movement;
Airplane like movement.

The natural way of things is, that the player primarily looks around in the XZ-plane and may look up and down (Y direction). There is a distinction between up and down, and there is an horizon to keep that clear. In an FPS or a racing game, when the player steers left or right, it is 'yawing' (rotating about the Y axis). The sky is up, the ground is below, and there simply is no roll.

In a space sim, it is more likely you will roll the ship on its side by steering left (rotation about the Z axis). Up and down typically adjusts the pitch. There is not really an up or down, although there are probably some other objects around like ships, space stations, and planets that give you a feeling of orientation. Yawing is probably possible, but by default it flies more like an airplane, because it feels more natural like that. Because you can steer the ship in any direction you like, this kind of control is called six degrees of freedom (6DOF).

Airplane-like movement is much like space sim movement, but there is a clear difference. Steering left will roll the airplane, and when you let go of the stick, the plane levels automatically and roll and pitch will return to zero. This is different from spaceship movement, because the airplane wants to fly 'forward', while a spaceship simply goes on into deep space in any direction you steer it.

Implementation

For the typical first person shooter style game you can get away with having a vector for your heading, and a pitch vector for looking up and down. A camera is easily implemented using only two glRotatef() calls.

For 6DOF, things are totally different. You'd say that you could add a vector for rolling, but that doesn't quite work. The reason that it doesn't work, is because rotations are not commutative. If the player does a roll, pitch, roll, yaw, and pitch sequence, you can not get this orientation right using glLoadIdentity() and three glRotatef() calls. (Note: In theory, it should be possible, but it's an incredible hassle to compute the new Euler angles every step of the way). The correct way to do it, is to use an orientation matrix.

The matrix holds the directional vectors and the coordinates for this object in 3D space. This matrix can then be loaded and used directly in OpenGL by calling glLoadMatrixf() or glMultMatrixf(). Manipulating the matrix is easily done through calling glRotatef() and glTranslatef(). Behind the scenes, glRotatef() and glTranslatef() are matrix multiplications (in fact, the transformation matrices are documented in the man pages) (1).

A single 4x4 matrix multiplication consist of 64 floating point multiplications. When you do incremental rotations without resetting the matrix to identity every now and then, the many floating point multiplications will eventually cause small rounding errors to build up to big errors. This leads to an effect known as gimbal lock. When gimbal lock occurs, the errors in the matrix have become so large that the spaceship can no longer be controlled.

Microsoft Freelancer was a pretty cool game, until one day I ran into gimbal lock right after saving a game. Loading up the saved game would throw you right into gimbal lock again, completely ruining the game.

A way to prevent gimbal lock is to make the matrix orthogonal every once in a while. Orthogonalizing a matrix is such a big mathematical hassle that practically no one is using this technique. So, just forget about that and read on.

There is another way of storing orientation and computing rotations, that does not suffer from gimbal lock. This is done with quaternions. Quaternions are a neat math trick with complex numbers that allow you to do vector rotations, just like with matrices, only a bit different.

Remember from elementary math class that a * a (or a squared) is never a negative number? Well, for complex numbers someone has thought up that i squared equals -1. As a consequence, a whole new set of interesting possibilities opens up, among which quaternions, which are 4D vectors in complex space that can be mapped back into a 3D matrix for use with OpenGL.

The quaternion stuff is quite hard to grasp when you try to understand the math (I guess "complex numbers" aren't called "complex" for nothing). However, if you just go and use them you will probably find that they are not that different from working with matrices.

I'm not going to duplicate the code here, there is some excellent description and quaternion code available here: GameDev OpenGL Tutorials: Using Quaternions to represent rotation. Go read it if you want to know more, and you should know that I think this code is better than the one in NeHe's quaternion tutorial, which apparently has the sign of the rotations wrong.

Note that many 3D programmers write matrix multiplication code by themselves, but this is not always necessary since you can use OpenGL's functions to do the matrix math. An advantage of rolling your own is that you can do some matrix calculations even before an OpenGL context has been created, so before OpenGL has been initialized. Your code will generate an exception/segmentation fault if you call OpenGL before having created a context.

New adventures in Cocoa OpenGL

2009-12-30T16:09:00.026+01:00

It's been a while since my last post, one reason is that I was away on a vacation, another that it's the holiday season, and another one that I caught a bad bad cold out in the snow. Well, enough with the excuses, it's time for some interesting programming blogging. Santa brought me a brand new Mac, so I will venture into the unknown (to me, at least) territory of Cocoa with OpenGL.

Nearly a year ago, I threw together an OpenGL demo for the iPhone. This was a bit of a hack, since I merely called my plain old C code from an Xcode template. While this works, it's not really the right way to go about when developing for iPhone, nor the Mac.

When you say Cocoa, you say it in Objective-C. This weird dialect of C has some pretty powerful features that should probably best be left alone and kept for later. The basics, however, are exactly the same as in any other OOP language that you may have encountered before — you have a class, members, methods, a constructor, and inheritance.

When learning a new programming language I usually go through these stages:

read about it, get sick over the syntax, and hate it
don't actually use it, and keep complaining about the syntax
let it rest for a while, sometimes for as long as a couple of months
read about it a little more
use it, and fall in love with it (if it's good)

Objective-C is good stuff. Although the APIs are from a totally different world than where I come from, I cannot help but think how Objective-C could have helped me in past projects. In Objective-C, everything is automatically reference counted, effectively taking care of the most difficult problems in C (and C++, for that matter), being memory management (e.g. with string manipulation) and pointers.

Strangely enough, developing Cocoa applications is not all about writing code. A part of "the magic" is done in the Interface Builder. With this tool you do not only draw your windows, but you also visually connect class instances together by drawing lines. This works not only for predefined classes, but also for classes that you newly created yourself (!).

When you think about it, it makes perfect sense for a windowing, event-driven operating system to have this kind of development model.

The applications themselves revolve around a design pattern called "Model-View-Controller", where a "controller" controls the data that is behind the application, and sees to it that the view is being represented to the end user. While you are not obliged to follow this paradigm, the code will be quite clean and more reusable when implemented as such.

Enough talk, let's get to the details. For implementing demos and games, what we need is an OpenGL window that reads keyboard and mouse input. Steve Jobs has summarized this for us in a Cocoa NSOpenGLView class. There is a lot of code on the internet that does not use NSOpenGLView, so my guess is that it's a relatively new class. It makes things so much easier, once you know how to use it.

You should subclass it and call it something like MyOpenGLView. You can drag the NSOpenGLView into a window in the Interface Builder, and rename it in the Object Inspector. In the Object Inspector, you should also specify whether you want to have a depth buffer, stencil buffer, accumulator buffer, etc. or you won't be able to use those. There is also a tab that allows you to specify how the view resizes, when the underlying window is resized.

Writing code for NSOpenGLView is easy, but like I said, you have to know how to use the predefined methods correctly.

/*
initialize, but do not set the matrices or the viewport here
*/
-(void)prepareOpenGL {
glClearColor(0, 0, 0, 1);
glClearDepth(1);

// load textures here
// (I wrote a texture manager class to do this)

glEnable(...);
}

/*
this gets called when the window is resized
*/
-(void)reshape {
NSRect boundsInPixelUnits = [self convertRectToBase:[self bounds]];
glViewport(0, 0, boundsInPixelUnits.size.width, boundsInPixelUnits.size.height);

glMatrixMode(GL_PROJECTION);
glLoadIdentity();
glFrustum(...) or glOrtho(...) or gluPerspective(...)

glMatrixMode(GL_MODELVIEW);
glLoadIdentity();
}

/*
draw to screen
*/
-(void)drawRect:(NSRect)rect {
glClear(...);
glLoadIdentity();

// reverse the camera ... or you could put this in a camera class
glTranslatef(-cam_x, -cam_y, -cam_z);

// draw stuff ... maybe do this from another class
...

glFlush();
GLenum err = glGetError();
if (err != GL_NO_ERROR)
NSLog(@"glGetError(): %d", (int)err);
}

To get keyboard and mouse input, use the keyDown and mouseDown methods. To get these events at all, you need to "tell" MacOS that you want to receive these events:

-(BOOL)acceptsFirstResponder { return YES; }
-(BOOL)becomeFirstResponder { return YES; }
-(BOOL)resignFirstResponder { return YES; }

keyDown will not see any meta-keys. For detecting key presses of the Ctrl, Shift, Alt/Option, Command keys and such, override the method flagsChanged.

You will find that MacOS key events have a method keyCode for getting the "virtual key code". A virtual key code is like a keyboard scan code, only with different values. There appear to be no symbolic constants for these virtual key codes, so go ahead and make some #defines yourself. Mind that key codes are usable for cursor and meta keys, but you should never use them for the other keys because of keyboard layout issues — look for the unicode character instead.

There is a mouseMoved method that does not do anything by default. To enable mouse move events, do this:

-(void)awakeFromNib {
[[self window] setAcceptsMouseMovedEvents:YES];
}

Now, you can put all your code concerned with keyboard and mouse input directly into the MyOpenGLView class, or you can be a good application developer and create a "controller" class that acts as a controller for the OpenGL view.

Create the class MyController as subclass of NSResponder. Put all the keyboard and mouse input code in MyController.m.

Add the controller definition to the MyOpenGLView class:

IBOutlet NSResponder *controller;

In Interface Builder, instantiate the MyController class and connect MyOpenGLView's controller outlet to it.

To enable the controller, do this in awakeFromNib in MyOpenGLView:

-(void)awakeFromNib {
[self setNextResponder:controller];
}

-(BOOL)acceptsFirstResponder { return YES; }
/* you may comment this one out now
-(BOOL)becomeFirstResponder { return YES; }
*/

Now, MyOpenGLView will not become a first responder, but it will set its controller as the next responder. Hence, the events will be sent to the controlling object.

After the controller has modified the model (e.g. the user is moving left), the view should be updated. Therefore the controller is also connected to the view ... Updating the view becomes as easy as this:

[glview setNeedsDisplay:YES];

Which will trigger drawRect in the MyOpenGLView class.

Games and demos usually run at a framerate, because there is so much going on, they update the screen all the time. The easiest way of getting this done, is by running the "main loop" as a timer function.

// set up timer for running the main loop

timer = [[NSTimer scheduledTimerWithTimeInterval:1/30.0f
target:self selector:@selector(mainloop)
userInfo:nil
repeats:YES]
[[NSRunLoop currentRunLoop] addTimer:timer
forMode:NSEventTrackingRunLoopMode];

The funny thing is, you do not need to call update explicitly from this mainloop/timer function. All you do is move some monsters around and call setNeedsDisplay whenever needed. Cocoa takes care of the rest.

NSOpenGLView does not provide a method for switching to fullscreen. I did find example code of how to do this on Mac Dev Center, but it looks advanced so I'll leave it at that for now. It involves creating a new OpenGL context with a special attribute NSOpenGLPFAFullScreen in the pixel format, and then calling setFullScreen. You can "share" this context, meaning that it's not needed to reload textures, reinitialize OpenGL, etc (which is great). What strikes me as odd, is that the example code utilizes an SDL-like event processing loop — exactly the kind that Cocoa is trying to hide from us.

For learning Objective-C and Cocoa, I recommend MacResearch. Although the man is a scientist, he knows how to explain things well enough to get you started. After a few lessons, it gets pretty advanced, at which point you should stop reading and try out programming some stuff yourself.

Writing your own CoverFlow (for Linux)

2009-10-04T21:15:00.006+02:00

In case you were wondering what the last post was all about, well, it was a little bit of "tech" that I needed to research for a nice little project of mine: a music player with a CoverFlow(tm)-like interface.

I've been wanting a CoverFlow for Linux for years now. I waited. I googled, found nothing. I waited more. No one implemented it. iTunes version X dot Y was released for Mac and Windows. I googled some more. I found something, but the author himself said it was dreadfully slow to startup and animated at two frames per second. Well, I'm terribly sorry but you must have done something wrong, dude! There was no option left but to give it a go myself.

Actually, I would have settled with a quick and simple popup-like music browser, but Linux did not even offer that — and deep in my heart I knew I craved for CoverFlow anyway.

So, in the design phase, my wannahaves list quickly came to hold these items:

popup-like app, with a borderless window
should display album art
should be a simple player to play albums, since that's all I ever do anyway
no app-centric database ... I hate databases; use the filesystem
startup should be fast, no loading lag

At first I thought implementing this was going to be easy ... well, not exactly. The borderless window gave enough headaches to dedicate a whole post to.

Making the startup fast was really a matter of not loading all album art at startup, but only the ones that are visible. There are only 10 or 11 or so covers visible at any time, and to go easy on resources it does not load any more than that.

The next problem was that I really did not want to have to write a complete music player. Luckily, there is this great player named the MPD or Music Player Daemon, which is a music server to which controlling clients can connect and act as a frontend. There are many frontends available to mpd, and this app would be another one.

Interfacing with mpd is easily demonstrated by the following:

$ telnet localhost 6600
OK
mpd version something ...
play
OK

So, I dusted off some old inet-code, only to find out that my code was all character based rather than line based, so it still needed some recoding.

mpd has commands to list its internal database (which is really fast, too), but sadly no command to ask where the music directory is, so I ended up parsing the /etc/mpd.conf file anyway to find the album directories and the corresponding album cover art.

The mpd protocol is quite well documented and you can play with it using telnet (as shown above) to see how it reacts.

Then there was the challenge of loading and displaying the album cover art. I've worked with BMP and TGA formats before, but how to load a JPEG image? Luckily, there is a SDL_image library to take care of it. It's surprisingly simple, and what's particularly nice, it just works:

SDL_Surface *img = IMG_Load("cover.jpg");

Well, now we're kind of stuck with an SDL_Surface. I don't like these, because I want OpenGL textures. Making a texture out of img->pixels is easy enough, but beware that OpenGL really wants the dimensions of the texture to be a power of two. This is never a problem on my NVIDIA card (which happily textures just about any dimension you feed it), but always a problem on my laptop, which has a much cheaper intel video chip. To counter this problem, we must find the next power of two for the dimensions of the image, and scale it to these new dimensions, before creating the texture.

Peepz on the net find the next power of two by using round() or ceil() and log2(). Yuck! I say yuck because of the slow floating point arithmetic. A computer works with bits, and bits are actually all powers of two. There are two neat algorithms on Wikipedia that I used:

The first is (nearly) only an AND operation and the second is a couple of bit shifts, whee!

So, if we have an album art image of 200x200 pixels, it will scale it to 256x256, and if it's 300x300 it will scale to 512x512. Note that this is a must-do for OpenGL textures to work correctly on all systems.

We still have to actually scale the pixel data to fit the new dimensions, before turning it into an OpenGL texture. Scaling images is incredibly hard to get right ... unless we use another library that handles it for us. There is the SDL_gfx library that includes a zoomSurface() routine, which is exactly what I needed. The zoomSurface() works very well and very fast, and I'm very happy with it.

After using this much SDL code, I almost wondered why I wanted OpenGL in the first place. (Of course, animating the rotating album covers in 3D is implemented with glRotate().)

Adding a shiny mirror effect of the album covers was easy; set the color to 30% (or something) and put the texture coordinates upside-down so that it looks like the object is mirrored in the shiny black glass table (or wherever they're situated). Note that I did not use any blending here; when you blend multiple images together, they will blend together (well that's what it does, right?), so you'd end up with the covers being blended thru one another in the reflection rather than having one cover in the back, and another one in the front center.

Next challenge, the album title needed to be displayed. Rendering text in OpenGL is, as always, a nightmare. OpenGL was not meant to render text, so it can't really do it. I decided to have a look at SDL_ttf, a TrueType font rendering library. SDL_ttf renders to SDL_Surfaces which you need to turn into textures again. After writing a lot of code and finally getting it to work, I found that SDL_ttf produces some really ugly output. I was quite unhappy with SDL_ttf.

So, I ripped out the SDL_ttf code again and threw it in the dustbin. Then I took some old piece of code that uses display lists and glBitmap() to blit text using a bitmap font. This looked quite nice, but it kind of bothered me that display lists are not in OpenGL/ES, so ... I ripped out this code as well, and used dedicated character blitting code to a temporary pixel buffer to create an OpenGL texture that represents the blitted string. For displaying text in OpenGL, you can also create a texture per glyph and use that to texture strings (this would be even faster, too), but in this case, I did not bother. (Maybe tomorrow, who knows?)

For the user interface, I opted to have as few buttons and bells and whistles as possible (1. to have a clutter free interface, and 2. because you have to implement all these bells and whistles too, which can be a lot of work). I decided that:

double click plays an album
single click pauses playback
right click skips song
click on the side flips through the album collection
click in the top corner flips to a screen resembling an "About" box
mouse click and move in the top to drag the window
shake the window to shuffle songs

Which called for some interesting mouse event code, especially the window shake was a bit of a challenge.

This concludes my story of implementing a CoverFlow-like interface for Linux, and I must say, I'm quite happy with it because it looks great and works nice and fast. There are some constraints to using it though; it only plays full albums, and you must have your music directory organized in albums like I have. Furthermore, it does not automatically download album art, but there are other tools to do this. I used Google images for a couple of hours to update all my album art to higher res images ...

What's really nice, is that I combined a number of technologies, and added some new things myself:

socket code for connecting to mpd
using the mpd protocol to interface with mpd
Xlib code, mainly for dragging a borderless window
SDL for event handling
SDL_image for loading JPEG image files
SDL_ttf for rendering TrueType fonts (which was taken out again)
OpenGL for 3D graphics
the power of two routines from Wikipedia
bitmap font blitting into a texture
window shake mouse event code

Anyway, I should end by providing the download link: mpflow

Dragging an SDL_NOFRAME borderless window

2009-09-23T21:45:00.004+02:00

Despite the curious title of this blog entry, I hope you will keep reading. I ran into a funny problem with SDL (the cross-platform library that is used for cool things like graphics and game programming). In SDL, you can create a main application window using the call SDL_SetVideoMode(). You can pass a flag SDL_NOFRAME to this library function to create a borderless window. Borderless windows are nice for making splash screens and such. There are two problems with borderless windows in SDL:

How to center the splash screen when it appears? In X-Windows, the window manager intelligently places the windows on the desktop, but the splash screen is not automatically placed in the center of the screen.
How do you move a window, when it has no title bar where you can grab it with the mouse to drag it across the screen?

I googled and googled, and I could not find an answer online, especially not to the second issue. So I guess this blog entry will be of value to some, as I did manage to solve it, and I will be giving the answer now.

The answer is: SDL can't do it. However, Xlib can.

Luckily, SDL has a hook for interfacing with the system's window manager, and this is what we'll be using. Mind that portability ends here; Xlib functions work for X11 (UNIX-like systems only, and you might be a little happy to know that MacOS X is derived from BSD UNIX and includes X11 support too) and not for Microsoft Windows or other systems.
Xlib programming is quite hard when trying to build great software, which is why people resort to GUI toolkits like GTK, Qt, KDE, GNOME, or SDL in the first place, but we're going to stick to SDL as much as possible and do only the missing bits with Xlib.

Centering the splash window
So, you've called SDL_SetVideoMode() with SDL_NOFRAME and got a borderless window. Now it's time to tell X11 to center this window onscreen. The little bit of trouble with this is, X11 works with screen coordinates, so you need to know the display resolution. SDL does not seem to have a way of getting the current display resolution — or did I miss something? Therefore, we ask X11 for the dimensions of the root window. The root window id can be obtained by calling XQueryTree(). After getting the dimensions, we can calculate the desired window position and set it by calling XMoveWindow().

The code looks a lot like this:

#include "SDL_syswm.h"

SDL_SysWMinfo info;

SDL_VERSION(&info);
if (SDL_GetWMinfo() > 0 && info.subsystem == SDL_SYSWM_X11) {
XWindowAttributes attrs;
Window root, parent, *children;
unsigned int n;

info.info.x11.lock_func();

/* find the root window */
XQueryTree(info.info.x11.display, info.info.x11.wmwindow, &root, &parent, &children, &n);
if (children != NULL)
    XFree(children);                 /* not really interested in this */

/* get dimensions of root window */
XGetWindowAttributes(info.info.x11.display, root, &attrs);
printf("debug: display res == %d by %d\n", attrs.width, attrs.height);

/* center the splash window on screen */
x = (attrs.width - window_width) / 2;
y = (attrs.height - window_height) / 2;
XMoveWindow(info.info.x11.display, info.info.x11.wmwindow, x, y);

/* force raise window to top */
XMapRaised(info.info.x11.display, info.info.x11.wmwindow);

info.info.x11.unlock_func();
}

Dragging a borderless window
For normal windows, the window manager takes care of window dragging when the user holds the window by the title bar using the mouse. Borderless windows do not have a title bar and it is left up to the application what to do on a mouse click and move.
For dragging a borderless window, we will also be using XMoveWindow(). SDL supports mouse events, and there is a SDL_MouseMotionEvent that we can use.
Sadly, when you try to implement window drag using the coordinates reported by the SDL_MouseMotionEvent, you will fail (or at least, I did). The problem is that SDL reports the mouse coordinates relative to the application window. Next, you are moving the window. This causes "jumps" in the mouse coordinates that SDL reports, which causes the window to jump, which causes larger mouse jumps, which causes a larger window movement, which causes ... In other words, SDL's mouse coordinate system is not good enough in this case. What we need to know is the absolute mouse coordinates on the desktop. The easiest way of getting these coordinates is by calling Xlib's XQueryPointer():

 XQueryPointer(info.info.x11.display, info.info.x11.wmwindow, &root, &child, &abs_mouse_x, &abs_mouse_y, &win_mouse_x, &win_mouse_y, &modstate);

Rocksolid window dragging is now easily implemented as:

mouse_button_down:
 if (mouse_y < window_height / 8) {       /* only top of window activates drag */
     mouse_drag = 1;
     call_XQueryPointer(... &drag_x, &drag_y, ...);
 }

mouse_move:
 if (mouse_drag) {
    call_XQueryPointer(... &new_x, &new_y, ...);

    call_XMoveWindow_delta(drag_x - new_x, drag_y - new_y);

    drag_x = new_x;
    drag_y = new_y;
 }

Naturally, the call_XMoveWindow_delta(dx, dy) calls XMoveWindow() with the current window position plus dx, dy.

Yippee
Although the X11 code is not very cross-platform, I'm quite happy with it, since it fixes some shortcomings of the SDL. If someone has ported this solution to Microsoft Windows, please send me your code; you never know when it might come in handy.

Implementing the end of the loop

2009-08-31T20:16:00.005+02:00

After yesterday's blog entry, I may have left you thinking "this guy Walter, he sure can talk the talk, but can he code the code?" Well, yeah. After writing the entry, I felt the irresistible need to actually implement the (not new) idea of having a generic framework for running a compute kernel distributed over N threads on a system with M cores. It was not as easy as I thought it would be, and there was a catch interesting enough to write about here. Talking the talk is one thing, but coding the code still is another.

Description of the problem
You want to able to process an array using a generic "compute kernel", which is a subroutine that computes a value for a single cell in the array. The system should run as many threads as needed to complete this task, so it should virtually run one thread per cell. As this is a framework, the compute kernel routine must be passed as a function pointer so that it becomes a generic interface for processing arrays in parallel.

Designing a solution
A big problem is that it makes no sense to spawn a hundred threads on a (for example) dual core system, as the overhead would play a significant role in slowing the system down rather than speeding it up in comparison to its serial brother. The solution is to spawn only as many threads as there are processor cores. Each thread processes its part of the array (using an "old-fashioned" loop) and does this without locking, so it's very fast.
However, the compute kernel is written in such a way that each invocation still works on only one array element. This is a requirement, because otherwise it wouldn't be a real compute kernel. From the compute kernel's point of view, it should look like there are a hundred threads (or more) running in the system. So rather than passing a real thread id to the compute kernel, the framework cheats and passes the cell number, which now acts as a "virtual thread id".

Even though threads are lightweight, in a system like this, it is not maximum efficiency to spawn threads on an as-needed basis. I chose to pre-spawn (or pre-fork) the worker threads and to let them sleep until called for. This requires some basic thread scheduling mechanism. After finishing the parallel work, there should be another synchronization point as well. So the end result is that an array gets processed in parallel, after which the program can continue in serial.

Implementation details 1: Automated data partitioning

OK, suppose we have 100 array elements, that we want to process on only 2 cores. That's easy, each thread handles 50 array elements. Now suppose we have 115 array elements, and 8 cores. Easy too, each thread handles 115/8th part of the array, plus a little part that is the remainder. First, let's focus on the 115/8th part. The compute kernel routine expects a cell number (or "virtual thread id" as I like to call it), which is determined as follows:

    part = 115/8              # num_elem / n_threads
    for i = 0 to part do
        vtid = part * tid + i
        call compute_kernel(vtid)
    end

By the way, I implemented this in C, but it's easier explaining in pseudo-code. Also, you may have noticed you can optimize this pseudo-code by moving the multiplication for the "base vtid" outside the loop, but it's not really important for what I'm trying to convey here. The idea is that every thread acts on its own part of the array, and it selects its own part by using its thread id as base to index the array. Now, you should be aware that the thread id of a POSIX thread can be an arbitrary number, so it should be a sequential number that is known to this thread and has been set by you at initialization time of the thread. In other words, you give the first created thread a tid of 0, the second 1, the third 2, etc, and this number should be known to the thread itself (you can do this by passing it as argument to the thread's main function). This may seem very obvious, but as said, POSIX thread ids are arbitrary numbers, and otherwise this trick of selecting the correct region in the array would never work.

When you have an uneven distribution, as is the case with 115 array elements and 8 cores, there is a remainder of the array to be processed. The remainder is computed as the modulo; 115 % 8 equals 3. The way to handle this is the same as in the following case; suppose we had an array of only 3 elements and 8 cores, then we'd do it like this:

    if tid <= num_elem then
        call compute_kernel(tid)
    endif

So, this is also how you handle the remainder part of the array in parallel, except that you'd make a simple calculation to get the "vtid" right.

This was all really simple, but we've actually accomplished a great thing here; we have created the ability to automatically process an arbitrarily sized array using any number of threads — meaning that this code will run good on a dual core system, and formidable on an 8-core system, with near linear performance improvement. Given the nature of scaling by data partitioning, this scales to 1000 cores just as easily, and further if you can find a machine that big (1).

Implementation details 2: Thread scheduling

Data partitioning was the easy part. The second part is all about thread synchronization, which is a schoolbook example, really, but very frustrating to get right if you didn't get it right the first time. I like to pre-fork the threads, and have them sleep until they are assigned work to do. Then they should be woken up, do their job, and go back to sleep. When all threads are sleeping again, that's our barrier point at which the parallel part is done, and the main application can continue in serial fashion.

This behavior can probably be implemented using mutexes only, but what's really fit for this job are condition variables. A condition variable enables a thread to sleep on a state variable, and then another thread (like in this case, the main thread) can signal it, to wake it up.

The way to do it is to use a state variable that says whether it's OK for the thread to run now, or not. This is a boolean that I named runnable. A thread is runnable when it can run, else it should go back to sleep.

thread code:
    mutex_lock(my_mutex)
    runnable = False
    while not runnable do
        condition_wait(my_mutex)
    end
    mutex_unlock(my_mutex)

main thread:
    foreach thread do
        mutex_lock(thread's mutex)
        thread runnable = True
        condition_signal(thread)
        mutex_unlock(thread's mutex)   
    end

To understand this code, you should know that condition_wait unlocks the mutex when going to sleep, and automatically (and atomically) relocks the mutex when waking up again. Apparently (at least according to the pthread specifications), there may be spurious wake ups, so the waking thread must always check its state when it wakes up. That's why it's enclosed in a while loop.

The main thread isn't so exciting, it simply signals all threads to start work. A caveat here is that upon startup, not all threads may have gone to sleep yet. So there must be a barrier sync before starting, and after ending. The barrier sync simply checks whether all spawned threads are not runnable, ie. already sleeping.

Implementation details 3: The number of threads to use

I said it's best to spawn as many threads as there are processor cores. This is true for tight code, if this doesn't drive your system close to 100% CPU utilization, you may add more threads until it does. How do you find out how many cores are in the system? This is a tough question, as it is different on every system. See this great info on stackoverflow.com, that shows how to get the number of cores from the system for various operating systems.

In my code, I choose the easy way and simply read an environment variable that you can set yourself, which is kind of inspired by OMP_NUM_THREADS, really.

Conclusion

Whew, this blog entry ended up much more text and much less code than I anticipated, but I got to tell you that it's a joy to see a function call like

    run_parallel(process_array, arr, sizeof(arr))

work in parallel by the number of threads given in an environment variable. What's really great about this routine is its flexibility and its scalability. It really scales "for free", gaining more performance when you add more cores.

1. At NASA Ames Research Center, they actually have an SGI Altix supercomputer named Columbia that has a partition running a single system image of 2048 processors, which is incredibly large, even by supercomputer standards.

The end of the loop

2009-08-30T13:47:00.012+02:00

Multi-core processors have been on the market for several years now. In commodity hardware we've seen dual processor systems (SMPs), four-way SMP systems, dual cores, quad cores, dual quad cores, quad dual cores, quad quad cores, and even the seemingly odd triple cores (XBox 360) and AMD's 6-core processors. IBM stepped into this this game by putting 8 low power SPEs and a controlling PowerPC into a single chip: the Cell processor that is the engine under the hood in the Playstation 3.

Consider a simple for-loop, running over an array to do some simple operation:

FOR i = 0 TO 100
DO
arr[i] = arr[i] + 1
DONE

The execution time of this loop is determined as follows: it's a memory fetch and store, an increment, a loop counter increment, and conditional branch (jump back if the loop counter is less than 100), so it's about 5 operations times 100, which adds up to 500 ticks. This is a very rough estimate because a modern CPU has some tricks up its sleeve like combining certain operations, but the 500 ticks will be good to illustrate what I'm talking about.

Now imagine you have a dual core system. On a dual core system, you could run this loop on one core, and play a CPU-consuming game on the second core. However, if you wanted to be clever rather than waste your time playing games, you could split the loop and be done with it in half the wallclock time.

LOCAL i LOCAL i
FOR i = 0 TO 50 FOR i = 1 TO 50
DO DO
arr[i] = arr[i] + 1 arr[i] = arr[i] + 1
DONE DONE

or you could split it like this, where the first core processes the even elements, and the second core processes the odd elements in the array:

LOCAL i LOCAL i
FOR i = 0 TO 100 STEP 2 FOR i = 1 TO 100 STEP 2
DO DO
arr[i] = arr[i] + 1 arr[i] = arr[i] + 1
DONE DONE

This code finishes in 250 ticks.

So, by dividing the array up we are enabling it for processing in parallel. This is called data partitioning, and often called a divide and conquer method. Running it in parallel made it twice as fast.

Now imagine you have a hundred cores in your CPU. It doesn't, it's insane, but what if technology had advanced so that you'd have a hundred cores in your CPU. If this was the case, then there would be no need to write the loop statement at all. The loop over the array would look something like this:

LOCAL i
arr[i] = arr[i] + 1

This one statement would be processed by a hundred cores in parallel, and the outcome of the program would be identical to outcome we obtained previously. This code would finish in just 3 ticks (fetch, increment, store) and no loop statement. (NB. Maybe the architecture would be such that it would be even less than 3 ticks, but it wouldn't be much more than just 3 ticks). Compare this to the 500 ticks that we started out with.

For a long time, many believed that this could only be achieved through quantum computing.

The funny thing is, this technique is possible today. A modern graphics card has a hundred cores (and even more than that). Technology has indeed advanced that much. The GPU is a massively parallel processing unit that was made for one purpose only: processing as many pixels (array elements) in parallel as possible. The graphics cards are programmable so that the graphics gurus can do cool things with shaders, which are essentially little programs that compute a value to put into each pixel/array element.

The computing power of graphics cards has been recognized before, but now the graphics card vendors have stepped into the world of high performance computing, literally delivering supercomputer power to your home. Moreover, Apple's latest release of OSX includes OpenCL, a programming API to harness the power of the NVIDIA chipset that is in the Powerbook.

The API (at the moment, either OpenCL or CUDA) allows you to create and destroy thousands of threads on the fly so you don't even have to care much how your array is going to be processed by the GPU cores. This is nice because often, you don't even know how many cores are in the machine that the code is running on.

It changes the way of programming because you must no longer think in terms of loops, but instead you should think only about what it is you want to do with each array element (1).

Of course, it is not all too good to be true; some problems simply can not be parallelized in this way, e.g. due to interdependencies or relations between array elements.

Still, it's pretty exciting to see supercomputing power coming to your laptop, and I can't wait until NVIDIA comes up with its next big thing.

1. This is, of course, already possible with pthreads. The only problem is that when you create a hundred threads on a dual core system, the CPU overhead of creating the threads is much higher than simply looping the loop, and thus slowing the program down. If you had the cores ready to run at your disposal, you wouldn't have this problem and you could run the code in a massively parallel manner without any overhead.

What I've been up to

2009-08-15T19:33:00.009+02:00

Hi folks, this post is a follow-up to my last blog entry, which was about GLFW. As quickly as I fell in love with GLFW, just as quick my crush was over; I switched back to SDL. The reason: GLFW — a "portable" library — was giving me huge problems with, you guessed right, portability. I really liked GLFW, and I really tried, but it just didn't work out. In the end, it only made me cry.

Portability is a strange phenomenon. Code that works perfectly on one platform, simply doesn't work on another. This is especially true if you haven't tested it and actually have seen it work with your own eyes. Unless you have actively engaged in the act of porting your software over, it is unlikely it will run 100% correctly. I am saying this because I just ported my (now SDL) game over to MacOS X and uncovered a really dumb bug: using an uninitialized variable, assuming it is zero. The code worked like a charm in Linux, but not on the Mac. Why the GNU C compiler didn't see this problem is beyond me since it does complain in most cases, but hey, you can't expect a free compiler to be bug free, either.

Anyway, I'm back with SDL and pulled a really neat trick; I wrapped it with some code to make it more GLFW-like! You see, I really liked GLFW's structure, hiding the event loop, using callback functions, etcetera. So, now can live with a framework that handles real easily, and on top of that, I may replace the inner workings of the "SDK" wrapper with something else some day — maybe even the next version of GLFW — without having to overhaul all of the code.

IMHO, this surrogate blend of a library is actually even better than the real thing.

In the meantime, I also switched editor. The editor is a very personal kind of tool for the programmer. I was fairly happy with joe in Linux, until the release came that has an annoying bug that SEGVs the editor when giving multiple files to edit on the command line. An editor that bombs out when you want to edit files, how great is that? Ah well. At least Joe gave away his Own Editor for free.

And then I found the Code::Blocks editor (cool name, by the way). Although it's kind of awkward to use a Windows program in a UNIX environment, I'm getting used to it. You read that right; Code::Blocks may run natively in Linux, the portable WxWidgets library makes it look and feel like a Windows program, independently from whatever platform or OS you are running it on. WxWidgets extrapolates portability to the max. This means no X mouse clicks to copy text (argh!), use the Ctrl-C/Ctrl-V copy/paste combination (oh, the horror!).

This surrogate blend is not really better than the real thing, but you do get a nice IDE that handles a lot friendlier than make and gdb. Yeah, I know you all like gvim ... but for some reason I never got to like vi enough to use it for anything larger than shell scripts. Code::Blocks is a great alternative, but I do miss integration of man pages and svn or git. These are available through plugins but I haven't sorted out all that stuff yet.

Being used to just a tabbed terminal window, Code::Blocks also suffers a bit from too much screen clutter like toolbars, panels, etcetera. It would be nice if you could press a magic key (the Windows key, perhaps ...) to make the clutter disappear and actually have a normal editing window on your desktop. Elaborating on that idea, it would be great if the "full screen" view would actually make the editor full screen, rather than making the application full screen and keeping all toolbars and panels in view.

I should end by saying that Code::Blocks is a great developers tool, even while it insists on linking standard C codes using the g++ command. (Somewhere out there, there must be a brilliant mind that can give a perfectly logical explanation for this. Naturally, I did not have g++ installed, since plain old C is my thing, but ... sigh. As I said, I should end by saying ... Code::Blocks is a great developers tool).

On the Mac, there is of course Xcode. Xcode has the same kind of interface with panels all over and a relatively small editing window, but that doesn't matter, you can't get anything done in Xcode without having taken Apple's developer course. I don't know why, but while Xcode looks fantastic, it is immensely complex to build software with. When I write software on the Mac, I use make on the command line. And that is one sad fact.

I like to finish this post on a positive note. The good news is, my game is nearing completion. I had something playable already after three weekends, but you know how it goes, you keep adding and adding new stuff as you keep getting more and more ideas. Creativity spawns more creative ideas. Some programmers call it "being in the zone". I've been there. It's addictive. I want more. But I also really want this project to be done with, mostly so I can find peace and round off two other, smaller projects that I've been working on. When you are working on three projects at the same time, none of them get finished any time soon.

So when it's done, I can catch my breath ... and start off writing code for a really cool idea that I've been having lately ...

Experiences with a different cross platform graphics library

2009-07-29T17:31:00.006+02:00

There are periods when I don't write any code at all. These times are like the silence before the storm ... Last month, the silence broke and the storm was unleashed. I wrote code, code, code, and still managed to keep my head above in the sea of binary.
I'm currently working on three interesting hobby projects at once; a rewrite of an old skool BBS using pthreads and an SQL database backend; a cluster administration tool written entirely in Python; an OpenGL arcade game. So, there's plenty to blog about, but for now, I'll pick the game because OpenGL and games are always interesting. As you may know, I like using the SDL for developing OpenGL programs because it is a portable library. And then I ran into some post on the net where a guy said, "I always use glfw". I decided to check it out, and believe it or not, I ported it over from SDL to GLFW in just a couple of hours. GLFW is deceivingly simple. I decided it's out with SDL, and in with GLFW.

Starting out with GLFW
A first look at the website reveals that the latest stable version dates back to 2007. Hmmm ... this could mean that it's really stable, or that bugs are no longer being fixed. There is mention of an upcoming new release, though.

How to make use of GLFW? Just create a window, and make library calls. The library does not assume you use an event loop in your code. While this is surprising, it's really all for the better. I spent lots of time perfecting the event loop that SDL needs. GLFW just doesn't care. You want to know if a key has been pressed? Well, ask for it! Want to know the state of your windowed app? Call a glfwGet function to obtain it. If you really want, you can also register a callback function, for example for keyboard input events, and do things the event driven way.

Example code:


void init_events(void) {
   glfwSetKeyCallback(key_event);
}

void key_event(int key, int state) {
   if (state == GLFW_PRESS)
       handle_keypress(key);
   else
       handle_keyrelease(key);
}

No library is perfect
As it says on the GLFW website, no library is perfect. I ran into little problems that had great consequences and had me hit the reset button of the computer (!) multiple times. Hello ... hitting reset is so 1989. But then again, I was programming an old skool arcade game.

I would like to detail the troubles I ran into here. Mind that they are not really big obstacles, just gotchas, things you need to know about GLFW, and maybe annoyances that might want you to favor SDL anyway, but to each his own.

There seems to be no good way to toggle between full screen and windowed mode. I tried to resolve this by closing the window and recreating it, but the window manager somehow doesn't like it. It is not an OpenGL problem, nor a problem of my app — SDL can do it and GLFW can't. So stick to either windowed or full screen, not both.
When you resize a window, you should reinitialize OpenGL, reload textures, etc. This may take some time. When you drag a window using the mouse, GLFW will register multiple resize events, causing your app to reinitialize multiple times and causing considerable lag. I never had this problem with SDL.
The characters of keys that are pressed will be reported in uppercase, even when shift is not being held down.
For text input, do not use glfwSetKeyCallback(). Use glfwSetCharCallback() instead, which does ASCII translation, etc. This will give lowercase characters, a working Shift key, etc. One thing I really don't like is that it does not translate the return key to '\n', nor does it translate backspace to '\b', and Escape is not code 27. So, I use SetCharCallBack() for the regular input, and I use SetKeyCallBack() at the same time to translate often used keys like Escape, Return, Enter, Backspace.
glfwGetTime() returns a double, in seconds. This is actually great, but keep this in mind because other libraries, like SDL, work with integers and milliseconds.
The library includes functions for multi-threading. Don't use them, they will be removed in a later version. Use pthreads instead.
GLFW does not include functions for sound. This is intended; use OpenAL for sound.

Do you want to know more?
If you would like to get started using GLFW, I recommend reading the users guide that is available in PDF format on the website: http://glfw.sourceforge.net/documentation.html

Taking out the trash

2009-06-22T20:48:00.009+02:00

While working on a hobby project in one of my all-time favorite programming languages (standard C), I once again encountered an old problem: memory leakage. I hunted down the problem and fixed it, but it bothered me that I made this mistake, and it bothered me that it was so easy to make this mistake. In my second favorite programming language (Python), this would never have happened. Python features a built-in garbage collector. Why can't C have a garbage collector? The answer is, it can, but you just have to implement it.

Description of The Problem, The Pitfall

The common mistake happens when doing things like this:

int foo() {
char *p;
struct some_struct s;

  p = (char *)malloc(NUMBER_OF_BYTES);
  bar(&s, p);

  if (...) {
      if (... && ...) {
          ...
      } else {
          ...
          return -1;
      }
 }
 free(p);
 return 0;
}

Clever folks will see that there's a memory leak at the "return -1" (forgot to call free(p)), but did you spot the other memory leak? That's right ... what I didn't tell you, is that function bar() also allocated some memory to store into a member of the struct, and it's not being freed anywhere because it's not obvious that it's using memory.

Use another language: C++

So, I can hear you say, use C++. C++ will call the destructor when the local variable goes out of scope. This only partly solves the problem. In practice, I've learned to hate C++ because it makes things even less obvious than before, causing more problems than solving them.

Reference counting

How does Python pull it off? In essence, it's simple — it uses reference counting. Reference counting means that when you point a pointer variable at a piece of memory, you are referencing this object, and so a counter is incremented. When you stop using this object, the counter is decreased. Once the counter hits zero, no pointer variable is tracking this space anymore, meaning that this object has become useless, and therefore OK to clean up. Hence, the object is being garbage collected. Note how the object can be cleaned up immediately, and that there is absolutely no need for a separate thread to actively scan memory to collect bits of unused memory. I have no idea where this myth stems from (the Java world?).

Mimicking the interpreted language

Reference counting can be done in standard C too, but it's actually quite hard to do it right. Every single time you assign a pointer variable, you have to increment the associated reference count. This is doable, and you can even write a set_xxx() wrapper function or macro to do it for you. What's much harder, is to unreference the object when you let go of it. You are bound to forget to do this correctly just the same as pairing malloc()/free() calls was too hard to get right. The only reason why (byte-code) interpreted languages like Perl, Python, PHP, Java, etc. do get it right, is because the outer layer that really drives the language is doing all assignments and keeping track of the references, rather than the programmer trying to track things from the inside. (Or am I mixing up "inside" and "outside" here, are you still with me?!?!)

I think it was Guido himself who once said that if you would get all the reference counting with objects right in C, you'd practically already be programming in Python.

Tracking mallocs

What if you'd register all malloc()ed memory to a Memory Manager, and replace C's standard "return" statement with a macro "Return" that first visits the Memory Manager to see if there's anything left behind to clean up.

Sounds great, but how can it see the difference between a temporarily allocated buffer, and an object that was allocated to live for the rest of the lifetime of the process? This is exactly the core of the problem — we use the same malloc() for two different things; we want temp memory that is somehow magically destroyed at the end of the function, and we also would like to allocate memory because our program needs it. (NB. There may be a situation where an object may be temporarily, but not quite ... although I can't say I can think of such a situation right now). The solution to this problem would be to implement a tmp_malloc() function that is used for temp variables (like local variables), and have it track this memory so that a "Return" statement can clean it up. This actually works, but in practice, a lot of duplicate code is needed because you want to able to call malloc() in one situation, and tmp_malloc() in another. A real slick trick to solve this, is to make Malloc a pointer to a memory allocating function, and have it point to either malloc() or tmp_malloc(). All the programmer needs to do now is decide whether he wants to temporarily use memory, or assign it for a longer period of time.

Implementing the solution

The solution with the Temp Memory Manager and the Malloc pointer to the allocator function is so exotic that I have not implemented it yet. Do I really want to write this kind of crazed code, just to keep from making small mistakes? One could just as easily label local variables as such, and alert the programmer to double check that this space needs to be free()d.

#define LOCAL

int foo() {
int a;
LOCAL char *p;       /* <-- indicator, just to alert the programmer */

    p = (char *)malloc(SOME_BYTES);
    ...

Here, the empty, seemingly meaningless #define alerts the programmer to double check this situation, and the mistake of forgetting to call free() is easily avoided. No need for in-program memory managers and self-inspection, only one simple empty #define and your common sense.

Conclusion

We've taken a shot at trying to find a way to do garbage collection in standard C. We've found reference counting, and thought up a way to free all 'locally' allocated memory. In the end, we're probably better off tagging potential leaks as such and leaving it up to the programmer to do his job right. While this non-technical solution may not appeal to everyone, at least we're not going for the technical solution for the sake of having a technical solution. Sometimes, "good is better than optimal".

I may still implement the technical solution, just for fun, of course.

pthreads and UNIX signals

2009-05-24T11:19:00.004+02:00

A while ago, I wrote in this blog entry that when sending signals to a multi-threaded process, it is unclear which thread receives the signal. This little problem is actually easy to solve when you realize that you can create a seperate thread whose sole purpose it is to catch signals and respond to them.

You can mask out certain signals using sigprocmask() and its threaded nephew, pthread_sigmask(). These signals will be effectively disabled and will never be received in these contexts.
In the "signal processing" thread, enable the blocked signals. This will now be the only thread who receives the signals.

In almost finished C-code:

int main(int argc, char *argv[]) {
sigset_t set;

/* create signal processing thread */
    pthread_create(&thread_id, NULL, signal_processor, NULL);

/*
    in the main thread, set up the desired signal mask, common to most threads
    any newly created threads will inherit this signal mask
*/
    sigemptyset(&set);
    sigaddset(&set, SIGHUP);
    sigaddset(&set, SIGINT);
    sigaddset(&set, SIGUSR1);
    sigaddset(&set, SIGUSR2);
    sigaddset(&set, SIGALRM);
/*  sigaddset(&set, SIGWHATEVER); */

/* block out these signals */
    sigprocmask(SIG_BLOCK, &set, NULL);

/* create other threads */
    pthread_create(...);

/*  ... */

/*  pthread_join(...); */

/*  ... */

    return 0;
}

/*
    implementation of the signal processing thread
*/
void *signal_processor(void *arg) {
/*
    install signal handlers for interesting signals
    I choose to install dummy handlers (see below for why)
*/
    install_signal_handler(SIGHUP);
    install_signal_handler(SIGINT);
    install_signal_handler(SIGUSR1);
    install_signal_handler(SIGUSR2);
    install_signal_handler(SIGALRM);
/*  install_signal_handler(SIGWHATEVER); */

    for(;;) {                  /* forever */
/*
    wait for any signal
*/
        sigfillset(&set);
        sigwait(&set, &sig);

/*
    handle the signal here, rather than in a signal handler
*/
        switch(sig) {
            case SIGTERM:
                exit(1);

            case SIGHUP:
                reload_config();
                break;

            default:
                printf("caught signal %d\n", sig);
        }
    }
}

void dummy_signal_handler(int sig) {
/* nothing */
    ;
}

So, the code first creates a signal processing thread. This thread has the default signal mask and will therefore receive signals. The main thread then installs a signal mask that blocks most signals. Any threads created from the main thread will inherit this new signal mask.
The signal processing thread uses sigaction() (not shown here) to install signal handlers. These signal handlers are empty dummies. The reason for this is, by installing a signal handler you tell the operating system that you do not want the default signal action for these signals. Next, call sigwait(), so wait indefinately until any signal arrives. Then, handle the caught signal.
It is possible to install useful signal handlers instead of using the dummies, but I'd much rather use sigwait() and make signal handling synchronous as opposed to asynchronous. (The threads are still run asynchonously in respect to each other, though).

It is tempting to simply use sigfillset() and block all signals. While this is perfectly possible, it does have some implications. Any errors that generate signals like SIGSEGV, SIGBUS, SIGILL, will be blocked in the thread that generated the error, and caught in the signal processing thread. Be wary of this, as this is likely to produce debugging headaches.

There is a pthread_kill() function that you can use to send signals to threads. Do not use this mechanism to communicate between threads. Threads should synchronize and communicate using mutexes, barriers, and condition variables, and if you want to terminate a thread you should use pthread_cancel(), or communicate to it that it should exit, so that it can call pthread_exit() by itself.
The only use of pthread_kill() is to copy the signal to other threads that should also receive it, if you have a (weird) code where multiple threads can be signalled.

Multi-core games programming

2009-05-06T13:31:00.013+02:00

I'm on sick leave, and although I've got some bad stomach problems and my head hurts, this is finally an opportunity to think over the problem of multi-core games programming. You see, modern computers are parallel machines, and it is a challenge to the programmer to take advantage of all this processing power.

Games are an interesting class of computer programs. Even the simplest of games draw our attention, because of the interaction between human and machine. On the inside, games are interesting as well. The code often contains things like an input handler, object allocators, sound file loaders, sprite or 3D object rendering code, etc, etc.
When switching from a single threaded game design to a multi-threaded one, you would probably think it would be smart to make a functional split:

a thread that handles sound
a thread that handles AI
a thread that handles rendering
a thread that handles input processing

While there is nothing wrong with this design, you are not getting the most out of the machine. What if we have a 8-core or 16-core or 100-core machine?

Imagine an old 8-bit 2D game where you walk around in a maze, picking up objects, and shooting bad guys. Do you have it visualized in your mind? Now, imagine a modern 3D shooter. What has changed? The amount of data, but also the amount of math. 3D worlds can be huge, with high-res textures, and realtime reflections and shadows. Great graphics hardware will take care of rendering objects to the screen, but the decision of what data of this vast 3D world is pushed to the GPU, is up to the programmer. All the culling has to be performed on the CPU, not the GPU.
What if the player bumps into a wall? Collision detection is a job done by the CPU. In our old 8-bit game, we could get away with checking the byte value (representing a wall) next to the player position in the two-dimensional array that represented the map. In a modern 3D game, we have to do a lot more than just that -- we have to compute the intersection between player and wall object with any of the walls that are near. In theory, we'd have to check every wall in the map, however, this is made more efficient by splitting the map into sections. Still, a section can be full of walls and other objects to bump in to. This takes a vast amount of computations.

Another subject is AI. While you'd probably think that good AI takes an enormous amount of CPU power, this is usually not the case. Yes, AI may utilize complex formulas, but this is generally totally unnecessary. Making a character behave or perform certain actions is accomplished by implementing a simple state machine. The state machine need not do much to get great results. It is the (vast) amount of intellectually behaving objects in the game world that results in AI taking up CPU time.
One last thing is animation. In the old 8-bit days, animations were done by drawing the next animation frame on every game tick. In the modern days of 3D graphics, there are still frames, but the 3D points can be interpolated in between frames, allowing for supersmooth animation. This requires every point to be interpolated on every game tick. In fact, nowadays we have multi-tasking operating systems, and a game tick is no longer a hard set value — one tick can last 10 ms, while the next one lasts 50 ms or more. This irregular behaviour of the game clock calls for interpolation too, in order to keep animations from stuttering.

As you may have realized by now, it is wise to parallelize by splitting on "data", or object handling. If we spawn as many threads as there are processor cores, we are fully utilizing the CPU. Maybe we even want to play nice and leave a core unallocated so that the operating system gets a chance to run its tasks while we are busy gaming.

We parallelize each big for-loop in the code:

PARALLEL DO
  foreach obj in objects
  do
     animate(obj)
     artificial_intelligence(obj)
     collision_detect(obj)
     culling(obj)   # set flag whether object is visible
  end
END PARALLEL DO

render:
  foreach obj in objects
  do
     if obj.visible
     then
        draw_object(obj)
     endif
  end
  flush_screen()

Note how the rendering loop is not parallel. Funnily enough, the GPU is addressed in serial. This is funny because the GPU in itself is a massively parallel processor.

I do not recommend putting the rendering loop in a thread by itself. The reason for this is that if you do, you will need to mutex-lock each object that is being rendered. This is less efficient than simply doing it in serial.

Enough talk and pseudo-code, it's time to sit down and implement this for real. But first, I need to get rid of my headache ...

Dining Philosophers

2009-02-28T22:38:00.026+01:00

A while ago, I wrote about threading. Last week, one of the students I'm guiding for their internship, mentioned he still had to complete a programming assignment. It was about implementing the dining philosophers problem in C, using pthreads. To a student, this can be quite a challenge.

The dining philosophers problem is a very fun programming problem concerning resource locking. The origins date all the way back to 1965, a time when computers were big clunky machines with green terminals, and the operators were computer scientists wearing lab coats.

An excellent description of the problem can be found in Wikipedia.

I remember my brother once explained it to me when I was young. He loves spaghetti, so I guess the idea of the philosophers having spaghetti kind of appealed to him. He noted that, in a real world situation, the problem is easily solved by adding a director, who tells the philosophers when to eat and when to think. So, a scheduling assistant can help in solving the problem. However, the problem can also easily balance itself by doing the right kind of locking, and be solved without the use of an explicit arbiter.

In pseudo code:

proc run_thread() { while plate not empty { lock(left_fork) if not trylock(right_fork) { unlock(left_fork) continue } eat from plate unlock(right_fork) unlock(left_fork) } }

In order to avoid deadlock, trylock is used rather than a hard lock. trylock is an atomic operation like bit-test-and-set; it locks only if the lock was free, and does not wait until you actually own the lock.

When locking multiple resources at once, it is good practice to unlock in the reverse order of locking, also to avoid deadlock.

Note that there is no need to sleep anywhere in the loop; waiting for short periods of time is something that a human would do, but is totally unnecessary in a computer program. (Think of all the cycles needed to load/execute the instructions in between as waiting for short periods of time!)

Starvation

In the above code, it's possible that one philosopher finishes his plate, while the others haven't even started yet — they are literally starving. It would be good table manners if we instructed each philosopher not to eat faster than his neighbors. This would produce automatic balancing in the use of the resources.

In pseudo-code:

if my_plate < left_neighbor_plate or my_plate < right_neighbor_plate then eat from plate

Making the wrong if-statement here results in nobody eating. You can also move this if-statement up, and refrain from trying to lock while the neighbors haven't eaten yet. This is giving your neighbors a chance to eat, and results in spinning before the lock, but also in a higher success rate for acquiring both locks.

What's fun is seeing how the outcome is different every time; you can actually gamble on which philosopher will finish first. Multi-threaded programs have a weird way of being undeterministic somehow.

As an exercise, and just for the fun of it, I coded up the dining philosophers problem with N philosophers in C with pthreads in less than an hour. I think that I would have had a much harder time at it when I was still a student, though.

OpenAL - sounds good!

2009-01-25T08:32:00.012+01:00

For getting sound to work on the iPhone, I needed to acquaint myself with the OpenAL sound system. OpenAL is also particularly interesting because it is a 3D sound system. You set the position of a sound source, and OpenAL will take care of getting the volume just right, as well as the "position" of the sound where you are perceiving it to be coming from, when you hear it played on your surround set. It can also do cool things like the doppler effect. While I do not need 3D sound and just have started using OpenAL, it would certainly be cool to get some simple stereo sound effects in my game. This is something that SDL_mixer can not do.

OpenAL tutorials and ALUT

There are some nice tutorials on the web, and they all use ALUT. It turns out that ALUT had some (simple to resolve!) bugs in it, and some guys decided to mark it as deprecated. When standard C code gets marked as deprecated, gcc won't compile it anymore. So, now all those nice online tutorials don't work anymore. ALUT had two functions that were really convenient: alutInit() and alutLoadWAVFile(). Writing my own WAV loader took some time, but I managed, and initializing OpenAL properly takes some magic sequence, but read below about how that works.

Ubuntu Linux suxxors

First a sidestep from writing code; getting your system to work, and be able to produce sound at all. My favorite development platform is still Linux. For some reason, Ubuntu decided to break sound in version 8.10 (Intrepid) and I've been hassling with it for days to get some audio output out of my programs. At it turns out, Ubuntu Intrepid mixes asound (ALSA), esnd, and PulseAudio, with an apparent preference for PulseAudio, except that it's not properly integrated or set up or whatever, it just doesn't work in all cases. That's right, one program seems to work, while others don't. The solution: I removed all PulseAudio packages from my system, and installed their ALSA counterparts. (In fact, I compiled the mpd music player daemon by hand, because Ubuntu's version tried to use PulseAudio anyway). After taking these drastic measures, my sound programs produced audio output, hurray!!

Initializing OpenAL

As said, we are going to have to do without ALUT. OpenAL needs to be initialized by creating a "context" and selecting the audio device, otherwise you will get nothing but errors. In some tutorials, I found that you may select "DirectSound3D" as a device, but that obviously only works on Windows. I have no clue what devices are available on Linux, MacOS X, or whatever other platform you may think of. Luckily, there is a way to get the default device.

I'll share The Code with you:

#include "al.h"
#include "alc.h"

int init_openal(void) {
ALCcontext *context;
ALCdevice *device;
const ALCchar *default_device;

default_device = alcGetString(NULL,
ALC_DEFAULT_DEVICE_SPECIFIER);

printf("using default device: %s\n", default_device);

if ((device = alcOpenDevice(default_device)) == NULL) {
fprintf(stderr, "failed to open sound device\n");
return -1;
}
context = alcCreateContext(device, NULL);
alcMakeCurrentContext(context);
alcProcessContext(context);

/* you may use alcGetError() at this point to see if everything is still OK */

atexit(atexit_openal);

/* allocate buffers and sources here using alGenBuffers() and alGenSources() */
/* ... */

alGetError(); /* clear any AL errors beforehand */
return 0;
}

First a remark about the includes. Including the files "al.h" and "alc.h" is much more portable than using <AL/al.h> and <AL/alc.h>, and it saves you from resorting to "#ifdef PLATFORM_SO_AND_SO" constructs.

Using the default device may not always be the best choice. There should be an option in the program to let the user decide on what device to use.

Note the atexit() call; OpenAL will complain loudly when you exit the program without having cleaned up properly. It has a right to complain too; you've allocated some valuable hardware resources and it may be well possible that the operating system is not exactly babysitting this hardware, meaning that when you exit the program without releasing the allocated hardware buffers, they will remain as marked 'in use' until the computer is rebooted (!).

A good atexit() handler frees the allocated resources and closes the sound device.

#include "al.h"
#include "alc.h"

int init_openal(void) {
ALCcontext *context;
ALCdevice *device;
const ALCchar *default_device;

default_device = alcGetString(NULL,
ALC_DEFAULT_DEVICE_SPECIFIER);

printf("using default device: %s\n", default_device);

if ((device = alcOpenDevice(default_device)) == NULL) {
fprintf(stderr, "failed to open sound device\n");
return -1;
}
context = alcCreateContext(device, NULL);
alcMakeCurrentContext(context);
alcProcessContext(context);

/* you may use alcGetError() at this point to see if everything is still OK */

atexit(atexit_openal);

/* allocate buffers and sources here using alGenBuffers() and alGenSources() */
/* ... */

alGetError(); /* clear any AL errors beforehand */
return 0;
}

Mind the order in which to call OpenAL in the atexit handler, always first stop the sound, delete the sound sources, and then delete the buffers. Then move on to the context, and finally close the device. If you don't do it in this order, the sound system will not be properly de-initialized.

Loading .WAV files

Loading WAV sound files is easy, although there is one big gotcha to it: it is a binary format, stored in little endian format. The intel x86 line of processors are all little endian, so no problem there. However, I like to write portable code, so this is a bit of fun. I have the pleasure of having access to a big endian machine, so I could test my WAVE loader code there, too. I came up with a very simple test too see if a machine is big or little endian:

#include <stdint.h>

int is_big_endian(void) {
unsigned char test[4] = { 0x12, 0x34, 0x56, 0x78 };

return *((uint32_t *)test) == 0x12345678;
}

The is_little_endian() function is left as an exercise to the reader.

Back to the WAVE loader, what I do is simply read the whole file into

memory and then map a struct that represents the WAV header over it. Then I do the integer fixups (read as little endian values), and then perform some basic checks on whether this really was a good WAV file. For a music player, you should do these checks before loading the music data, but for my game code, I was happy with simply loading the file all at once.

You can find good information about the structure of a WAV file header on the web. Note how a WAVE loader is really a RIFF loader, and in my case, also a PCM sound loader.

There is a gotcha when blindly pouring the WAV header information into a struct, which is alignment. The compiler may mess around with the size of your struct ... use pragma pack to

instruct the compiler to refrain from doing that:

#pragma pack(1)
typedef struct {
uint32_t Chunk_ID;
uint32_t ChunkSize;
...
uint16_t AudioFormat;
...
} WAV_header_t;
#pragma pack()

I've noticed that there are quite a few WAV files out there that have little mistakes in the

headers, in particular the final field data_size (or subchunk2_size), which represents the length of the music data, is often wrong. The correct value is file size minus header size, and note that you can now 'repair' the WAV file.

Now that we've succeeded in loading the .WAV file, feed this data into alBufferData() and we're ready to make some noise.

Closing remarks

In this blog entry I've shown how you can survive without ALUT. Although SDL_mixer happily handles .mp3s, and many other formats, it doesn't give you the stereo and 3D sound that OpenAL does. For OpenAL, you will need to write your own sample loader. Painful as it seems, it is really just a good exercise in handling data formats.

In the devmaster OpenAL tutorials they show how to stream Ogg Vorbis files through OpenAL. Be sure to read all their tutorials, they're pretty straightforward once you've gotten through lesson 1. Also note how they rely on ALUT ... forget about ALUT. Use OpenAL, it sounds good.

Porting an OpenGL demo to iPhone

2009-01-11T12:24:00.013+01:00

You may read this blog entry as "a beginners guide to OpenGL ES". Like many others, I wanted to write a cute little app for the iPhone. Also, like many others, I know nothing about MacOS X programming (the Cocoa API), so I quickly found myself lost in the woods. I do have experience with SDL and OpenGL, however, so I decided to port the infamous "WHYz!" demo to iPhone, using Apple's Xcode and iPhone simulator.

History of the WHYz! demo

The WHYz! demo is a story by itself. It is included here as background information and for the sake of story-telling. Skip this section if you are interested in the OpenGL ES code only.

Way back in them good old days, 1996, I wrote the first WHYz! demo on an 33 MHz 486 PC. It was meant as an electronic birthday card. During a dark night of coding, I rewrote the whole thing in 100% assembly code, hoping to squeeze a few extra frames out.

In 1997, I ported the C version to Linux using svgalib. I also played around with Qt around that time, but I don't think I ever made a Qt port of the WHYz! demo.

In early 2006, I was first trying out SDL and made an SDL implementation of the WHYz! demo.

In 2007, I made a completely new rewrite in SDL/GL. This version is different from the original, but demonstrates the same kind of wave effect.

Now the wavy WHYz! demo comes to the iPhone with OpenGL ES.

Taking the first hurdle: Objective-C

The iPhone's operating system closely resembles MacOS X. In MacOS X, applications are typically written in Objective-C. This is an object-oriented dialect of C. When you see Objective-C code for the first time in your life, your stomach will turn and your eyes won't know where to look and you will feel dizzy. Remember this: Objective-C is much like C++, only with a different syntax. Readers of this blog may know I have already expressed my aversion of C++, well, Objective-C is even less prettier on the outside. On the other hand, the first impression is not everything. Objective-C seems to come with a very nice API, that is going to cost time and dedication to master. At this very moment, life is too short to spend valuable time on this, so lucky for us, it is possible to mix standard C with Objective-C, just like it is possible to write "C++" code in standard C, and only benefit from the handy "// comment" C++ syntax.

So, we will have Xcode generate the startup code for the main application for us, and call our good old standard C code from there. Cheating? No, just not rewriting working code in a dialect that I don't speak.

Taking the second hurdle: SDL for iPhone

As my existing code is all SDL/GL, I really need SDL for iPhone. How else would we setup the screen, handle input events from the operating system, play sound, and finally, render out OpenGL scene? As of yet, the answer is ... you don't. Maybe I didn't look hard enough, but I did not find a SDL library for iPhone. It appears to be in development. For this demo, I managed to do without SDL, but things will be much harder when trying to port a full blown game.

For setting up the screen: Let Xcode generate an EAGLView.m for you. Insert your own init_gl() routine to setup the viewport, and reset the projection and model view matrices.

Input events: The demo doesn't need input, but I'm sure Apple has some neat CoreInput or whatever framework for this.

Play sound: Not used in the demo, but they say you should use OpenAL, which sounds nice. OpenAL is portable and doesn't look hard to use.

Render OpenGL scene: Insert your own draw_scene() code into the EAGLView drawView() method.

All done? NO, the best is yet to come. Hit the "Build and go" button in Xcode and you will get a ton of errors on OpenGL calls.

Hurdle #3: The limitations of OpenGL ES

OpenGL ES stands for "OpenGL, Embedded Systems". Mobile devices are always relatively slow, simple, low-power computers. In the beginning, there would not even be a FPU. If your mobile device has no FPU and therefore only implements OpenGL ES 1.0, you are stuck with fixed point calculations. Lucky for us, modern mobile devices like the iPhone are capable of doing floating point calculations in hardware.

The graphics chips in mobile devices are also real simple compared their mean big brothers in gaming PCs. The OpenGL ES API has been slimmed down to mirror this.

Just to annoy developers, the great creators have altered a fundamental concept of OpenGL, only to force people into writing more efficient code. Shocking news: in OpenGL ES, there is no glBegin()/glEnd(). There is no glVertex(). There is no glTexCoord(). Argh!

There are only glDrawArrays() and glDrawElements().

(By the way, remember my OpenGL optimization lesson? Use glDrawArrays() to speed things up a little).

There is not even glFrustum() and glOrtho(), but their callings have been made more consistent with the rest of the API; call glFrustumf() and glOrthof().

There is no polygon mode, so no more cool debugging in wireframe (my absolute favorite polygon drawing mode). Well, you can do it, but not through glPolygonMode().

There are no quads, only GL_TRIANGLE and GL_TRIANGLE_STRIP remain.

There are no display lists, use a subroutine as workaround.

You can not push/pop attributes. The programmer should be knowing what the state is at all times, and he should be knowing what he's doing anyway. Just like in the real world.

There is no full set of color manipulation routines, only glColor4f().

There is no GLuint, only GLfloat.

Oh yeah, and you have to find the right include somewhere, too.

This leaves you with a rather big mess of cool OpenGL standard code, that just doesn't work in OpenGL ES. I guess you could write a set of macros that converts existing code to ES, but I'd rather stay away from this headache. Nothing remains but to go through the code and do the tedious work of converting each and every block of OpenGL code to ES.

Taking hurdles: Converting existing OpenGL code

Converting the existing code is mostly looking for glBegin()s and putting all glVertex()s into a vertex array. Finally, call glDrawArrays(). I will give a 2D example for the sake of simplicity:

/* old code, in some kind of orthogonal coordinate system */

#include "SDL_opengl.h"

glBegin(GL_TRIANGLE_STRIP);
glTexCoord2i(0, 0);
glVertex2i(-1, 1);
glTexCoord2i(0, 1);
glVertex2i(-1, -1);
glTexCoord2i(1, 0);
glVertex2i(1, 1);
glTexCoord2i(1, 1);
glVertex2i(1, -1);
glEnd();

New:

#include <OpenGLES/ES1/gl.h>

GLfloat vertex_arr[8] = {
-1.0f, 1.0f,
-1.0f, -1.0f,
1.0f, 1.0f,
1.0f, -1.0f
};
GLfloat tex_arr[8] = {
0.0f, 0.0f,
0.0f, 1.0f,
1.0f, 0.0f,
1.0f, 1.0f,
};

glEnableClientState(GL_VERTEX_ARRAY);
glEnableClientState(GL_TEXTURE_COORD_ARRAY);

glVertexPointer(2, GL_FLOAT, 0, vertex_arr);
glVertexPointer(2, GL_FLOAT, 0, tex_arr);

glDrawArrays(GL_TRIANGLE_STRIP, 0, 4);

I was lucky that my code already used triangle strips ...

If you use display lists, convert those to subroutines. You will lose the performance benefit that glCallLists() has. My guess is that mobile devices lack the GL "compiler" and cache memory that are needed for display lists.

Simply delete calls that set the polygon mode. If you need to draw lines ... pass GL_LINES to glDrawArrays().

Finally, search your source for "glColor" and replace all by glColor4f().

glColor3ub(0xff, 0x80, 0);

becomes:

glColor4f(1.0f, 0.5f, 0.0f, 1.0f);

The final hurdle: Reaching the finish line

When I finally got the code to compile, it still did not work. One of the problems was, the textures did not load. The thing is, on MacOS X, applications and data files are part of a bundle. If you want to load a texture, you have to access the bundle using the NSBundle class in the Cocoa library. Since my code is based on fopen(), I chose to cheat and not use the NSBundle class. At startup, I do a chdir(dirname(argv[0])) and find my texture files there. This is quite ugly, as it manipulates argv[0].

I had another caveat that was pretty obvious after I figured it out ... I deleted the SDL resize_window() code from the source. This routine also (re)initialized OpenGL in the proper way ... so I was trying to start out without having set the right coordinate system (oops).

When this was fixed, I could now happily enjoy watching the WHYz! demo in the iPhone simulator. (Yeah, it's time to go buy a real iPhone ...)

Networking, routing, and bit masks

2008-11-23T12:17:00.011+01:00

Last week I got funny little assignment through a colleague of the Networking department. They've got a huge set of routes set in a major internet exchange machine in Amsterdam, and wanted to have a program to optimize the routes. Optimizing the routes is not only important for performance reasons, but also because of money — some connections are more expensive than others.

This assignment is interesting for a number of reasons:

I feel like I haven't coded anything useful for ages
I will not be writing the code, but designing it together with a co-worker, who will do the actual implementation
Someone will actually be using this
This will save the boss money (we could've been rich ...!)
The internet might benefit from this, implicitly pleasing many people (the good folks at home)
It involves some good old-fashioned bit-mucking about (and I love it!)

So, what does an internet route look like? Well, you've got the network address in an IPv4 decimal dotted quad notation, and the destination to route to also in IPv4 decimal dotted quad notation. So:

Network address Destination

10.0.1.0/24 172.16.3.91

10.0.2.0/22 172.16.4.1

10.0.0.0/16 192.168.2.2

Let's call these three routes A, B, and C. Now, let's pretend that using route A is more expensive than using route C. Anyone can see in this (pretty bad) example, that route C is such a large network, that it encompasses both A and B — the network address ranges of A and B both fit in C. Therefore, route A and B can be eliminated and we can cheaply use route C.

To be able to do this programmatically, one must realize that IPv4 addresses are 4 bytes. The decimal dotted quad 10.0.1.0 translates to 4 bytes (hexidecimal notation): 0A 00 01 00, or the 32 bit word 0A000100.

I like writing this in hexadecimal because the network range '/24' translates to a bit mask; '/24' means the first 24 bits of the 32 bit word are 1s, giving a bit mask of FFFFFF00. Likewise, a /22 gives FFFFFC00 and /16 is FFFF0000.

Why is this important? Well, it shows how the internals of the internet work, and why it is so fast. For example, a source IP address of 10.0.1.18 is bitwise AND masked with its network address, and it will match route A in the routing table. The packet is consequently sent to the configured destination (in this case, 172.16.3.91).

Finding the cheapest route now only breaks down to this:

Find a route that has a smaller bitmask, but still matches the address
The route has to be cheaper in terms of cost, we don't like spending more money

We can see that route C fits these criteria for A and B:

10.0.1.0/24 => 0A000100 AND FFFFFF00

10.0.2.0/22 => 0A000200 AND FFFFFF00

10.0.0.0/16 => 0A000000 AND FFFF0000

0A000100 AND FFFF0000 == 0A000000, so route A fits in C

If we would have a route D like 10.10.0.0/16, it would not fit in C:

10.10.0.0/16 => 0A0A0000

0A0A0000 != 0A000000, so route D does not fit in C.

As you can see, routing is just simply bitmasking and using a lookup table (the "routing table"). If there is one thing that hardware can do fast, it's bitwise AND operations.

I came up with a funny statement that creates the bitmask from the slash-notation:

((1 SHIFTLEFT (32 - numbits)) - 1) XOR FFFFFFFF

This is overly complicated. It is possible to look at it in another way; e.g. with a /16 all the left-hand side bits are set, and all the right-hand side bits are clear. So it is possible to start with all bits set, and shift the clear bits in from right to left:

FFFFFFFF SHIFTLEFT (32 - numbits)

Be mindful that this works only for 32 bit registers, otherwise the mask will overflow. You can prevent this be explicitly selecting the least 32 bits:

(FFFFFFFF SHIFTLEFT (32 - numbits)) AND FFFFFFFF

We can do even better than this. There is a cool operation named arithmetic shift right which is ideal for the job, but it is not present in all programming languages. The arithmetic shift right copies the highest bit into the next bit, which is exactly what we want:

80000000 ARITHMETICSHIFTRIGHT (numbits - 1)

Just for the fun of it, I thought about implementing this in assembly language. There are many implementations possible, depending on what CPU you are programming. Just for the kick of it, I picked a 32 bits ARM processor. You have to be a bit clever with the bit operations, especially on this system.

@
@ first solution, using (-1 SHL (32 - numbits))
@
LDR R0, numbits
MOV R1, #32
SUB R1, R1, R0 @ R1 is (32 - numbits)
MVN R0, #0 @ R0 is FFFFFFFF
MOV R0, R0, LSL R1 @ R0 becomes the bitmask

@
@ second solution, using an arithmetic shift right
@
MOV R0, #1
MOV R0, R0, LSL #31 @ R0 has only highest bit set
LDR R1, numbits
SUB R1, R1, #1 @ R1 is (numbits - 1)
MOV R0, R0, ASR R1 @ R0 becomes the bitmask

Note that the routing theory holds true for IPv6 as well, except that for IPv6, you have to work with 64 bits addresses rather than with 32 bits addresses.

Parallel programming with pthreads

2008-10-21T20:40:00.005+02:00

Today, we had a little conversation about pthreads programming in the office. Every now and then the topic of pthreads seems to come up. Surprisingly, I'm one of very few who actually has had some hands-on experience with it. I remember that learning pthreads was difficult because there were no easy tutorials around, and I didn't really know where to start. There is a certain learning curve to it, especially when you don't really know what your doing or what it is you'd want to be doing with this pthread library.

A thread is a "light-weight process", and that doesn't really explain what it is, especially when they say that the Linux kernel's threads are just as "fat" as the processes are.

You should consider a thread a single (serialized) flow of instructions that is executed by the CPU. A process is a logical context in the operating system that says what memory is allocated for a running program, what files are open, and what threads are running on behalf of this process. Now, not only can the operating system run multiple processes simultaneously (1), a single process can also be multi-threaded.

The cool thing about this multi-threadedness is that the threads within a process share the same memory, as the memory is allocated to the process that the threads belong to. Having shared memory between threads means that you can have a global variable and access and manipulate that variable from multiple threads simultaneously. Or, for example, you can allocate an array and have multiple threads operate on segments of the array.

Programming with pthreads can be hard. The pthread library is a fairly low-level library, and it usually requires some technical insight to be able to use it effectively. After having used pthreads for a while, you are likely to sense an urge to write wrapper-functions to make the API somewhat more high-level.

While there are some synchronization primitives like mutexes and condition variables available in the library, it is really up to the programmer to take proper advantage of these — as is often the case with powerful low-level APIs, the API itself doesn't do anything for you; it is you who has to make it all work.

Programming pthreads is often also hard for another reason; the library enables you to write programs that preempt themselves all the time, drawing you into a trap of writing operating system-like code. This kind of parallelism in code is incredibly hard to follow, and therefore also incredibly hard to debug and develop. The programmer, or developer, if you will, should definitely put some effort into making a decent design beforehand, preferably including a schematic of the communication flow that should occur between the threads. The easiest parallel programs do not communicate at all; they simply divide the data to be processed among the threads, and take off.

It should be clear that the pthread library is powerful, and that the code's complexity is really all the programmer's fault.

While the shared memory ability of pthreads is powerful, it does have the drawback that when the programmer cocks up and a single thread generates a dreadful SIGSEGV, the whole process bombs (2).

Also, as already described above, pthreads has the tendency of luring you into a trap of creating parallelism that is not based on communication, creating overly complex code flows.

The automatic shared memory has the drawback that you may not always want to share data among all threads, and that the code is not thread-safe unless you put mutex locks in crucial spots. It is entirely up to the programmer to correctly identify these spots and make sure that the routines are fully thread-safe.

It is for these reasons that communication libraries like MPI, PVM, and even fork()+socket based code are still immensely popular. The latest well-known example of a forking multi-threaded application is the Google Chrome browser, in which a forked-off "thread" may crash, but will not take the entire application down.

This blog entry has gotten too long to include some useful code examples. Therefore I will provide you with a useful link:

ptheads programming tutorial

Skip right to the examples, unless of course you wish to learn some more on the theory of threads... Note how this tutorial covers all you need to know, and cleverly stays away from the more advanced features of the pthread library, that you are not likely to need to know anyway.

If the C programming language is not your thing, try using the Python threading module. Although not truly concurrent threads, Python's threading threads appear very similar in use and behavior to pthreads.

Another interesting topic related to parallel programming is that of deadlock and starvation, and the "dining philosophers" problem. See this online computer science class material for more.

Multiple processes or threads of execution can run concurrently on multi-processor or multi-core machines. On uniprocessor machines, they are scheduled one after another in a time-shared fashion.
There are (or have been, in the past?) implementations of UNIX in which it's unclear what thread receives the UNIX signal. I believe Linux sends it to the main thread, ie. the first thread that was started when the process was created. For this reason, it's wise to keep the main thread around during the lifetime of the process.

Why C++ is not my favorite programming language

2008-10-13T19:29:00.011+02:00

Eric S. Raymond, famous figure in the open source movement (1), wrote on his blog he was working on a paper with the colorful title "Why C++ Is Not Our Favorite Programming Language". The title alone struck a chord in me, having a general aversion of C++ for a long time now.

C++ is the object-oriented dialect of the C programming language, and was originally meant to be a "better C". C++ offers full "object-orientation", as it boasts classes, inheritance, templates, exceptions, operator overloading, references, constructors, destructors, accessors, virtual member functions, templates, and more. All of this is then mangled by the compiler and eventually a binary comes out, just like you would compile and link regular C codes.

I have personally written quite a lot of C++ code, but my latest C++ code dates back to the late 1990s. The reason: I was completely fed up with programming in C++ (and Java, that other object-oriented language), and switched back to plain C.

The C programming language is simple, and therefore very straightforward. C translates back to assembly language and machine code relatively easily, and because of this, if you know how a computer works, you will know how to write in C.

This is entirely not the case with object-oriented languages — object-oriented languages are on a higher level of abstraction and take the low-levelness away from the programmer. While this seems nice when you are working on a high level of abstraction, it makes things annoyingly difficult for the programmer who likes/wants/needs to understand what is really going on at a lower level.

Technically, this is a non-issue because in C++ the developer decides what objects look like, and when there is a need to do so, you can take a debugger and trace into those classes to see what is going on. In reality, C++ is making things harder rather than simplifying them.

Back in the day, C++ code always produced a binary that performed less well than a compiled and linked plain C code. The reason? The C++ program is calling constructor and destructor functions all the time, often consuming cpu for no real reason. Moreover, C++ has runtime type-checking that costs performance.

After more than a decade, compilers have advanced, and there are always codes for which the degraded performance is not important. Being also an assembly programmer (speed freak!), it annoyed the hell out of me to actually feel the C++ apps being sluggish on my old 80486 cpu.

For certain codes, like games, graphical user interfaces, or 3D modelers, it appears to be a good idea to use an object-oriented language, because you are already thinking in objects. Now replace that last word "objects" with "structures", and you've already taken the first step to implementing the same thing in plain, good old C.

While classes appear as useful "structures-on-steriods" (ie. regular C structs with member functions), their C counterparts (ie. structs with functions that operate on the structs) are easier to comprehend only because of the use of pointers. While pointers are usually hard to comprehend by a novice, they are a must-have for the experienced programmer.

While C++ does not hide pointers, the preferred way handling objects is by reference. A reference is like a hidden pointer that only confuses the journeyman programmer. In machine language, there is no such thing as a reference, there are only pointers.

I can already hear the crowd say the old saying "pointers are the root of all evil", but in reality, "bugs are the root of all evil". The pointer is a very powerful asset than can prevent unnecessary copying of data.

As a master in C, I've actually managed to write object-oriented-like codes in plain C. This is not surprising, because C allows you to create anything you like, even weird programs like compilers and operating system kernels. In fact, the first C++ compilers spit out mangled C code rather than object code.

They say C++ is good for teaching object-oriented programming. This was only true until Java arrived. I have experience with Java, and it's awful, but I guess it can be used to teach object-oriented programming.

What strikes me as odd, is that C++ was not ready at the time when I learned it. I actually have C++ code that does not compile today without making some necessary changes, while it was all correct when I wrote it. This actually also holds true for very old C codes (2), but I've never encountered this kind of issue for my own C codes. (Anyway, C does evolve because there is also C99 and the like. However, C99 is fully backwards compatible with older Cs).

Later, templates were added and while this black magic was presented as the Next Big Thing, it never did anything useful for me. Templates are best used for implementing lists and stacks into classes, although it appears better to me to have a list of structs with pointers point to the object data (3).

Implementing good C++ classes is hard because they are supposed to be generic, abstract implementations. Often, there comes a time when the class will turn against you and needs redesigning — leading to a major overhaul of the complete code. Proper design should prevent this, but in practice, implementating code is different from designing code and there will be frequent times when you curse at C++ for putting this on your head.

Even if a clever C++ supporter manages to undermine every statement I have made against C++ in this blog entry, I will still have the final word: I just don't like the C++ syntax.

Honestly, tell me which code fragment looks nicer:

std::cout << "Hello, world!\n"; // in C++

printf("Hello, world!\n"); /* in C */

In the C++ code fragment above, intuition would tell you that the direction brackets point in the wrong direction (!) Also, no one seems to know how to pronounce "cout" (4).

The "cout" function is actually being called without having instantiated an object of the "std" class, making this a very questionable example of "object-oriented" programming.

In fact, "cout" is not a function; it is more like the "stdout" global variable in standard C. The output is being produced via an overloaded operator function, for the shift-left operator. Funky? Yes. Fancy? Yes. But as to why a shift-left operator would have to print text, totally eludes me. The fact that printf() is a library function that, in the end, enters the write() system call, that I can understand.

My favorite object-oriented language is Python. But then again, I don't use its object-oriented capabilities much. The best things about python are its comprehensive syntax, and its brilliant memory management (to the developer, there appears to be none because all objects are reference counted and garbage collected). This costs performance, so for the more cpu-intensive stuff, I use C.

Either way, I prefer a procedural language over a weird, code obfuscating, mind bending object-bloated language that attempts to mask the natural program flow, any time.

Eric S. Raymond is the author of various well-known open source programs, and he is the author of the essay The Cathedral and the Bazaar.
The Lion's Book lists an ancient UNIX kernel source code that contains old C statements that are no longer valid today.
Actually, my old, now famous, bbs100 code uses a dirty (but clever and efficient) typecast trick to turn structs into linkable or stackable items.
No one seems to know how to pronounce "Stroustrup", either.

Fullscreen GL ...

2008-08-31T12:56:00.005+02:00

Programming games is fun. Games typically run in fullscreen mode, so in today's world, it's important to have a portable way of setting a full screen mode. It looks like this is more of a hassle than you'd think it is.

I'm fond of SDL because it's quite a powerful library. There is a SDL_WM_ToggleFullScreen function that lets you switch between full screen and windowed mode. I noticed however, that on the Mac, the full screen mode of SDL would actually resize the application window to maximum size rather than take up the whole screen. The problem is that the Apple menu bar remains visible on the top of the screen, and also the dock would still pop up when you move the mouse to the bottom of the screen.
In Windows, I found that it helps to resize the window to the maximum resolution before trying to toggle to full screen.
The man page of SDL_WM_ToggleFullscreen does say that toggling to full screen is not supported on all platforms.
To my astonishment, there is a rather simple fix for this, but first I'd like to tell you about the little adventure I had with GLUT.

Because of the full screen problem I had with SDL, I decided to switch to GLUT and try that out. GLUT is real easy to use, because it feels much more high-level than SDL and you quickly get results with little effort. GLUT features a so called 'GameMode' in which it switches to a full screen mode. While this seems to work across platforms, I'm having an incredibly pesky issue in that the screen is no longer being updated — all animations and movement appear frozen although the display function is being called. It's like glutSwapBuffers is not swapping buffers anymore or so?
Switch back to windowed mode, and everything works perfectly again. It's not the obvious beginners mistake of not re-initializing GL ... I don't know what it is, and I spent way too much time on trying to get this to work. Searching the web also doesn't turn up much information, other than people saying that GLUT is bugged and you should use SDL.
What's also really odd, is that GLUT allowed me to set a 10000x3000 video mode on my 1440x900 monitor. SDL doesn't let you do weird things like that.

Exit GLUT, it's nice for trying out a quick scene, but for anything larger, I'm through with it.
Getting back to SDL, it turns out to be amazingly simple to enter full screen mode. Forget about SDL_WM_ToggleFullScreen, as it's useless. Use SetVideoMode instead:

SetVideoMode(max_xres, max_yres, bpp, SDL_OPENGL | SDL_FULLSCREEN);

The maximum resolution can be obtained by using SDL_ListModes. You should always use this, as a good program knows what video modes are supported and what modes are not.
You can switch back to windowed mode by omitting the SDL_FULLSCREEN flag, and mind to set the window size back to it's original size.
The beauty of all of this is that it appears to be portable, too. As to why anyone ever thought up a broken SDL_WM_ToggleFullScreen function, we'll probably never know.

Doomed to code

2008-08-26T18:00:00.008+02:00

I read an interesting interview with John Carmack, lead programmer at id Software, famous (1) for creating the game DOOM. In the interview, he talked a little about his game engines with the cool sounding code names "Tech 4", "Tech 5", "Tech 6", etc. To my surprise, there were some very negative comments to this article, people complaining that Carmack is not doing anything innovative at all, as he is recreating the same old game over and again. He is obsessed with his engine and not creating fun games any more.

This made me realize that Carmack is, above all, a programmer, and he is making his code evolve. This is what technical programmers do and what they live for.
In the early 1990s he had a lot of success with his DOOM project, and all he wants is to impress people with a better, faster, cleaner, leaner, more technologically advanced version. Likewise, in the early 1990s, I had a lot of success (although never as much :-) by doing a lot of programming on a BBS (2) and I developed several iterations of this BBS. You wouldn't believe the amount of time spent thinking up new ways of doing the internals and tinkering with the code.
Not only is programming addictive, so is having success. Trying to recreate that past success can be a great driving force. Deep inside of me there may always be the wish to create a new implementation of the BBS. John Carmack has this dream too, and he's earning a living with it.

To my surprise, Carmack is not merely striving for visual perfection. He has recognized that today's popular gaming console (read: the XBox 360) contains 2 year old hardware and therefore needs simpler graphics (like, for instance, tricked shadows rather than compute intensive real shadowing effects) to get more performance.
Kiddies that are complaining that Carmack is only talking about performance, simply don't get it. The performance of the rendering engine is a very important aspect of a game.
The "60 Hz versus 30 Hz" debate is hyped, but not entirely unimportant; having a 60 Hz engine sounds more technologically advanced, however, it sounds to me that a 30 Hz engine would have tons more time per cycle left for doing other things, like AI. Good AI is what makes games fun to play.

One last thing he mentioned that raised my interest was what Carmack said about mega-textures, a technique developed by him that makes it possible to define the world in one giant unique texture, rather than to build the world from repeating textures.
The interesting thing is that he said "it is only two pages of code"; he is now talking casually about what was presented a year ago as his big new thing. Now that he's been working with it for many months, it's not that special to him any more. This behavior is typical for programmers (I do it all the time).
Funnily enough, a lot of cool code snippets are only one or two pages.
It is also a jab at other game developers; the mega-texture technique is apparently not that hard to implement and other knuckleheads should have been able to find out how by now, too.

John Carmack is still a hero in my book, even if id Software's games are not as shockingly groundbreaking as the original DOOM. It's not like the guy gathered fame for no reason at all, (Paris Hilton comes to mind ...) and as long as he keeps revealing technical details about the inner workings of his engines, he's got my attention.

As for the complaining kids out there ... it's just like what I always told the users of the BBS: anyone who dares complain should go and write their own. And one day, I even followed my own advice.

Carmack is like a celebrity, lately doing more interviews than a movie star, and spending more time writing keynote presentations than writing code.
BBS: Some kind of (now ancient) online service featuring a message board with forums, and interactive chat.

Optimizing an OpenGL star map

2008-05-31T19:25:00.008+02:00

It's time for some fun stuff, and write about programming. A while back, I was working on a way cool 3D OpenGL space thing. It had lots of stars, the orbits of all major planets (and their moons!) and you could fly around through this 3D space. The only drawback was that I'm still relatively new to 3D programming and it was *hard* to get things right. So, after a break of a couple of months, I took some of the data and turned it into a 2D star map.

Graphics programming is fun, but even in 2D it is not always easy. As always when programming, there are many ways to accomplish what you want, but you should try and find the most optimal way. Even with great NVIDIA hardware in your machine, your program will be slow if you don't optimize.

The reason I have to optimize the star map code, is because it features over 300,000 background stars. The stars are plotted as GL_POINTs. The magnitude or brightness of the star is also taken into account.

Another reason is that it features some planets. I like drawing planets with many polygons so they don't look blocky. Having many polygons makes it go slow. Any modern 3D game has a high polygon count, so how do they do that?

Optimizing the stars

Today's hardware can output a staggering amount of pixels per second, but dealing with 300K+ stars was just too much for my poor old 6800 GT. (One of the bad things of speedy hardware is, no one tries to write good code any more). Of course, it is amazingly stupid to draw 300,000 stars when you can only see a couple of hundred in the viewport at once. One of the most annoying things of OpenGL is that it has this cool viewport that doesn't seem to do anything for you; it doesn't cull, it doesn't scissor, this is all left to the programmer as an exercise. The reason for this is that OpenGL is not a magical tool and will not do anything right unless you get it right. There are many ways to determine what is visible and what is not, and it greatly depends on what kind of program you are making and how your data is laid out. In fact, the layout of the data greatly determines whether the program will be fast as lightning, or slow as a donkey.

For the star map code, I decided to chop the entire space up into sectors. A sector is like a square on a map with longitude and latitude lines. Only a few sectors will be visible at any given time, so only a limited number of stars have to be drawn. The chopping-up of the star data file was done by writing a small python script. Running the script on this large input took a while, but remember that when you are preprocessing, you have all the time in the world. When you are rendering frames in realtime, that's when you don't have that luxury. Data partitioning is a very fundamental way of making programs act fast on huge amounts of data. Google does it with their data, too.

In full screen, it still draws a considerable amount of stars. This results in a large amount of calls to OpenGL functions, and the sheer number of function calls is what is making the program slow down at this point. Luckily, there is a way to make it better. You can point OpenGL to an array of vertex data and tell it to render the entire array in one go.

Something like this:

glEnableClientState(GL_VERTEX_ARRAY);
glEnableClientState(GL_COLOR_ARRAY);

/* point to 2D coordinates */
glVertexPointer(2, GL_FLOAT, 0, sector->star_coordinates);

/* each star has RGB colors */
glVertexPointer(3, GL_FLOAT, 0, sector->colors);

glDrawArrays(GL_POINTS, 0, count);

Do this for every visible sector, and it's blazing fast.

In my code, I still have to manipulate the vertices (star coordinates) because you can scroll the screen. However, I think it is also possible to keep the data completely static and have OpenGL look at it from a different position (moving the camera). This may seem like an odd approach for a 2D code, but it is "the OpenGL way".

Optimizing the planets

For drawing planets I take the easy way and use a quadrics object, a glusphere. A quadric is really a 3D object, so it's odd to use it in a 2D program, but on the other hand it looks kind of cool too. I don't know what OpenGL does, but what I learned is, it is common practice to compile the quadric into a display list.

From the top of my head:

display_sphere = glGenLists(1);
glNewList(display_sphere, GL_COMPILE);
gluSphere(sphere_quadric, radius, slices, slices);
glEndList();

Now draw the sphere:

glCallList(display_sphere);

The display list now has a compiled-in radius. Unfortunately, not all planets are the same size. Therefore, the sphere has to be scaled to match the size of the planet. This is not without consequences. When you scale objects in OpenGL, so will their normals. The normal vectors are used by OpenGL to compute the correct lighting on the object. Planets without shade don't look nice, so after scaling, the normals of every vertex (of the many sided sphere) have to be recomputed.

Now, because this planet is not going to change shape, it makes no sense to compute this object over and again for every frame. You can compute it once at program startup and keep a separate copy for every planet. This takes up more memory, but it will be fast.

In this blog entry I've given a couple of examples of how to optimize OpenGL programs. One problem that you will encounter is that optimizing sometimes means turning the code upside-down and inside-out. Optimizing performance can involve making major design changes. It is wise to draw things out on paper, and keep a couple of good copies of your code when trying new approaches.

Hard experiences with Ubuntu Hardy

2008-05-25T21:43:00.010+02:00

I already wrote about the buggy installation procedure of Ubuntu Hardy Heron. After a few weeks of using Ubuntu Hardy, I am near to throwing it off my system (!) It is simply frustrating, I seem to hit a bug every time I try to use it. The whole release is just a hodge-podge of "latest greatest" releases of software. There is no stability factor involved, the whole thing just feels like a "testing" release. I used Ubuntu Feisty and Gutsy and in fact, I was happy with Gutsy. Maybe I should reinstall Gutsy, argh.

As said, every day I find another bug in Hardy. I have a talent for finding bugs in bad software, as I was software tester in another lifetime. So, I decided to lend the Ubuntu project a helping hand and submit my bug reports to https://bugs.launchpad.net/ubuntu.

I hit bugs dating back to as far as 2005 that were closed as invalid because the support guy said he need to have more information. I quickly found three other instances of "I need more information", while the bug report was perfectly well described and clear to me.

From the top of my head:

dvorak keyboard setting is not being remembered. This little bug is three years and was closed due to insufficient information. Lots of googling led me to the astonishing solution: GNOME gets its keyboard settings from Xorg. It doesn't matter what you configure (or try to configure) in the System|Preferences|Keyboard menu. The setting is really tucked away in /etc/X11/xorg.conf. Use sudo vi to change.
Firefox 3 is beta, and it shows. Random crashes all over the web. Reporting the bugs won't help you, they are closed as invalid because they can not be reproduced. Yet everybody is experiencing these random crashes.
can't add bookmark in nautilus (the GNOME file manager). It turned out that at the time, my disk was full. Nautilus didn't report the error. Ubuntu support calls this a "user error", because my disk shouldn't be full. Hmm, Linux for human beings...??
The hardware testing application shows text that is too long to fit in the dialog, so you can not read the text. This is absurd. Who tested this?
The IT8212 chip in JBOD mode is not supported. You must build your own kernel and include the right module. A quick check in launchpad shows that this is a long-standing issue with remarks in the ticket like "invalid, need more info, have you tried this with a raid box?" etc. No! I'm glad I solved this issue by myself. I feel sorry for the poor dude who didn't know to build his own kernel.
The "Open With" function in nautilus is weird. It shows applications in the list that are no longer installed on the system. How do you open a file with an application that is no longer installed? (Actually, I had a total of four problems with this dialog box).
The menu editor, alacarte, doesn't edit the System menu. Or in fact, it does, but it doesn't show this to the user, as it doesn't update the screen properly. Another "invalid" bug from the dark ages of Breezy (now in the dark ages of Hardy).
Rhythmbox can't handle my music collection. I have a lot of mp3's, but come on! At startup it grinds and grinds and grinds... until I get fed up with it and kill it with -9. Die, die, you bad imitation of iTunes. (Note: iTunes is not a very good music player, either. But at least it plays music).

The music player is really a story by itself. My fav music player for all time, XMMS, has been obsoleted and pulled from the distro. The player exhibited major problems (stu-stu-stutter) after a change in the Linux scheduler, and the developer went totally nuts over it, flaming around that the whole world had gone insane except for himself. Consequently, XMMS was pulled from just about any distro you can think of.

There is an XMMS2, that I tried, but ... it sucks! As a matter of fact, there are a lot of music players for Linux, and they are all kinda sucky in one way or another. Wait, wait a minute. For the moment, I'm happy with mpd and Sonata. It's kind of weird design to have a daemon and a frontend for playing music, but it's a fun little player and at least Sonata won't grind my disk to pieces when it starts. Too bad the volume control in Sonata doesn't work under GNOME, but my guess is it'll be "invalid" and "need more information" if I report this bug.

Time to take a deep sigh and conclude this blog entry. The Hardy experience has not been a fun one so far. While the system is usable if you spend your days in a Terminal window, it clearly shows deficiencies when you are actually trying to use it. The support guys are not being helpful. Granted, the OS is free and without warranty, but then don't pretend to be a good OS. Ubuntu is not for human beings. Period. The Hardy release was done just to get an Ubuntu release out the door, not to deliver a good product. It's like the Vista of open source. The more tired I get of Ubuntu, the more I love MacOS. On the other hand, Linux paniced on me a lot less often.

Ah well, maybe I should try ArchLinux. Or maybe that distro also includes crappy GNOME, Firefox beta and more untested software. I long back to the days of debian and a simple fvwm2 desktop, maybe I'll try that.

Dvorak keyboard in SDL

2008-05-07T20:41:00.010+02:00

A while back I wrote a blog entry about the dvorak keyboard on my laptop. Funnily enough, it won't work for SDL programs. SDL is the Simple Directmedia Layer library that allows for portable game development. I'm a huge fan of the SDL because it is simple, and it is very powerful too. I've made some pretty cool stuff using SDL, that I could not have made otherwise. Unfortunately, the SDL does not behave in a portable way when it comes to alternative keyboard layouts.

My personal experience:

In Linux, it works. I have a GNOME2 desktop with dvorak keyboard layout configured, and SDL programs get the correct keypresses.
In Windows XP, it does not work. SDL programs behave as if the keyboard was a qwerty keyboard.
In MacOS X, it does not work. It behaves like a qwerty keyboard.

Google turns up this solution, which does not work — at least not on the Mac, where I tested it:

In your initialization:

SDL_EnableUNICODE(1);

and then when you get a keyboard event: (From 'man SDL_keysym')

if(!(event.key.keysym.unicode & 0xff80))
  ascii = event.key.keysym.unicode;
else
  <deal with international characters>;

This method actually *works*, even with weird keyboard layouts like my custom swedish Dvorak variant. :-)

Let me repeat that this does not work, no matter what he says.

I wrote a conversion routine that maps the SDLKey keysyms from qwerty to dvorak, but this is really no solution. SDL should be made to use the platform-specific keyboard routines so that it correctly uses the configured keyboard layout.

I submitted this as a bug in bugzilla.libsdl.org, now let's see whether I got it all wrong or if someone is going to fix it.

Apple Airport Express: It just does not work

2008-05-05T21:14:00.007+02:00

As you might know, I too fell for Apple's sleek looking hardware and its apparent easy-to-use software. The company from California that is being run by the no-nonsense genius Steve Jobs has a good reputation (well, at least for the last couple of years, ever since the ipods and Mac OS X) of delivering high quality products. Sadly, the Airport Express is a major letdown. I would go as far as to say that Apple is selling a broken product and is lying to their customers about it.

The Airport Express is a wireless networking device, which you can hook up to your home stereo to play your favorite music using iTunes. Apple's website and on the packaging of the Airport Express it is promised that you can use it in your existing wireless network. This is a downright lie, unless your entire network consists of Apple products only. That's right, the Airport Express will not play nicely with wireless equipment from other manufacturers. Oddly, this thing is getting rave reviews all over the web. Yes, it would be a great product ... if it would only just work.

The manual says setup is easy, just run the admin utility and the light on the Airport Express will turn green. Not true. One caveat is that you have to allow the MAC address of the device in your wireless router. It will get its IP address over DHCP and I got the light happy and green, but iTunes would not play "airtunes".

Eventually I hooked up an ethernet cable (direct link to my macbook!) and got it to play music, but it would not work wireless. After hours and hours of fiddling and resetting the Airport Express one more time, I decided to search the web some more.

What I found were some very disturbing messages on mailing lists, even on the Apple forums:

One guy wrote: "The Airport Express is a useless white brick with an amber light".
Another guy wrote, apparently frustrated: "What the frak is going on?!".
On amazon.com someone wrote: "Do not buy this product".

The article I am linking to ("Nothing but Problems: It just does not work!") is dated, but it also shows that it did not work in 2004 and it still does not work in 2008.

Some weblog writes that you can write some unsupported firmware into your Linksys router and make a bridged setup with the Airport Express. I sure am glad I did not try doing this ...

I returned the Airport Express the next day and got my money back. Sadly, I still can not play music from my macbook on my home stereo without plugging in a long audio cable.

Anyway, do not waste your time, do not buy this product!

Hardy Heron: Quite Hard

2008-04-26T11:50:00.007+02:00

The latest buzz in Linux land is the new stable (or Long Term Support) release of Ubuntu, also known as "Hardy Heron" or plain "hardy". Upgrading should be a breeze, but it still cost me a few hours of sleep as it wasn't until 0:30 AM before I got the stupid thing to work. I am generally content with Ubuntu and I have seen systems where it just works, just never with mine. My main frustration is that the same issues were present 2 years ago, and haven't been fixed.

OK, Let's do a network upgrade; open the software update manager and it shows a new distribution release is available. Click "Upgrade".

A dialog window opens and it shows it is going to upgrade the system. Click to continue. The window goes blank. Nothing happens. I wait. There are no progress bars, nothing. It just hangs there doing nothing. Eventually I xkill the blank window and kill its left behind siblings from a Terminal window. Any non-power user would give up at this moment. I remember this headache from the last upgrade, and decide to continue in console mode with "apt-get dist-upgrade".

The command-line method isn't all that bad, except that it runs into a dependency problem at one point. I use "dpkg -i --force-overwrite" for one package and "apt-get -f install" gets it going again.

The upgrade process retains most settings, but sadly, it resets my dvorak keyboard to qwerty and I can't type a single command anymore until I hook up an old qwerty keyboard that I have lying around. Now, how to set the console keymap to dvorak again? It was something with loadkeys or so.

To my surprise, X-Windows starts, but sadly only in 800x600. Again, to my surprise, a nice monitor config app pops up and I select my monitor brand and model (well, almost the right model. You know how they list 12 different models but never the exact one you own) and the 1440x900. The screen switches resolution and I click to accept this rez -- at which point it switches back 800x600 (!)
I zap Ctrl-Alt-Backspace out of X and restart it. GNOME does not come up. My custom wallpaper is there, that's nice. Nothing else works, not even Ctrl-Alt-Backspace. I hit the reset button on the PC and pray it will boot Linux at all.

It does boot and after wrestling my way out of gdm (I hate that thing, it keeps coming back when you try to exit it) I am back on the command-line to reconfigure X, but first I put an "exit 0" in /etc/init.d/gdm to shut it up.
I run "nvidia-xconfig" but afterwards, X does not start! No screens found. So, I move the backup xorg.conf.backup file back, and when I try it, X runs in a nice high resolution. Yippee!

My brief moment of joy is soon over. When I open a Terminal window, I can't type a single command. WTF?! I play with the keyboard typematic rate settings, but it doesn't help. Oddly, there is a an option in some tab in the keyboard config utility that makes your keyclicks respond dead slow. For some strange reason, this option has been turned on. (I wonder what the use of this option is, why would anyone deliberately want to break the keyboard like that?!) Uncheck the option, and I can TYPE again praise the Lord!!

I like using a VGA font in the Terminal window. Oddly, the font file is still present in the fonts directory, but the system isn't using it. I run "mkfontdir" and "xset fp rehash" and I got my favorite font back.

My MP3s are stored on a disk that is behind a IT8212 controller (not in raid mode) that Ubuntu does not include in the kernel. Consequently, I always have to build my own kernels only to include this one module that enables Linux to access my MP3s. It is annoying, especially because Ubuntu configures the kernel to include nearly everything (ever seen a desktop system with an InfiniBand adapter??) but not the module that I need.

Building the kernel takes a long time, but afterwards it does work. One thing that also works better now is sound; I suffered from stuttering sound every now and then and this appears to have been solved in newer kernels by the snd_rtctimer module.

So much for the upgrade process. What else is new in Hardy? I haven't seen much of it, but ... Firefox 3 is nice. It is beta, but they say it is fast and has a smaller memory footprint than Firefox 2. I was happy to see that Flash works right out of the box.
I was less happy to see that the bookmark sidebar has gotten more ugly.
Speaking of ugly, I have album art icons on my MP3 folders in nautilus. This used to look quite nice, but it doesn't look as good anymore. You can tune it a bit in the Preferences, but somehow it just looks worse.

Anyway, overall I'm very happy with Ubuntu. I just wanted to show that it is not always as easy to work with as they say. Remember, Ubuntu is Linux for human beings. And I am only human, after all.

OpenPGP smartcard

2008-03-05T21:21:00.010+01:00

Due to my recent work in the field of security, I am now the proud owner of a socalled OpenPGP smartcard. The card looks like a regular credit card and has a chip on it. The card can be ordered from a German company called g10 and they will send it to you by (snail) mail. The card does not come pre-programmed; you need to get a "supported" smartcard reader (and writerrrr!!) in order to be able to load your personal GnuPG key onto it. (Why the card is named "OpenPGP" while it uses GnuPG, I've yet to find out).
Information on what smartcard readers/writers are "supported" and how to (supposedly) do it is described here.

Now, the bad news is that Linux totally sucks simply because the kernel development is going way too rapidly and third party applications/devices can't keep up. On top of that, the Linux documentation is outdated in some places, making it even harder to get things working. The information on gnupg.org is confusing, because some brand/type of smartcard reader needs to be configured differently than others.

Some hints on getting it working:

get the SCM Microsystems device; it is the only one that does not require pcscd and is therefore a little bit less complicated to set up.
Install the needed libraries. On Ubuntu, "apt-get install opensc" will get the packages. It will recommend the pcscd daemon, but you don't need it if you have the SCM Microsystems device. For other kinds of devices, you will probably need the daemon (read below for more info).
When GnuPG can not access the card reader, it will output a message about the pcscd not running. Ignore this misleading error message if you have the SCM Microsystems device, and instead check with strace what USB path it is trying to open.
use lsusb to get the device ID and put this in /etc/udev/rules.d/50-gnupg-ccid
the udev script gnupg-ccid provided by gnupg.org does not work. The script gets called with environment variable DEVICE set to something like /proc/usb/001/001, but this path mystically disappears after the script exits. The real device is /dev/usb/001/001, but this character device does not yet exist at the time that the script is being run by udev, so it cannot set the group permissions (No such file or directory).
By the way, it helps greatly to use "logger" to debug the udev script.
Don't bother with hotplug or usbdevfs unless you are running an ancient Linux kernel for some obscure reason. Reading the hotplug documentation will only confuse you, so skip these parts if you don't need it.

If you are lucky, you will get it working after some time. If you are unlucky enough to have an older device or something other than the SCM reader (no, they are not paying me to promote it) you will have to install the pcscd daemon. This daemon is actually an interface between gpg and the device driver. You will have to download (and often, compile from source) the driver from the website of the manufacturer of the smartcard reader. Don't be surprised if you run out of luck at this point; as said, Linux tends to change quickly and third-party drivers tend to lag behind, so don't be surprised if the driver for kernel 2.6.5 doesn't build against your 2.6.24 setup.

Another important point is "To use PC/SC make sure you disable CCID by passing the --disable-ccid option to GnuPG".

If you don't succeed, cry, and bang your head against the wall.
If you do succeed, there is of course the sweet taste of victory!

Honestly, I've only partly succeeded in getting the card to work yet. There is much work to be done and there isn't enough time in a day. To do:

try to get it working on my Mac
there must be a way around the permission problem with the udev script
use gpg-agent with this thing
try to get the OmniKey reader to work with PC/SC (drivers for 2.6.stone_age, but maybe there are more recent versions out there)

The card is way cool, but the main drawback is that you can't use it everywhere; the card always needs a reader to be present, and the reader always needs the software to be installed on the system. And especially that last part should not be underestimated.

Dvorak

2008-02-19T22:33:00.009+01:00

Being a geeky programmer, I've grown accustomed to typing dvorak. After 15 years of qwerty my wrists and fingers started to hurt badly (again) and after I saw a new colleague typing dvorak on his (strange, but definately cool) TypeMatrix keyboard, I decided to give dvorak a try. Of course, I couldn't type a single e-mail message in less than 15 minutes, so I gave up before my boss got angry. During the Christmas holidays I practiced dvorak using the online ABCD typing course, and I've since then fully switched to dvorak.

Rearranging the keys on a Macbook

The reason I came to write this blog entry is of course that I rearranged the keys on my Macbook to dvorak. You should be very careful when attempting to do this, as the keyboard is quite fragile. The best way to go about doing it, is to get a paperclip and put it under the top-left corner of the key. Be gentle! It will click, now slide down the left-hand side of the key and try popping the lower left corner of the key. Trying to rotate the key clockwise off (keep it flat down, but spin it around carefully) also helps. I realise now that I'm a left-hander, so keeping the Macbook upside down if you right-handed will help. The clips that hold the keycap in its place are on the left side of the key.

If the keycap won't give, don't force it. Take your time and take a deep breath every now and then.

You will find that in most cases, the keycap will come off cleanly. In some cases however, you might accidently rip off the inner tiny plastic layer mechanism-thingy as well. Do not despair. Hold the keycap between thumb and forefinger, and use the paperclip again to gently pry the piece out of the keycap. Now reinsert the inner piece again into the keyboard, and be sure to do it right (upside down won't work OK). Put the right side in first and shove it under the metal clip. Now use your fingers to put the tiny "hinges" into place. If your fingers are too big for this, try fiddling with the paperclip and/or a tiny screwdriver (the kind you use for your glasses).

Now reinsert the keycaps by gently pushing them into place. Make sure you get the layout right the first time! You don't want have to do the operation again.

On my Macbook, the tilde and the backslash are in a different place than expected, but this is because I have a Dutch keyboard. Click the image for a larger version.

All in all, I'm very happy with this layout, at least now I know where to find the letters!

Learning Dvorak

Dvorak can be learned in a couple of weeks if you practice a lot, but do not expect to type up to speed after only a few weeks. In my experience, it is like your brain remembers all the movements your fingers make for every word by itself. Especially in the beginning, your brain will know where to find the words and you will automatically mistype it. What I'm trying to point out is, studying the layout of the keyboard won't help you; the brain seems to remember words and not characters. For a long time, I had trouble typing words that I had not yet used after switching to dvorak. As a consequence, it is hard getting your original typing speed back.

Count on as many as six months to get up a reasonably fast speed, and don't be surprised if you're still not any faster than you used to be (often due to still making too many typo's to be blazing fast). This is one of the main reasons why critics say that dvorak isn't any better at all. I say they should give it a try; you will find that when typing text, you are using one hand more than the other using a qwerty layout. With dvorak, your hands are often alternating in a surprisingly evenly balanced manner. This is due to the fact that in natural language, words that are made up from series of alternating characters, and the dvorak layout uses this fact to its advantage. A slight disadvantage is that a programming language is not much like a natural language. If you are fluent in C, for example, it takes some getting accustomed to programming in C on a dvorak keyboard as well.

A word on portability

2008-02-16T13:15:00.009+01:00

When I first switched to Linux (it was 1993 or 1994 so, and the music was way better back then), I wrote a vi-like editor program for MS-DOS. With the help of a bunch of ifdefs, the thing would also compile and run under Linux. Some argued that this was pretty useless, because Linux already came with editors that were much more powerful than my poor clone. But the main reason I was so thrilled with it, was because the same code worked for both platforms (1). It was portable.

Linguists might say "of course", because the C programming language is portable. In practice, there are many tiny differences to be taken into account when programming cross-platform. On top of that, the differences between MS-DOS and Linux are huge (you can't argue with that).

The UNIX operating system is a wonderful piece of machinery and it runs on all kinds of hardware. All variants of the UNIX operating system look more or less the same, at least from a distance. When you start programming under UNIX you will learn the true meaning of the term "portability" (2).

Portability does not mean that your code will build on run everywhere by default. You will find out that UNIX A is not the same as UNIX B, and your Linux code may not run on BSD, AIX, Solaris, or whatever. It's the little differences that will make a big difference. Your code may misbehave, dump core, or not build at all.

To counter these problems there is POSIX compliancy for operating systems. POSIX is a set of rules that dictates what system calls are available in the operating system, and how they behave. POSIX is what makes cross-platform development possible today, although it is by no means a perfect world yet.

A great tool aiding portability is autoconf. You should clearly understand though, that autoconf is not a magic tool that makes your code portable; it is a tool that can help you rephrase your code so that it works cross-platform. As with many tools, you still have to do the majority of the work yourself (3).

Autoconf takes some time to learn, but it is worth the investment, if your project is large/important enough. It took me a week or two to make a good configure.in for my bbs100 project, but afterwards it built and ran correctly on every machine I could get my hands on -- that includes PC, Sun, IBM, SGI, and CRAY hardware. With little more effort, it was also ported to Apple Mac OS X.

Autoconf revolves around checking whether a function is available, and if it is, it #defines a HAVE_FUNCTION for you that you can use. A good configure.in script makes very specific checks on functionality that you actually need for your program to work. A lot of software packages come with some kind of default configure script that checks everything, which is totally useless if the code doesn't make use of it.

In general, a check for ifdef HAVE_FUNCTION is much better than operating system-specific checks like ifdef __linux__, or ifdef __IRIX__.

An ifdef BIG_ENDIAN works much better than checking every existing architecture with ifdef __ppc__, ifdef __mips__, etcetera. I happen to know a Linux code that completely broke because of this. Linux is probably the most ported operating system there is, but lots of people seem to believe it is a PC-only, RedHat-only thing (4).

Actually, the best-practice trick is to stay away from using autoconf's ifdefs as much as possible, and to stick with what works everywhere. Once you learn what works and what is funky, you are often able to get away with not having to use autoconf at all. A well-written program is not kept together with the duct tape that ifdef is. This is somewhat of a bold statement, especially since so many software packages run configure before build. But a truly valid question is, do they depend on autoconf that badly and is autoconf's functionality actually being used? It is a joy to see (some of) my Linux software build everywhere with a simple make.

The funny thing is, it is still hard to write truly portable code today. Last week I wrote some 2D SDL/OpenGL code on my Linux machine. When I moved it over to Mac OS X, I got a blank screen. I found up to three problems with the code:

Apparently there is a slight difference in the SDL library when it comes to blitting bitmaps that have an alpha channel. The man page mentions that the outcome may be unexpected (when you blit a pixel surface over an empty surface with an alpha channel the outcome is zero; hence the blank screen) but then why does it work alright under Linux? I resorted to writing a TGA image loader and staying away from SDL's blitting functions.
Resetting the polygon mode in conjunction with enabling/disabling texturing multiple times in one frame seems to confuse OpenGL on Mac OS. It messes up badly.
After resizing the screen, OpenGL has lost its state and texture data and must be reinitialized. This is actually in the OpenGL standard and a bug on my side. But it does raise the question why this never surfaced on my Linux box. Apparently the (NVidia) video card has enough memory and does not get into an undefined state after a screen resize.

Lessons learned: Test your code across multiple platforms, test, test, test..!

I have yet to see my favorite DOS editor(s) run under Linux natively. Switching platforms usually means leaving your familiar apps and tools, and replacing them with a substitute.
In fact, I have a feeling that the ifdef preprocessor was invented for the sake of portability. It has other uses, but it kinda smells of a "fix" for the problem of supporting different architectures.
Having a hammer does not make you a great carpenter.
Supporting all kinds of distributions is not easy either.

A brief history of time

2008-02-16T00:14:00.005+01:00

I've been programming for a fairly long time now. I didn't start out as young as some did, though. My first program was a school assignment, a birthday calendar written in Commodore BASIC. I used the computer in class, I didn't have one at home.

It must have been something like four years until I went to college, got a computer, and started programming. I got hooked on assembly code and spent whole days and nights writing code.

... and that was the beginning of a whole lot of bits and bytes ...

That was a really long time ago. At some point you think you know everything, but then you realize the world has changed since then, and people are blogging and stuff. Having never written any 3D code before, I found a new challenge in OpenGL. Now, this is certainly not the most important thing that's happened to me, but it is where I am at now. So, this is where the story ends, for tonight.