Rigid Body Motion

Last week I had to give a presentation about Rigid Body Motion (ie the basics of rigid body physics and some general mechanics).

Here are two versions of my presentation (one with less text and one with more):

Rigid Body Motion Presentation as PPTX; Rigid Body Motion Presentation as PDF
Rigid Body Motion Full Version as PPTM; Rigid Body Motion Full Version as PDF

If you are truly interested in learning about rigid body physics, here are some books/links:

Cheers, Andreas

PowerPoint LaTeX

Hey everybody :-)

I only wanted to point out that I've uploaded a new and improved version of PowerPoint LaTeX at http://code.google.com/p/powerpointtools/ - it now supports MiKTeX /

I've also finally added a project page for it to this blog. More updates might follow soon if I find enough spare time :-)


A quick note on quantifiers: For almost all and there exist infinitely many

It's been a while since my last post and now it's time for a mathematical post:

I'm currently preparing for a math exam (calculus) and I'm thinking it would be nice if there was a way to avoid much of the "for every \(\epsilon > 0\) there is an \(N \in \mathbb{N}\), so that for all \(n \ge N\) some property ... holds" stuff you find in textbooks. Some textbooks actually shorten it to "for every \(\epsilon > 0\) some property ... holds for almost all \(n\)".

However, I haven't found a quantifier to express this anywhere yet, so I'm proposing to introduce a new one:

\(\tilde{\forall} x \in M: P(x)\) should mean "for almost all \(x \in M\) \(P(x)\) holds", which suggests that there are only finitely many elements for which it does not hold.

One can formalize this as:

\[ \tilde{\forall} x \in M: P(x) \equiv \exists n \in \mathbb{N}: \left | \left \{ x \in M \mid \neg P(x) \right \} \right | \le n \]

Of course, a new existential quantifier is required then, too (for negation):

\(\tilde{\exists} x \in M: P(x)\) stands for "there exist infinitely many \(x \in M\), for which \(P(x)\) holds".

And this can be formalized as:

\[\tilde{\exists} x \in M: P(x) \equiv \forall n \in \mathbb{N}: \left | \left \{ x \in M \mid P(x) \right \} \right | > n \]

It's easy to see that \[\neg \left ( \tilde{\forall} x \in M: P(x) \right ) \equiv \tilde{\exists} x \in M: \neg P(x) \]

Thus one can use the two quantifiers just as one would use \(\forall\) and \(\exists\) usually. Note however than \(\forall\) and \(\tilde{\forall}\) don't interchange and neither do \(\exists\) and \(\tilde{\exists}\).

One last note: it might be worth using a different notation, for example: \(\exists ^ \infty\) might be easier to understand than \(\tilde{\exists}\), and \(\forall ^ \approx\) might be better than \(\tilde{\forall}\).

I'll try to formalize these quantifiers some more when I find some spare time.

Stay tuned for coding related updates soon :-)

Random Things

It's been a while since the last update. Here's a small update on what I'm thinking about various stuff.


Gameplay is okay I guess. Nothing I would spent too much time on though. It looks a lot worse than GTA 4 though (same as Crackdown).

Resident Evil

Seems to be lots of fun and some nice graphics, too.

Red Faction: Guerrilla

Some weird texture filtering issues and the presentation doesn't knock off my chair (terrain popping and other ugliness), but multiplayer is loads of fun with friends. Physics isn't completely stable though. I played the game for one hour in MP with friends and there were quite a few cases where geometry dropped through the floor with enough pressure from above (after destroying a building).


A bad and quite stupid movie (Ali G in Da House is probably the only movie I kinda like that stars Cohen). If you haven't watched it already, don't >_<

Shadow Complex

I bought shadow complex a few weeks ago and I have to say that it is an awesome game. I read somewhere that the developer used the Metroid series as inspiration and it shows. It's really fun to play and quite addictive. The graphics are pretty awesome (it is using the Unreal 3 engine) and the whole presentation is pretty polished. It certainly is worth its 1200 gamerpoints

Summing Formulas

A month ago I was doing some exercises in an analysis book (Königsberger) and found a nice/interesting problem:

