Loci - A Human Figure Animation API

XML Scripting

2010-04-06T23:35:00.004+01:00

I'd also like to write about the XML scripting that I'm working on, this will be used to script up cut-scenes and maybe even semi-dynamic behaviours. I got my first script working earlier:

<actor>
  <activities>
   <activity id="montage">
   <sequence loop="true">
   <stage overlap="500"><clip name="female/Female1_D6_CartWheel.bvh" /></stage>
   <stage overlap="500"><clip name="female/Female1_B01_StandToWalk.bvh" /></stage>
   <stage overlap="500"><clip name="female/Female1_C05_WalkToRun.bvh" /></stage>
   <stage overlap="500"><clip name="female/Female1_C11_RunTurnLeft90.bvh" /></stage>
   <stage overlap="500"><clip name="female/Female1_C20_RunToJumpToWalk.bvh" /></stage>
   </sequence>
   </activity>
  </activities>
</actor>

The script simply sequences up a few animations together with a blending overlap of 500ms for all of them, it's fairly self explanatory really. The sequence node is set to loop and since the first stage is given an overlap it will transition back to the start smoothly, making an infinitely long continuous animation.

It certainly makes playing about with animations simpler as I now don't need to wait for the tedious recompile every time I want to fiddle around with numbers.
The script doesn't yet handle every kind of node, in fact it only handles sequence and clip nodes at the moment but the system is in place now and with that exposing new interfaces to the script is relatively easy.

Quaternion Fun

2010-04-06T23:27:00.001+01:00

I recently implemented velocity based blending, this in terms of vector-based velocity and quaternion angular velocity. This essential feature wasn't implemented before and as such animations could not transition correctly; if you imagine a person strolls a corner and intends to blend into a straight-walking animation you would not expect them to change heading any further, without velocity based blending the direction encoded in the original animation decides the direction the character moves with respect to the global axis.

To blend quaternions correctly I had to implement weighted quaternions, these are scaled, non-normal quaternions which are contributed into the blend buffer and eventually combine into a regular, near-normalised, quaternion. Getting this working was quite a mean feat, various boundary cases play havoc with the interpolation causing the actor to 'jump' sporadically when extreme blends are performed. The main issue was that a dot product test would change sign, signalling a sign-inversion of the to-be-weighted quaternion, this is important to ensure a shortest-arc blend around the quaternion hypersphere. Unfortunately the sign would change a fraction too early, as a consequence of the discretised sampling and tweening. To solve this I detect when the dot product is close to zero, at which point I begin calculating both the inverted and non-inverted quaternions, contributing them both to copies of the destination buffer. I then blend between the destination buffer alternatives, depending on the actual value of the dot product in the epsilon range around zero. This has the effect of smoothing out the inversion transitions in a range around the boundary case and produces visually pleasing results.

Calculating the positional and rotational velocities is simply a matter of working out the delta from frame to frame, the rotational delta is propagated through the blend-tree but not through the pose structure, rather it is propagated through the blend_info structure. This structure holds various useful infos that travel from node to node, including the destination buffer, blend weight, skeletal structure/bone names and the rotational delta. Rotation is handled separately simply because of the nature of this delta. It's actually the rotational delta around the y-axis, the x and z axis are not stored as deltas and remain in the pose structure to be blended as usual, only the y-axis rotation is converted to a delta since this decides the heading of the character over an essentially 2D terrain system. Naturally, to achieve this, I have to extract the y-rotation from the interpolated root rotation, this proved interesting when combined with my smoothing algorithm and required a couple of attempts to get it right.

All in all the quaternion blending is quite robust, numerically stable and reasonably fast, although there's plenty of room for improvement.

New Renderer

2010-03-10T17:29:00.003Z

The new renderer is actually fairly basic in terms of what's already out there, but it serves its purpose. For one it's based entirely on the fixed function pipeline, I'm not sure yet whether I'll write any shaders for this project, for the time being basic FFP stuff is serving me well.

