## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

No credit card required

# Optimizing Animation with Vertex Skinning

Typically, blending refers to color blending, discussed in Chapter 6. Vertex blending (also known as vertex skinning) is an entirely different kind of blending, although it too leverages linear interpolation.

First, a disclaimer, this is a chapter on optimization, and yes, vertex skinning is an optimization—but only when performed on the GPU. Generally speaking, vertex skinning is more of a technique than an optimization. Put simply, it makes it easy to animate “rounded” joints in your model.

For example, let’s go back to the stick figure demo, originally presented in Rendering Anti-Aliased Lines with Textures. Figure 9-4 shows a comparison of the stick figure with and without vertex skinning. (Usually skinning is applied to 3D models, so this is a rather contrived case.) Notice how the elbows and knees have curves rather than sharp angles.

The main idea behind GPU-based skinning is that you need not change your vertex buffer during animation; the only data that gets sent to the GPU is a new list of model-view matrices.

Yes, you heard that right: a list of model-view matrices! So far, we’ve been dealing with only one model-view at a time; with vertex skinning, you give the GPU a list of model-views for only one draw call. Because there are several matrices, it follows that each vertex now has several post-transformed positions. Those post-transformed positions get blended together to form the final position. Don’t worry if this isn’t clear yet; you’ll have a deeper understanding after we go over some example code.

Skinning requires you to include additional vertex attributes in your vertex buffer. Each vertex is now bundled with a set of bone indices and bone weights. Bone indices tell OpenGL which model-view matrices to apply; bone weights are the interpolation constants. Just like the rest of the vertex buffer, bone weights and indices are set up only once and remain static during the animation.

The best part of vertex skinning is that you can apply it with both OpenGL ES 2.0 (via the vertex shader) or OpenGL ES 1.1 (via an iPhone-supported extension). Much like I did with bump mapping, I’ll cover the OpenGL ES 2.0 method first, since it’ll help you understand what’s going on behind the scenes.

## Skinning: Common Code

Much of the prep work required for vertex skinning will be the same for both OpenGL ES 1.1 and OpenGL ES 2.0. To achieve the curvy lines in our stick figure, we’ll need to tessellate each limb shape into multiple slices. Figure 9-5 depicts an idealized elbow joint; note that the vertices in each vertical slice have the same blend weights.

In Figure 9-5, the upper arm will be rigid on the left and curvy as it approaches the forearm. Conversely, the forearm will curve on the left and straighten out closer to the hand.

Let’s define some structures for the rendering engine, again leveraging the vector library in the appendix:

```struct Vertex {
vec3 Position;
vec2 TexCoord;
vec2 BoneWeights;
unsigned short BoneIndices;
};

typedef std::vector<Vertex> VertexList;
typedef std::vector<GLushort> IndexList;
typedef std::vector<mat4> MatrixList;

struct Skeleton {
IndexList Indices;
VertexList Vertices;
};

struct SkinnedFigure {
GLuint IndexBuffer;
GLuint VertexBuffer;
MatrixList Matrices;
};
```

The `Vertex` structure is a POD type that defines the layout of the vertex buffer.

The `Skeleton` structure encapsulates a relatively small set of points that make up an animated “stick figure.” We won’t be sending these points to OpenGL: it’s for internal purposes only, as you’ll see.

The `SkinnedFigure` structure encapsulates the data that we’ll send to OpenGL. It contains handles for the static VBOs and a list of matrices that we’ll update at every frame.

Given a `Skeleton` object, computing a list of model-view matrices is a bit tricky; see Example 9-6. This computes a sequence of matrices for the joints along a single limb.

Example 9-6. Generation of bones matrices

```void ComputeMatrices(const Skeleton& skeleton, MatrixList& matrices)
{
mat4 modelview = mat4::LookAt(Eye, Target, Up);

float x = 0;
IndexList::const_iterator lineIndex = skeleton.Indices.begin();
for (int boneIndex = 0; boneIndex < BoneCount; ++boneIndex) {

// Compute the length, orientation, and midpoint of this bone:
float length;
vec3 orientation, midpoint;
{
vec3 a = skeleton.Vertices[*lineIndex++].Position;
vec3 b = skeleton.Vertices[*lineIndex++].Position;
length = (b - a).Length();
orientation = (b - a) / length;
midpoint = (a + b) * 0.5f;
}

// Find the endpoints of the "unflexed" bone
// that sits at the origin:
vec3 a(0, 0, 0);
vec3 b(length, 0, 0);
if (StickFigureBones[boneIndex].IsBlended) {
a.x += x;
b.x += x;
}
x = b.x;

// Compute the matrix that transforms the
// unflexed bone to its current state:
vec3 A = orientation;
vec3 B = vec3(-A.y, A.x, 0);
vec3 C = A.Cross(B);
mat3 basis(A, B, C);
vec3 T = (a + b) * 0.5;
mat4 rotation = mat4::Translate(-T) * mat4(basis);
mat4 translation = mat4::Translate(midpoint);
matrices[boneIndex] = rotation * translation * modelview;
}
}
```