Prove that if we denote of the sum of the numbers 1 to n to the p-th power by \[ S_n^p = 1^p + 2^p + ... + n^p \], then the following equation by Pascal holds: \[ (p+1) S_n^p + \binom{ p + 1 }{ 2 } S_n^{p-1} + \binom{ p + 1 }{ 3 } S_n^{p-2} + ... + S_n^0 = (n+1)^{p+1} - 1 \]

It can be used to get recursively/iteratively get formulas for sums of higher powers of numbers.

This is interesting because the proof doesn't need any advanced maths (like eg the Euler-MacLaurin formula, which can be used to show this, too).

You can download the proof and a few examples here.


Extracting Information from StudiVZ

Some time ago somebody stole 1 million data records from StudiVZ, the German Facebook clone. I'm not exactly sure why people call the person a hacker who stole data, because it appears he simply wrote a tool that harvested the publicly available data from StudiVZ (which everyone with an account can view).

People on StudiVZ share all their data by default---contrary to Facebook which values a person's private data a lot more. Thus by simply opening each profile from a dummy user and processing the HTML data from StudiVZ one can extract a lot and some more information from random people who probably don't even know about it or don't care.. so I'm not sure about the stealing part.

Apparently there are some captcha's when you start browsing searches beyond a few pages. I guess that is where the hacking part comes in, because getting around a captcha probably constitutes hacking---maybe?

Anyway I think part of the media coverage is a bit ridiculous because anyone can write a simple harvester in an hour or two. It took me one and half hours, so I think I'm on the safe side with this estimate and I didn't really have a clue about this stuff before either.

Since I don't want to "hack", I've only written a very tame harvester. It connects to your personal StudiVZ account, and retrieves the name and profile ID (and thus profile URL) of all your friends in the "Meine Freunde" pages.

It could do a lot more with that like retrieving everybody's birthday or random pictures, but I'm too lazy to code that because you use the same pattern for extracting data over and over again and it stops being interesting quite fast.

You can download the project here. It is a one file C# project. I'm releasing it under GPL (whatever).

It's really easy to explain how it works:

  • It uses System.Net's HttpWebRequest and HttpWebResponse to get (and post) web pages.
  • StudiVZ (like every other portal) uses cookies, so I create a CookieContainer and use it in every http request.
  • There are a few hidden values that StudiVZ expects during login. I'm retrieving them from the main page using custom built regular expressions. I've found a handy AJAX tester for .NET regular expressions. It was really useful for building the expressions and debugging them. (BTW you can find all URLs I used in the comments.)
  • After login I use the same pattern: get page & parse using regex for everything.
  • Visual Studio has an awesome "HTML Visualizer" for strings. It displays the content of a string as HTML page, which is really nifty if you're doing anything related to HTML processing.

The code is quite ugly. Well, it's not production code and this is only meant as a proof of concept.

Also note that I have at most violated the AGB of StudiVZ and not committed any criminal acts and I'm not planning to sell my friend's profile IDs or data either :-)

Maybe someone can extend the code and make it more useful. I guess it would be fun to automatically download all your pictures (including tags) and feed them into flickr or picasa... but someone else can do that.

Cheers, Andreas

My Bachelor Thesis

Screenshot of Utah
Screenshot of Utah

For the last two months I have been working on my bachelor thesis at the Chair of Computer Graphics and Visualization. It is about "Multi-Tile Terrain Rendering with OGL/Equalizer". The chair has a very nice Direct3D 10 terrain rendering engine and they want to run it at the newly founded KAUST (King Abdullah University of Science and Technology) in a massive CAVE environment. A CAVE is a room whose walls are actually screens. The CAVE at KAUST even supports stereoscopic rendering, so in total 12 screens that you need to render to.

My job was to port a terrain engine from Direct3D to OpenGL and afterwards to the Equalizer framework, which is an open-source framework for parallelizing OpenGL applications.

You can find/download an online version of my bachelor thesis here. I'll upload the LaTeX at a later date and update this post.

I've spent the last months writing about all this, so I don't feel like talking about the thesis itself anymore. Instead the remainder of this post will contain a post-mortem of it.



I think I did a good job at preparing myself for the thesis: I'm a LaTex noob, so I got 4 LaTeX books; and I'm a (paper-)writing noob, so I got 3 books about writing papers and writing good English.

The books have helped me a lot and it is always a good decision to get as many books as possible, because the more sources you have, the better. :)

