skeleton-based animations on Android with OpenGL

Written by Sébastien Carceles

Saturday, 27 February 2010 12:59

This article describes a way to make skeletal animations in OpenGL for Android with Java.

It is necessary to well understand the theory before working on the implementation; the risk is to find the task so difficult that the best solution is giving up. However, the principle is easy! You just have to take the time to understand it.

In this article, I will explain my understanding of this technique, and my implementation. Other ways are possible and I encourage you to read some other articles to improve your comprehension and build your own implementation.

To understand this technique, I spent a lot of time reading documentation in books, websites and forums. I didn’t find any documentation about my problem (Android + OpenGL + Skeletal Animation), but all this reading helped me to see all I had to understand. You will find all the references at the end of the article.

To finish, this article is illustrated with code and sometimes Java code.

Note: mistakes could be present in the article, do not hesitate to contact me if you find any.

Prerequisites

To understand this article and carry out the skeletal animations, it is better to have prior knowledge of some subjects:

- knowing OpenGL and specifically knowing the use of the basic primitives to display volumes, rotate them, make a translation, dimensioning, etc.

- having some mathematical basis, matrix and vectors multiplication, and eventually the quaternion. (I know it sounds scary but it’s not so complicated compared with our need).

- knowing Android if the objective is to implement skeletal animations on this platform ; if it’s for another platform, even for other languages, the theory and the implementation in this article are still pertinent.

Definitions

Frame: step of a model animation

Keyframe : key step in an animation, it means a very important step in a specific animation (it’s a specific frame)

Mesh : 3D model composed of a set of polygons. Polygons are generally triangles, so composed of three apexes. In our case, an apex has 3 coordinates (x, y, z) and 2 texturing coordinates (u, v).

Skeleton : hierarchical tree of points (called Joints), which represent the model skeleton ; the joints are the skeleton’s articulations.

Gazillion : means « big quantity of ». Definitely more than a dozen. For instance: “the development of this game needs gazillions hours of work”.

Theory

The mesh animation consists in moving apexes with time. To do that, 2 methods are possible:

- Animation by frame: for each step of the animation, we export the entire model. In the end, we have a set of models that we display successively to give the illusion of movement, as in a movie.

- Skeletal animation: we separate the mesh and the skeleton; only the skeleton is animated. It’ll control and facilitate the movement of apexes.

In this last case, for each step, we only animate the skeleton and we calculate the new positions of the apexes of the mesh. There are several advantages to it:

- We don’t duplicate apexes for each step of the animation, so we gain memory space,

- We can animate models with the skeleton more easily,

- During the mesh rendering, we can calculate its animation on the fly.

Examples

Before going further, let’s take a look at two examples: one of a skeleton and one of a mesh to make things clear.

In order to avoid overloading this article with huge examples (xml is very wordy), I have voluntarily truncated most of the files. For your information, the format in question is OgreXML, one which allows to stock in two separate files:

- The mesh, with all its apexes and links to skeleton (file mesh.xml),

- The skeleton, with its hierarchy and animations (file skeleton.xml).

In these examples we can already see important notions.

In the skeleton, joints (hereby named bones) are already hierarchically organized. When we observe a joint, regardless of the rest, the indicated transformations (position, rotation, scale…) are the ones to be applied to move the local marker from its parent to itself. Those transformations take the form of a matrix that we will call “relative matrix”. This matrix indicates the transformations of a joint “relatively” to its parent.

Thus, to draw a given joint, you have to apply all the transformations of its antecedents so as to move the local marker from the origin to itself. This set of transformations, for a given joint, take the form of a matrix that we will call “absolute matrix». This matrix allows moving the local marker from the origin to the joint.

One can also note the animation structure: key frames indicate, for every joint, the extra transformations to be applied in order to draw the joint while the animation is at this step. Those transformations are relative to the joint original position and in the form of a matrix too.

These files stock the position of both skeleton and mesh at the time they were linked together. We call this pose, the “reference pose”. Each apex of the mesh is linked to one or several joints of the skeleton, with various levels of importance. It consists in notions of “assignment” and “weight”, about which we’ll speak again later.

The mesh is encoded according to the local marker to origin. Animations are encoded according to the reference pose of the skeleton. To animate the mesh, it’ll be needed to express it in accordance with the marker and the hierarchy of this reference pose, as if to apply the inverse transformations of the reference pose before applying transformations of an animation n. They take the form of a matrix, so-called “inverse”, which is the inverse of the absolute matrix for each joint within its reference pose.