At the highest level the renderer takes a list of skeletons to render, paired off with their current frame given as a pose instance. It configures the pipeline and iterates the list, extracting their hierarchy instances and sending it off along with the pose frame to a function dedicated to drawing skeletons. The function recurses the hierarchy, extracting the quaternion rotation from the relevant bone/joint pose description, concatenates it together with the parent transform as a matrix to get the joint transform for the bone and forwards that onto a bone renderer along with with the resting bone vector. This renderer uses the bone vector to calculate the resting direction and length of the bone (currently using an expensive sqrt), converts those to appropriate rotation and scaling matrices (using dot and cross products ) and concatenates them with the joint transform given to it previously to arrive, eventually, at the bone's final world-space transformation that turns a unit-sphere mesh into a bone. When calculating the scaling the thickness of the bone is calculated to be 0.3 times its height, it seems that a number of other academic skeleton renderers do something similar as it produces a familiar looking skeletal figure with the very tiny heads and feet.

The high-level renderer does this twice, once for the main skeleton and again, with inverted z-axis and culling winding order, to get the reflection. It then uses an arena renderer to draw a checkered, semi-transparent floor.

There are still improvements needed to the renderer, I don't really like performing square roots etc in the renderer, I might move this work to the animation tree if I can. In addition there is no instancing going on, it should be possible to instance the sphere mesh to draw the bones of the skeletons. Having the renderer accept a list of skeleton-pose pairs is a little hacked together at the moment too, it just needs a tidy-up. My supervisor has also requested that I try and use a proper model for the scene too, so I might have a go at getting .X-files working. Whether or not I decide to write any shaders for the renderer remains to be seen, certainly a lot work could be moved to shaders but I don't know HLSL at all so we'll see.

The renderer, as it stands, is pretty complete it terms of how I envisioned it initially, I hadn't planned to do any more than this. It has all the features that I said it would a few blog posts previously, so I'm pleased it has got this far.

That's all again for now, I'll leave with a screenshot of the new renderer displaying some skeletons, you can see it in motion a few blog posts down too.

The BVH Loader

2010-03-10T14:46:00.000Z

This last month has been a rather productive one in terms of finishing off sections of the API. This post is about the BVH loader itself.

As mentioned previously, the evolution of various core data structures resulted in breaking changes to the old BVH loader. The old loader could only parse the MOTION section of a given BVH document anyway, it was also heavily dependent on reading 'good' files, otherwise resulting in seg-faults - a result of having been quickly hacked together in an evening.

My first attempt at writing a revamped loader concentrated on using the Boost Xpressive library to perform the parsing. With this library you construct expressions using a familiar regular expression style syntax, expressions may recursively refer to themselves thus permitting the construction of context-free grammars (conceptually, push-down automata). The library is built to be more than just a toy however, so rather than sticking to the technical, academic, models it pragmatically gives the user control over backtracking and offers the ability to populate data-structures mid-parse so that by the end you will have accumulated all the relevant information together, no need to further traverse the parse tree afterwards.

Unfortunately, after spending the time to perfect the regexes and tracking down bugs in the grammar, I discovered that for some unknown reason certain files would fail and the Xpressive library would emit a null pointer exception (which cannot be caught in C++) whilst parsing the HIERARCHY region of the .BVH. Presumably it was caused due to some misuse on my part but the fact that it worked slightly more than half the time was highly confusing. I was unable to identify anything wrong with the offending files either, but an invalid file ought to simply not match the grammar and fail at loading, the library should still not be accessing null pointers.

Ultimately I decided to scrap that loader and take a more straight-forward route. I probably should have just obeyed KISS in the first place although I did enjoy the learning experience associated with Xpressive which is likely to benefit me if/when I use it in other projects. With this version of the parser I simply went with using the white-space tokenisation feature afforded by std::istreams to split up the tokens without reading the entire file into a string to begin with (Xpressive operated primarily on strings). I then used boost::lexical_cast to convert certain numeric values that the stream might fail at (mainly the frame-time part).

