Monday, April 13, 2009

Larrabee

I have to say, I bought into the hype that surrounded Larrabee. I thought it would be awesome. So, excuse my disappointment when they finally released the full Larrabee instruction set. See: Larrabee @ GDC (rasterization) and an article over at Dr. Dobbs Journal on Larrabee.

One of the first bits of production coding I did was optimizing rendering code for MMX/3dNow. It was a painful experience, the code I'd hand optimized took months to write, and by that time computers and compilers had gotten so much faster that it would have been easier just to buy a faster PC. I stopped all pretense of writing assembly code for any practical purpose around the time the eight version of the Intel C++ compiler came out. It did vectorization, and it did it,.. not-bad. (This translates to f$#in awesome for anyone who dealt with 'vectorizing compilers' before)

Having a look at Larrabee, it seems immediately clear to me that it's just another Itanium (The wonderchip that wasn't). The instruction set (gather/scatter is cool!) is far too complex for a compiler to do well at, so to get good performance you'll need to go down to the metal. And not even Carmack does that, he hires someone else to do it. I don't think there will be many people taking advantage of this technology. Nevertheless if Intel and Microsoft get together to write the DX software renderer in Larrabee assembly, we might end up with half decent low power intel GPU's in laptops. (One presumes Michael and Tom can do a decent job of that!) At least that would be nice.

Shared Libraries

Shared libraries, dynamic linked libraries, .so, .dll, .dylib, whatever you might call them seem to be a bit of a black art of programming. Especially when you mix C++ into the picture.

One key part of PAL is the self-registering plugin system. This allows extra functionality to be extended to the system on demand. It was very useful to allow the development of various simulation systems where fixes or alterations to the physics system can be loaded on demand.

It also greatly simplifies the whole process of creating/managing objects. The big catch is getting it to work in a portable cross platform manner.

The basics of the system is this:
Abstract factory which will have plug-ins self register via either a static constructor, or add themselves to a list of available constructors that can be retrieved via a shared object function call.

For staticly constructed objects, its not a big deal, just have a single static version of each object which registers itself with the factory. This works fine as long as those static variables are initialized. Unfortunately, the Microsoft compiler does not link those symbols from a static library, unless a function in the static library is explicitly called. So your options are to link all the objects to your program, or have a 'stub' in the static library, that you are forced to call to populate all the objects. PAL follows this latter approach. (Note, if you put that static stub into a separate header file, you can save yourself a lot of include header problems)

For dynamic libraries, well, it's not such a big deal for Windows. Under MSVC you just create a DLL project, and load the library with LoadLibrary and GetProcAddress. Ofcourse you need to remember to '__declspec(dllexport)' the functions you need to access, or write the def file (far too complicated). Then make sure the compiler exports the symbols.

MacOSX didn't pose great problems either, again, just use dlopen and dlsym. Remember to compile with '-dynamiclib'.

That brings my to GCC/Linux. This one was a bit tricky, and I could only solve this with the kind help of B. Watson over on #slackware. The problem with GCC is the way it handles run time type information. You need RTTI for dynamic_cast's etc, to work. This is relatively critical for design patterns such as abstract factories and virtual inheritance, which are heavily employed in PAL.

Under Linux to open a shared object, dlopen and dlsym will do, however you need to specify RTLD_GLOBAL, otherwise the type info will be stored locally and not globally. Now this normally doesn't cause a problem, but with GCC class types are compared by pointer references and not strings, so of course, with each object having its own local address space, the code just wont work!

That fixes one problem, the other is getting the symbols to export. By default GCC won't export all the symbols that you need. To force GCC to do this we need to pass through to the linker from the compiler the '-rdynamic' flag. But, alas, we are hampered again, we need to actually make sure the symbols are visible. GCC has introduce the ability to have private/local symbols, and if only one person specifies something to be private then the whole subsystem becomes private. No major dramas though, just specify '__attribute__ ((visibility("default")))' everywhere.

