Converting animations between skeletons

I have written one more piece about the skeleton merge about half year ago - you can read it here. What follows is the a much better version of the original algoritm.

The problem

Say you have some good animations (there are many free BVH sites in web) and want to use these for your own models. Unfortunately - unless you made your models using exactly the same skeleton layout, the bones do not match and copying animations is not trivial problem.

There are many ways, how skeletons may differ:

• Bone names do not match. This is easy to overcome - either build mapping or rename bones.
• Rest pose orientations use different systems (like XYZ euler angles vs. ZXY euler angles vs. quaternions). This is also minor problem, as normally you want to convert everything to quaternions or matrices anyways.
• Bone lengths do not match. Thus copying animation directly can make movement unnatural. 
• Rest pose bone positions (directions) do not match. Thus animations can not be immediately copied between skeletons, but have to be transformed to absolute space (object space) before.
• Skeleton topologies do not match. This is often a showstopper, because if you do not even have similar bones, there is no way to copy animations. 

Example of different common skeleton topologies

The topology mismatch is the hardest problem to overcome. In the example above, if you, say have animation for the right skeleton, the 4 parts of backbone should move the 2 backbone parts and pelvis of the left skeleton. While in theory it should be possible to solve this problem analytically, it is not easy - and has to be done by hand for each combination of skeletons.
Instead of that, using IK solvers gives us easier way to map those skeletons. It is still not universal - the mapping algorithms have to be adjusted to object itself - in current case a humanoid. But normally this is not big problem, because in 99% cases humanoid is precisely what you want to animate.

In any case you need good IK solver, that can do at least 6-7 bones long chains, adjust both positions and rotations and use both absolute positions and bone directions for targets. Also, the solver has to support comparing up to 4 target points or directions simultaneously. I am currently using simplex method in Khayyam (the code is in helpers/ik.cpp), but there are other options as well.
Also the skeleton should have bone constraints defined - otherwise you may discover that elbows or knees will be bent to completely wrong direction.

We start implementing the algorithm by a small observation. Namely - while there are different ways to construct skeletons, the joints have to be still placed to precise spots - otherwise the movement of joints will not be natural. Thus we can use the joints as anchor spots for the algorithm.

The body

The first and hardest part is moving the main bodies of skeletons to the same position. First - the root bones may be arranged differently. Second - root bones may be joined with body either below or above pelvis. Third - there may be different number of backbone elements. Fourth - there may or may not be extra bones, like hips or collar bones.
To solve this problem, we can do the following:

• Set 4 IK target points to the corner joints of body - both hips and both shoulders.
• Scale the source skeleton so, that the distances between hips and shoulders are approximately the same, as in target skeleton.
• Find the topmost common parents of both hips and shoulders Ah and As.
• Find the topmost common parent of Ah and As B.
• Build rotating IK chain of bones from  B to Ah and from B to As, not including B.
• Add both the rotations and translations of the rootmost bone R to chain. 

The schematics of body IK solver (green: translate + rotate, red: rotate, blue: not moving)

After solving this IK chain, the corner joins of body will be approximately aligned to the original. Normally you do not achieve perfect alignment, because the width of shoulders and hips is different in skeletons - but this is not big problem, because the direction of hip-hip and shoulder-shoulder lines should be aligned.
It is important to do this alignment in one step - otherwise the alignment of hips may involve extensive rotations and translations of root bone R - and you cannot later align shoulders at all.

Limbs 

To align limbs, there are two strategies - depending on what we want to achieve.

• We can align the endpoints - if we want to model some specific action - like taking some item from table. In thus case the hand will be in correct place - but because the lengths of arms and forearm probably differ, elbow will be off.
• Or we can align the directions of bones - for example if modeling hand movement during walking - in that case both elbow and wrist will be off, but the overall look of hand will be more similar.