Compute the primary model-view, which will be multiplied with each bone-specific transform.

Fill the columns of a change-of-basis matrix; to review the math behind this, flip back to Another Foray into Linear Algebra.

Translate the bone to the origin, and then rotate it around the origin.

Translate the bone to its current position.

Combine the primary model-view with the rotation and translation matrices to form the final bone matrix.

## Skinning with OpenGL ES 2.0

Example 9-7 shows the vertex shader for skinning; this lies at the heart of the technique.

Example 9-7. Vertex shader for vertex skinning

```const int BoneCount = 17;

attribute vec4 Position;
attribute vec2 TextureCoordIn;
attribute vec2 BoneWeights;
attribute vec2 BoneIndices;

uniform mat4 Projection;
uniform mat4 Modelview[BoneCount];

varying vec2 TextureCoord;

void main(void)
{
vec4 p0 = Modelview[int(BoneIndices.x)] * Position;
vec4 p1 = Modelview[int(BoneIndices.y)] * Position;
vec4 p = p0 * BoneWeights.x + p1 * BoneWeights.y;
gl_Position = Projection * p;
TextureCoord = TextureCoordIn;
}
```

Note that we’re applying only two bones at a time for this demo. By modifying the shader, you could potentially blend between three or more bones. This can be useful for situations that go beyond the classic elbow example, such as soft-body animation. Imagine a wibbly-wobbly blob that lurches around the screen; it could be rendered using a network of several “bones” that meet up at its center.

The fragment shader for the stick figure demo is incredibly simple; see Example 9-8. As you can see, all the real work for skinning is on the vertex shader side of things.

Example 9-8. Fragment shader for vertex skinning

```varying mediump vec2 TextureCoord;
uniform sampler2D Sampler;

void main(void)
{
gl_FragColor = texture2D(Sampler, TextureCoord);
}```

The ES 2.0 rendering code is fairly straightforward; see Example 9-9.

Example 9-9. ES 2.0 Render method for vertex skinning

```GLsizei stride = sizeof(Vertex);
mat4 projection = mat4::Ortho(-1, 1, -1.5, 1.5, -100, 100);

// Draw background:
...

// Render the stick figure:
glUseProgram(m_skinning.Program);

glUniformMatrix4fv(m_skinning.Uniforms.Projection, 1,
GL_FALSE, projection.Pointer());

glUniformMatrix4fv(m_skinning.Uniforms.Modelview,
m_skinnedFigure.Matrices.size(),
GL_FALSE,
m_skinnedFigure.Matrices[0].Pointer());

glBindTexture(GL_TEXTURE_2D, m_textures.Circle);
glEnable(GL_BLEND);
glBlendFunc(GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA);

glEnableVertexAttribArray(m_skinning.Attributes.Position);
glEnableVertexAttribArray(m_skinning.Attributes.TexCoord);
glEnableVertexAttribArray(m_skinning.Attributes.BoneWeights);
glEnableVertexAttribArray(m_skinning.Attributes.BoneIndices);

glBindBuffer(GL_ELEMENT_ARRAY_BUFFER, m_skinnedFigure.IndexBuffer);
glBindBuffer(GL_ARRAY_BUFFER, m_skinnedFigure.VertexBuffer);

glVertexAttribPointer(m_skinning.Attributes.BoneWeights, 2,
GL_FLOAT, GL_FALSE, stride,
_offsetof(Vertex, BoneWeights));
glVertexAttribPointer(m_skinning.Attributes.BoneIndices, 2,
GL_UNSIGNED_BYTE, GL_FALSE, stride,
_offsetof(Vertex, BoneIndices));
glVertexAttribPointer(m_skinning.Attributes.Position, 3,
GL_FLOAT, GL_FALSE, stride,
_offsetof(Vertex, Position));
glVertexAttribPointer(m_skinning.Attributes.TexCoord, 2,
GL_FLOAT, GL_FALSE, stride,
_offsetof(Vertex, TexCoord));

size_t indicesPerBone = 12 + 6 * (NumDivisions + 1);
int indexCount = BoneCount * indicesPerBone;
glDrawElements(GL_TRIANGLES, indexCount, GL_UNSIGNED_SHORT, 0);
```

