Vortex Slides

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

4K programs

One of my favourite programming tasks is to create a program in under 4k.  This is something the Demoscene excel at (see scene.org awards).
Some of my favourites are:
stiletto by Rgba for the humanoid 3d models.
Glitterati by Fairlight for the ambient occlusion and fantastic physics. (My favourite overall perhaps?)
Micropolis by TBC & Mainloop for the awesome robot and city.
 Void 3 by Kolor, an oldschool DOS intro, with a voice synthesizer. Awesome DIY.

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 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...

Catchup Post

A short collection of interesting links/articles recently:

• Designing Fast Cross-Platform SIMD Vector Libraries plus source code, an interesting read on rolling your own vector libraries. If your looking for a bigger library you can try WildMagic or the Sony maths libraries.
  
• Compiler Cache helps reduce your compile times.
  
• Howard Yeend has an excellent tutorial on K-means clustering (ie: grouping data together, given you know how many groups you want - always a shame..)
  
• New DirectX SDK is out, not sure how this is exciting..
  
• Apple released the iPad, I have no idea if this is good. But I like the alternative, Linux-friendly iPad.
  
• I stumbled upon Alexandre Mutel's blog on 4k programming
  
• I discovered the IEEE has RSS feeds for most journals.
  
• nVidia have named the GF100 chips: GeForce GTX 480 and GeForce GTX 470.
  
• Anandtech have an
  article on GF100 explaining how the CUDA centric card is also great for gaming.
  
• Facebook released HipHop a PHP to C/gcc conversion tool.
  
• Clang self-hosts! I wonder how long until it becomes a serious g++ competitor.
  
• Symbian OS will be open sourced, perhaps a little too late? Still, Nokia are to be admired.
  
• An interesting gallery of processor cache behaviour, unfortunately I don't think the author is fully qualified on this topic. Still, interesting pictures.
  
• The PS3 hypervisor was hacked
  

Finally, a video of the top Tron AI from the Google AI Challenge:

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..

Antialiasing (multisampling) OpenGL with SDL

Very straight forward. After the "SDL_Init" call, simply call:

SDL_GL_SetAttribute(SDL_GL_MULTISAMPLEBUFFERS, 1);
SDL_GL_SetAttribute(SDL_GL_MULTISAMPLESAMPLES, 4);

before the call to "SDL_SetVideoMode".

You will need to call

glEnable(GL_MULTISAMPLE);

as well.

The smooth hint calls might help you too:

glHint(GL_LINE_SMOOTH_HINT, GL_NICEST );
glHint(GL_POLYGON_SMOOTH_HINT, GL_NICEST );
 
glEnable(GL_LINE_SMOOTH);
glEnable(GL_POLYGON_SMOOTH);

All done, you should see smoothed edges (as in the picture above, left is antialiased, right has jaggy edges)

Critical Mass Labs Presentation

Together with Ronald Jones from iVEC, I organized a presentation from CMLabs.

Michel Carignan, lead product engineer from CMLabs, discussed the internal structure of Vortex, a real-time physics-based simulation engine with collision detection. Michel covered issues in maintaining interactive performance with complex dynamical systems, and a number of applications from the areas of vehicle simulation, robotics and control.

Details of the constraint solver, collision detection, scene graph interaction, and the interactive editor were covered.

Vortex has a number of interesting features designed to support the simulation of cranes / booms with rigid-body chains for representing wires, etc. The simulation system features a highly accurate and fast solver (iterative/LCP, so I'm not sure what is so special about it..) and most constraint interactions are modeled as simple spring-damper systems. The package does not support continuous collision detection, but has 'Fast' objects, which perform iterative collision detection. A simple way to save computation time, while still achieving the goals of a CCD system, by putting some labor onto the programmer.

Constraints can be 'relaxed' to different degrees, enabling 'wobbly' links, eg: ropes. Each constraint can have a maximum force allowed, and this enables frictional forces with the ground to be simulated in a generic manner.

Vortex also has a few additional novel features including SPH fluids (and normal RB hydrodynamics), simulation of sonar sensors, cameras, etc.

One area where CMLabs seems to have put a lot of effort is the validation of the physics engine - quite an interesting topic, especially in validating motor models, etc.

The key new feature seems to be an interactive editor, however I was disapointed to hear they were building on their own file format and not supporting COLLADA (or let alone any other common 3d package like SolidEdge or Havok's physics format)

In any case it was an interesting talk, but unfortunately I had to leave early. Hopefully I can get the slides.

Barycentric Coordinates

Barycentric Coordinates, or 'Area Coordinates' (or uv's) provide a linear interpolation of coordinates in terms of the space of a triangle (or polytope), and have applications from collision detection to texture mapping.

In essence any point P on a triangle with vertices A,B,C can be described as:
P = A + u * (C - A) + v * (B - A)
this is the parametric form of describing a triangle. (ie: Make A the origin, and describe the coordinates in terms of a linear combination of C and B)

The barycentric coordinates are illustrated in blackpawn's barycentric flash application


We can rearrange this parameterized equation by subtracting A from both sides:
(P - A) = u * (C - A) + v * (B - A)
And substitute v0,v1,v2 for our vectors v2=(P-A),v0= (C-A), v1= (B-A):
v2 = u * v0 + v * v1

Now we can convert this single equation into two equations with two unknowns by performing the dot product on both sides. This is different from the scalar case, as we are performing a dot product with 2D vectors, ie:
a + b = k
Multiply both sides by two vectors:
(a + b).v0 = k.v0
(a + b).v1 = k.v1
Expanding:
(a.x + b.x)*v0.x+(a.y + b.y)*v0.y = k.x * v0.x + k.y*v0.y
(a.x + b.x)*v1.x+(a.y + b.y)*v1.y = k.x * v1.x + k.y*v1.y
Giving us two equations with two unknowns.

Applying this to our paramaterized triangle equations above we now have:
(v2) . v0 = (u * v0 + v * v1) . v0
(v2) . v1 = (u * v0 + v * v1) . v1
and can re-arrange to:
v2 . v0 = u * (v0 . v0) + v * (v1 . v0)
v2 . v1 = u * (v0 . v1) + v * (v1 . v1)
Which we can re-write in matrix form as:

Finally, we can perform a matrix inversion and get the final result:
u = ((v1.v1)(v2.v0)-(v1.v0)(v2.v1)) / ((v0.v0)(v1.v1) - (v0.v1)(v1.v0))
v = ((v0.v0)(v2.v1)-(v0.v1)(v2.v0)) / ((v0.v0)(v1.v1) - (v0.v1)(v1.v0))

This gives us the complete routine:

// Compute vectors        
v0 = C - A
v1 = B - A
v2 = P - A

// Compute dot products
dot00 = dot(v0, v0)
dot01 = dot(v0, v1)
dot02 = dot(v0, v2)
dot11 = dot(v1, v1)
dot12 = dot(v1, v2)

// Compute barycentric coordinates
invDenom = 1 / (dot00 * dot11 - dot01 * dot01)
u = (dot11 * dot02 - dot01 * dot12) * invDenom
v = (dot00 * dot12 - dot01 * dot02) * invDenom

// Check if point is in triangle
return (u >= 0) && (v >= 0) && (u + v <= 1)