(Simple) Flight Mechanics and quaternions

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:

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

Now, do this:

1. stand in the center of the room, and look straight up to the ceiling
2. 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:

1. FPS or racing game style movement;
2. Space sim like movement;
3. 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.

1. 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

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:

1. read about it, get sick over the syntax, and hate it
2. don't actually use it, and keep complaining about the syntax
3. let it rest for a while, sometimes for as long as a couple of months
4. read about it a little more
5. 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)

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:

• determine whether number is a power of two
• determine next power of two

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

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:

1. 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.
2. 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.