We’ll get back to these notions, in details a little bit later.

Skeleton: Reference Pose

The skeleton is a hierarchical tree of joints. There is a root joint and every other joints are its children or descendants of its children.

For instance, the root could be the top of the head. It has one child: the neck. This joint has three children: the left shoulder, the right shoulder and the torso. The left shoulder has one child: the left elbow, which itself has a child: the left wrist and so on and on. This example is simplified of course; generally a full skeleton is composed of twenty to forty joints.

See a joint as an articulation, related to its parent. A joint is composed of a position, a rotation and sometimes of a scale. In pseudo-code, it produces an object Joint:

Joint:

- position (tx, ty, tz) : float

- rotation (qx, qy, qz, qw) : float

- scale (sx, sy, sz) : float

- parent: Joint

- children: Joint[]

One can see the appearance of a quaternion: the rotation. The quaternion is a mathematical object who describes a rotation of an angle qw in accordance with the axis (qx,qy,qz) of the local marker. It’s a very convenient object as we’ll see further on.

Knowing all of that, how to draw a skeleton? Let’s take the following recursive function, still in pseudo-code:

draw(Joint j) {

glPushMatrix();

glTranslate(j.tx, j.ty, j.tz);

glRotate(j.qw, j.qx, j.qy, j.qz);

glScale(j.sx, j.sy, j.sz);

drawAPoint();

foreach(Joint child : children) {

draw(child);

}

glPopMatrix();

}

Drawing the skeleton is quite simple: with each loop cycle, you simply have to call on the draw() function; giving it, as a parameter, the root joint of the skeleton.

Let’s apply it to our simple example mentioned earlier: the root is the joint “head”. The first call to the function moves the local marker to this point by translation then makes a rotation and adjust to scale. A point is drawn. The “head” only child is “neck”. Thus the function is called “neck” for this joint: the translation moves the local marker to the right place. Then we apply rotation then scale etc…

Recursively, we draw our skeleton in its reference pose (bind pose) that is to say the skeleton pose at the time when the mesh was linked to it.

Skeleton: animation

And now, how will we animate this skeleton?

The principle is quite simple: for each joint, at a given time of the animation, we apply an extra transformation relatively to the reference pose. A transformation is composed of a translation, a rotation and eventually of a scale.

From an object point of view, a joint contains one or more animation. An animation contains one or more transformation to apply to this joint. Let’s call these transformations, frames. In pseudo-code:

Anim :

- duration : long

- frames : Frame[]

Frame :

- time : long

- position (tx, ty, tz) : float

- rotation (qx, qy, qz, qw) : float

- scale (sx, sy, sz) : float

One can see the appearance of the notion of time. For instance, an attack animation will last 2.25 seconds. In the file containing the skeleton, the animation is composed of four frames, at 0, 0.75, 1.5 and 2. These frames, of special importance, are called key frames.

Let’s assume that we have an ongoing animation. How to take it into account in our drawing code?

draw(Joint j) {

glPushMatrix();

glTranslate(j.tx, j.ty, j.tz);

glRotate(j.qw, j.qx, j.qy, j.qz);

glScale(j.sx, j.sy, j.sz);

if(j.anim != null) {

Frame f = j.anim.frameCurrent;

glTranslate(f.tx, f.ty, f.tz);

glRotate(f.qw, f.qx, f.qy, f.qz);

glScale(f.sx, f.sy, f.sz);

}

drawAPoint();

foreach(Joint child : children) {

draw(child);

}

glPopMatrix();

}

Of course, between two drawings, don’t forget to update the animation to pass to the next frame if necessary.

Frames Interpolation

If for a given joint, we just let the key frames unfold one after another, we quickly understand that there will be a jerk effect. Thus we’ll have to calculate the intermediary frames in order to get a frame every 40 milliseconds, that is to say 25 frames per second. To interpolate the different frames, we use a simple linear interpolation in-between the animation parameters.

Let’s take two key frames, at time T0 and T5. We wish to calculate the frames at time T1, T2, T3 and T4. For this, for every property of Frame (tx, ty, tz, qx, qy, qz, qw, sx, sy, or sz), we call the following method:

interpoler(float init, float final, float i, float nbFrames) : float {

return init + i * (final - init) / nbFrames;

}

For instance, to calculate tx1, we use this formula: tx1 = tx0 + 1 * (tx5 - tx0) / 6.