At the first case it is just ordinary single-target IK solver. Or if you want to keep the elbow/knee direction more similar to original, there should be additional directional target at midpoint.
At the second case, the IK chain has to be solved with two directional targets (shoulder-elbow + elbow-wrist or hip-knee + knee-ankle) simultaneously. Otherwise the topmost bone may turn it to such direction, that 1 DOF joint at midpoint (elbow or knee) cannot move other bone to the right direction.

Palm

There are probably different strategies for adjusting palms. In khayyam I did the following:

• Set 4 directional targets from wrist to the topmost joints of fingers
• Add the 3 DOF rotations of palm to IK chain
• If forearm includes extra rotational bone (like at the skeleton at left), include the axial rotation of it to chain 

By solving this chain, the positions of finger joints will be approximately aligned to the original.

Fingers

Fingers can be aligned in the same way as limbs - but here we need three targets instead of two. Also, as the fingertips are normally the end sites, the last target does not coincide with any joint, but has to be placed about 2-3 cm from the last joint along the bone direction.

Head

Head should be placed by adjusting three positional targets - eyes and skulltop. This can become tricky, because many skeletons may not include eye positions at all.

Sara chan in skeleton merge editor (blue: figure skeleton, red: animation skeleton)

At the above picture you can see the results of adjustment of Sara-chan skeleton to Illusion Characolle animated skeleton. Although the skeleton topologies and bone lengths differ, the pose is pretty close to the original.

At moment the skeleton merge works only in CVS version of Khayyam, but expect it in the next release.

Khayyam architecture: libthera

For a quick overview of all Khayyam subcomponents, look at the introduction.

Overview 

Libthera is the backbone of Khayyam document system. It is very simple DOM-like tree of XML nodes, implementing file IO, transactions (think undo and redo) and property, tree and content mutation events.

The schematic layout of Thera object tree

All properties inside libthera tree are simple text strings. Thera nodes do not know anything about the semantics of attributes, content or child nodes. They only serve as the containers of base state for more semantic-aware objects in libmiletos.

Thera::Node

The basic building block of Thera tree is Thera::Node - an object encapsulating XML node (either element, text or cdata). It has the following properties:

• Name (only for element nodes) 
• Backlink to containing document 
• One or more attributes (key/value pairs, only for element nodes)
• Optional text content
• Linked list of children
• Linked list of eventlisteners

The tree is modified by atomic methods of nodes - content change, attribute change, child insertion, child removal and child reordering. The API is kept as simple as possible - setting attribute to NULL deletes it, using NULL as ref value during child insertion prepends child and so on. The result is true if the action succeeds, false if not.

bool Node::setAttribute (const char *key, const char *value);
bool Node::setTextContent (const char *newcontent);
bool Node::addChild (Node *child, Node *ref);
bool Node::removeChild (Node *child);
bool Node::relocateChild (Node *child, Node *ref);

By default all methods above are allowed on all proper nodes (no attribute change or child management on text and cdata nodes). Actions can be vetoed by event listeners. The idea here is, that thera tree is not typed - all element nodes are similar and do not know anything about the semantic meaning of themselves or attributes. To implement semantic checks, another structure has to be added to thera tree, that can interpret the property changes and veto/allow these. In case of Khayyam, that additional layer is libmiletos scene graph library.

Event system 

For each property change (attribute or content change, child insertion and so on) node first invokes query events from linked EventVector list.
EventVector is list of function pointers, which - if not NULL - will be called during mutation events. I did not implement real signalling system for two reasons. First - to keep things simple. Second - normally single Thera::Node is tracked by single Miletos::Object and thus having all listeners in one structure makes perfect sense.

For example, if one tries to change the attribute of Thera::Node, the following happens:

1. Old and new attribute are compared. True is returned immediately, if they are identical.
2. change_attribute listeners are called by function pointers from all linked EventVectors. If any of these returns false, attribute is left intact and false returned.
3. Actual attribute value of Thera::Node is set to new value
4. attribute_changed listeners are called by function pointers from all linked EventVectors. This is post-mutation callback and thus cannot veto the change anymore.
5. If no attribute_changed event was installed, downstream_attribute_changed listeners are called from parent node EventVector list.
6. Containing Thera::Document is notified about attribute change

