Animation and other updates

Over the holidays I have been working on creating the low-level animation library. This represents the core of the project and I have tried very hard to get this part right. One of the problems with existing animation libraries is that they leave little scope for configuration and optimisation. As a result developers are left implementing their own systems on a per-project basis with optimisations to suit. An example of this I recently read about over at gamedev.net was about one team who needed to compress 4 floats of rotational data into a single 32bit value which required restructuring their code.

Such optimisations are common place in the real world in order to attain acceptable performance when, for example, targeting low-RAM systems or when aiming to transmit a high throughput of animation data to the GPU, or over a network (some modern networked games now perform dynamic animations on the server-side to avoid the pitfalls of dead-reckoning). In order to make a successful library I wanted to address the issue of customisation.

Poses - A pose models a snapshot of time-dependent data for a skeleton and its bones. In a typical application this would be a translation for the root and a rotation for each bone in the hierarchy. Poses are the primary source and location of any user-defined customisation and optimisation. Currently the library provides three levels of flexibility:

1. A default pose implementation which caters for the general case and provides dynamic 'any' types to allow users to easily attach custom data structure instances at run-time but in a type-safe manner. This is comparable to, or in excess of, what is provided by existing library implementations already.
2. A pose implementation that is parameterised on root and per-bone data; this allows users to easily build new pose types if all they want to do is supply a custom root and/or bone data structure. Default structures for both roots and bones are supplied for when the user only wants to define one of them.
3. The library allows users to define their own pose implementations entirely provided it adheres to an interface concept.

When creating custom pose structures it is generally necessary to also implement interpolation functions. The exact way that interpolation techniques are supplied to the library has not yet been completely hammered out. At the moment only lerping is supported and supplied as a member function of the pose. It is unlikely that things will remain this way in order to flexibly support more sophisticated interpolation methods, such as Hermite Spline interpolation, which are necessary for some of the planned features of the library, namely the motion graph implementation.

It is important to realise that this degree customisation comes with no associated run-time cost, all custom types are substituted at compile-time. Any components that rely on poses and wish to remain agnostic to the type of pose they're dealing with (i.e. most loci components) must be parameterised by pose type. To make things nicer for the end user such components tend to alias themselves with a version that uses the default pose implementation, e.g.

typedef basic_component<pose> component;

In addition when a family of components are created a special helper class can be created to parameterise the entire family of components by type in one go,

typedef loci::family_types<custom_pose_t> custom_family;
custom_family::component c;

Motion - A motion models a progression of poses over time. Currently the only implementation of motion I have is a keyed_motion class which stores keyframes as (time, pose) pairs and provides a sample() function to tween between keyframes and return a sampled pose. This implementation is suitable for general purpose animation. Motion capture data, however, lends itself to a more compact representation with improved performance since frames are sampled at regular intervals; as such I might be tempted to write a sampled_motion class, but for the time being this is unnecessary.

Hierarchies - Neither poses, nor motions, have any comprehension of the relationship that exists between the bones that comprise a pose; nor do the bones themselves (unless a custom implementation was supplied by the user to give them that information). Rather, this information is maintained in a hierarchy class. Hierarchies permit the construction of tree-based relationships between hierarchical elements. Elements are represented as indexes, with zero being the root of the hierarchy. To allow clients access to this hierarchical information a generalisation of iterators, cursors, are used with the hierarchy providing member functions that return cursor instances pointing at specific points in the hierarchy.

As an aside, and an implementation detail, hierarchies store their node relationships in a contiguous block, sequentially in the order they were added. Since most hierarchies are typically constructed in the same order they are intended to be later iterated though, often depth-first, then this makes for improved cache performance over the usual allocation-per-node hierarchies of other libraries.

Hierarchy Cursors - These allow navigation through the hierarchy from any point, though typically from the root or the current node of an algorithm. The cursor models the hierarchy as a quadly-linked graph, providing functions to navigate to the parent, first child, next sibling and previous sibling of the node it is currently positioned at. Cursors can be invalidated if they are made to move to a non-existant node (such as the child of a leaf node or the parent of the root node) and provide a predicate to check their validity. A function is also provided to inspect the current position of a cursor, this position can then be used as a index into another collection, such as a pose's bone list, which might store some associated data. This therefore supports a clear separation between hierarchy representation and data, which makes it easy to associate new information with a hierarchy.

Based on this, functions have been written which perform a depth-first iteration over the hierarchy from a provided starting cursor, or the root cursor if the hierarchy itself is provided. One such function also takes a separate sequence iterator and a function/functor; then at each step using the cursor's position to index into the sequence and pass the data found there to the functor for processing.