This solution is quite satisfying if we have sufficiently close key frames. A better solution, in case of rotation (qx, qy, qz, qw) is to apply a spherical linear interpolation. That’s beyond the scope of this article. Look for “quaternion+slerp” on Google, several documentations explain this method.

Skeleton: approach by matrices

There is another way of drawing the skeleton which, as we’ll see thereafter, is very convenient to move the mesh positions: the approach by matrices.

As you already know, the first step of the OpenGL pipeline is making the choice of the matrix to use: projection or model view. In the latter case, we often start a rendering by loading the identity matrix: glLoadIdentity(); then each transformation (glTranslate, glRotate or glScale)consist in multiplying this matrix model view by the corresponding transformation matrix.

For the skeleton, if we don’t want to draw it, we can do this matrix operation “by hand” and conserve this result matrix for each joint. This matrix will allow us to move the mesh position but also to draw the skeleton if loaded in OpenGL.

With each refresh, there are two steps: one to calculate the matrix for each joint and one to draw the skeleton. For this, let’s extend our Joint class so as to add the useful matrices:

Joint :

- position (tx, ty, tz) : float

- rotation (qx, qy, qz, qw) : float

- scale (sx, sy, sz) : float

- parent : Joint

- children : Joint[]

- absolute matrix : float[16]

- relative matrix : float[16]

In fact, there are two matrices. The relative matrix is the matrix of the transformations to apply in order to get to the current joint from its parent. The absolute matrix represents all the transformations to apply to get from the point 0, 0, 0 to the current joint.

How to calculate these matrices? In Java:

private static final float[] IDENTITE = { 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1 };