Normally the libmiletos scene graph objects (subclasses of Miletos::Object) listen to attribute_changed, content_changed, child_inserted and other post-mutation events and update their internal state whenever something changes. The exceptions are two special attributes id and xmlns. As each object in scene graph has to have unique id for reference system to work, the uniqueness of the value of id attribute is checked in change_attribute handler and mutation blocked if new value is not unique. All xmlns changes are blocked, as those change the semantics of object, and would require replacing one scene graph node with another one.

The reason for downstream listeners is to reduce the number of objects, that libmiletos has to implement. For example <color> nodes in Collada tree do not build their of objects (i.e. there is no Miletos::Collada::Color objects) but instead the containing nodes (ambient, diffuse, light nodes and so on) get signalled of color content changes by downstream propagation.

Transactions

The untyped nature of thera tree makes it ideal place to handle generic editing functions, that have to be consistent for all scene graph nodes - undo, redo, cut, copy, paste, load and save. The invariant in Khayyam document system is, that the properties of Miletos::Object are determined only by the attributes and children of Thera::Node. So restoring the Thera::Node properties to previous value, also restores scene graph to previous state.
Thera::Node has very few properties, so to implement undo and redo, we have to only record 5 different types of mutation events (attribute change, content change, child insertion, child removal and child relocation). This is managed by Thera::Document container.

For each mutation event, a new record is appended in document undo list.

• For attribute changes keep node location, key and old value
• For content changes keep node location and old content
• For child insertion keep the location of new node
• For child deletion keep the copy of child node and it's previous location
• For child relocation keep the old and new locations of child

Undo works by rolling back the record, and moving it from the top of undo list to the top of redo list.

Transaction logging can be turned on and off. Normally it has to be always on for editable document, but in certain cases - like during ensuring unique id attributes to all objects during document creation, it is turned off (id uniqueness is required feature, so this procedure cannot be undone).
In addition to transaction logging, there is transaction collation. If this is turned on, subsequent changes of the same attribute do not create new records, but only update the last record. It is used for tracking continuous numerical attribute changes - like the ones controlled by spinbutton or slider.

Similarly cut, copy and paste are implemented by storing the clone of copied node(s). During paste, the clone is re-cloned into document tree - and libmiletos objects will be built and updated automatically by event listeners.

Some concerns

While the untyped nature of thera tree makes editing functions simple and consistent throughout document, it has one drawback. As objects are often referenced by id values, and id has to be unique in document, copying reference pair does not work as intended. The id of new referee will be changed to some unique value, but the referencing attribute of referer will be not. So the referer will link back to the original object, instead of the new object.
I have some ideas, how to handle it - by keeping a dictionary of id overwrites during libmiletos object building phase, but at moment it has to be adjusted by hand.

Also, as libthera keeps all values as text, updating parsing these may take more time than is reasonable to spend during interactive editing. To dealt with this, many interactive functions work in two-stage way.

• When input is grabbed (mouse button pressed), the initial state of object is recorded
• During editing (normally dragging) libthera is skipped and editing function applied directly to scene graph nodes
• When editing is finished, the last state is written to libthera
• If editing is canceled, object state is read back from libthera (which has the initial value) 

Thus interactive functions do not constantly update text attributes, but instead the state of scene nodes directly. As an extra bonus the single editing action (click-drag-release) is recorded as single document transaction, because the libthera values are updated only during release.

That's all for now. Libthera can be donwloaded as part of khayyam source from SourceForge page. Or the latest version can be fetched from Sodipodi SVN:

https://sodipodi.svn.sourceforge.net/svnroot/sodipodi/trunk/thera

Have fun!

How to use Poser/DAZ models in Khayyam

There is almost endless number of Poser models and props (accessories) available from sites like DAZ3D, Renderosity and Renderotica (adult content). It is possible, although somewhat tricky, to get many of these to work in Khayyam. So I have composed a small tutorial of loading figures, hair, clothes and materials in Khayyam.