I got pretty much all the LaTeX books from our university library:

  • [Einstieg in] LaTeX A big book (696 pages) but not particularly helpful. The reviewer on Amazon is pretty much right: it contains lots of information., but always stops short of providing the really useful details/information.
  • LaTeX - Ge-packt A small but thick pocket book (608 pages). I totally forgot I had it and it stood on my bookshelf until I found it yesterday. I've used it though while writing another paper last year, and it's pretty neat. It's a nifty reference, that's what it is.
  • LaTeX Hacks: Tipps und Techniken für professionellen Textsatz This book is very good. It contains 100 "LaTeX hacks" (on 416 pages). These are small, closed sections describing the solution to a specific problem you might encounter while using LaTeX. I've used the book a lot of times and it references many useful LaTeX packages, too---so it's a good start for searches.
  • Wissenschaftliche Arbeiten schreiben mit LATEX Get this book if you want to write your thesis with LaTeX. It's incredibly useful and covers most of what you'll need. It takes you on a journey through all features of LaTeX that you will use and describes the most common use cases. It even has a section describing how to fix common LaTeX errors like overflowed hboxes and others.

I've also bought some books about writing papers and the English language in general:

  • A Manual for Writers of Research Papers, Theses, and Dissertations, Seventh Edition: Chicago Style for Students and Researchers This book covers everything you need to know about the style and format of a thesis. It has a huge chapter about how to add citations and what format the bibligraphy should use, etc. In retrospect reading it was probably overkill, because a bachelor thesis apparently doesn't have very strict requirements (well, I'll see about that when I get my feedback..). It, however, contains a few nice chapters about editing your text and improving its readability, and the punctuation and spelling chapters are nice, too.

  • Oxford Guide to Effective Writing and Speaking I've only read this book in parts but it's not bad. It contains a useful introduction to English grammar, if you want to refresh that knowledge.

  • Oxford Guide to Plain English Get this book This book is simply awesome. Plain English refers to writing English in a simple and easily understood way. This book describes what makes a text 'plain'/easy to read and how to transform your texts to improve readability. It contains lots and lots of examples of complicated texts and shows how easy it is to improve them with few changes. The book itself is a very nice read and in parts even funny. The author clearly knows what he is teaching and it helped me a lot while writing my bachelor thesis.

Writing the Thesis

I had two months for the implementation of the project and for writing the thesis. The plan was to implement everything in August and write everything in September and be done at the beginning of October (before my birthday). So last week I ended up being in crunch mode working 15 hours on it every day :-|

The implementation went mostly as planned. I found a few driver bugs though, bought gDEBugger for debugging shader issues and found some bugs in it, too. I think I reported 5-7 bugs in gDEBugger's support forum in a matter of days and still have to write/extend a few reports.

I wrote my thesis in LaTeX and used the very good Texmaker as editor. It supports multiple file projects and allows you to select a main file (usually latex is called with the file that is currently being edited).

jEdit also supports LaTeX editing through a plugin: LaTeXTools. It isn't working as well as Texmaker though, but it generally has more text editing options and supports directory searches and regexp which is useful for a multi-file project.

I used subversion for version management, which proved useful at times, even though TortoiseSVN's difference viewer doesn't support line wrapping :(

For creating vector graphics, a very cool LaTeX package exists. It's called TikZ ("Tikz ist kein Zeichenprogramm"), and it allows you to create illustrations the LaTeX way: by coding them. See http://www.texample.net/tikz/examples/ for some neat looking examples.

I really wanted to use it to create my illustrations, but due to time constraints I couldn't read the whole manual (it's huge!) and even then it would have been too difficult. You see, it suffers from the same problem TeX and LaTeX suffer from in general. It's easy to write something that looks okay, but as soon as you want to tweak something to look exactly the way you imagine it and it is not a standard option, you end up reading weird package code and wishing you had a Phd in TeX editing.

TikZ has exactly the same problem. I understood the tutorials and the manual well enough, but I wanted to create class diagrams with it. I got lost quickly and the 500 page manual didn't offer a straight-forward way either.

In the end, I installed the latest version of Inkscape and created all my illustrations with it. Well, actually I always tried to create them with TikZ first, got frustrated after losing an hour or two, and spent another hour creating them in Inkscape.

