Saturday, October 25, 2014

Round Balls and Flat Disks

I used to call gluSphere() to render simple planets in 3D space programs. For reasons beyond me, this function has been deprecated. Apparently, all GLU functions have been scrapped in the newer OpenGL standard. I've been told by an expert that OpenGL maintains backward compatibility by using version numbering, meaning that you should still be able to use old OpenGL 2, as long as you don't try to mix it with OpenGL 4 functions. GLU and GLUT are not really part of the OpenGL standard so that's where the story ends, I suppose. The problem is, I found myself being unable to compile older programs anymore after upgrading the operating system — totally unexpected, an unpleasant surprise. Searching for an answer, I found StackOverflow. The answer: “Do the math.”

I had to scratch my head a little there. I have to admit, it's been a while since I ‘did the math’ on anything, really. A visit to MathWorld turned up some nice formulas. Now, how to put that into code.

Implementing gluSphere()
As you can see in wireframe mode, the gluSphere is built up from quads. Clearly, triangle strips speed up the process. It should be possible to use a single triangle strip, but I didn't bother trying to figure that one out. So I went for stacked triangle strips that wrap around the sphere. This method uses slices and stacks (similar to lines of longitude and latitude) just like gluSphere() does.

Anyway, the math. We need to calculate all the vertices for the triangle strips that make up the sphere. A sphere is like rotating a vector 360 degrees around in a horizontal plane (left, right), while rotating a vector 180 degrees up and down in a vertical plane. We'll call the first angle alpha and the second beta. The size of the sphere is determined by radius r. Any point (x, y, z) on the sphere is given by:
    x = r ⋅ cos α ⋅ sin β
    y = r ⋅ cos β
    z = r ⋅ sin α ⋅ sin β
One caveat is that the angles should be given in radians rather than degrees for the C math library, so use M_PI. Another is the OpenGL coordinate system; you may have to work with -z, or like in my case, I had to exchange the Y and Z-axis to get the desired result.

Knowing this, calculating all vertices is easy. Setup a double loop that calculates all coordinates, taking into a account the number of stacks and slices that you wish to have.
    for(beta = 0.0; beta <= M_PI; beta += M_PI/num_stacks) {
        for(alpha = 0.0; alpha <= 2.0*M_PI; alpha += 2.0*M_PI/num_slices) {
            calculate x, y, z
            store in vertex array
        }
    }
Calculating Sphere Normals
The get good lighting on the sphere, we need to know the normal vectors. The normal at each vertex is given by normalize(x,y,z). That's easy.

Calculating Sphere Texture Coordinates
Having planets without texture is not fun. Texture coordinates run from 0.0 to 1.0.
    x = alpha / (2.0 * M_PI)
    y = (M_PI - beta) / M_PI

Implementing gluDisk()
For the rings of Saturn, it's easy to use a gluDisk. gluDisk() renders a flat disk, with an inner hole in the center. In math terms, the disk uses a circle formula, and there are two radii (one for the outer circle, one for the inner hole). So a gluDisk is really nothing but a single triangle strip that loops around, and its vertices are determined by two circles with radius r1 and r2.
The vertices are given by:
    // inner vertex
    ax = r1 ⋅ cos α
    ay = r1 ⋅ sin α
    az = 0.0

    // outer vertex
    bx = r2 ⋅ cos α
    by = r2 ⋅ sin α
    bz = 0.0
Calculating Disk Normals
The disk is really a 2D object in 3D space. The normals point to +Z, they are all defined as (0, 0, 1).

Calculating Disk Texture Coordinates
Texturing a disk is not at all like texturing a sphere. When you put a texture on a gluDisk, it's like sticking a label onto a DVD. You can take a rectangular image and put it onto the circular disk without distorting the image or wrapping it around the object. The texture is mapped to the bounding rectangle of the disk, which is two times the outer radius.
    x = ax / (2.0 * r2) + 0.5
    y = ay / (2.0 * r2) + 0.5
Do the same for bx and by. Note the plus one half, you want to be in the center of the texel or else OpenGL may show artifacts.

Implementing gluCylinder()
I did not implement gluCylinder(), but with the information given for gluDisk() you should be able to pull it off. It's just two circles and an added Z-axis.

Roundup
So, that's it. A bit of simple math, but still a sizable amount of work to get spheres going again in OpenGL. It's something that any serious 3D programmer should be able to do, but I still feel a bit bummed that they just deprecated those really useful functions.