Warning: Khayyam is still in very early stages of development and many models do not work. So better do not purchase expensive models unless you also have Poser/DAZ or know, that you can get them working. But you can always hunt for cheap things, bargains and free stuff (DAZ forums is a great resource for finding free models). If something does not work, I can usually fix the Khayyam code - but you have to buy given model for me so I can experiment :D

1. Loading Cr2 model

Cr2 (Character Rig) is the skeletally controlled model, that is mostly used for human figures (also animals) and more complex hairstyles.
Select Object -> Import -> Import Poser mesh
Depending on your library size it may take some time to load all previews. When done, the import dialog will open. If you have not specified Poser library path yet, the library list is empty. Click on Choose Library and select the Runtime directory of your model installation tree.
Most human figures are under Character subtree. I use DAZ People -> Victoria 4.2.cr2 as an example for the tutorial.

Khayyam Cr2 import dialog with Victoria 4.2 selected

 Click Import and the the import options dialog will open.

If importing main figure you should keep all options at default values, as shown above.

•  Create skeleton will build editable skeleton for rigged model. Normally you want to keep this checked.
•  Import as standalone mesh will build new toplevel figure. Unless you are adding hair or clothes to existing figure, this should also be checked.

Click Import and the figure will be inserted to main document. You can close the Import Poser dialog or keep it open, as we will use the same dialog later again.

Figure imported to main document

As you can see, the default look is quite plain. We'll add proper materials soon to make her more attractive.
Now it is time to open the Document Tree dialog, if not already open. Select the figure (click on it, so the selection box turns orange) and choose Dialogs -> Document Tree.

Document Tree dialog with some nodes expanded

At the left side is the DOM tree of current document. At the right side are the property pages of the currently selected node. Most fine-tuning of objects is done with property pages.

All poseable objects have toplevel node Figure. It works as a container of one or more geometries (actual poseable objects), skeleton (a controller of those geometries) and possibly other node types.
Selecting the single geometry under imported figure opens the property page of Cr2 object. Here you can see a tree of actors and associated dials. The base V4 figure has only few morphs, but if you expand the tree and select head actor, you can access the lip sync dials, for example.

Khayyam build IK Chains automatically from model data - but does not set bone constraints. You can play with IK chains (and FK posing too) by selecting bone edit mode in main window.

NB! V4 figure has extra EyeBrow object, that partially covers the face. To turn this off, select the geometry node in document tree, select the middle Geometry property page from the notebook at right, scroll down and turn the visible checkbox off for 1_EyeBrow material.

2. Adding clothes

Clothes have to follow body position, so they are also poseable objects (of type cr2). To import clothing item, keep the main figure selected and open again Import Poser Dialog (or bring it up, if you did not close it). Select proper clothing item (it should appear in preview, if Khayyam can load it) and click Import. Unfortunately the free V4 base does not include clothes, so you have to buy these yourself or search for free ones. I am using free Bucketload 3D Sunny Bikini for current tutorial.

If you had the figure selected, the import options dialog has a bit different set of controls selected. Normally you want to keep the preselected values.

•  Create skeleton is unselected, because the figure already has skeleton.
•  Skin of selected mesh - it means, that it will be fully controlled by main figure skeleton.
•  Parent bone and anchor bone are set to the lowest common bone (actor) in the hierarchies of both objects.

