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);
}
Posts