On a final note I'd like to mention that there is another way of creating spheres, one that presumably looks better. Imagine an icosahedron, and subdividing each face into more triangles to enhance resolution. You can subdivide as many times as you like, and at a certain point it will be a good approximation of a sphere. This method is described in the Red Book.

Monday, September 22, 2014

How To strcpy()

I've written a lot about strcpy() already, the tiny but famous C library function for copying strings. There is a lot to say about its (in)security, and ways to improve on that. I didn't realize before that implementing your own strcpy() function could be part of a job interview for a programmer position. If I were asked to rewrite strcpy(), I would at least put in an abort() (for lack of exceptions) when passing in a NULL pointer. Moreover, I would add a length parameter for doing bounds checking — albeit that might be considered cheating, because it would change the function declaration; the signature of the function.

Rather than zooming in on this rather old topic, I'm going to be lazy for once and just link to this excellent post that tells the story of the solutions given by job applicants for the problem of writing your own strcpy() function. It's a must read, hilarious, but also somewhat alerting.

How Do I Copy Thee? Let Me Count the Ways by David Avraamides

Sunday, August 3, 2014

A Bugs Life

Software bugs are everywhere. This shouldn't be so bad, except that software is everywhere — from your office computer, to your cell phone, home router, television set, car engine, and the list goes on and on. Heck, even an electric toothbrush has a tiny microcontroller programmed with firmware in it. Most of this software has been tested and tried, but bugs keep popping up nevertheless.
Last week I kept a bug diary. The dreadful results are described below.

Saturday, July 26 - FaceTime would not connect. After updating iOS the problem was resolved. Of course, “you must always update to the latest version”, but mind you, this problem never existed before. User experience: Everything was working fine, and then all of a sudden it didn't.

Sunday, July 27 - Tried the OS X Yosemite Beta. Okay, it's a beta release. Reported a bug where the GUI was actually messing up the screen. Sadly couldn't take a screenshot, because it would redraw the screen, effectively clearing things up. Luckily, the bug did reproduce every time.

Monday, July 28 - Didn't go near my computer, but today a colleague sent in a bug report for a piece of software of mine. My bad. One of those cases of “this should never happen”. A set of dictionary keys holds only unique items, so how could it be that an item appeared twice?

Tuesday, July 29 - Encountered trouble trying to build the PCRE regular expression library with gcc 4.9.1 on Linux. Somehow it wouldn't pass confidence tests. Reportedly did work with older gcc; smelled an awful lot like a compiler problem.
Found a recent online tirade by Linus Torvalds, in which he called gcc, I quote, “pure and utter *shit*.” Turns out the compiler's code generator emits buggy code.

Wednesday, July 30 - The pedestrian lights near the office stayed on “Walk” all day long. Nearly got run over by a BMW, as the driver hit the gas when he got the green light. Could have been caused by a loose wire somewhere, but I like to think it was a software bug.

Thursday, July 31 - Twitter app on iPhone kept crashing upon loading a particular news article. Who knows, maybe it was ad malware trying to infect the system.

Friday, August 1 - At last, a small victory. Fixed an endless loop problem in the RADIUS PAM module. Found some additional related issues, such as by the looks of it is a broken stupid unusual implementation of our RADIUS server.


Special bonus bug of the week (Linux): Exiting an interactive bash shell and getting “Illegal instruction” on the screen. This is most likely caused by stack corruption.

Sunday, July 6, 2014

Game On

I have a PS3 game controller lying around, so I got the idea to add support for it to an old SDL game code. This code was still using SDL 1.2, which is now a thing of the past. So the first thing to do was quickly porting it over to SDL 2, a more modern game programming API. It even includes a GameController API, and because of that, programming support for game controllers with SDL is remarkably easy.

Initialising initialisation
For initialisation, call SDL_Init() with extra flag SDL_INIT_GAMECONTROLLER. Additionally, you must open the game controller. The game controller is found by first querying the system for the number of connected joysticks.
    SDL_GameController *ctrl = NULL;

    SDL_Init(SDL_INIT_VIDEO|SDL_INIT_GAMECONTROLLER);

    int num = SDL_NumJoysticks();
    if (num <= 0) {
        printf("no joy connected\n");
        return false;
    }
    if (!SDL_IsGameController(0)) {
        printf("it's not a game controller\n");
        return false;
    }
    ctrl = SDL_GameControllerOpen(ctrl);
    if (ctrl == NULL) {
        printf("open failed: %s\n", SDL_GetError());
        return false;
    }
    name = SDL_GameControllerName(ctrl);
    printf("game controller: %s\n", name);
