Saturday, January 30, 2010

Antialiasing (multisampling) OpenGL with SDL

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

You will need to call
as well.

The smooth hint calls might help you too:
All done, you should see smoothed edges (as in the picture above, left is antialiased, right has jaggy edges)

Friday, January 22, 2010

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.

Monday, January 18, 2010

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
(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)

Fast divide by X

A friend sent me a thread on quick divide routines for the AVR microcontroller. While the article is interesting, it is also a very poor solution.

The problem was to provide a fast result for divide by '5' in the range 0..255 (or even 0..100).
The solution was a fixed-point cludge, what was suggested was using the high byte result from: x * 51 + 1.
Unfortunately this gives the wrong result. The original concept can be made to give the correct results from 0..100 by modifying this to: x * 51 + 20
However, an even better solution is simply: (x+1)*51, which gives correct results all the way to 255.

A similar answer is possible for division by 3: (x +1)*81.

(Note: If you want to use this on the PC, don't forget to shift right by 8, eg: y = ((x+1)*81) >> 8

There are many more wonderful bithacks documented online.

Monday, January 11, 2010

SDL on Apple Mac OS X

Short post on using SDL on Mac OS X:
  1. Download SDL - the source tarball.
  2. Extract the tar, and open the command prompt to that directory
  3. Type "./configure" "make" and "sudo make install".

    You should have the libSDL.a in /usr/local/lib, and headers in /usr/local/include/SDL
  4. Download/write a simple SDL test program, I like Sol's SDL tutorials, the nice old school plasma.
  5. Compile:
    g++ main.cpp -lsdl -lsdlmain -framework Cocoa -o output
    If you are using OpenGL, add a "-framework OpenGL" in the command line as well. (You can get a sample OpenGL SDL C++ program for OS X here).
And thats it!

Sunday, January 10, 2010

OpenGL vs DirectX

A post from Wolfire on OpenGL vs DirectX has made a big splash on the usual news sites. My personal opinion can be summed up as: OpenGL (pre 3) - a good learning tool, easy to use. DirectX - good for more advanced things. And OpenGL is just trying to be like DirectX and failing, so why bother with it..

A few things worth noting about the post:
  1. "OpenGL is more powerful than DirectX" - This is just simply wrong. OpenGL does NOT have faster draw calls (they are SLOWER! - the driver has to put together all your glVertex calls, etc.) It does NOT have first access via vendor extensions - this is vaguely true for nVidia, but certainly not for AMD/ATI - infact, I believe OpenGL still doesn't have all the ATI extensions from as far back as 2000. (point sprites anyone?) Other vendors often provide thier own custom API's for additional functionality - OpenGL is rarely at the fore-front and certainly hasn't been for a long time. They also state DirectX has "almost as many features" as OpenGL, and this is completely false. The opposite is true. DirectX has way more features, and a very quick browsing of the OpenGL SDK and DirectX SDK will illustrate that point in no time. Especially if you consider the DirectX utility libraries (mesh compression, ambient occlusion, radiosity - where is that in OpenGL?)
  2. "OpenGL is cross platform" - This is true, one could argue DirectX should be called cross platform too (Xbox), however the key point to make is that OpenGL implementations vary quite a lot so any attempt at using advanced features is likely to end up breaking or looking very different on different platforms. If you are going to develop any kind of serious application, you would use an API-independent graphics engine that would target the native platforms API.
  3. "OpenGL is better for the future of games" - This is absolute nonsense. Most games don't even use OpenGL, and I believe that in the future games will abandon the whole drawing API in favour of their own software engines. Many engines already feature software renders for optimization purposes (typically, occlusion culling). OpenGL and DirectX don't support the concept of raytracing, etc. very well either. I would argue OpenCL/CUDA and custom rendering engines is the future (aka the past, eg: Unreal 1).
The final point made is 'Can OpenGL recover'. If you believe that traditional GPU's are dead (and nVidia believe it: they are focusing on general purpose compute aka GPGPU), then OpenGL will never recover, because the whole need for a graphics API will be gone. I hope we eventually see some kind of Larabee like architecture that maps better to OpenCL than it does to OpenGL and CUDA. Perhaps ID Tech 6, will fit the bill. To quote Carmack: "There's a real chance that the next-generation rendering engine will be a stable, mature technology that lasts in more or less its basic form for a long time" ... "Programmers will move from being engine coders to being technical directors in the Pixar style."

GPU update

A few updates in the GPU world for the last month:
Tony Albrecht from Sony released his slides on Pitfalls of Object Oriented Programming, which describes how to write optimal C++ code. (I'm a strong believer in C++ for all problems). Tony demonstrates how to convert 'typical' C++ code for managing a scene graph into optimal code getting a 6x speedup from using a custom allocator to ensure linear SOA data, removing conditionals (doing more calculations since compute is faster than branch), flattening the scene hierarchy, and prefetching data. It's a great read! (a bit light on some details though!)
Finally, this excellent video of a DirectCompute fluid simulation was released by Jan, you can get the fluid source code from his website.