Earlier I wrote a post about some research I have been doing into how to produce realistic movement for characters. After a large amount of implementation work, trying to understand papers and bug fixing I have some progress to share.

In the previous post I used relatively simple inverse kinematics (IK) to place the feet at the correct positions. The approach that I used only looked a small distance into the future and the past when determining the IK targets and weights so the results were ok, but not that good. Based on the paper “Planning Biped Locomotion using Motion Capture Data and Probabilistic Roadmaps” I have now implemented a higher quality technique which adjusts both the position and rotation of the character as well as the rotations of the character’s bones. This is done by first simulating the movement of the character and at every point in time and calculating the rotations of the bones if IK would have been applied. Then b-splines are used to produce a fit to this data so that the result is a collection of b-splines that determine how much the rotations of the bones (or the position of the character) should be modified when playing the animations. B-splines can have varying number of control points or “knots” and the higher the number of knots, the more detail they can represent.
The approach that the paper and I use is to first fit the data to splines with a very low number of knots, run the IK algorithm again when the adjustments from that spline have been added and then add another b-spline with more knots. This produces a hierarchical b-spline that can both generalize over stretches with few data points as well as capturing the smaller details. In the image below you can see 4 levels of a hierarchical b-spline. The first level in blue only captures very rough information about the points, but subsequent levels add more detail. Note that the black points are the input points for the curve fit, not any kind of control points for the b-splines.

The benefit of using hierarchical b-splines over the earlier approach is that they make it much easier to spread information further back and forwards in time so that the character can anticipate where a foot needs to be placed and adjust its pose accordingly.
The particular IK technique that is used also modifies the position of the character. Most IK techniques keep the position of the character fixed and only modify the rotations of the bones, but by allowing the position of the character to be modified slightly a higher quality movement can be achieved. The downside is that this makes the IK algorithm significantly slower (it takes around 200 ms to process all the IK for the path in the video below). It will use a normal IK technique that does not modify the position of the character and then it will try to minimize the deviation of the bone rotations from the original animation by using conjugate gradient descent where it can for example move the character slightly if that makes it have to adjust the bone rotations less. In my current implementation this step takes the majority of the time by a very large margin, however I have some thoughts on how to optimize it. Firstly it uses numerical gradients at the moment which works, but it is prone to floating point errors and it requires an evaluation of the IK algorithm for each parameter that we are optimizing over (in my current implementation I use x y and z coordinates of the character as well as the rotation of the character around the y axis). A better approach would be to use automatic differentiation to calculate the derivative explicitly. Automatic differentiation is a bit tricky to implement correctly however. Another thought I had was to adjust the relatively new IK algorithm FABRIK so that it will move the position of the character instead of keeping it fixed as is normally the case. I have yet to test if this is a viable approach.

See the video below for the results.