Anim-Trees - A animation tree (anim-tree) is a graph of generator nodes where each node outputs a pose to the parent node. The fundamental nodes of an anim-tree are blending nodes and sampling, clip, nodes which perform blending between the returned poses of their child nodes or motion. Implementing algorithms into the nodes for the anim-tree will represent a large bulk of the work set for the coming semester.

The anim-tree API is still in the early stages at the moment; the main difficulty with this at the moment is that it isn't clear yet exactly how poses will be propagated through the graph and populated with data without incurring expensive and repeated copying costs. On the one hand I feel unhappy about relying on (N)RVO copy elision here, which would suggest that I should have parent nodes allocate empty poses and pass references to those to their children to be populated. In that case should the referenced poses be populated via swap semantics or mutation functions. The latter demands a more complex interface for poses and means they cannot be immutable, whilst the former is likely to be less efficient. This isn't a difficult problem, I just haven't tried to weigh the pros and cons yet.

In addition to the animation system I've also revamped aspects of the numerics package, firstly vector-space types (Eulers, vectors, etc) now share a common implementation and they merely implement domain-specific functions on top of that. Whilst the code for the common vector-space is somewhat complex (to support generality) its usage is not. This has made it simple to introduce a (currently partial) implementation of quaternions to the framework.

A quaternion is a four-dimensional vector-space (w, x, y, z) and have an entire branch of algebra all to themselves, however unit quaternions are commonly used to model rotations in three dimensional space by being a parameterisation of the space of 3D rotations (a 4D sphere). They are favoured for rotations over 3x3 matrices because of their numerical stability when it comes to interpolation and they are favoured over euler angles because they avoid gimbal lock (a situation where a degree of freedom (dof) is lost when it is rotated to align with another dof).

Motion capture data tends to store its data as Euler angles and although, as a consequence of the way the motion is captured, it generally does not suffer from Gimbal lock for simple playback and blending - this does not apply to artist-created animations. Furthermore, some of the algorithms I intend to implement later will be performing more complex interpolations. In order to avoid any problems later, and to provide a stable general-case implementation to end users, it is practically necessary to make the unit quaternion the default representation of a rotation for a bone. As such the loaders will need to convert from Euler angles (or whatever representation is stored in the file) to quaternions. Fortunately the numerics framework provides such conversion routines.

All in all, I have been making general progress on the system as a whole, preparing for the implementation of the complex algorithms that are to come. I feel I am approaching a point where all the tools are stable and complete so that I can concentrate on plugging them together appropriately when implementing higher level algorithms. From a pragmatic standpoint the preparation time spent now, making the API clean and flexible, will directly benefit me later during "crunch time" (if there is a such a time) as I'll be able to more quickly 'hack' together solutions without compromising on the stability or usability of the library as it will all be wrapped up and abstracted away. On that note, correctness...

All the code I've written so far is thoroughly exception safe, type-safe and const-correct. A lot of the code is heavily templated to allow for flexibility without performance overhead. Unfortunately this adds to the compilation time and executable bloat if it's not used properly; this forms part of the motivation for providing a default pose implementation with run-time user-data attachments as it should keep both compilation time and executable size to that of an inflexible, non-templated implementation with a fixed pose type. In addition to this, the code so far is OO-strict to ensure that clients, and my future self, have a clean and modern API to be using. A list of the object-oriented techniques along with links to ObjectMentor which has .pdfs describing them in more detail is given below:

• The Single Responsibility Principle (SRP)
  
• The Liskov Substitution Principle (LSP)
  
• The Interface Segregation Principle (ISP)
  
• The Dependency Inversion Principle (DIP)
  
• The Open-Closed Principle (OCP)

There's still more work to do before the start of term. The idealised plan of features to implement before then are as follows:

• Implement a skeleton class to sync a bind-pose and hierarchy together into a convenience API for users to manually construct skeletons in code. [Easy]
• Improve the renderer [Easy]:
• Add proper mesh support (D3DX already supplies this, I just need to put it to use).
• Render bones as ellipsoid meshes rather than lines
• Add a virtual floor mesh
• Lighting
• Finalise the API and pose propagation technique for the anim-tree.
• Implement "Anim Events", these are events which are associated with specific bones in specific poses and raised when the virtual playhead passes over them. They are essential to allow client-code to sync logic with an animation, such as playing a sound when a character's feet touch the floor.

Whether or not this can be all be implemented given that revision is occupying a large amount of time, is another question. I certainly plan to make a dent in it :-)

Unfortunately I can't show you any pictures of the system working in this post since the project currently resides in an uncompilable state and the last compiled version of it didn't provide any real visual output. Hopefully next time will be a somewhat smaller but prettier post.