Overall the new BVH Parser Version 3 is faster, smaller and simpler than it's Xpressive counterpart, not to mention the fact that it works for all BVH's I've found so far. It also handles invalid or corrupt files much better; the Xpressive version would simply fail at matching the grammar within the library, reporting success or failure back to me as a boolean and so you would get a generic invalid-file exception upon failure. The new version can attach a string message indicating exactly what went wrong and roughly where that is within the file. It doesn't report a line number, it could do but ultimately I didn't want to assume new-lines within the file, as long as tokens are separated by white-space then the parser can correctly interpret the file. As such no new-line counting is performed either.

Both the Xpressive and the new stream-based parsers incrementally populate a data-structure that is tailored to approximate the structure of a BVH file. Abstractly this is a parse-tree, although it can only loosely be called a tree, being a flat structure. This is stored as a data member within a bvh_document class instance, the class exposes a compile() member function that uses this structure and, using the SoA tools described in a previous blog post, will construct a mocap instance (which is little more than an aggregator of skeleton and motion class instances).

The parse-tree structure was originally created for the Xpressive parser; populating a data-structure that is dissimilar to the grammar would be have a more challenging task. After replacing the Xpressive parser with the stream-based parser it opened up the possibility of constructing a mocap directly at parse time; I didn't go down this route though, in addition to not really wanting to re-write more code than is necessary I also like the separation of concerns involved although it may be somewhat less efficient to do things this way. mocaps don't quite maintain all the information that a BVH file provides either, only keeping those bits relevant to the API; mainly information about the order of channels (Euler angles primarily) and ordering of the hierarchy is lost, although this isn't a problem as such, it does mean that a bvh_document instance can round-trip much better due to its internal parse-tree. It sets a precedent for future file formats too for which round-trip imports/exports might be more desirable.

Since, for the time being, exporting isn't supported, the bvh_document class is really just a go-between temporary object. Even when exports are supported the typical use-case will still primarily be imports; as such a convenience function called import_bvh_file exists, it's a pretty trivial function really, implemented like this:

bvh_document::mocap import_bvh_file(const std::string & path, bool first_frame_as_bind_pose)

{

std::ifstream ifs(path.c_str());

return bvh_document(ifs).compile(first_frame_as_bind_pose);

}

It makes importing BVH's nice and simple though.

You'll notice that the loader supports the option to interpret the first frame of the MOTION section as being the bind-pose rather than being actual motion. This is quite a common thing to do with BVH's and it's something that has been done to most of the BVH's that I'm using (they're a conversion of Carnegie Mellon University's data-set).

Well that's all for this post, you can see the BVH's in action in the video I posted last time :-)
Next up, I'll talk a bit about the new renderer, stay tuned.

First Video

2010-03-09T11:59:00.001Z

So it's getting to the point now where I have a substantial amount of media to share with you for my project. Thusly, a video of people moving around. It doesn't really demonstrate the full capabilities of the API but it's all a bit in flux at the moment.

With any luck I'll be posting some overdue blogs about how I arrived at this point, getting additively blended quaternions working was quite a feat, more interestingly I believe the solution I have arrived it is somewhat unique.

Back in swing

2010-02-08T08:45:00.000Z

A few weeks of heavy revision has meant very little free time for working on the project, however with exams over as of Friday it has given me a chance to get back into development properly.

Firstly, a brief detour. As I mentioned last time there are various structures that express different aspects of a skeleton and work together implicitly to fully specify one. Each structure is essentially a list with data about each bone and a block of information about the skeleton as a whole from its perspective. This is commonly referred to as the Structure-of-Arrays approach (SoA) which opposes the Array-of-Structures approach (AoS). There are two major benefit of SoA, one is that its cache friendly and the other is that it allows you to reason much better about what an algorithm will do if you know which arrays it operates over.