Click Import and clothing item should be added to the figure.
NB! If the clothing item is built for a different base figure (V3, A3...) it is quite possible, that it does not "fit". Sometimes you can adjust it with morphs, but often this does not help. You can remove wrong objects by selecting corresponding geometries in document tree and clicking on trashcan image.
Repeat clothing import for as many items as you need (well - you do not need any, but to keep this tutorial work-safe, I'll add at least bra and panties).

V4 figure with bikinis loaded

As you can see, both the main figure and bikini are plain. We'll set material as the next step.

3. Loading materials

Predefined materials are either Pose files (pz2) or Material definition files (mc6). It is also possible to set materials by specifying texture files directly, but I'll skip this at moment (the procedure is the same, as in SBZ tutorial).
Materials are applied to geometry nodes - not the full figure. So in Document Tree Dialog, select the body geometry. On the property page, click the button Load Material... 
Materials are usually either under the Pose (older version) or Material (newer) subsection of library tree. You have to select correct material type - the ones for wrong object (clothes vs. body) do not work.

Library tree with material file selected

Click OK, and material will be imported. Usually the textures are huge, so depending on the speed of you computer and GPU it may take some time.
Material definitions are added as Pose nodes under Geometry nodes. There can be many material definitions - they are parsed from bottom to top - so it is, for example, possible to add makeup on top of body materials. To delete material definition, simply delete corresponding Pose node.
Repeat the same procedure for clothes - first select clothing geometry node and then click Load Material...  (of course you have to select appropriate material file for clothing).

4. Adding hair

There are 2 types of hair - poseable (cr2) and prop (hr2).
Adding cr2 hair is exactly the same as adding clothes - select main figure, choose hair object in Import Poser Dialog and import it as skin of selected mesh. Apply material just like for clothes.
Hr2 meshes do not have skeleton, thus they are imported as Poseable elements. Usually short hair is hr2, as it simply follows the movement of the head and does care about the neck and shoulders. But this will be shown in the next tutorial.

V4, bikinis and hair with materials applied

And this is it.
The next time I'll show, how to load poses, inject morphs and import Hr2 hair. Or you can try this yourself - it is not complicated at all, once you find the right place in document tree :D

Have fun!

Snapshot release 20110310

A new snapshot release 20110310 is available from SourceForge page as source tarball and precompiled Win32 binary.

• Fixed PNG export gamma so Pov-Ray rendered images have similar tone to screen
• Directional lights now cast shadows
• Fixed Poser cr2 joint order and pose loading
• Support for Yuusha models
• BVH export allows one to manually specify root bone

Also Sara-chan (included as demo model) got a little update - better face topology, cuter and more realistic mouth and thicker hair.

Sara Tween Girl version 1.1 (Blender render)

Included model has IK chains and constraints, so it can be used as a reference, how to set up these for other figures. Until I'll get time to write tutorial about it.

A new face topology of Sara-chan in Blender

Have fun!

Where to find free 3D models?

Even if it works for you, Khayyam is only as good as the 3D models you can insert into your scene. Thus I put together a small list of useful and/or interesting sites where you can find free or cheap 3D models. It does not pretend to be some sort of top 8 - there are many-many more websites, so you are free to suggest more.

A discus and neon tetras from Toucan Virtual Museum, rendered with POV-Ray

The places to go for models (in no particular order).

1. TurboSquid
This is probably the biggest resource of user-submitted 3D models in Internet, ranging from free or cheap class works to very professional and expensive characters and architectural models.

2. DAZ 3D
DAZ is the creator of both the professional 3D applications and the base human characters for Poser/DAZ Studio (Victoria, Michael and various derivatives). They have online store with lots of high quality models, some of them available for free (require registration still), including the starter versions of most of their human characters.

3. DAZ 3D forums
They have special sections for advertising free models. From there you can find links to some free hair and clothes to complement your figures.

4. Renderosity
For many this is The Internet Marketplace for 3D art. Huge amount of models for Poser/DAZ including many free ones. The prices seem to be a bit cheaper than in DAZ store. Registration required.

5. Toucan Virtual Museum
A small site that has some very nice free fish, flower and insect models, that are hard to find otherwise.

6. Archive 3D
More than 20 000 architectural models (mostly furniture) available fro download. No registration required.

7. Google 3D Warehouse
The companion site to Google SketchUp free modeling program. Big and growing selection of free user-created models.

8 Renderotica (Warning: Adult Content)
A must be site, if you want to render some steamy action. No free models, but otherwise good selection of characters, poses and accessories.


I have not tested them all, so I cannot tell, how much Khayyam compatible model formats are there.

Have fun! And do not forget to support the creators by purchase, donation or advertisement, if you find their models useful for you!