Improving Animations’ Key Frame Performance on the CPU

For my 3D Android RPG game Heroes Of Honesty( I was making 3D animated characters.

There are numerous ways to animate a 3D characters and one of the ways is to have an artist set animation key frames.

A key frame is a state of an object or bone of the character set in a specific time of the animation timeline. By setting many key frames you can animate the characters into all sort of pre made behaviors.

When drawing an animated character in a 3D game, you would select a specific time in the animation timeline and calculate the posture of the character in that specific time. The posture is then calculated by the nearest keyframes in the timeline and interpolate two adjacent key frames if there is no key frame at that specific time.

How would you find which key frame is the closest to the frame time?

Linear search

Since the keyframes are ordered from the earliest to the latest we can go from the beginning to the end, one step at a time, and stop when we find the first key frame that is bigger than our current frame time.

This sort of search has O(n) complexity and it is pretty slow when we have a lot of key frames.

We might have many key frames if our animation software bakes the keyframes for things such as Inverse Kinematics.

Binary search

We can do better than linear search.

Since our key frames are ordered in the time line from small to big, we can do a binary search.

The binary search algorithm always check half of the relevant key frames. If we know a specific key frame is bigger than our frame time then all the key frames above it are irrelevant for us. We then continue to check the second half of the first half(the quarter) we found is relevant and so on.

The following code is a binary search in C++:

	unsigned int
	Mesh::AnimationNode::CoreFindPosition (aiNodeAnim * n, unsigned int First, unsigned int Last, double t)
		if (First+1>=Last)
			return First;
		unsigned int Index = (Last+First)/2;
		if (n->mPositionKeys[Index].mTime==t)
			return Index;
		if (n->mPositionKeys[Index].mTime<t)
			return CoreFindPosition(n, Index, Last, t);
		return CoreFindPosition(n, First, Index, t);

For the binary search we get a complexity of O(log(n)).

Baked Search

We can do even better. Our game render rate is limited. Most games run at no more than 60 Frames Per Second. This means that at the very least the animation time steps would be 16.67 ms.

We can create an array that will be the size of the animation timeline divided by the rendering frame time(16.67 ms). This array will have indices to the nearest key frame to the frame time each entry represents.

Now in order to find the closest key frames we simply access one array cell that corresponds to the animation’s frame time and get the index of the closest key frame.

This algorithm is of O(1) complexity.

Full baking?

A character usually consists a hierarchy of objects that compose all the parts of the character. In order to animate the character we need to find each object’s relative position key frame, and then calculate its absolute position up to the root object.

Instead of baking indices of key frames in the baked search, we can bake the absolute position of the object in that specific time. Since the rendering FPS is limited, we can bake the absolute position dense enough so we won’t need to interpolate.

This will save us all the hierarchical calculation of the animation tree. However, this way we won’t be able to mix this specific animation with other animation or mix it with dynamic elements such as rag doll animation.