To explain the improved cache performance, imagine that a bone is a <name, position, rotation> tuple and that we have a list of these tuples (AoS) that we want to iterate through for rendering. As we access each bone's data the computer doesn't just transfer numbers to registers, it takes an entire 64KB chunk of RAM at and around the memory location of the bone and copies it to one of the CPU's L1 cache lines. This means that successive elements are already on the CPU which now doesn't need to fall back to system memory until the we run off the end of the cached data. However, it turns out that for rendering, we only care about positions and rotations; the names of bones aren't important yet they occupy a large proportion of the space in the cache line. This means there are fewer cached positions and rotations available, increasing the frequency at which that the CPU goes back to the system RAM for more data. When this happens it's referred to as a cache miss; at this level cache misses are about the most expensive thing a CPU has to put up with and a primary drain of an applications performance. Using SoA instead means that only positions and rotations are going to be cached, so more bones can be referenced in a cache line.

In order to benefit from SoA but also retain convenience for the user and myself, I wanted a class that would keep the various structures in sync with one another. As I said before I had in mind a skeleton class to do this. After implementing it I fell into a design pattern that is most familiarly known to us from various string API's. First there is an immutable string class (I have an immutable skeleton class) which efficiently and conveniently models a string/skeleton and all relevant invariants therein. Of course, being immutable makes it hard to build and modify one without lots of expensive copying; if the class is changed to be mutable then it needs more complex logic to maintain invariants and a more flexible, less efficient, underlying representation. Instead a builder object is created (such as C++'s stringstream class), in this case a skeleton_builder. It has a more flexible, transient representation of a skeleton that is easily mutated. On request it builds and returns a skeleton object which houses a more static and compact representation.

I have also done some more work on the interface for the anim-tree. It's not completely finalised yet and I suspect it won't be until later in the semester when the various nodes are actually implemented and it is easier to see what the exact requirements are. However, I have solved the issue of pose propagation, a single pose is instantiated at the root of the tree, initialised with the bind pose, and gets passed from node to node via reference semantics; this means three things, firstly there is no expensive copying of poses going on, I am not relying on (N)RVO and there are not multiple poses being allocated per node.

At each node a weighted contribution of the current frame's motion is additively blended onto the pose instance's data; the weights are calculated such that once every node in the anim tree has been visited the weights will sum to 1 and the pose will finish up with the final posture of the skeleton at the current frame. Each node chooses the weights for its child nodes, making sure to factor in its own from given by its parent. Weights can be selected on a per-pose basis or a per-bone basis. In this way, a weight of zero for a particular bone essentially disables it from future contributions, I plan to use this to implement bone masking; as a theoretical optimisation nodes are able to inspect the weight of each bone and if its zero (or close to zero) then they may choose not to calculate a contribution at all.

Different node types can communicate with each other freely as they all inherit from a common abstract base class; the pose and its weights can be supplied to child nodes via a polymorphic member function. As more complex nodes are added I expect that more such functions will be required. One that I have in mind already is the ability to ask a for multiple samples at once over a duration of time, each being a regular interval apart; using this a node can examine the velocity and acceleration of motion in upcoming frames.

I think the blending system is quite elegant really and I have already begun to implement nodes, the most interesting one being the motion node which adapts a keyed_motion instance -- actually it accepts any type so long as it adheres to a specific motion interface concept. It contributes samples from the motion to the pose using the described weighting system. This brings me onto talking about poses and motions...

In my previous post I mentioned that poses are the primary source of optimisation and customisation for the client to make to the low level animation system. All this has changed. Poses don't easily lend themselves to allow the user to control the storage policy used to model a motion (a motion being successive poses) and they don't permit various compression techniques, such as using splines to model motion rather than a list of poses. The obvious solution to this, then, is to increase the level of granularity and make the motions the smallest unit of customisation for the user. This drastically simplifies everything. Users now build their own motion classes and wrap them in motion nodes in the anim-tree, it's as simple as that

