Understanding the gimbal lock

After reading the gimbal lock sections in several books and watching a few videos, what really made it clear to me was this explanation at gamedev.net by Atash:

think about having two sets of coordinate axis. One set can be considered 'local', as in local to the orientation of what you're rotating. The other set can be considered 'global', as in, the world's natural axis (just for a moment, think of it that way. The world is flat right now >_<)

Now, when you have those two sets of axis, imagine that they are standing up aligned, perfectly without an issue. If you take the local axis, and rotate it around 90 or -90 degrees around it's local y-axis, you'll find now that the x-axis is aligned perfectly with the z-axis. Now, the problem is now that if I continued to rotate the object by euler angles (rotating around the global axis) while the local x-axis are aligned with the z-axis, then when I rotate around the global z-axis, I am in fact rotating around the local x-axis, thus having no influence on which way the local x-axis is pointing! (remember that when you rotate around a certain axis, that axis doesn't move. The contra of that statement is true as well.) Okay, now we have a problem... One of our rotational axis has gone caput! Gimbal Lock has totally screwed us over.

It all makes sense now!

C++ std::min/std::max compilation issues

I just came across this issue today: http://support.microsoft.com/kb/143208

Basically, if you have code like this:

#include "windows.h"

...

int minimum = std::min(a,b);

it's going to blow up in your face.

Notice this at the bottom of that page: "This behavior is by design" . Seriously???

I solved the issue using extra parenthesis to prevent macro expansion thanks to stackoverflow:

int minimum = (std::min)(a,b);

And by the way... "windows.h" redefines lots of other stuff, beware! e.g. try to define the function DeleteFile and see what happens!

Good explanation of the Levenshtein distance: http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Dynamic/Edit/

And a good implementation: http://stevehanov.ca/blog/index.php?id=114

Very good generic game action framework software engineering discussion here:
http://www.gamedev.net/topic/624995-am-i-over-engineering-a-generalized-game-action-framework/page__view__findpost__p__4940963

Easy grammar parsing with CodeTalker

Looking at libgdx-cpp I wondered how they ported libgdx from Java to C++ so fast. The two languages have very similar syntax, but still, one would think it's still quite tedious to manually rewrite each class, thus there must be a way to translate the few differences into C++. Even if the translation is not perfect, at least it speeds up the whole process.

It seems that they were using CodeTalker. It certainly is parsing made easy, check this JSON parser!

Searching file names from a directory in a given file

At work, at some point I had to clean up old stuff so that we could use it as a base for the next project. I needed a script that would search the *.sprite filenames in a given .game file, which was just a simple file with references to those sprite filenames.

If I remember well, it executed fast enough (in about 100ms for our whole sprite folders). TODO note to self: explain the algorithm!

import sys
import re
import os  

class UsedSpritesLister:
    """ Class that contains util functions to find and list the sprites that are not used in a .game file """
    
    def __init__ (self):
        # members that need to be set for the processing to work
        self.input_sprite_path = ""
        self.input_gamelevels_path = ""
        self.ignoreDirSet = set(['.svn'])
        self.fileExtSet = set(['.level'])
        
        self.spriteNameSet = set()
        self.foundPatternsSet = set()
        self.notUsedSpritesNameSet = set()
        
        # caches the sets of whole words of the texts read from disk
        self.textSetCache = dict()
        
    def process (self):
        
        print 'Processing sprite names...'
        self.spriteNameSet = self.getSpriteNamesSet(self.input_sprite_path)
        
        if not self.spriteNameSet:
            print 'No sprites found, stopping.'
            return
        
        print 'Checking which sprite is not used...'
        self.foundPatternsSet = set()
        
        for spriteName in self.spriteNameSet:
            found = self.searchInDir(self.input_gamelevels_path, spriteName)
            if found:
                self.foundPatternsSet.add(spriteName)
        
        #print "found patterns: " , self.foundPatternsSet
        #print "sprite name set: " , self.spriteNameSet
        
        self.notUsedSpritesNameSet = self.spriteNameSet.difference(self.foundPatternsSet)
        
        #print "difference: " , self.notUsedSpritesNameSet
        
    
    def printResults (self):
        """ Prints the processing results. If nothing was processed, an empty set is printed """
        print 'Not used sprites: '
        
        for spriteName in self.notUsedSpritesNameSet: 
            print '--- ' , spriteName
    
    def getSpriteNamesSet (self, dir):
        """ Gets the names of the sprites in a given dir. Note that this function
            assumes that all names are UNIQUE, since a set is being used for storing the names
            
            Params:
                - dir: directory where to start looking for sprites
            
            Returns: set with the names of the sprites found
        """
        
        spritesSet = set()
        
        for (dirpath, dirnames, filenames) in os.walk(dir):
            for filename in filenames:
                if filename.endswith('.sprite'):
                    spriteName = os.path.splitext(filename)[0]
                    spritesSet.add(spriteName)
            
            for dirname in dirnames:
                # not ignored dir?
                if dirname in self.ignoreDirSet:
                    # remove it from the list so that we don't recurse there
                    dirnames.remove(dirname)
        
        return spritesSet
        
    
    def searchInDir (self, dir, pattern):
        """ Walks the given directory recursively searching for the given patterns in the files.
        
            Params:
                - dir: directory to search recursively
                - pattern: pattern to search in the files of the directory
            
            Returns: True if pattern is found, False otherwise.
        """
        
        # search the pattern in the files recursively. If found in a file,
        # the search will be stopped.
        for (dirpath, dirnames, filenames) in os.walk(dir):
            for filename in filenames:
                #only search in files with the given extensions
                file = os.path.join(dirpath, filename)
                ext = os.path.splitext(file)[1]
                if ext in self.fileExtSet:
                    found = self.searchInText(file, pattern)
                    if (found):
                        return True #found the pattern, so stop searching
            
            for dirname in dirnames:
                # not ignored dir?
                if dirname in self.ignoreDirSet:
                    # remove it from the list so that we don't recurse there
                    dirnames.remove(dirname)
        
        return False
                    
    def searchInText (self, file, pattern):
        """ Searches a pattern in the given file.
        
            Returns: True if found, False otherwise
        """
        
        # file loaded previously?
        if (file in self.textSetCache):
            gamefile_set = self.textSetCache[file]
        else:
            fileHandler = open(file, 'r')
                    
            gamefile_text = fileHandler.read()
            
            # find all whole words (CASE-INSENSITIVE) and create a set from them
            gamefile_set = set(re.findall(r"\b\w+\b", gamefile_text, re.IGNORECASE))
            
            # cache the set
            self.textSetCache[file] = gamefile_set
        
            fileHandler.close();
        
        # search for the given pattern
        found = pattern in gamefile_set;
        if (found):
            #print 'Found ' , pattern, ' in file: ' , file
            return True
        
        return False

def printUsage ():
    print ''
    print 'usage: %prog input_path game_levels_path'
    print ''
    print 'Lists the sprites from a given folder that are not used in the game levels in the given folder'
    print '  input_path           path to the input folder without quotation marks'
    print '  game_levels_path     path to the game levels folder without quotation marks'

if __name__ == '__main__':
        
    if len(sys.argv[1:]) != 2:
        print 'Invalid number of arguments'        
        printUsage()
        exit(2)
    
    input_sprite_path = sys.argv[1]
    input_gamelevels_path = sys.argv[2]
    
    if (not os.path.exists(input_sprite_path)):
        print 'ERROR: input folder <' , input_sprite_path , '> does not exist'
        printUsage()
        exit(2)
    
    if (not os.path.exists(input_gamelevels_path)):
        print 'ERROR: game folder <' , input_gamelevels_path , '> does not exist'
        printUsage()
        exit(2)
    
    spriteLister = UsedSpritesLister()
    spriteLister.input_sprite_path = input_sprite_path
    spriteLister.input_gamelevels_path = input_gamelevels_path
    
    print 'Input dir: ' , input_sprite_path
    print 'Game levels dir: ', input_gamelevels_path
    print 'Processing...'
    
    spriteLister.process()
    spriteLister.printResults()
    
    print 'Finished'
        

Vertex arrays vs VBOs

Just came across this post at StackExchange. Particularly interesting is the third link referenced from the accepted answer, which is a presentation from a GDC.

Syntax highlighting

Looks like I finally have syntax highlighting... thanks to this!
Turns out the previous link worked only for Java and XML and I'm too lazy to compile my own version for supporting other languages, so I'm now resorting to google-code-prettify. To make it work here, I followed this tutorial.
I didn't quite like the default style as I wanted line numbers for every single line. Also, I didn't want it to have a completely white background, so after linking the default CSS file, I overrode some styles:

<style type="text/css">
pre.prettyprint, code.prettyprint {
        background-color: #C4C4C4;
}
li.L0, li.L1, li.L2, li.L3, li.L4, li.L5, li.L6, li.L7, li.L8, li.L9
{
    background: #F7F7F7;
    list-style-type: decimal;
}
</style>

Java example:

public class SyntaxHighlighterWorksFineHere
{
    public static void main(String[] args)
    {
        System.out.println("Yes!");
    }
}

In order to avoid to having to place the script loading line each time, I just added it to the HTML template. Et voilà!

Installing gevent

If you're a Python noob like me, installing gevent is not trivial. In my case, I'm using Ubuntu 10.04. These are the steps to follow:

1. Install libevent package (apt or synaptic)
2. sudo easy_install greenlet
3. sudo easy_install gevent
4. ldconfig
5. test that 'import gevent' and 'from gevent import socket' work.

Step 4 was necessary in my case since step 5 wasn't working, but you may try to see if it does in your case.

Now, I was interested specifically in the datagram server. At the moment of writing this, the release version of gevent was 0.13.6, which didn't include it, so I had to perform a check out of the latest version in the repository.

However, I didn't want to install it as I wanted to be able to switch between different versions or easily move a setup to another computer. Therefore, I wanted to manually build it into a given directory. For this, I had to do a few more undocumented steps:

1. sudo easy_install cython
2. (in gevent root folder) python setup.py build, which generates a build in build/lib.linux...
3. In my Eclipse project, link the build folder as an external library source.

Now, I wanted to be able to execute my project without eclipse... so I added a main file which set up the paths:

...

GEVENT_PATH = "../gevent/build/lib.linux-i686-2.6"

import os
import sys

# append paths to PYTHONPATH
sys.path.append(os.path.abspath(GEVENT_PATH))

# begin importing and using gevent!

...

And finally... that was it!

Installing Ack on Windows

Ack is a great command line grep alternative. In order to install it on Windows, follow the instructions here:

http://blog.thecybershadow.net/2010/09/12/color-grep-for-windows/

Vertex throughput on modern GPUs

I've read that the optimal number of triangles in order to maintain 60fps that the GPU can process is something between 1500 and 4000.

Found this interesting link:

http://nuclexframework.codeplex.com/wikipage?title=PrimitiveBatch&referringTitle=Nuclex.Graphics

But according to this presentation about nvidia http://origin-developer.nvidia.com/docs/IO/8230/BatchBatchBatch.pdf?q=docs/IO/8230/BatchBatchBatch.pdf, the question is not how many triangles per batch, but how many batches per frame!

Following that last link, the conclusions that can be drawn are:

- Number of vertexes per batch: whatever between 1 and 10.000.
- Number of batches per frame (CPU bound): 25k * GHz * Percentage_available_for_draw_calls/Framerate
- Bad performance at a small number of vertexes per batch could mean:
- GPU vertex engines are idle but the triangles itself could be expensive
- CPU bound --> add triangles for free!
- GPU idle: add complicate pixel shaders for free!