So now finally your ready to compile a linux shared object with position independent code:
-fPIC -shared -rdynamic
But it still doesn't work!

Yes, for some reason I don't know, you need to make sure your MAIN program is also compiled with the '-rdynamic' flag.

I guess the lesson for the end of the day was, '-rdynamic' is your friend.

Heres a useful snippet that summerizes all this:

REMEMBER: Export ALL symbols (shared or not!)
Linux: RTLD_GLOBAL & rdynamic!



#if defined (OS_WINDOWS) || defined(WIN32)
# define DYNLIB_HANDLE hInstance
# define DYNLIB_LOAD( a ) LoadLibrary( a )
# define DYNLIB_GETSYM( a, b ) GetProcAddress( a, b )
# define DYNLIB_UNLOAD( a ) !FreeLibrary( a )

struct HINSTANCE__;
typedef struct HINSTANCE__* hInstance;

#elif defined (OS_LINUX) || defined(OS_OSX)
# define DYNLIB_HANDLE void*
# define DYNLIB_LOAD( a ) dlopen( a, RTLD_LAZY|RTLD_GLOBAL )
# define DYNLIB_GETSYM( a, b ) dlsym( a, b )
# define DYNLIB_UNLOAD( a ) dlclose( a )
#endif


To compile:

OSX:
main:
g++ main.cpp -o main
DLL:
g++ shared.cpp -o shared.dylib -dynamiclib

Linux:
main:
g++ main.cpp -o main -ldl -rdynamic -fPIC
g++ shared.cpp -o shared_single.so -fPIC -shared -rdynamic