While Inkscape makes it harder to change an illustration later on and there is no way to layout diagrams automatically, you can still become quite fast with it after learning a few hotkeys.

I wanted to use Eclipse and Omondo's UML plugin to create some diagrams of a Java subproject and it failed horribly..

Having to wait 20 minutes, while it hogs your computer at 100% CPU usage and 400 MB memory usage, to create a UML model of a 5 classes project is quite unacceptable!

Starting Eclipse later crashed it every time, too, by the way. I had to uninstall the damned plugin for Eclipse to start at all again.

In the end I recreated the classes in C++ and used Visual Studio's class diagram viewer to display the classes. You can then print the diagram to PDF and edit it some more in Inkscape, which supports importing single-page PDFs.

I hope I'll find time to write about game development related topics again in the next weeks. There are a few things I want to work on, but sadly university starts on Monday again and it will probably use up most of my time.


Sploidz Revisited (Unofficially)

I've already written about the semi-conductor project and how I've written some Flash animations/applications for it. Of course, I'm more interested in making fun stuff1, so I've decided to put my knowledge to good use and write a small game to see how difficult/awkward Flash actually is.

To sum it up, it is somewhat awkward, at least if you use the IDE itself. FlashDevelop still is as nice as ever, but you can quickly develop games nonetheless. I prefer Torque Game Builder though in retrospect.

Before I continue talking about the development itself, let's take a look at the actual game. Sploidz was the first game I wrote using Torque Game Builder for Joshua Dallman, and since I still had all the assets in my subversion repository, it was an easy decision to try and port this game. If you want to play it, you can download it for free here. I haven't ported everything: I've just rewritten the main characteristic features that make up Sploidz's code in ActionScript.

Without further ado, here is the game:

Click to open Sploidz in its own window

Because the art is still copyrighted and I haven't heard back from Joshua yet, I decided to create a free version that only uses "coder art" :-)

Mr. jRAD has said that this version looks cuter, decide for yourself:

Click to open SploidzCC in its own window

Below you'll find a description of the development and at least one helpful trick and most importantly a link to the source code of the "copyright-free" version.

Because the orginal version is way too difficult to be really fun, I actually sat down one more time and added code to make the platform slower if you're in danger of losing (up to 3 times slower):

Click to open SploidzMoreFun in its own window


I think I spent less than 20 hours on the project. It's hard to say because I worked on it on three different days, but only probably less than 6 hours on each.

The main problems during the development were:

  • How do I get the art assets into Flash?
  • How do I use the IDE and objects in a way that is helpful?

Lessons learned:

Even though the project isn't that big, it didn't take long for annoying bugs to appear - mainly in the matching code, because it's somewhat asynchronous and you have to make sure that an item doesn't get removed between events, etc. So again, I can only say that assertions and lots of debug messages are your friend and are really useful for understanding the sometimes mysterious ways of non-obvious code interaction.

Again one of the biggest headache was how to make the game a game and this resulted in implementing the platform game element from the original Sploidz game, although I wanted to avoid that in the beginning because of the added complexity. Roy pointed out though, that if you have 8 columns and only 5 different item types, the main idea of matching items becomes trivial. It's obvious, but I didn't think of it while coding the proof of concept code. Of course you have to somewhat tune the speed and animation durations of everything to make it playable. The game is really hard at the moment, but that's better than too easy and I especially added the "survival timer" in the upper right panel to allow for some competition and personal best times. I might change the platform code at some point to be more player-friendly, but I have more pressing projects to do at the moment: my Bachelor Thesis... /o.

As said above, I actually sat down and added a time scaler to the platform. The code is quite simple but helps the game a bit (I managed to survive 2 minutes and it was more challenging and less depressing to play the game ^ ^). The code is quite simple:

