Thursday, June 24, 2010

Blending a Walk/Run cycle

My friend, Rory Aguilar, posed an interesting problem to me:

"Suppose you have a walk animation, and a run animation, and you want to blend them together in such a way that you can smoothly go from walking to running without the feet sliding all over the place."

(Rory is kind of girly, so Rory quotes are hilighted in pink.)

This is very interesting for character animation, since it becomes possible to smoothly vary the speed of a character, while maintaining realistic movement.

Let's assume some things about our underlying animation system:

1) it is possible to get the instantaneous pose on any frame, or intermediate frame, of a particular animation
2) it is possible to do this for multiple animations
3) it is possible to perform a weighted blend of the resulting poses on a per bone basis

Now, let's assume some things about the walk and the run animations:

1) both the walk and the run animations represent a single loop of the cycle
2) the walk animation does not need to have the same number of frames as the run animation. It will likely have many more frames.
3) the run animation does not need to cover the same amount of distance as the walk animation. It will likely cover a longer distance, since when you run you have a longer stride.
4) for now, we will assume that the footfalls happen at the same fraction, e.g. the right foot hits the ground 45% of the way throgh the animation on both animations.
5) The animations will contain translations off of the origin. In other words, we are not going to remove the translations off the origin, and then add them in after the fact.

Ok, we're ready to go. Let's dive on in.

Step 1 : define the blend parameter

We are going to define a blend parameter b, that defines how much we are walking or how much we are running. If b = 0, then we are walking. If b = 1, then we are running.

You can relate the blend parameter to the variable speed you desire your character to go. Before doing this you need to calculate the speed of the walk animation, and the speed of the run animation. To calculate the speed of an animation that has N frames, runs at 30 fps and has distances d measured in feet, you do the following

$v=\frac{d\,{\rm ft}}{N\,{\rm frames}}\frac{30\,{\rm frames}}{{\rm s}}=\frac{30d}{N}\frac{\rm ft}{\rm s}$

If you want the speed to be in units other than feet per second, then you can multiply this by an appropriate conversion factor. For instance, if you want to express the speed in miles per hour, then the speed becomes

$v=\frac{225d}{11N}\frac{\rm m}{\rm h}$

You can express the blend parameter in terms of the variable velocity, and the velocities of the walk and run animations as follows

$b = \frac{v - v_w}{v_r - v_w}$

Step 2 : unify the duration of the animations

When you are blending the two animations together, you wouldn't want to blend the beginning of the walk animation with the end of the run animation, because it would result in nonsense. However, the run animation is likely to end much quicker than the walk animation. What we would like to acheive is some type of temporal correspondence between the frames of the walk animation and the frames of the run animation. One way to acheive this is to slow down the run animation, so that it ends on precicely the same frame as the walk animation. The rate that acheives this is

$R=\frac{N_r}{T_w}$

This ratio represents the rate required to play the number of frames in the run animation Nr within the time it takes to complete a walk cycle Tw.

The time it takes to complete a walk cycle is

$T_w=\frac{N_w}{30\,{\rm fps}}$

So the rate is

$R=\frac{N_r}{N_w}30\,{\rm fps}$

This rate represents the rate of the run animation when the blend value b is equal to 0, i.e. we are in a full walk. For intermediate blend values, we not only need to slow down the run animation, we also need to speed up the walk animation. The blended rates for both animations are given as

$R_w=\left(b\frac{N_w}{N_r} + \left(1-b\right)\right)30\,{\rm fps}$

$R_r=\left(b + \left(1-b\right)\frac{N_r}{N_w}\right)30\,{\rm fps}$

If you plug in a value of b=0 into these equations, we see that the rate of the walk animation is 30 fps, and the rate of the run animation is exactly what we had calculated before. If we plug in a value of b=1 we see that the run animation rate is now 30 fps, and the rate of the walk animation is modified.

You can use these rate equations to calculate the animation frame that should be evaluated, given the time delta of the loop Δt measured in seconds, and the animation frame evaluated on the previous loop.

$F_n=F_{n-1} + \left(R_x\right)\left(\Delta t\right)\left(30\,{\rm fps}\right)$

