mgr's weblog

Networking

Completely new is the networking mode: My good friend Moritz has kindly written a 377 line long server in Python that will listen for UDP packets in a trivial protocol from the Cube Modeller. The modeller has three new buttons: "Go Online", "Go Offline", and "Upload Animation". If you press "Go Online" the program sends every frame to the server and they will be displayed right away on the real cube; even while you are making a new animation.

The default server is cube.entropia.de, a computer located in the rooms of our computer club and to which the cube is usually connected. So if you press "Go Online" on your computer (and the network between both computers works) we can see what you do in your modeller on the real, physical LED Cube in our computer club at the same time! (Sorry, you can't do this as well unless you are at ours, as there's no webcam.)

If you have made a nice animation just press "Upload Animation" and it will be transferred to our server and sometimes being played for some minutes. The application will ask for a title and your name first. (Be aware that McCLIM's dialogs act a tad strange: You have to confirm your input to every text box by hitting the enter or return key before clicking on OK.)

Beautified appearance

Well, you see the screenshot above; compare it with an old one. You can still switch to the old display by selecting "Day mode" in the toolbox window. You might find it more easy to create a new animation in that mode. But isn't the new "Night mode" much more nice? The LEDs are now transparent spheres that actually emit a bit of red light, with specular and ambient light in red, not grey, and a diffuse color that goes towards more red and less transparency for brighter LEDs, not towards less grey while always being opaque.

And there is a cute, little coordinate system that rotates around its own axes with its own lighting.

Transparency in OpenGL

Making objects transparent in OpenGL isn't just changing the alpha value. No, sadly, I got to know that you have to do much more than that: Apart from enabling blending and selecting a blending function you have to sort your objects from back to front and display them in that order. Not completely trivial when your GUI allows to rotate the world at will. Stupid OpenGL. I solved this problem together with Moritz by implementing a very simplified version of the binary space partitioning algorithm (also called the painters algorithm) that works because of the simplicity and regularity of our scene. Have a look at the file viewer-draw-leds.lisp.

We then needed the eye (or camera) coordinates for our BSP implementation, so, sadly again, we had to apply the two rotations (that were originally performed by two simple calls to GL:ROTATE-F) to the eye coordinates by ourselves by means of two rotation matrices.

But with those two changes the spheres were finally transparent. Yay!

New mouse picking algorithm

I switched form the proprietary graphic driver from ATI to the more stable free Radeon driver of X.org X 7.0. At first I was very happy that the free driver finally supported hardware acceleration for 3D operations, but my enthusiasm has been damped by the fact that it does (or at least did) not support the GL_SELECT render mode, ergo I had to reimplement mouse picking without using the selection buffer. At least the new method is not only different but also better in my opinion:

Luckily I stumbled upon the brilliant idea of using GL:READ-PIXELS asking for the depth component in the Z-Buffer. This z value together with the converted x and y coordinates of the mouse pointer will be thrown into GLU:UN-PROJECT: E voilà!, you'll get modelview coordinates within your OpenGL scene. Once more because of the simplicity in the way I draw the spheres I can quite easily convert these values to get the one sphere, or LED, that has been picked. If you're curious have a look at the function GET-NUMBER-OF-PICKED-LED in the file viewer.lisp.

User Effects

Effects, formerly called "transformations", are little programs that modify a single frame or the whole animation. There is a bunch of already built-in effects. They add a fade or shadow effect to your animation, mirror or duplicate the animation or append a mirrored copy, they let you insert text, or, a tad more complex, there is an effect that generates the matrix effect of dropping letters (just bright LEDs in this case) with a shadow.

You can write your own effects as Common Lisp code and load those so called "User Effects" into the running Cube Modeller via the "Load User Effects" button. The messages that Lisp emits when loading User Effects will appear in a new window.

There is a very simple example effect in the file cube-modeller/data/user-effects.lisp; this file will be loaded on start-up of the modeller (there will be no window for the messages in this case, errors will be ignored). The built-in effects can be found in the file cube-transformations.lisp. The latter file is also included in the binary release as cube-modeller/data/built-in-effects.lisp, but you don't have to load it as the effects are already, well, built-in. It is only included so that you have easy access to more source code of effects you can copy from when writing your own impressive and handy effects. (Don't forget to share them! ;-) )

Major speed-up

OpenGL Display Lists

Display Lists are the main reason for the speed-up. Much like subroutines, procedures or functions of most programming languages they allow to group a couple of OpenGL commands and give them a name. More than that, as they are immutable, they can be precomputed and perhaps even stored in the graphic card's memory if you're lucky. Less than ordinary procedures they are static that is they are uneffected by any variable: When you define a Display List the current values of the variables are stored and not references to the variables themselves. You could say that a Display List only stores the effect of the given OpenGL commands, not the commands themselves. This also gives a hint how those lists can accelerate your application: The effect of the commands can be optimized (e.g. by combining several rotations), precompiled, or caused by a completely different means than executing the original command sequence. (More on Display lists here, here, or there.)

