Wednesday, December 30, 2009

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.

Sunday, October 4, 2009

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:
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

Wednesday, September 23, 2009

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.

Monday, August 31, 2009

Implementing the end of the loop


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.