Saturday, May 31, 2008

Optimizing an OpenGL star map

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.

Sunday, May 25, 2008

Hard experiences with Ubuntu Hardy

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.

Wednesday, May 7, 2008

Dvorak keyboard in SDL

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.

Monday, May 5, 2008

Apple Airport Express: It just does not work

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!