In my application, instead of drawing the LEDs each time as freshly computed spheres (via GLU:SPHERE) after calculating and setting their material (again each time), I now create 12 Display Lists (6 for the intensity levels 0 to 5 in the "Night mode", and another 6 for the "Day mode") when starting the viewer and in order to draw an LED the corresponding Display List is called after moving to the correct position. (Of course, the lists will be destroyed when exiting the viewer.)

Lisp profilers

In addition to the OpenGL-level optimizations other, traditional optimizations have been applied as well, after having searched for bottlenecks in the modeller with SBCL's statistical and its accurate profiler.

The speed-up in numbers

With that the modeller was able to be draw, undelayed, ~76 frames per second an my computer, instead of the previous ~27 frames per second. On a machine of a friend this value has been beyond 1200 frames per second; on another machine that frame rate was even achieved without direct rendering, i.e. without 3D hardware acceleration! Though, this is not quite fair as in the undelayed mode the toolbox window becomes really unresponsive as there is no time left for it. With a little delay of 1µs that will in fact account for a delay of probably 4ms (if your kernel is configured with CONFIG_HZ_250=y, as 250Hz equals 1 divided by 4ms) the toolbox window is still usable, but the frame rate is limited to 250fps (displaying a frame will at least take the 4ms of the delay). Well, that's always guaranteed to be enough. On my machine it's 50fps with the delay, and that's also enough. Why would one need faster display than 50fps, you ask? As you'll see in the next section higher frame rates make the animation playing more exact. By the way, if you want to know the frame rate of the modeller on your machine, start it with cube-modeller/cube-modeller.sh --print-fps.

Separation of frame display and animation progression

The problem

Why does one want this? Well, in earlier versions of the modeller I had a simple delay after a frame has been displayed, and the application would only display each frame of the animation one single time. I set a delay of 80ms between the frames, with earlier versions of the modeller this resulted in a frame rate of probably about 8 or 9 frames per second. Well, it seemed to work nicely. But than someone in Vienna asked: "Why does it jerk when I rotate it? Isn't it accelerated by the hardware?" And that's the problem: As long as you don't touch the viewer everything is okay, but when you rotate the virtual cube you want more than 9fps otherwise it will look choppy.

To change that I've made the application faster and reduced the delay to 1µs (see above), fixing the jerking, but it also introduces a new problem: A mean frame duration of about 20ms is just to short for practically every animation, and it will even be shorter on faster machines.

The solution

The solution is to separate frame display and animation progression. To achive that I took the idea from Glenn Fiedler's article Fix Your Timestep!, that's about separating the calculation of "physics steps" and the display frame rate of a simulation. I adapted the idea for my application and improved it for my purpose.

The idea is quite simple: Let's say there is a loop (in my case the idle section of the SDL event loop of the viewer) in which the current frame is over and over displayed. Now you do not just progress to the next frame of the animation in each loop but you measure the time from one cycle of the loop to the next one and add it to an accumulator. Once the accumulator reaches (or passes(!)) a certain value (80ms in my case) it switches to the next animation frame.

Fiedler's version substracts that value from the accumulator and calculates "physics steps" until the accumulator gets below that value, and that's the correct behaviour for a physics simulation. But in my case that would mean to drop frames of the animation and I do not want that to happen, therefore I set the accumulator to zero in case the value, the desired frame duration, has been reached (or passed).

That's all.

In my application the idle loop calls ANIMATION-STEP, and that function only goes to the next frame if (the animation is running and) enough time has elapsed (that is *frame-duration* seconds). The latter is determined by ENOUGH-TIME-ELAPSED-FOR-NEXT-FRAME-P, which returns TRUE only if enough time (*frame-duration*) has elapsed since its last invocation (the previous cycle of the idle loop). This is in the file play-animation.lisp

(Okay, I lied a bit: This could be it. But there's always room for improvements, and so I have also improved this first implementation after some measuring. Alas, I bet you are already tired and so I've decided to better make a different article from the already written text on that topic.)

Some minor but still noteworthy improvements

The binary

I've added quite a couple of command line options that you'll see when starting the modeller with cube-modeller/cube-modeller.sh --help. So far the handling of these options has been improved a couple of times.

SBCL has quite a bit improved with regard to binary releases since the modeller's last edition: There is an :executable option to SAVE-LISP-AND-DIE that produces a single, executable file that contains the image, the SBCL executable, and SBCL's former two shared objects, both named alien.so. Also the path of the image file is available from within the image as the value of the variable sb-ext:*core-pathname* now, — no need for crude hacks anymore. Have a look at save-cube-lisp.lisp if you are interested in the code that produces the Cube Modeller binary.

Configuration of the serial port

I have added the function cfsetspeed to SBCL's contrib module sb-posix, and so the serial port can be configured from within the modeller; no need for stty that's being called from the start script anymore. (I've sent the patch to the mailing list of the SBCL developers.)

Configuration via the GUI

In addition to the command line options networking and serial device can be configured from within the application (if one really has to).