This is the largest number of attributes we’ve ever enabled; as you can see, it can be quite a chore to set them all up. One thing I find helpful is creating my own variant of the `offsetof` macro, useful for passing a byte offset to `glVertexAttribPointer`. Here’s how I define it:

```#define _offsetof(TYPE, MEMBER) (GLvoid*) (offsetof(TYPE, MEMBER))
```

The compiler will complain if you use `offsetof `on a type that it doesn’t consider to be a POD type. This is mostly done just to conform to the ISO C++ standard; in practice, it’s usually safe to use `offsetof` on simple non-POD types. You can turn off the warning by adding `-Wno-invalid-offsetof` to the gcc command line. (To add gcc command-line arguments in Xcode, right-click the source file, and choose Get Info.)

## Skinning with OpenGL ES 1.1

All Apple devices at the time of this writing support the `GL_OES_matrix_palette` extension under OpenGL ES 1.1. As you’ll soon see, it works in a manner quite similar to the OpenGL ES 2.0 method previously discussed. The tricky part is that it imposes limits on the number of so-called vertex units and palette matrices.

Each vertex unit performs a single bone transformation. In the simple stick figure example, we need only two vertex units for each joint, so this isn’t much of a problem.

Palette matrices are simply another term for bone matrices. We need 17 matrices for our stick figure example, so a limitation might complicate matters.

Here’s how you can determine how many vertex units and palette matrices are supported:

```int numUnits;
glGetIntegerv(GL_MAX_VERTEX_UNITS_OES, &numUnits);

int maxMatrices;
glGetIntegerv(GL_MAX_PALETTE_MATRICES_OES, &maxMatrices); ```

Table 9-1 shows the limits for current Apple devices at the time of this writing.

Table 9-1. Matrix palette limitations

Apple deviceVertex unitsPalette matrices
First-generation iPhone and iPod touch39
iPhone 3G and 3GS411
iPhone Simulator411

Uh oh, we need 17 matrices, but at most only 11 are supported! Fret not; we can simply split the rendering pass into two draw calls. That’s not too shoddy! Moreover, since `glDrawElements` allows us to pass in an offset, we can still store the entire stick figure in only one VBO.

Let’s get down to the details. Since OpenGL ES 1.1 doesn’t have uniform variables, it supplies an alternate way of handing bone matrices over to the GPU. It works like this:

```glEnable(GL_MATRIX_PALETTE_OES);
glMatrixMode(GL_MATRIX_PALETTE_OES);
for (int boneIndex = 0; boneIndex < boneCount; ++boneIndex) {
glCurrentPaletteMatrixOES(boneIndex);
}
```

That was pretty straightforward! When you enable `GL_MATRIX_PALETTE_OES`, you’re telling OpenGL to ignore the standard model-view and instead use the model-views that get specified while the matrix mode is set to `GL_MATRIX_PALETTE_OES`.

We also need a way to give OpenGL the blend weights and bone indices. That is simple enough:

```glEnableClientState(GL_WEIGHT_ARRAY_OES);
glEnableClientState(GL_MATRIX_INDEX_ARRAY_OES);

glMatrixIndexPointerOES(2, GL_UNSIGNED_BYTE, stride,
_offsetof(Vertex, BoneIndices));
glWeightPointerOES(2, GL_FLOAT, stride, _offsetof(Vertex, BoneWeights));
```

We’re now ready to write some rendering code, taking into account that the number of supported matrix palettes might be less than the number of bones in our model. Check out Example 9-10 to see how we “cycle” the available matrix slots; further explanation follows the listing.

Example 9-10. ES 1.1 Render method for vertex skinning

