Friday, February 19, 2010

Profiling on Mac OSX with Saturn

It is always advisable to profile your code before trying to optimize it. It is often most helpful to role your own (using timers & counters), but often a quick and simple tool will help a lot.

For windows I like the very sleepy profiler. On Mac OSX Apple provide the Saturn profiler (See: Saturn profiler user guide).

To demonstrate we can try compiling a small program:
#include <math.h> 
#include <stdio.h> 

#include <saturn.h> //include the saturn profiler

double func1(double x) { //do some maths
    return sin(x)*cos(x); 

double func2(double x) { //do some more maths
    return pow(x,3); 

int main() { 
    double x=0; 
    double z=0; 
    startSaturn(); //being profiling 
    for (x=0;x<100;x+=0.01) {
    stopSaturn(); //end profiling 
    printf("z:%f\n",z); //make sure compiler doesn't throw our computations away
    return 0; 

Now we need to compile it with profiling support:
g++ x.c -finstrument-functions -lSaturn -m32 -O2

Some common problems include:

  • Undefined symbols: ___cyg_profile_func_enter
    This comes from the -finstrument-functions option : it requires a special hook for each function - this is provided by saturn, so you must link with it.

  • ld: warning: in /usr/lib/libSaturn.dylib, file is not of required architecture
    Undefined symbols: _startSaturn
    Again, either you forgot -lSaturn, or you have remembered it, but are using a 64 bit OS/chip. Specify '-m32' to force 32bit mode.

If it all compiled succesfully, then start Saturn and choose 'Saturn', 'Launch Process'. Then select the executable (eg: a.out) in the dialog box.

Press OK, and Saturn will run and profile your program, and generate a folder with the profiler output data. (eg: Saturn_profile_a.out.000)

You can then select the data file to view the output, and Saturn will display a call graph and the amount of time spent in each function. Now the fun of optimizing can begin. Enjoy!

Thursday, February 18, 2010

Intersection of a Convex Hull with a line segment

A ray, or line segment can be represented parametrically as:
S(t) = A + t(B-A)
Where A and B are the endpoints of the segment, and t is the parameter that ranges from –infinity to +infinity for a ray, or just 0..1 for a segment.

A plane can be represented as n.X = d, where n is the plane’s normal, and d is the offset. (Given the plane’s normal, and a single point on the plane, P, we can calculate: d = -n.P)

A convex object can be represented as the area contained within a set of planes. Thus, to find the intersection between a line segment and a convex object, we just need to clip it against all the planes that form the convex object.

First, substitute the line equation into the plane, and solve for t:
n.(A+t(B-A)) = d
n.A + t*n.(B-A) = d
note: using identity = rs(u.v), where u,v are vectors, and r,s are scalars
re-arrange to solve for t, the intersection point along the line:

We can determine if the plane faces the segment or not by evaluating the dot product of the plane’s normal, and the line segment’s direction vector.
From this we can determine which point of an intersecting line segment to influence. If the plane is facing the segment direction, then we can clip against the end point, otherwise we can clip against the start point.
As we are testing the intersection against a convex object we can simply keep clipping against each plane and altering the segment endpoints until we have the minimum remaining line length, or the intersection length becomes empty (there is no intersection).

In pseudo-code the entire operation is:
AB = B – A
tFirst = 0
tLast = 0
for all planes:
 denom = N dot AB
 dist = d – N dot A
 t = dist/denom
 if (denom>0 )
  if (t>tFirst) tFirst = t;
  if (ttLast)
  No Intersection

Solving Linear Systems

In school you probably learnt how to solve systems of linear equations with techniques like Gaussian elimination, and Row-Reduced Echelon Form (RREF). However a simple, brute-force way to solve linear systems on a computer is through iteration.

Say we wish to solve the following equations:
4x -  y +  z = 7
 4x - 8y +  z =-21
-2x +  y + 5z = 15
Then we can re-write them as:

We can solve these with Gauss-Seidel iteration just by plugging in the current x,y,z values we calculate from these equations (and begining with an initial estimate.)

Thus, the Gauss-Siedel method in C-code looks something like:
#include <stdio.h> 

int main() { 
//a sparse way of representing the equations 
float eq[3][4];
eq[0][0] = 7/4.0; eq[0][1] = 0; eq[0][2] = 1/4.0; eq[0][3]= -1/4.0;
eq[1][0] = 21/8.0; eq[1][1] = 4/8.0; eq[1][2] = 0; eq[1][3]= 1/8.0;
eq[2][0] = 15/5.0; eq[2][1] = 2/5.0; eq[2][2] = -1/5.0; eq[2][3]= 0;

float x,y,z; 
x=1;y=1;z=2; //initial guess

//10 iterations of gauss-seidel 
for (int i=0;i < 10;i++) {
  x = eq[0][0] + eq[0][2]*y + eq[0][3]*z;
  y = eq[1][0] + eq[1][1]*x + eq[1][3]*z;
  z = eq[2][0] + eq[2][1]*x + eq[2][2]*y;
  printf("%f %f %f\n",x,y,z); 

return 0; 
Producing this output:
1.500000 3.625000 2.875000
1.937500 3.953125 2.984375
1.992188 3.994141 2.998047
1.999023 3.999268 2.999756
1.999878 3.999908 2.999969
1.999985 3.999989 2.999996
1.999998 3.999999 3.000000
2.000000 4.000000 3.000000
2.000000 4.000000 3.000000
2.000000 4.000000 3.000000

Converging towards the solution nicely. (Things don't always converge, only when Ax=B, A is diagonally dominant - but that is another story)

Jacobi iteration does not converge as quickly, but is easy to execute in parallel. With Jacobi iteration you simply use the last iterations x,y,z value instead of updating it.

See? Solving systems of equations is easy.

Wednesday, February 17, 2010

Building MRPT under Windows with MSVC

These are brief instructions on building MRPT under Windows.
  1. Download CMake, and install it. (You need a recent version, > 2.6)
  2. Download OpenCV, and install it. (I used the source package)
  3. Download wxWidgets, and install it. (Again, I used source.) [Note: wxWidgets is in my opinion one of the worst packages I've ever had to deal with - its build is notoriously unstable]
  4. Find the wxWidgets 'include/wx/msw/setup.h' file, and enable the use of OpenGL widgets:

    #define wxUSE_GLCANVAS       1
  5. Open (and convert) the VC6 build solution (build/msw: wx.dsw), and perform a batch build (select all, and go!). You will need to do this three or four times. (wx does not have the dependencies correct!)
  6. Close Visual Studio, and add an environment variable (right click on my computer, properties, advanced). Set wxWidgets_ROOT_DIR to C:\wxWidgets-2.8.10\lib\vc_lib (or your equivalent).

    We are now done with wxWidgets - you may wish to try some samples to make sure it works. (Pick ones that use OpenGL)

  7. Now run CMake with OpenCV. Set the Source and Bin directories to your OpenCV directory, eg:

    source: C:/OpenCV2.0
    bin: C:/OpenCV2.0
    . Press Configure a few times and generate the solution files.
  8. Compile OpenCV from the generated solution (Should be in C:/OpenCV2.0). Try some of the examples. Many of them require a webcam, so try plugging one to make sure DirectShow works.

  9. Set your visual studio library directory (Projects and Solutions/ VC++ Directories) to include the OpenCV lib directory. Close visual studio.
  10. Run the MRPT makefile 'win32_rebuild_MSVC9_GUI.bat' (not sure why?), and then start CMake again, clear the cache, and point CMake to MRPT. eg:

    source: C:/lib/MRPT/mrpt-0.8.0
    binaries: C:/lib/MRPT/mrpt-0.8.0/makefiles/MSVC9
  11. Build MRPT, all done!
Before running the examples you will probably need to copy all openCV dll's from the OpenCV bin directory, and copy all the wx widgets dll's from lib/vc_dll directory into the MRPT bin directories.

Friday, February 12, 2010

PEAK CAN Linux drivers

PEAK system provide a number of CAN cards with open-source drivers, and so far they have been working fine for us. (Unlike some other CAN cards!).

Installing the drivers is relatively straight-foward on a clean linux system (a fair bit more complicated with a Xenomai based system), but there are still a few quirks that can get in your way. I've described a simple way that works for us.

Starting with a fresh install of linux, the first thing you probably want to do is add some new users, eg:
adduser (name)
And perhaps add the user to admin group:
sudo usermod -a -G admin (name)
Then you need to make sure gcc, g++ have been installed, and the system is up to date. Having wget and a browser are always handy too. With ubuntu we can use apt:
sudo apt-get update
sudo apt-get install lynx
sudo apt-get install gcc
sudo apt-get install g++
Next, we need to ensure we have our linux header files. Find out your linux version:
uname -r
And install the linux headers, eg:
sudo apt-get install linux-headers-$(uname -r)
Now we need a symbolic link to this for the CAN driver to compile.
So you need to find your linux 'version.h' file. (You can try whereis/locate). eg, mine is at:
So you need to make a new symbolic link there:
cd /usr/src
sudo ln -s linux-headers-2.6.31-14-generic-pae linux

We are now ready to compile the driver, but first, we need to get it. Go back to your home directory and download the driver:
cd ~/
Then extract:
tar -xvf peak-linux-driver.6.15.tar.gz
cd peak-linux-driver-6.15
Now we are ready to compile! (and install the libraries)
make clean
make NET=NO

sudo make install
Now we can load the driver (if it isn't already):
cd driver
sudo /sbin/modprobe pcan
And we are all done!

Now, we can check if it is ok:
cat /proc/pcan 
cat /dev/pcan0
cat /dev/pcan1

If you have the dual-channel version you can try sending some data with a terminated CAN cable between the hardware modules. Example:
console1: cat /dev/pcan32
console2: echo "m s 0x111 2 0x12 0x34">/dev/pcan0
console1 will receive:
m s 0x00000111 2  0x12 0x34       310146 619


Thursday, February 11, 2010


Drishti is a real-time interactive volume rendering and animation tool. Paul Bourke
organized a tutorial at WASP/iVEC. The tool is developed by Ajay, a very friendly guy, and very open to user feature-requests.

Drishti has three parts, the renderer, the importer, and the painter. We only covered the renderer and importer.

The importer can import from various file formats, including standard image stacks and raw data. (unsigned characters, Z=1 .. ns
, Y=1 .. wd, 
X=1 .. ht)

To use the importer you just
 drag and drop (raw) data
, then you can adjust the top slider nob to alter contrast
, and left click to add an additional point that you can move to compress the range. You can view the data in different color spaces, and use the sliders to inspect the data. When you save you have a number of additional options including sub-sampling and filtering.

Once you have finished with importing your data and generated the you can drag and drop this into the renderer. Pressing F2 swaps you between high and low-resolution mode.

You can edit the transfer functions to explore the volume. The 2D version depicts the gradients of the data set, and takes a bit of playing around with before you get used to it. You can left/right click to shift the points, add points, make curves, etc throughout the selected volume. Space will bring up additional color maps. You can add new transfer functions to highlight different parts of the volume. The two sliders on the side can be used to set the alpha, and 0.5 each for a gaussian influence instead.

In low-resolution mode you can alter the bounds for the volume by draging on the sides of the box, or using the arrow keys for fine change movements.

Under the preferences tab you can set the step size (ie: quality of the render), or add an axis and labels, etc. Strange things seem to happen when you set the steps too low (< 0.2).

The final thing we discussed was creating keyframe animations. Selecting View, Keyframe editor displays the dialog. You can then click anywhere on the keyframe line, and set the viewport however you like (ie: rotate/zoom) and then click 'add keyframe'. Select another keyframe position, move the camera and add another keyframe, etc, etc. until you have the animation you like. You can move individual keyframes, or shift-left mouse to select an entire region and drag/reposition a whole group of keyframes.

To rotate the camera in another axis or to manually modify the camera positions, etc. use the brick-editor. Press 'a' to show the axis, and you can modify the axis of rotation (eg: alter 1,0,0 to 0,0,1, etc.).

Thats a fast-short introduction to Drishti. Take a look at the gallery for more screenshots and videos - unfortunately few of the fanciest features have videos.

Wednesday, February 10, 2010

Interzone Games - No more!

It is finally official. Interzone Games / Interzone Futebol is
(almost) dead
. After having heard the various horror stories for years, it is finally all out in the open. (Sumea also re-covered the story)

And with Staring Man/Spinfast loosing their lead programmer things don't look too great for the Interzone legacy right now. Still the ex-Interzoners are hardly alone, computer games have had it tough in Australia recently, Melbourne-based Transmission Games fired most of their employees, and closed its doors, Krome and Fuzzyeyes also had bad times. Seems reminiscent of the Ratbag games fiasco.

It is a shame it had to be such a public end. I still think it has helped nurture a WA-based games industry and given a lot of people some valuable experience. (Although actually RELEASING the game would have been a much more rewarding experience).

Hopefully it won't hurt future attempts - it seems WA independent game developers are doing well with a few good recent releases such as square-off, surf prodigy, and former-interzoners releasing Space Crash, pools of blood, etc..

Tuesday, February 09, 2010

Vortex Slides

Michel Carignan from CM Labs Vortex has kindly provided me with the slides to his presentation on Vortex.

edit: update, CM Labs can not publicly distribute the slides, but they are still available upon request.

Monday, February 08, 2010

4K programs

One of my favourite programming tasks is to create a program in under 4k.  This is something the Demoscene excel at (see awards).
Some of my favourites are:
Of course, achieving this seems impossible, however a few tools make this easier. I used many of these tools and tricks to create my 3kb entry to the global game jam.  First of all a drop/compression tool. Crinkler has eliminated the need for com/cob droppers and gives excellent compression. This little tool has made most of my 4k productions possible. IN4K has plenty of tools and code examples to help you learn the trade, but Iñigo Quilez has an excellent set of beginner projects. (Not the most optimized ones out there, but still a fantastic starting point).  FIT have an excellent set of demoscene resources, including source code to some fantastic 4k intros (plus synthesizers!). Ryg/Farbrausch has some interesting reads as well. The other thing that you will find when making 4K intros is the lack of maths functions (which you can get around by using intrinsics /QIfist in MSVC, or something like that), and by writing them yourself in assembly.  The next problem is often getting rid of the C standard library, in particular rand(). This is where Linear congruential generator (LCG) come in handy. This is where IQ comes handy again with a 'better, smaller and faster random number generator'. And again, this isn't the fastest or most optimal, but it will do. Finally you will probably want to allocate memory dynamically, and on Windows you can simply use: GlobalAlloc instead. (Feel free to overide operator new and use your standard C++ coding style). If your really looking to crunch size, then stick to values that will compress well (ie: powers of 2), but the latest crinkler can drop floating precision for you anyway, so I'm not sure how much you save with this trick these days...

Thursday, February 04, 2010

Catchup Post

A short collection of interesting links/articles recently:
Finally, a video of the top Tron AI from the Google AI Challenge:

Monday, February 01, 2010

Game Jam

I entered the 2010 Perth Game Jam again this year, but only had about 6 hours to put together an entry. Simon Wittber did a great job of organizing it again this year.

Simon has put up photos from Perth Game Jam, and ofcourse the Perth 2010 Game Jam games.

I put together a very simple multiplayer game for OSX, with the aim of making it into a 4k game. I managed to bring it in at around 3.5kb, but it was quite unstable.
You can download the game (Puggle) for Windows/OSX.

Below is a time-laps video of the event, I arrive at around 2:30..