Poses still exist, of course, but they are no longer open to customisation. Rather, the anim-tree has a fixed pose type, allowing nodes to make apriori assumptions, both simplifying their implementation and opening up better in-node optimisations. The pose consists of root-pose data (position and rotation) and a vector of bone-pose datas (just rotation), rotations are currently represented as euler angles for my own sanity during testing but they'll be replaced with quaternions eventually. The pre-supplied motion class (current only keyed_motion) also makes use of the fixed pose structure, it simply stores a sequence of them. Provided that user-created motion classes end up contributing their samples to the (now one and only variety of) pose, then all is well, but internally they are free to model motion however they want.

All of this has resulted in breaking changes to the renderer and the bvh loader. I am currently in the progress of revamping the renderer anyway to use spheres and lighting rather than lines. It's much more complicated in Direct3D9 than in would be OpenGL but I should get that done today. As for the bvh loader, its previous implementation was exceptionally fragile, being more of a prototype than anything, as such it needs to be re-written - I plan to implement the loader in terms of the new skeleton builder and have the parser use recursive regular expressions to model the grammar (I know they're technically not 'regular' expressions if they're recursive, but you get the idea). If all goes well I'd like to have that done sometime tomorrow ideally. I can then spend the rest of the week working on the anim-tree.

Although the renderer does actually generate something visual, it's not really worth posting a screenshot on its own just yet, so in lieu of anything more decent at the moment I'll leave with a snippet of code comprising the contents of the main() function used for testing, it draws two bones connected together at different angles and just shows how easy it is, even at this low-ish level, to make an application go:

// alias some names for convenience

typedef loci::bone_pose bone;

typedef loci::root_pose root;

typedef loci::numeric::vector3f position;

typedef loci::numeric::eulerf rotation;

typedef loci::skeleton_builder::hierarchy_cursor joint;

typedef loci::video::render_view app_window;

// create a skeleton builder with a root node at the origin

loci::skeleton_builder b(

"root", root(position(0, 0, 0), rotation(0, 0, 0)));

// add bones to the hierarchy

joint parent = b.root();

parent = b.add_bone(parent, "test1", bone(rotation(0, 0, 45), 20));

parent = b.add_bone(parent, "test2", bone(rotation(45, 0, 0), 5));

// build the skeleton

loci::skeleton s = b.build();

// create a rendering window

app_window canvas(LOCI_TSTR("Loci Test App"), 800, 600);

// game loop

while (!loci::platform::win32::dispatch_messages())

{

canvas.render(s);

}

Animation and other updates

2010-01-14T05:08:00.001Z

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:

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

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.

Research progress and BVH loader

2009-11-13T18:42:00.004Z

Unfortunately it has been a while since I last updated the blog. I think updating more frequently with smaller posts is more achievable than infrequent and longer updates.

I have begun to write the next stage of the dissertation, the survey and analysis stage. I have to maintain a high level of work throughput on this now, producing one or more pages a day ideally. Most of my work up till now has been based on research so it is now a matter of writing this up for the literature survey; I have been researching numerous topics including:

Data Structures to Represent Skeletons

Being a computer scientist data structures are an avid interest to me and it is important that I get the data structure of the skeletal hierarchy correct. There are essentially two most promising solutions to this in C++, one is to use a pointer hierarchy in other words have a node structure that maintains (smart) pointers to other nodes; the other is to use a heap data structure which not only more efficiently supports algorithms such as Dijkstra's shortest path algorithm (potentially useful for constrained Inverse Kinematics) but it can also be efficiently stored as a single array and traversed using iteration. Using an array rather than linked nodes has the additional benefit of a strong locality of reference, specifically spatial locality, which aids in efficient caching to within a modern computer's layered memory model.

