Saturday, December 22, 2007

You've got your Templates in my Inheritance

Templates and object-oriented inheritance are the two main features that separate C++ from it's precursor C. The can both be used to solve complex problems on their own, but when used together some truly unique properties pop out. One of the most useful is static polymorphism.

Polymorphism is the reason virtual methods exist. The ability to separate interface from implementation can reduce program complexity greatly; but at a cost. Every type that uses virtual methods must have a vtable, and every object of that type must have a pointer to this vtable. In and of itself this isn't a huge cost. However, a poorly chosen object hierarchy can introduce hidden bloat.

I've seen projects were more then a meg of memory was wasted on these hidden vtables. This might not sound like a lot, but on an embedded system it matters.

There is also a runtime cost, as the method pointer is looked up in the v-table. With modern CPU caching this isn't really a big deal, but again, embedded system caches are usually very small.

There is a little trick that can eliminate these problems, with some caveats. It uses the curiously recurring template pattern.

Here's a class "A" that calls dispatches foo to whatever its template argument is.
template < class D >
class A
{
public:
void foo()
{
static_cast<D*>(this)->foo();
}
};
Here's two sub-classes of A, B & C.

class B : public A<B>
{
public:
void foo()
{
printf("B::foon");
}
};

class C : public A<C>
{
public:
void foo()
{
printf("C::foon");
}
};
Notice how both these classes supply themselves as the template argument for A.

Here's a function which calls foo on its argument.

template< class D >
void call_foo( A<D>& a )
{
a.foo();
}
Now when you run call_foo, on an object of type B or C, you'll get polymorphic behavior. Try it.

int main()
{
B b;
C c;

call_foo( b );
call_foo( c );

return 0;
}
This will effectively give you polymorphism without a v-table and without the run-time dispatch overhead. There are some caveats though. Because templates are evaluated at compile time, the compiler has to infer exactly what type something is so it knows which version of foo is invoked. This prevents doing things like putting B's and C's into the same collection.

Overall it's a handy trick that's used in many modern C++ api's. For example Microsoft's WFC API & Boost.



Saturday, December 8, 2007

Visualizing Transformation Matrices

When working in 3D, you have to learn to love, or just tolerate, transformation matrices. You'll see them & use them all over the place. Whenever you find yourself face to face with a series of 16 floats, it's really handy to be able to build a mental picture of what that matrix represents.

A typical transformation matrix looks like this:
Not very helpful. But by partitioning the matrix into groups, you can get a feel for what's going on. First let's take a look at the last column.
Most of the time you'll be dealing with object transforms so this group should be [0, 0, 0, 1]. If it's not, you're either looking at a projection matrix, or things have gone very very wrong.
The green group represents the translation. [m=x, n=y, o=z]. This is where the pivot point of your object will be. If you transform zero, [0 0 0 0], by this matrix, the result will end up at this position in world space.
This blue grouping is a bit trickier because it represents both orientation and scale. But you can further subdivide it further to get a better feel for whats going on.
Each of these three vectors represent where the principle 3 axes will end up AFTER being transformed. Try it, take the vector [1 0 0 1] and multiply it this matrix. You'll end up with [a b c 0].

By looking at these vectors you will be able to tell which way the object will be oriented in world space.

For example: if you have a rocket-ship that's pointed along the x-axis and z is up.
And you have a rotation matrix that looks something like this:
You can tell by looking at the first row which way the rocket ship will be facing in world coordinates, along the z-axis, straight up. Similarly by looking at the third row, you can tell what direction the top of the rocket will be facing, along the y axis.

By looking a the last row of the matrix [0 0 9 0], you can see the rocket is 9 units off of the ground. So the rocket-ship is pointing upward and is off the ground, just like it's taking off from it's launch pad.


Now what about scale? Well typically the length of the red [a b c] vector is one. But what happens if it's not? It will compress or stretch vertices along the x-axis. Similarly, the length of the green [e f g] vector will scale along the object's y-axis. If you want a long thin rocket, just make the magnitude of the [a b c] vector larger.

Blender Second Impressions

I've been messing around on and off with Blender, but sadly it didn't live up to my initial positive first impression. The problem has to do with consistency and workflow.

A well designed piece of software sticks to it's own paradigms. If you right-click-drag in one window to select things, you should do this in all windows. It shouldn't matter if you are selecting animation keyframes or mesh vertices. This consistency is what makes software easy to use. You learn a few simple rules, and can apply them everywhere.

Software is only a tool; it's intended to get things done. It's important that commonly performed tasks take a minimum of effort. Or that a specific task can be performed on many things at once. This workflow is what makes software powerful.

These are they areas where Blender doesn't quite make the cut. The reason has to do with design rather then implementation. This is where most open source software falls apart. Design is hard and not something programmers are particularly good at.

Sunday, March 25, 2007

Blender First Impressions

Most of my experience with open source software has been pretty painful. Ugly web sites, broken installs & inexplicable error messages are the norm. Surprisingly, my first 10 minutes with Blender exhibited none of these problems. On the surface, it has all the core features of its proprietary competitors. Once you actually start using it the warts start to show, UI inconsistancy, poor work flow for common tasks, etc. But, I'm willing to overlook that. After all it's free.

One of the things that attracted me to Blender was the python scripting, and I'm glad to say I was not disappointed. The API documentation is a bit spotty, and has the stench of auto-generatation. But they do provide lots of example scripts, so I tore open a simple import script and added support for Cylindrix PFD files in no time.


I'm going to use it for my devious character animation experiments. Hopefully, the joy of the strange will remain...

Directed Acyclic Garbage

I hope to explore some interesting topics in this space. Things will likely be tech oriented, with a leaning toward game programming & all it entails, 3D graphics, animation, c++ etc.

So without further adieu...