This code is just an example. It assumes the first connected joystick is indeed the game controller that the player wants to use. This is of course ridiculous, and you should really loop over all joysticks and open as many connected devices as possible.

Mapping the mappings
In them old days, supporting game controllers was ... problematic. The thing is, every game controller is different and there is no common standard among manufacturers for numbering buttons and analog sticks. Even a simple D-pad is different between different controllers — think XBox360, PS3, PS4, but even PS2, Logitech, OUYA game controller? SDL 2 solves this incompatibility by mapping the raw device button ids to generic SDL enums. You do need to provide the correct mappings, these can be imported from a flat-file game controller database.
    SDL_GameControllerAddMappingsFromFile("gamecontrollerdb.txt");

    if (SDL_GameControllerMapping(ctrl) == NULL) {
        printf("no mapping for %s\n", name);
        SDL_GameControllerClose(ctrl);
        ctrl = NULL;
        return false;
    }
Finally, enable events so that SDL will generate events for us to collect in the main event loop.
    SDL_GameControllerEventState(SDL_ENABLE);

Moving forward
When SDL game controller events are enabled, you will receive events of type SDL_CONTROLLERAXISMOTION in the event loop. You will find that SDL sends lots of these events, even when just holding the controller. This is just noise on the sensor, and the analog sticks are quite sensitive. Merely touching already registers movement. The ‘axis values’ are a signed 16-bit value, between -32768 and 32767. The SDL documentation says values between -3200 and 3200 are in the ‘dead zone’ where the sticks should be considered at rest.

The SDL_CONTROLLERAXISMOTION event boils down to this:
event.caxis.which     connected joystick number
event.caxis.axis      axis number
event.caxis.value     amount of movement

Click image to enlarge

Analog triggers L2 and R2 register as axis 4 and 5, but they only report value 32767 when pressed, acting like digital buttons. This could be a driver issue (I'm on a Mac) or SDL not properly supporting the triggers. I'm not sure.

Benjamin Buttons
SDL generates SDL_CONTROLLERBUTTONDOWN and SDL_CONTROLLERBUTTONUP events. Inspect event.cbutton.button to see which button was pressed.
The button codes are hard to find in the documentation, but look in SDL_gamecontroller.h to find the enums. The API is modeled after an XBox type controller, for PlayStation the button ‘A’ is a cross, button ‘Y’ is a triangle, etcetera. The ‘guide’ button is the PS logo button.
SDL_CONTROLLER_BUTTON_INVALID = -1
SDL_CONTROLLER_BUTTON_A
SDL_CONTROLLER_BUTTON_B
SDL_CONTROLLER_BUTTON_X
SDL_CONTROLLER_BUTTON_Y
SDL_CONTROLLER_BUTTON_BACK
SDL_CONTROLLER_BUTTON_GUIDE
SDL_CONTROLLER_BUTTON_START
SDL_CONTROLLER_BUTTON_LEFTSTICK
SDL_CONTROLLER_BUTTON_RIGHTSTICK
SDL_CONTROLLER_BUTTON_LEFTSHOULDER
SDL_CONTROLLER_BUTTON_RIGHTSHOULDER
SDL_CONTROLLER_BUTTON_DPAD_UP
SDL_CONTROLLER_BUTTON_DPAD_DOWN
SDL_CONTROLLER_BUTTON_DPAD_LEFT
SDL_CONTROLLER_BUTTON_DPAD_RIGHT

Any other business
I have a single player game so programmatically, I took the easy road and just map all buttons and stick movement to key presses, internally translating to a keyboard joystick. This works, but it's not good enough for multiplayer games. It also loses the ability to properly react to stick acceleration; you might want to scale the axis values to have a proper difference between large and small stick movement.

Some tutorials suggest you ignore the ‘dead zone’, but this is wrong because when you fully ignore those events, you are unable to detect when someone suddenly lets go of the joystick. Instead, the dead zone should be mapped to zero movement. You can also keep track of sticks entering/leaving the dead zone, and react correspondingly.

The DualShock 3 controller has pressure sensitive buttons. SDL has no support for measuring the amount of pressure. Nor does it support the sixaxis motion sensor. SDL 2 can do rumble however via its Haptic API.

The cool thing about SDL is that it also ports to other platforms, maybe most notably the Steam OS. Since I'm on OS X I also had a quick look at how to do this joystick & game controller thing in pure Cocoa — not so easy at all. I'm with SDL 2 on this one.

Links
SDL 2 GameControllerDB file
SDL 2 API by Category
How to connect a PS3 controller