And would you believe it took me almost 3 hours to figure this all out. (At least I didn't end up having to write my own RTTI system like the last guy.

You can check out the PAL self-registering abstract pluggable factory in the code. (see also the test programs and makefiles).

Wednesday, April 08, 2009

Essential free utilities for setting up a new PC

Every once in a while you get a new computer and you need to go through the usual process of setting it up.

Here are my favorite bits of free software to install.


First of all, a new browser. Everyone seems to like Firefox, but I prefer Chrome and Opera. Make sure you install Gears for offline gmail, and flash, etc. too. You might want FileZilla for your FTP needs, and if you want an email client, Thunderbird is a good choice.

WinRAR, for all your unzipping needs. Archive file formats supported are ZIP, RAR, ACE, CAB, ARJ, LZH, TAR, GZ, BZ2, UUE, JAR, ISO, 7Z and Z.

Notepad++ and OpenOffice or StarOffice or of course MS Office (if your a student) for all that document and spreadsheet work you need to do.
Adobe Acrobat PDF reader, or FoxIt (great for mobile devices too!).
PDF Creator to print to PDF.

For your photo collection, Picasa and Paint.NET for image editing. Irfanview is a nice small powerful image utility.

If your not happy with windows media player (and who is?), try
VLC for all your media streaming needs, and MediaPlayer Classic, Mplayer, for a few more codecs. Finally, VirtualDub for video editing. foobar2000 is great as a lightweight video player that can also convert audio formats. (You might also want LAME).

To get all those video and audio goodies there is of course µTorrent, the lighterweight BitTornado and SoulSeek.

To stay safe, AVG antivirus, just because it happens once every three years, and then your happy you have it. (Also, install some data recovery software, for the same reason.) You can try Recuva, personally I use a commercial product.

Then there are those additional annoyances to deal with: Disabling IE7 auto-update and Disabling IE8. Tweak UI and CMD here powertoys. Tweak UI will let you change annoying default behavior, (like autoplay) and remove additional icons.
To remove additional annoyances, right click on the clock to customize notifications and remove some of those additional startup options, and right click properties on the start button to get the quick launch etc. Finally strip those additional start menus clean by going through your Documents and Settings\All Users\Start Menu\Programs

Finally, Synergy will help you work effectively with your old and new PC.

Obviously I'm not covering details for Vista, because why would anyone want to use that?

Friday, March 27, 2009

AdaBoost

There are a couple of algorithms that float around that I always feel I need to know more about. During a number of data mining conferences the top 10 algorithms in data mining were collated.

One that seems to get a lot of attention in computer vision and robotics is Adaptive Boosting (aka AdaBoost). You can use this algorithm to create a strong classifier from a set of weak classifiers. (One way to think of this is that weak classifiers give you a very approximate answer to a classification problem, strong ones give a much much better approximation)

For example in the figures below, you can see how the algorithm builds up a strong classifier from combining multiple weak classifiers.
(from Jan Sochman's AdaBoost talk)











AdaBoost combines these classifiers through a set of weights that it adaptively adjusts.

I can hardly claim to be an expert on the subject, but since I find the mathsy description of it on Wikipedia confusing, here is my summary of it in CS-algorithmish talk:

Start with a training data set of features, labeled with the correct answer.
ie: data[i], correct_answer[i]
Run each weak classifier with the data set and store its results.
ie:results[x,i] = classifierX(data[i])
Initialize each of the weightings with 1 / (number of entries in the data set).
At this step we are starting of with each classifier having equal weighting.
ie: D[i] = 1/m

For N number of iterations:
For each classifier:
For each feature, i:
if the output of the classifier does not equal the correct answer, update the error.
error+=D[i]
(ie: sum of the weights of the misclassified samples)
if the error is less than the minimum error, mark this as the best classifier
End For
Now update the importance of the classifier:
alpha[best classifier] = 0.5 * log(1 - minimum error)/minimum error
And update all the classifier weightings:
For each feature,i
D[i] = *= exp(-alpha[best] * answer[i] * result(best,i)
z+=D[i]
End for
For each feature, update D[i] = D[i]/z to renormalize.

And.. were done!

In my experiments it seems not to work too well,.. it definitely improves on your weak classifiers a bit, but they have to be pretty close to spot on or able to solve the problem already. I think I'd still prefer using a neural net for classification..

Wednesday, March 25, 2009

Environment Design

Environment design for levels/missions seems to be a very tricky thing to get right.
My favorite resource on the topic is from Bungie:
Environment Design in HALO 3 by Mike Zak. It goes through some great detail on how they design and built up their levels, and dealt with AI.

Here's the halo 3 whiteboard for the factory level:



Alex Galuzin has some nice introductory material on Level Design Work Flow and Planning levels. Also check World of Level Design.

Basics of good design are also covered in Brian Upton's GDC 2007 talk on Narrative Landscapes.

There are some good tips on environmental storytelling by Don Carson, part 1
part 2.

Ben Cousins gives some good metrics to evaluate a map in Low-Level Game Design, Atoms, Measurement and Hierarchies, and Cevat Yerli illustrates some great examples of how a map can be effecitvly laid out in "Crysis in the Making".

Finally Realistic Level Design in Max Payne by Aki Määttä covers some details on indoor levels.

Alright, you should be all up and ready to make some awesome levels now!

Monday, March 09, 2009

Underwater Robot

The problem with real robots is that they keep breaking. Little things add up, hardware acts weird, batteries run out. Simulations are much easier to deal with.




Above is a picture of Markus and I trying to debug the AUV in the water. The AUV is slightly positively buoyant - which means at least you don't need to worry about it sinking..

Sunday, March 08, 2009

Update

Been a week or so since I blogged. (or remember doing so) Had a busy week, did some experiments with an autonomous underwater vehicle, and created a benchmark set for physics engines. Create a mini website for the physics engine benchmark - MoDBench repository - COLLADA & PAL API benchmarks.

Also found Pocket UFO. It's great to play all your old games on your PDA again. Other great toys for your PDA are ScummVM, Pocket Lemmings (runs multiple versions of lemmings),
Pocket Nester Plus (NES emulator!),
Vexed, SuperDoku (sudoku)

and Patiences (Spider Solitare, Free Cell)

That should keep you busy with your new windows mobile phone.