public void calculateMatrix() {

float[] absParent = this.parent == null ? IDENTITE : this.parent.absolute;

this.relative = new float[16];

Matrix.setIdentityM(this.relative, 0);

Matrix.translateM(this.relative, 0, tx, ty, tz);

Matrix.rotateM(this.relative, 0, qw, qx, qy, qz); // beware, the angle qw must be in degrees

Matrix.scaleM(this.relative, 0, sx, sy, sz);

this.absolute = new float[16];

Matrix.multiplyMM(this.absolute, 0, absParent, 0, this.relative, 0);

for (Joint e : this.children) {

e.calculateMatrix();

}

We can see several interesting things:

-the identity matrix (if you don’t know what an identity matrix is, take a look at Wikipedia)

-the android.opengl.Matrix class is used to solve matrix operations.

This class is often used by the Android OpenGL wrapper. It allows solving common operations on 4x4 matrices, such as multiplication or inversion, but also operations peculiar to OpenGL: translation, rotation, scale. I advise you to read this class documentation to understand the aforementioned code.

What is happening in this method?

We start by retrieving the absolute matrix of the parent joint, if any. If not, it will be the identity matrix (for the root joint). Then, we build the relative matrix, while applying these following operations to it:

1 – Defining it as being the identity

2 – Translating

3 – Applying a rotation

4 – Putting it up to scale

All this is done by matrices multiplications. The Matrix class offers convenient methods to solve these operations.

Finally, we calculate the absolute matrix of the current joint: it’s the result of a multiplication between the absolute matrix of the parent and the relative matrix of the current joint. Of course, we’re still in a recursive context and we don’t forget to call the same method for each child of the current joint.

Once the matrices are calculated, we can use them to draw the skeleton with the function glLoadMatrix().

Two additional comments: the matrix is hereby calculated with each refresh, producing gazillions of useless operations. It’s possible to calculate it once and for all within the builder of Joint, for instance.

In the code above, an eventual ongoing animation is not taken into account! A better code would be:

private static final float[] TMP = new float[16];

public void calculateMatrix() {

float[] absParent = this.parent == null ? IDENTITY : this.parent.absolute;

float[] relAnim = this.anim == null ? IDENTITY : this.anim.getFrame().relative;

Matrix.multiplyMM(TMP, 0, absParent, 0, this.relative, 0);

Matrix.multiplyMM(this.absolute, 0, TMP, 0, relAnim, 0);

for (Joint e : this.children) {

e.calculateMatrix();

}

If an animation is ongoing, we recover the relative matrix of its current frame. Otherwise, we use the identity matrix. To calculate the absolute matrix of the current joint, we start as earlier by multiplying the parent absolute matrix by the relative matrix of the current joint, but this time retaining the result in a temporary matrix. Then, we multiply this result by the relative matrix of the ongoing animation current frame. This is our absolute matrix for the current joint.

In other words: to place the current joint in an absolute manner, I use the transformations (absolute) of the parent, I apply both the transformations (relative) of the current joint on it and also the transformations (relative) of the ongoing animation.

One last detail: in our example, a frame also contains a relative matrix. But relative to what exactly? In the first approach, we were applying the transformation from the current frame to the current joint in order to place it correctly to be drawn. A frame contains transformations to apply to the corresponding joint, relatively to its reference pose. We can calculate this matrix from these transformations, as if for the joint:

1 - we define it to the identity

2 - we apply the translation

3 - we apply the rotation

4 – we apply the scale

These operations can be done at once, within the frame builder for instance, as for the joint.

Mesh

Having a skeleton is good. Having a mesh is better. Now that we know how to calculate the transformations matrices to apply to each joint, we can use them to move the mesh position. Assuming that you already know how to display a mesh for it is once again beyond the scope of this article… if not, I advise you to Google it as usual.

In order to move the mesh positions, we calculate with each refresh the position of each apex composing it. Let’s take the following Mesh class:

Mesh :

- apexes : Apex[]

- faces : int[][]

It’s using the Apex class :

- position (px, py, pz) : float

- texture coordinates (u, v) : float

- assignments : int[]

- weight : float[]

I’m voluntarily skipping over the “face” mesh class. If you already know how to render a mesh, you know what it means.

Assignments

The Apex class is a bit more interesting. In addition to the usual fields for the original position and texture, there are two notable fields: “assignment” and “weight”. As previously explained, each apex is linked to one or several skeleton joints. Generally, an apex is linked to four points top. Assignments are the indexes of the joints to which the apex is linked.

To know the relative impact of these joints on the apex, we use a weighting system: each assignment is related to a weigh. The sum of all weights of an apex must equal 1. For instance, look at the following apex:

Apex 5

- assignments : [3, 17, 28]

- weights : [0.3, 0.3, 0.4]

This indicates that joints 2, 17 and 28 will have an impact on the apex position with weights of 0.3, 0.3, and 0.4, respectively.

Calculating position

With each refresh, in order to move the mesh positions, we need to calculate the apexes new positions. To do so, we’ll need two extra matrices for each joint:

-The inverse matrix of the joint absolute matrix, in its reference pose, that we’ll call « inverse »,

- The resulting matrix of the multiplication between the inverse matrix and the absolute matrix at a given time. We’ll call it the “final matrix”.

In other words: inverse_P0 = inv(absolute_P0) (in the reference pose)

And: final_Pi = inverse_P0 X absolute_Pi (at any given time)

In a case where the apex is linked to a single joint, the operation to calculate the apex position is to multiply its position vector by the joint absolute matrix, then by the inverse of this absolute matrix. Consider the inverse as a cancellation.

About the reference pose (no ongoing animation), we multiply the apex position by a matrix then by its inverse thus canceling the first multiplication. In a reference pose there is no mesh transformation. The apex position doesn’t change.

However, if there is an ongoing animation:

- The multiplication by the absolute matrix is like applying the transformations of the ongoing animation into the skeleton repository,

- Multiplication by the inverse of the reference pose absolute matrix means returning to the mesh repository.

To sum things up under the form of an operation:

New position = position X absolute X inverse of absolute in its reference pose.

What is happening when the apex got more than one assignment? We calculate the new position for each assignment and we balance it according to the assignment weight. The apex new position is the result of the sum of the new positions.

Now we’ll try to put it into code. To begin with, we need to calculate the inverse matrix of each joint absolute matrix, in its reference pose

public void calculateMatrixInverse() {

float[] absParent = this.parent == null ? IDENTITY

: this.parent.absolute;

Matrix.multiplyMM(this.absolute, 0, absParent, 0, this.relative, 0);

Matrix.invertM(this.inverse, 0, this.absolute, 0);

for (Joint e : this.children) {

e.calculateMatrixInverse();

}

We call this method once after having built/loaded the skeleton.

Then we need to modify the joint matrices calculation method in order to calculate the final matrix.

public void calculateMatrix() {

float[] absParent = this.parent == null ? IDENTITY

: this.parent.absolute;

float[] relAnim = this.anim == null ? IDENTITY

: this.anim.getFrame().relative;

Matrix.multiplyMM(TMP, 0, absParent, 0, this.relative, 0);

Matrix.multiplyMM(this.absolute, 0, TMP, 0, relAnim, 0);

Matrix.multiplyMM(this.final, 0, this.absolute, 0, this.inverse, 0);

for (Joint e : this.children) {

e.calculateMatrix();

}

In facts, this is the same as the previous code but with an extra line: the calculation of the final matrix, result of the multiplication of the absolute matrix (at a given time) by the absolute inverse matrix in its reference pose.

Finally we can calculate the apexes new position in the Mesh class, with each refresh:

public FloatBuffer createBufferSommets() {

Joint[] joints;

int nbJoints;

float[] weightss, m;

float p, x, y, z;

Apexes;

int nbApexes = this.apexes.length;

ByteBuffer apexesByteBuf = ByteBuffer.allocateDirect(nbApexes * 3 * 4);

apexesByteBuf.order(ByteOrder.nativeOrder());

FloatBuffer apexesBuf = apexesByteBuf.asFloatBuffer();

float[] v = new float[nbApexes * 3];

for (int is = 0; is < nbApexes; is++) {

s = this.apexes[is];

joints = s.getJoints();

nbJoints = joints.length;

weightss = s.getWeights();

x = s.getPx();

y = s.getPy();

z = s.getPz();

for (int i = 0; i < nbJoints; i++) {

p = weightss[i];

m = joints[i].getFinal();

v[is * 3] += (x * m[0] + y * m[4] + z * m[8] + m[12]) * p;

v[is * 3 + 1] += (x * m[1] + y * m[5] + z * m[9] + m[13]) * p;

v[is * 3 + 2] += (x * m[2] + y * m[6] + z * m[10] + m[14]) * p;

}

apexesBuf.put(v);

apexesBuf.position(0);

return apexesBuf;

}

We start by declaring some variables then we create a float buffer containing the apexes new positions so as to send it subsequently to the graphic card. Its size is: number of apexes x 3 x 4. 3 float by apex and a float is encoded on 4 bytes.

We also prepare a chart, v, which is going to stock the apexes new positions.

Then we can start the apexes course. For each apex, we take the joints assigned by s.getJoints(). This is comparable to our aforementioned “assignment” chart except that it directly stocks joints references and not only their indications

We also stock within variables (x, y, z) the original apex position.

For each joint (that is to say for each assignment) we do the following calculation : nvPosition+=positionOrigin X final Matrix X corresponding assignment weight. Given that the final matrix is the result of the multiplication between the joint instant absolute matrix and the inverse of its absolute matrix in its reference pose, we can see clearly now the principle explained above: in order to calculate an apex's new position, we multiply it's origin position by the joint's absolute matrix, then by the inverse of it's absolute matrix in reference position, finally we weight according to the assignment.

Thus, once we've checked all assignments, the table v contains the new position of the apex. We can move on to the next apex.

We could have used the class « matrix » to have this multiplication done, but doing the job “by hand” allows, in this case, to optimize the calculation, which is not negligible if we consider we will re-calculate the position of all of the apexes for each refresh,

Once this job done, we can render the mesh using the new position of the apexes,

File formats

Several file formats allow the separation of the mesh and skeleton, sometimes the skeleton's animation too, There is the format created by MilkShape, very readable and easy to understand for developers, but sometimes MilkShape is not sufficient for 3D modelers. There is also the MD5 format used by Doom 3, which is very readable too and easy to process. Finally we can mention Collada, which is very wordy but really well documented and has the advantage of being in XML.

In the context of Runes, we chose the OgreXML format. It is the XML version of the format used by the Ogre engine. It allows modelers to work with their favorite software and to export their work thank to OgreMax plugin. For each export, this plugin creates two files :

.mesh.xml containing the mesh
.skeleton.xml containing the skeleton

In this article, we will not go any further in the study of the different formats. The choice of a particular format depends a lot of the context : what tools you are using, how you use them, where you want to go, your workflow...

However, here are a few Android related eflection

The <XML format is easy to read whatever the context, on Android, you can read XML by simply placing it in your resources' xml folder. Unfortunately, this method is not advised if you manipulate large files (which is often the case with skeletons and meshes), for a simple reason : loading times are too long. A .mesh.xml file for a character made of 1000 triangles is over 25000 lines, It's 40 joints skeleton with 5 animations will be between 5000 and 15000 lines. This takes a long time to parse.

I would advise going through this a first time, in a different project, in order to transform those XML files in binaries, without any flourish. Doing so will let you use files of a few dozen Ko instead of Mo sized files. You can get this job done easily with Java tools like DataOutputStream. Place then your binaries in the raw folder of your Android project resources. You will now easily open an input stream on it thanks to the openRawResource(int id) method.