public function getPlatformTimeScale():Number {
    var maxRow:int = 0;
    for ( var column:int = 0 ; column < Grid.numColumns ; column++ ) {
        var firstEmptyRow:int = grid.getFirstEmptyCellRow( column );
        if ( firstEmptyRow > maxRow ) {
            maxRow = firstEmptyRow;

    const minScale:Number = 1.0;
    const maxScale:Number = 3.0;
    var scale:Number = minScale + (maxScale - minScale) * Math.pow( maxRow / (Grid.numRows - 1), 8 );
    trace( "Using platform scale: " + scale );
    return scale;

As you see, it uses a power function to make the platform slower only if really few empty rows are left.

Interesting things to know

  • If you want to important a sequence of images (say you have an animation stored as picture frames diamond_black00.png to diamond_black15.png, only select the first image when "importing to stage" in Flash, otherwise you won't get the dialog asking you whether you want to import an image sequence as animation.
  • If you have animations that stores multiple frames in one image, you'll have to split the images up into the respective frames. To do this in Photoshop make use of "guides" and slicing and notice the "Slices from Guides" button that is offered. It's really helpful. You can also store the creation of the guides and the slicing as action/macro and reuse it which also saves some time.
  • If you ever get the error "type was not defined or was not a compile-time constant", you might have a symbol instance that has the same name and class name. Flash freaks out for some reason and displays this weird error message.

For added fanciness, I've also included two older builds that show the evolution of the game code.

Note: There are bugs in these builds, so they are really just meant to show the progress on the first and second day.

Click to open Sploidz0810 in its own window

Click to open Sploidz0813 in its own window

Fun note: I implemented most of the fancy features (combo matches, the score bubbles, the platform) today in a few hours (a lot less than expected). I think ActionScript is an okay language, although it lacks quite a few comfort features of regular modern programming languages (eg function overloading or delegate types that actually check parameter type).

Last but not least here is the link to the code: FlashySploidz Source I release the code itself under GPL and the art under Common Creative.

Over and out, Andreas

  1. of course, the math stuff is also fun from a different point of view

More Book Reviews and re: Design Patterns

Pattern-Oriented Software Architecture - A System of Patterns (PoSA I)

I've finally finished Pattern-Oriented Software Architecture - A System of Patterns and I want to say a few words about it.

First I don't think, it's a must-buy. It's okay to read (but more about that in a minute) and certainly it can come in handy to look up patterns while developing, but if you have small budget, it's better to get it from a library.

The book can be roughly divided into 4 parts: architectural patterns, design patterns, idioms, "trivia".

The chapter about architectural patterns is the most interesting, where as the chapter about design patterns is okay, too, but also borrow or expands upon lots of concepts from the GoF book. The idioms chapter only contains one idiom (think small, language-specific "design pattern", e.g. reference counting in C++).

The "trivia" part contains information what pattern are, who came up with the idea, influences, the community, yada yada. The most interesting topic being the community and links in there.

The book itself is quite boring to read and the patterns are described in endless detail, which is good, if you want to look things up and avoid common mistakes. On the other hand this makes it a book, you should not read front to back, because it doesn't really make sense and you won't get a lot out of it either. (I actually read it front to back, and from that experience I draw my advice :-|) Just skim over the patterns, until you find something you don't know and then read the paragraphs that are interesting until you think you understand the pattern and then read some more to verify that you really understand it, but you can probably skip 40% (or more) of the text, if you just want to learn about new patterns and not go into all the details.

Next I'll try to write a few words about each pattern, so I (and maybe you, too) can look up the pattern here instead of in the book.

Note: I just found an awesome page, http://vico.org/pages/PatronsDisseny.html, that contains information about all patterns in the book, so it doesn't make sense for me to write about each and every one of them.

Architectural Patterns

  • Layers

To sum up 20 pages: it's good to use a multi-layered architecture in your software.

  • Pipes and Filters

This is something Pragmatic Programmer mentioned, too: Use and support the usage of your tools through pipes and filters. This is mainly something that is common on Unix, but it's incredibly useful and if you support some standard text I/O helps interoperability with little cost.

Finally an interesting pattern, it's also described in Pragmatic Programmer, but you can read the description here, too, because it's a quite interesting pattern.

This one is interesting and worth having heard of. It's similar to MVC above, but more general.

  • Microkernel

  • Reflection

Design Patterns

  • Whole-Part

  • Master-Slave Anyone who has ever done parallel programming with MPI has used this pattern extensively

  • Proxy

  • Command Processor A more elaborate version of the Command patten in the GoF book

  • View Handler The pattern describes how to design a document/view manager

  • Forwarder-Receiver

  • Client-Dispatcher-Server

  • Publisher-Subscriber


  • Counted Pointer

Now that I'm done with this, I want to share a few useful resources mentioned in the book:

Personally idioms are very interesting for me, too, because the day-to-day coding work is in a specific language and idioms are exactly about that.

A little googling already turns up lots of useful sources. For example:

There are a few more pattern books that I plan to read, so let's see how that turns out..

A Manual for Writers of Research Papers, Theses, and Dissertations

This is an awesome book, that explains a lot about how to write research papers and also about all the little details you should pay attention, too. It's a good read - I spent 1.5 hours a day for a bit more than a week to read through it - and I think it's going to be quite useful, when I start writing my Bachelor Thesis in a few days.

I'm currently writing some ANTLR grammar and StringTemplate stuff and I might write something about that, too, on the weekend.

I'm not sure I'm really happy with ANTLR, but it's probably the best thing out there at the moment, but I'm totally in love with StringTemplate, even though you might say it has some rough edges, too.

But more on that on another day.

Over and out,

PowerPointLaTeX Update

Because people complained to me about the formula feature in my PowerPointLaTeX add-in, which used a somewhat experimental approach to editing formula objects by adding an editing text shape that contained the formula code and that would be merged back into the formula as soon as you deselect it, I decided to rewrite it to use a standard modal dialog to edit formula objects:

Updated Ribbon (above) and Formula Editor Dialog (below)
Updated Ribbon (above) and Formula Editor Dialog (below)

The editor isn't perfect (yet), but it certainly shouldn't add any bugs to the add-in and solve some natural issues the old approach created.

Implementation Note

The idea was pretty straight-forward but the actual UI design was a PITA due me not knowning the panel/flow/table layout concepts very well and the code still has some annoying quirks with auto-scroll, so I need to fix that later.

I almost rewrote the whole cache system, because I'm using a background thread for updating the preview (if the text is changed, a 500 msec timer is started which triggers an update) and the update accesses the cache system, which in turn accesses PowerPoint to return some data, which in turn is busy because of the modal dialog -> dead-lock.

The solution to this is very simple but was not obvious to me at first (I actually began to rewrite the cache system with a feeling that there should be an easier solution): The background thread needs an Invoke call to update the preview picture because the control has been created by a different thread (the main thread) and the code to get an updated picture can simply be moved into Invoke delegate function.

This solved all my problems and made 4 hours of previous work and thinking about a new cache system obsolete :-|

Download the new build at: http://code.google.com/p/powerpointtools/downloads/list


Semi-Conductor Optimization (Uni Project)

I've written my last exam yesterday (except for two oral exams in September), so now I have got some spare time before I start working on my Bachelor Thesis tomorrow and I want to use it to wrap up a few things.

During this term I took part in a course that was both a (research) project/presentation/lecture thing, which was fun but also a lot of work. I've already written about one mathematical aspect of it in my post about Analysis, Cauchy-Schwarz and Reciprocal Sums.

The project was about optimizing semi-conductor wiring placement. We wrote a small paper about our findings and the work it was based one - you can look download it here.

We also created a self-running presentation that doesn't contain any Maths at all but makes heavy use of Flash animations (which were exported to .gif manually, which was a huge pain in the ass, which I will never do again if possible) to visualize all the concepts and algorithms.

You can download a PowerPoint 2007 (.pptx) version here or one that works with PowerPoint 2003 here.

For the Student's I sat down and wrote a small Flash application to show the algorithms at work. It's not obvious how it works, so let me explain the major points:

  • On the right you have a number of panels that you can enlarge by clicking on the small button in the upper right of each panel.
  • The upper three panels show different views of the same dataset. They will all be updated as you run the algorithm step by step.
  • The fourth panel lets you change the number of wires and/or their activity.
  • The last panel shows the electrical field that is created by one active wire in the center. It was created using MatLAB. I've also uploaded the script here.


Last but not least I've also uploaded the current version of all my .fla and .as files. You can download it here.

ActionScript is a nice language and you can quickly learn it using the available resources from Adobe. While ActionScript 2.0 is arguably weird, ActionScript 3.0 is quite logical and it's syntax is straight-forward and consistent, too. You can't say that about the IDE (Flash CS4), which is braindead, but if you're only interested in writing ActionScript code, FlashDevelop is an excellent and free alternative.

This is it for now, maybe I'll play around with Flash some more another time. Cheers,