```const SkinnedFigure& figure = m_skinnedFigure;

// Set up for skinned rendering:
glMatrixMode(GL_MATRIX_PALETTE_OES);
glEnableClientState(GL_WEIGHT_ARRAY_OES);
glEnableClientState(GL_MATRIX_INDEX_ARRAY_OES);

glBindBuffer(GL_ELEMENT_ARRAY_BUFFER, figure.IndexBuffer);
glBindBuffer(GL_ARRAY_BUFFER, figure.VertexBuffer);

glMatrixIndexPointerOES(2, GL_UNSIGNED_BYTE, stride,
_offsetof(Vertex, BoneIndices));
glWeightPointerOES(2, GL_FLOAT, stride, _offsetof(Vertex, BoneWeights));
glVertexPointer(3, GL_FLOAT, stride, _offsetof(Vertex, Position));
glTexCoordPointer(2, GL_FLOAT, stride, _offsetof(Vertex, TexCoord));

// Make several rendering passes if need be,
// depending on the maximum bone count:
int startBoneIndex = 0;
while (startBoneIndex < BoneCount - 1) {

int endBoneIndex = min(BoneCount, startBoneIndex + m_maxBoneCount);

for (int boneIndex = startBoneIndex;
boneIndex < endBoneIndex;
++boneIndex)
{

int slotIndex;

// All passes beyond the first pass are offset by one.
if (startBoneIndex > 0)
slotIndex = (boneIndex + 1) % m_maxBoneCount;
else
slotIndex = boneIndex % m_maxBoneCount;

glCurrentPaletteMatrixOES(slotIndex);
mat4 modelview = figure.Matrices[boneIndex];
}

size_t indicesPerBone = 12 + 6 * (NumDivisions + 1);
int startIndex = startBoneIndex * indicesPerBone;
int boneCount = endBoneIndex - startBoneIndex;

const GLvoid* byteOffset = (const GLvoid*) (startIndex * 2);
int indexCount = boneCount * indicesPerBone;
glDrawElements(GL_TRIANGLES, indexCount,
GL_UNSIGNED_SHORT, byteOffset);

startBoneIndex = endBoneIndex - 1;
}
```

Under our system, if the model has 17 bones and the hardware supports 11 bones, vertices affected by the 12th matrix should have an index of 1 rather than 11; see Figure 9-6 for a depiction of how this works.

Unfortunately, our system breaks down if at least one vertex needs to be affected by two bones that “span” the two passes, but this rarely occurs in practice.

## Generating Weights and Indices

The limitation on available matrix palettes also needs to be taken into account when annotating the vertices with their respective matrix indices. Example 9-11 shows how our system generates the blend weights and indices for a single limb. This procedure can be used for both the ES 1.1-based method and the shader-based method; in this book’s sample code, I placed it in a base class that’s shared by both rendering engines.

Example 9-11. Generation of bone weights and indices

```for (int j = 0; j < NumSlices; ++j) {

GLushort index0 = floor(blendWeight);
GLushort index1 = ceil(blendWeight);
index1 = index1 < BoneCount ? index1 : index0;

int i0 = index0 % maxBoneCount;
int i1 = index1 % maxBoneCount;

// All passes beyond the first pass are offset by one.
if (index0 >= maxBoneCount || index1 >= maxBoneCount) {
i0++;
i1++;
}

destVertex->BoneIndices = i1 | (i0 << 8);
destVertex->BoneWeights.x = blendWeight - index0;
destVertex->BoneWeights.y = 1.0f - destVertex->BoneWeights.x;
destVertex++;

destVertex->BoneIndices = i1 | (i0 << 8);
destVertex->BoneWeights.x = blendWeight - index0;
destVertex->BoneWeights.y = 1.0f - destVertex->BoneWeights.x;
destVertex++;

blendWeight += (j < NumSlices / 2) ? delta0 : delta1;
}```

In Example 9-11, the `delta0` and `delta1` variables are the increments used for each half of limb; refer to Table 9-2 and flip back to Figure 9-5 to see how this works.

Table 9-2. Bone weight increments

LimbIncrement
First half of upper arm0
Second half of upper arm0.166
First half of forearm0.166
Second half of forearm0

For simplicity, we’re using a linear falloff of bone weights here, but I encourage you to try other variations. Bone weight distribution is a bit of a black art.

That’s it for the skinning demo! As always, you can find the complete sample code on this book’s website. You might also want to check out the 3D skinning demo included in the PowerVR SDK.

## Watch Out for Pinching

Before you get too excited, I should warn you that vertex skinning isn’t a magic elixir. An issue called pinching has caused many a late night for animators and developers. Pinching is a side effect of interpolation that causes severely angled joints to become distorted (Figure 9-7).

If you’re using OpenGL ES 2.0 and pinching is causing headaches, you should research a technique called dual quaternion skinning, developed by Ladislav Kavan and others.

## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

No credit card required