Using this calculation, you should be able to vary the value of b from one loop to the next, and still maintain temporal correspondence between the frames of the two animations, e.g. both animations should always cycle on the same loop, and the footfalls should always occur at the same time.

Step 3 : unify the distance traversed by the animations

The footfalls of the independent animations are now happening at the same time, but the animations are not in the same place when this happens. As stated before, the stride of a run animation is probably longer than that of a walk animation.

To synchronize the position of the charachter across the two animations, I will define a "target bone". This bone can be used to define the floor plane, the position of the character, the forward direction, and the up direction, on each frame of the animation.

We will need to know the full joint matrix for the target bone (T), both in animation space TA, and in world space TW. These two are related by the animation origin AO through matrix multiplication

$\mathbf{TW}=\left(\mathbf{TA}\right)\,\left(\mathbf{AO}\right)$

Each animation will have a unique independent animation origin, and the value of TA is the animation space representation of the target bone, evaluated at the frame determined by the rate calculated in the previous section. Therefore each animation will have a unique result for the value of TW

As we blend from one animation to the other, we want to transition which animation controls the world space value of the target bone matrix. To do this, we will blend the world space representation of the target bone.

$\mathbf{TW}_b={\rm blend}\left(\mathbf{TW}_w, \mathbf{TW}_r, b\right)$

Blending a matrix is kind of tricky. If the matrix is composed of only translates and rotates, it is possible to decompose the matrix into a translate vector, and a rotation quaternion, both of which can be blended, and then recomposed back into a matrix.

If we want the individual animations target bone to be the same as the blended target bone in world space, we will need to move the respective animation origins.

Using the blended world space values of the target bone matrix, we can determine the incremental offset that needs to be applied to each of the animation origins. Use the formula

$\mathbf{TW}_b=\left(\mathbf{TW}_x\right)\,\left(\mathbf{\Delta}_x\right)$

And solve for Δ.

$\mathbf{\Delta}_x=\left(\mathbf{TW}_x\right)^{-1}\,\left(\mathbf{TW}_b\right)$

Now apply Δ to each animation origin to incrementally update it.

$\mathbf{AO}_x =\left(\mathbf{AO}_x\right)\,\left(\mathbf{\Delta}_x\right)$

Finally, you need to find the animation origin for the blended animation. This can be done using the same blend function that was used for the world space target bone matrix.

$\mathbf{AO}_b = {\rm blend}\left(\mathbf{AO}_w, \mathbf{AO}_r, b\right)$

You are tracking and updating the animation origins of the walk and run animations independently, but the origin you use to actually position the animation in world space is the blended origin.

Using this method, the blend parameter will determine which animation has more control over the actual world space position of the character. If we are in a full walk, then the run origin will continuously move backward, in order to conform to the position set by the walk animation. When we are in a full run, the walk animation origin will continuously move forward to conform to the position set by the run animation.

Step 4 : The next level

We should now have a walk/run blend, with the only constraint on the animator being that the footfalls happen at the same fractional intervals on both animations. However, placing constraints on animators never turns out well in practice, so let's discuss how we might remove the "fractional interval" constraint on footfalls.

Let's say we break the animation up into a set of events:

Presumably, we start the cycle with the left foot down, and the right foot stepping forward. On some frame, the right foot becomes stationary relative to the ground. Later the left foot becomes stationary relative to the ground, and finally the animation ends.

We can split the animation up into these four segments. Both the walk and the run animations should have these segments, and they should occur in the same order. We can either visually determine which frame each footfall happens on, and tag it, or we can have an automated process determine this for us. Either way, let's assume we know the exact number of frames in each of the four sub-intervals of each animation.

The only portion of our process that needs to be modified is the rate calculation. Now, instead of requiring that both animations end at the same time, we require that they reach the first event at the same time.

After reaching the first event, we recalculate the rates using the number of frames between the first and second events.

After reaching the second event, we recalculate the rates using the number of frames between the seond and third events.

After reaching the third event, we recalculate the rates using the number of frames between the third and fourth events.