Motion Capture File Formats

I have been researching motion capture file formats recently, particularly the BVH file format and the ASF/AMC formats. To this end I have created a BVH file loader prototype which loads and displays the hierarchical structure of the skeleton:

Currently each bone is drawn from the position of it's parent to the position of its joint's offset from that parent, as such there is no rotation happening. The next prototype will support the correct rotations of joints which will allow me to use render using oriented ellipsoids rather than lines. To get to this stage requires the addition of Matrix, Euler-Angle and, perhaps, Quaternion components to the numerics library.

Procedural and Parametric Motion Generation

This topic, I have found, is essentially divided into two parts. One is the generation of long sequences of generation and the other is the generation of slightly altered but short motions.

The generation of long sequences of animation has been achieved in a number of ways, one way is to take motion capture animation, split it up and recombine it into longer chains than can reoccur. Another method is to use parametric equations to generate motion and simply alter the parameters. Finally there is also the analysis of motion capture data using statistical methods and Fourier analysis to extrapolate further motion.

The generation of new short sequences of animation typically involves the blending of several similar animation pieces together to form the new motion, there is a good video on this from one of the most successful attempts to date (2004) by Lucas Kovar and Michael Gleicher (source).

Joint Sliding and Inverse Kinematics

I have done some reading about Inverse Kinematics (IK) which is a commonly used algorithm in computer animation for calculating the angles and motion of joints in order for an end-effector to reach a target point. It gets used at design-time by artists to help pose animations to create key-frames, but it also gets used at run-time. There are two run-time applications of IK that I am interested in, one is to allow extremities such as arms or tails to reach for certain objects in the world correctly and another, more important in my mind, application is to keep the character's feet realistically planted on the ground despite the fact that an animation might have been recorded for a flat surface yet the ground is not flat.

The Description Stage

2009-10-10T18:51:00.002+01:00

This week I have been working on, and researching for, The Description Stage; this is the initial part for the written aspect of the module. I have made this available online since I was unable to print this in colour.

Beginnings

2009-10-05T01:27:00.000+01:00

Welcome to the Loci project's blog. In this blog I intend to journal the development and progress of the Loci API, my 3rd year dissertation project. In addition to this blog there is a dedicated Loci website, there you can find more information about Loci and this project. At the moment everything is in a state of flux and the website has only just been created so there isn't much to read, but the hope is to progressively add content as time goes on.

My plan at the moment is to make fairly regular blog posts, I don't think it necessarily makes sense to tie them to a fixed schedule, for if there is a slow period in development for various reasons then I would rather not have forced myself to make posts that only contribute to 'blog noise'. That said, I do hope I can make a post at least once a week where possible, and then more frequently as required, perhaps a regular schedule will fall out of that - milestones will be blogged about as well as general progress and any expected long delays in blog posts should hopefully be indicated too.

I shall also be taking screenshots (of screenshot-able progress), here's the first one:

In this screenshot, you can see a console window display details about a 2-bone hierarchy and a black Win32 window. I am working on writing an infrastructure for supporting a high-level renderer implemented with Direct3D9 - at the moment none of the black in the screenshot is hardware accelerated black. The renderer is planned to be an official component of Loci but not a required dependency, it is expected that many users will want to use 3rd party renderers in conjunction with Loci and may not wish to be tied to Direct3D and Windows.

Why Direct3D in the first place? - I have elected Direct3D as my graphics API of choice over OpenGL for a few reasons:

I have some experience with OpenGL already and would like expand my knowledge.
Direct3D exposes only the most efficient code paths, OpenGL's efficient code paths are hard to find in a large sea of extensions.
As things stand, and if there's time, then I hope to write a jogl renderer later and I would like to showcase the variety of two different renderers working with Loci.

That's it for this first post, I don't expect that they will be this long generally, but as this my first post there is a fair amount to write about (and a lot I haven't said yet).