Introduction to the skeletal animation technique

This is an updated version of my article “Introduction to the skeletal animation technique”.
The first time it was published in Game Coder Mag Physics 2/2012.
Here is the link to the facebook page of this magazine.

Introduction to the skeletal animation technique

The skeletal animation technique is based on two main foundations: skeleton and skin mesh. Sometimes skin mesh can be also called skeletal mesh (because it is using skeleton). The basic idea of skeletal animation is assumption that “only the skeleton is animated”. Then the skin mesh vertices are moved because they are smoothly connected to the skeleton. It gives natural way of human-like controlling movement.
In this article I will try to explain the basic concept of skeleton and skin mesh (including skinning) with the code example of 4-bones animation. The goal of this article is to give as simple as possible introduction to the skeletal animation technique.
But first of all we need to start with the knowledge of matrices.
In this article we will use coordinate system from this picture: (used for example in Direct3D library)

Coordinate system

Coordinate system

Matrices

Matrices are one of the foundations of 3D graphics. Manipulation of points, vectors and matrices is the essential thing in the programming computer graphics.
The matrix can hold information needed to transform point in a three-dimensional space. All of the math theory behind this concept exceeds the size and theme of this article, but we need to understand the basic practical usage of the matrices in computer graphics.
Points are elements of 3D space described using 3 numbers: X, Y and Z.
Vectors are describing displacement between two points.
Matrix holds information how to translate, rotate and scale points. Matrices are built from rows and columns. We need matrices with 4 rows and 4 elements in each row (4 columns).
Here are the examples of points and 4×4 matrices:

\boldsymbol{u} = \begin{bmatrix} -3 & 2 & -8 \end{bmatrix}

\boldsymbol{v} = \begin{bmatrix} 1 & -1 & 0 \end{bmatrix}

\boldsymbol{A} = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 4 & -3 & 8 & 1 \end{bmatrix}

\boldsymbol{A} is the translation matrix – it translates with vector \begin{bmatrix} 4 & -3 & 8 \end{bmatrix}.

\boldsymbol{B} = \begin{bmatrix} 0.707 & 0.707 & 0 & 0 \\ -0.707 & 0.707 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix}

\boldsymbol{B} is the rotation matrix – it rotates around axis Z with 45 degrees (Pi/4 radians).

One of the main practical features that we will use is the multiplication of point and matrix. The result of this multiplication is another point. This multiplication should be understood as an operation of “transforming a point by matrix” or “applying transformation to a point”.
To perform such multiplication, we need to extend 3-dimensional point to 4 dimensions by adding 1 as a fourth coordinate.
If you know how to multiply points and matrices on paper – that’s good for you! If you don’t know how to do it – please take a look at some math courses and our C++ code in this article – functions MultiplyMatrices4x4() and MultiplyVector3AndMatrix4x4().
Here are the examples of such multiplications:

\boldsymbol{w} = \boldsymbol{u} \text{ transformed by } \boldsymbol{A}

\boldsymbol{w} = \begin{bmatrix} -3 & 2 & -8 & 1 \end{bmatrix} \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 4 & -3 & 8 & 1 \end{bmatrix} = \begin{bmatrix} 1 & -1 & 0 & 1 \end{bmatrix}

The resulting point \boldsymbol{w} is point \boldsymbol{u} translated by matrix \boldsymbol{A}. Point \boldsymbol{w} in 3D space is \begin{bmatrix} 1 & -1 & 0 \end{bmatrix}.

\boldsymbol{p} = \boldsymbol{v} \text{ transformed by } \boldsymbol{B}

\boldsymbol{p} = \begin{bmatrix} 1 & -1 & 0 & 1 \end{bmatrix} \begin{bmatrix} 0.707 & 0.707 & 0 & 0 \\ -0.707 & 0.707 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix} = \begin{bmatrix} 1.414 & 0 & 0 & 1 \end{bmatrix}

The resulting point \boldsymbol{p} is point \boldsymbol{v} rotated by matrix \boldsymbol{B}. Point \boldsymbol{p} in 3D space is \begin{bmatrix} 1.414 & 0 & 0 \end{bmatrix}.

Another important feature is a multiplication of two matrices. In other words, it is the composition of two transformations.
From a practical point of view, it acts in the same way as the multiplication of point and matrix. For example, let’s imagine that we have two matrices: one matrix that is a translation matrix and the second matrix which is a rotation matrix. If we multiplicate these two matrices, the resulting matrix will be a transformation that does both: translates and rotates. One thing to remember is the order of multiplication! If we multiply in other direction, we will receive the matrix that rotates and then translates.

Here is the example of matrices multiplication (composition of transformations):

\boldsymbol{C} = \boldsymbol{A} \boldsymbol{B}

\boldsymbol{C} = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 4 & -3 & 8 & 1 \end{bmatrix} \begin{bmatrix} 0.707 & 0.707 & 0 & 0 \\ -0.707 & 0.707 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix} = \begin{bmatrix} 0.707 & 0.707 & 0 & 0 \\ -0.707 & 0.707 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 4.949 & 0.707 & 8 & 1 \end{bmatrix}

Now I can show the beauty of matrix transformations. Matrix \boldsymbol{C} holds both transformations (\boldsymbol{A} and \boldsymbol{B}) in one matrix. Let’s see what is the result of transformation point \boldsymbol{u} by matrix \boldsymbol{C}:

\boldsymbol{q} = \boldsymbol{u} \text{ transformed by } \boldsymbol{C}

\boldsymbol{q} = \begin{bmatrix} -3 & 2 & -8 & 1 \end{bmatrix} \begin{bmatrix} 0.707 & 0.707 & 0 & 0 \\ -0.707 & 0.707 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 4.949 & 0.707 & 8 & 1 \end{bmatrix} = \begin{bmatrix} 1.414 & 0 & 0 & 1 \end{bmatrix}

The resulting point \boldsymbol{q} in 3D space is \begin{bmatrix} 1.414 & 0 & 0 \end{bmatrix} and it is equal to point \boldsymbol{p} because matrix \boldsymbol{C} holds both transformations at once! We’ve done these transformations before but in two steps.

In Direct3D functions that generate transformation matrices are:

D3DXMatrixTranslation() – generates translation matrix
D3DXMatrixRotationX(), D3DXMatrixRotationY(), D3DXMatrixRotationZ() – generate rotation matrix for one of the axis
D3DXMatrixScaling() – generates scaling matrix

You can try these function with different parameters and see what are the resulting matrix transformations.

Skeleton

We can think about the skeleton in a biological way: the skeleton is a hierarchy of connected bones. From our point of view bones are represented by matrices and skeleton is just the tree structure where every node holds the matrix.

Every matrix represents the full transformation (translation, rotation and scale) for one and every bone. It means that it has position, rotation and scale of the bone. For us it is important that one matrix holds all of the transformations data needed by one bone.
We can think about the one matrix as the black box – we put something in (transformations from animation) and get something out (the bone that controls the skin mesh).

Another important thing is that we can multiply bone matrices. The result is a multiplication of transformations as described above in the Matrices section. This is the main feature which is the foundation of the skeletal animation technique. For example – if we have a matrix which represents rotation around Y axis with 40 degrees and another matrix that rotates around Y axis with 30 degrees – the multiplication of these two matrices gives us the matrix that rotates around Y axis with 70 degrees. The same happen with matrices which contain full transformations (position, rotation and scale) in one matrix. It is the exact behavior like in the real world. If we move upper arm – the same happen with the lower arm and hand – because these parts of the body are connected to the upper arm in a tree-like structure. Near root nodes transformations influences near leaf transformations. In other words, a transformation from one particular node influences all its children.

Simple human-like skeleton

Simple human-like skeleton

Multiplication of the matrices introduces another important concept: a local vs. world space. Every matrix represents a local space for every bone. For example hand transformation gives us only the local space for the hand – doesn’t matter what is the parent transformation. We can think about it as a relative transformation to its parent. When we finalize matrix multiplication process, we can think about world space transformations for every bone (which will be stored in another matrix variable). These matrices will be used by skin mesh during the skinning process.

Every bone can be described as a structure:

struct Bone
{
    Matrix4x4 LocalSpaceTransformation;
    Matrix4x4 WorldSpaceTransformation;
    int ParentBoneIndex;
};

We can store the whole skeleton just as an array of bones!

struct Bone Skeleton[MAX_BONES_IN_SKELETON];

For simplicity in this article we will assume 4 bones skeleton that will look like on this picture below:

Skeleton structure used in this article

Skeleton structure used in this article

We can store bones in array in this way that we can assume that every child has index greater of its parent.
The algorithm of evaluating world space matrices for the whole skeleton can be written like this:

// There's no parent for the first bone!
// Just copy local matrix to world matrix.
Skeleton[0].WorldSpaceTransformation = Skeleton[0].LocalSpaceTransformation;

for (int i=1 ; i<MAX_BONES_IN_SKELETON ; ++i)
{
    const int parent = Skeleton[i].ParentBoneIndex;
    Skeleton[i].WorldSpaceTransformation = MultiplyMatrices4x4(
        Skeleton[i].LocalSpaceTransformation,
        Skeleton[parent].WorldSpaceTransformation
    );
}

Because of our assumptions, parent world space transformation matrix will be always evaluated before its child. So the whole loop will evaluate world space matrices in the correct order. This simple algorithm is implemented in function UpdateSkeleton_EvaluteWorldMatrices().
To deeply understand what exactly does this simple loop please take a look at its iterations and the results of matrix multiplication. After finishing this loop matrices should contain:
(we shorten the names of variables: Sk=Skeleton, W=WorldSpaceTransformation, L=LocalSpaceTransformation)

Sk[0].W = Sk[0].L

Sk[1].W = Sk[1].L * Sk[0].W = Sk[1].L * Sk[0].L

Sk[2].W = Sk[2].L * Sk[1].W = Sk[2].L * Sk[1].L * Sk[0].L

Sk[3].W = Sk[3].L * Sk[2].W = Sk[3].L * Sk[2].L * Sk[1].L * Sk[0].L

Every bone’s WorldSpaceTransformation matrix “collects” local transformations from all of its parents. That is the essential thing to get properly calculated world matrices.
When we have all of the skeleton work done, we can proceed to the another theme:

Skin Mesh

Skin mesh is a normal mesh – a set of the vertices. But we need to add additional data to every vertex. This additional data represents “how much vertex is connected to the particular bone”. Every vertex can be connected to more than one bone (but usually not more than 4). This feature gives us the feeling of the smooth animation. For example part of the arm skin that lies near elbow will be strongly connected to elbow bone, but part of the arm skin near wrist will be connected more to the hand bone and maybe only a bit to the elbow bone. The strength of the connection between a vertex and particular bone can be described using one float number from the range 0.0f … 1.0f.
We can think about the structure describing skin mesh vertex that looks like this:

struct SkinMeshVertex
{
    float lX , lY , lZ; // Local space
    float wX , wY , wZ; // World space
    float Weight1 , Weight2 , Weight3 , Weight4;
};

We need to assume that all weights sums to 1:

Weight1 + Weight2 + Weight3 + Weight4 = 1

The resulting position of skin mesh vertex can be evaluated from expression:

VertexWorldPosition =
VertexLocalPosition*Bone1WorldMatrix*Weight1 +
VertexLocalPosition*Bone2WorldMatrix*Weight2 +
VertexLocalPosition*Bone3WorldMatrix*Weight3 +
VertexLocalPosition*Bone4WorldMatrix*Weight4;

This final position will be the position for a rendering system, where to put the vertex in 3D world space. This process is implemented in function UpdateSkinMesh_EvaluateVerticesPosition().

The thing that is necessary for us is to set up the weights for every vertex in our skin mesh.
We will do it through the code (function EvaluateSkinWeightForVertex described below), but usually it is the job for the artist. He is describing which part of the body should be influenced by particular bone.

Our skin mesh’s triangles:

Skin Mesh Triangles

Skin Mesh Triangles

Please take a note that here, during the skinning process, we don’t care about the LocalSpaceTransformation matrices in every bone – we only use world space matrices. So before this step all of the world space matrices should be properly calculated.

Code example

Our code example is based on a standard tutorial from Microsoft DirectX 9 SDK \ Samples \ C++ \ Direct3D \ Tutorials \ Tut03_Matrices. All of the Direct3D/Windows specific code is taken from this example (all unnecessary code is removed).

I tried to write the code as simple as possible. My goal was to create educational self-explaining source code strictly connected to the content of this article.

After compiling and running this code, you should see on the screen “the tower” built from 4 bones. The tower should smoothly move from left to right. Every bone should be animated at different time rates – from the bottom to the top. The lower bone is moving slower, but the amplitude is greater. The upper bones are moving faster, but the amplitude is smaller.

We use two basic structures: Vector3 to represent points (and vectors) and Matrix4x4 to represent matrices.
The skin mesh is just an array of vertices:

struct SkinMeshVertex SkinMesh[NUMBER_OF_VERTICES_IN_SKIN_MESH];

There are three functions to manage DirectX vertex buffer: CreateVertexBufferForSkinMesh(), DestroyVertexBufferForSkinMesh(), PutSkinMeshVerticesIntoVertexBuffer(). The third function copies vertices’ world position from SkinMesh array directly to the vertex buffer.

Function CreateSkinMeshVertices() is responsible for a proper creation of all skin mesh vertices. It creates a local position for all vertices and sets up the skin weights. We build “the tower” with thickness going down (Thickness -= ThickStepDown). Every step of the tower is created from two triangles. We put three vertices for every triangle into SkinMesh array. All local positions of the vertices are placed within the rectangle X = -0.31 … 0.31 , Y = 0 … 1. Third coordinate (Z) is zero for all vertices. World position for vertices is not set up here because it will be calculated by the skinning process – function UpdateSkinMesh_EvaluateVerticesPosition().

Function EvaluateSkinWeightForVertex() is called for every vertex. It evaluates weights (describing the strength of connection to a particular bone). Evaluation of the weight is based on the Y value of vertex local position. Because all the vertices lies in the range 0.0f … 1.0f on Y axis we can divide this distance into 4 segments – one segment for every bone. Vertices from three lower segments are connected to two bones with different weights. Vertices from the highest part are connected only to the fourth bone. All of the weights sum correctly to 1.0f for every vertex. There are no vertices connected to more than two bones at once.

Specific code for skeletal animation technique starts with the definition of a Vector3 structure. All of the code above this definition is specific to the Direct3D and performs all of the Windows and DirectX initialization. Only 4 functions are called from Skeletal Animation Technique specific code:

SkeletalAnimationTechnique_INIT()
SkeletalAnimationTechnique_UPDATE()
SkeletalAnimationTechnique_RENDER()
SkeletalAnimationTechnique_DEINIT()

Forward declarations are put at the beginning of the source file (to allow calling these functions from Direct3D/Windows code). Please take a look at function SkeletalAnimationTechnique_UPDATE(). In this function we call skeletal animation update functions in a specific order:

UpdateSkeleton_Movement()
UpdateSkeleton_EvaluteWorldMatrices()
UpdateSkinMesh_EvaluateVerticesPosition()
PutSkinMeshVerticesIntoVertexBuffer()

The first function updates only the skeleton local matrices (UpdateSkeleton_Movement). After this we evaluate world matrices for every bone of the skeleton (UpdateSkeleton_EvaluteWorldMatrices). These world matrices are used in the skinning process – calculation of the final world position for every vertex (UpdateSkinMesh_EvaluateVerticesPosition). Finally, these vertices are put into the vertex buffer and ready to render.

Function UpdateSkeleton_Movement() performs essential updates of the skeleton in the skeletal animation technique. Please take a closer look at the transformations done for every bone. We create only local space transformations – doesn’t matter what are the transformations in the other bones. Every bone is set up separately. Upper bones are moving because the lower bones are moving and because upper bones are connected to the lower bones. As the result we get our “tower” moving smoothly in a snake-like sequence – hard to get it in the other way! Every bone has translation transformation – but with different vector. The lower bones are longer than the upper bones. Three bones (except the first one) are also rotating around Z axis with different timing and amplitude. Of course we set up everything locally for every bone. The effect of full movement is the result of multiplication of skeleton matrices which gives as world matrices for every bone. World matrices “collects” all of the transformations from its parents.

One of the things that you should also take a closer look at is the function MultiplyVectorAndMatrix. This function takes as a first parameter 3-dimensional point and multiplies it by the second parameter – 4×4 matrix. It is done by assuming that a point is 4-dimensional and the fourth coordinate is equal to 1. This function is equivalent to “applying the matrix transformation to the point”. After calling this function, the point from the local space is transformed to the world space using transformation described by the matrix.

Summary

In this article (and code example) all of the calculations for skeletal animation technique are executed on CPU. The goal of this article was to explain basic concepts of skeletal animation. Locking a vertex buffer every frame and writing to it all of the vertices usually isn’t an optimal technique for real-time games. A common solution is to execute the skinning process on GPU using vertex shaders.

In the end you can take a closer look at the SkinnedMesh tutorial from Microsoft DirectX 9 SDK \ Samples \ C++ \ Direct3D \ SkinnedMesh. This tutorial offers 5 different variants of skinning.
Some elements of the whole pipeline are hidden in DirectX functions so it is hard to learn from that complicated tutorial. But I hope that this article explains the core ideas behind the skeletal animation technique.

Source code with all project files (Microsoft Visual C++ 2010 Express) and executables is available here ready to download.

Source Code

#include <Windows.h>
#include <d3dx9.h>

// Forward declarations:
void SkeletalAnimationTechnique_INIT(void);
void SkeletalAnimationTechnique_UPDATE(void);
void SkeletalAnimationTechnique_RENDER(void);
void SkeletalAnimationTechnique_DEINIT(void);

LPDIRECT3D9             g_pD3D = NULL;
LPDIRECT3DDEVICE9       g_pd3dDevice = NULL;

struct CUSTOMVERTEX
{
    FLOAT x, y, z;
    DWORD color;
};

#define D3DFVF_CUSTOMVERTEX (D3DFVF_XYZ|D3DFVF_DIFFUSE)

HRESULT InitD3D( HWND hWnd )
{
    if( NULL == ( g_pD3D = Direct3DCreate9( D3D_SDK_VERSION ) ) )
        return E_FAIL;

    D3DPRESENT_PARAMETERS d3dpp;
    ZeroMemory( &d3dpp, sizeof( d3dpp ) );
    d3dpp.Windowed = TRUE;
    d3dpp.SwapEffect = D3DSWAPEFFECT_DISCARD;
    d3dpp.BackBufferFormat = D3DFMT_UNKNOWN;

    if( FAILED( g_pD3D->CreateDevice( D3DADAPTER_DEFAULT, D3DDEVTYPE_HAL, hWnd,
                                      D3DCREATE_SOFTWARE_VERTEXPROCESSING,
                                      &d3dpp, &g_pd3dDevice ) ) )
    {
        return E_FAIL;
    }

    g_pd3dDevice->SetRenderState( D3DRS_CULLMODE, D3DCULL_NONE );
    g_pd3dDevice->SetRenderState( D3DRS_LIGHTING, FALSE );

    return S_OK;
}

VOID Cleanup()
{
    if( g_pd3dDevice != NULL )
        g_pd3dDevice->Release();
    if( g_pD3D != NULL )
        g_pD3D->Release();
}

VOID SetupMatrices()
{
    D3DXMATRIXA16 matWorld;
    D3DXMatrixIdentity( &matWorld );
    g_pd3dDevice->SetTransform( D3DTS_WORLD, &matWorld );

    D3DXVECTOR3 vEyePt( 0.0f, 1.0f,-5.0f );
    D3DXVECTOR3 vLookatPt( 0.0f, 1.0f, 0.0f );
    D3DXVECTOR3 vUpVec( 0.0f, 1.0f, 0.0f );
    D3DXMATRIXA16 matView;
    D3DXMatrixLookAtLH( &matView, &vEyePt, &vLookatPt, &vUpVec );
    g_pd3dDevice->SetTransform( D3DTS_VIEW, &matView );

    D3DXMATRIXA16 matProj;
    D3DXMatrixPerspectiveFovLH( &matProj, D3DX_PI / 4, 1.0f, 0.1f, 100.0f );
    g_pd3dDevice->SetTransform( D3DTS_PROJECTION, &matProj );
}

VOID Direct3D_Render()
{
    g_pd3dDevice->Clear( 0, NULL, D3DCLEAR_TARGET, D3DCOLOR_XRGB( 0, 0, 0 ), 1.0f, 0 );
    if( SUCCEEDED( g_pd3dDevice->BeginScene() ) )
    {
        SkeletalAnimationTechnique_RENDER();

        g_pd3dDevice->EndScene();
    }
    g_pd3dDevice->Present( NULL, NULL, NULL, NULL );
}

LRESULT WINAPI MsgProc( HWND hWnd, UINT msg, WPARAM wParam, LPARAM lParam )
{
    switch( msg )
    {
        case WM_DESTROY:
            Cleanup();
            PostQuitMessage( 0 );
            return 0;
    }
    return DefWindowProc( hWnd, msg, wParam, lParam );
}

INT WINAPI wWinMain( HINSTANCE hInst, HINSTANCE, LPWSTR, INT )
{
    UNREFERENCED_PARAMETER( hInst );

    WNDCLASSEX wc =
    {
        sizeof( WNDCLASSEX ), CS_CLASSDC, MsgProc, 0L, 0L,
        GetModuleHandle( NULL ), NULL, NULL, NULL, NULL,
        L"SkeletalAnimationTechnique", NULL
    };
    RegisterClassEx( &wc );

    HWND hWnd = CreateWindow( L"SkeletalAnimationTechnique", L"Skeletal Animation Technique",
                              WS_OVERLAPPEDWINDOW, 100, 100, 800, 600,
                              NULL, NULL, wc.hInstance, NULL );

    if( SUCCEEDED( InitD3D( hWnd ) ) )
    {
        SetupMatrices();

        SkeletalAnimationTechnique_INIT();

        ShowWindow( hWnd, SW_SHOWDEFAULT );
        UpdateWindow( hWnd );

        MSG msg;
        ZeroMemory( &msg, sizeof( msg ) );
        while( msg.message != WM_QUIT )
        {
            SkeletalAnimationTechnique_UPDATE();

            if( PeekMessage( &msg, NULL, 0U, 0U, PM_REMOVE ) )
            {
                TranslateMessage( &msg );
                DispatchMessage( &msg );
            }
            else
            {
                Direct3D_Render();
            }
        }

        SkeletalAnimationTechnique_DEINIT();
    }

    UnregisterClass( L"SkeletalAnimationTechnique", wc.hInstance );
    return 0;
}

//###################################################################
// The skeletal Animation Technique specific code starts here:

struct Vector3
{
    FLOAT v[3]; // Three coordinates: X,Y,Z
};

struct Matrix4x4
{
    FLOAT m[4][4]; // [rows][columns]
};

struct Bone
{
    Matrix4x4 LocalSpaceTransformation;
    Matrix4x4 WorldSpaceTransformation;
    int ParentBoneIndex;
};

static const int MAX_BONES_IN_SKELETON = 4;

struct Bone Skeleton[MAX_BONES_IN_SKELETON];

struct SkinMeshVertex
{
    Vector3 LocalPos;
    Vector3 WorldPos;
    FLOAT Weight1, Weight2, Weight3, Weight4;
};

static const int NUMBER_OF_VERTICES_IN_SKIN_MESH = 600;

struct SkinMeshVertex SkinMesh[NUMBER_OF_VERTICES_IN_SKIN_MESH];

LPDIRECT3DVERTEXBUFFER9 VertexBufferSkinMesh; // Vertex Buffer to hold vertices

Matrix4x4 MultiplyMatrices4x4( const Matrix4x4 &m1, const Matrix4x4 &m2 )
{
    Matrix4x4 result;
    for (int i=0 ; i<4 ; ++i)
    {
        for (int j=0 ; j<4 ; ++j)
        {
            result.m[i][j] = 0;
            for (int k=0 ; k<4 ; ++k)
            {
                result.m[i][j] += ( m1.m[i][k] * m2.m[k][j] );
            }
        }
    }
    return result;
}

void UpdateSkeleton_EvaluteWorldMatrices(void)
{
    // There's no parent for the first bone!
    // Just copy local matrix to world matrix.
    Skeleton[0].WorldSpaceTransformation = Skeleton[0].LocalSpaceTransformation;

    for (int i=1 ; i<MAX_BONES_IN_SKELETON ; ++i)
    {
        const int parent = Skeleton[i].ParentBoneIndex;
        Skeleton[i].WorldSpaceTransformation = MultiplyMatrices4x4(
            Skeleton[i].LocalSpaceTransformation,
            Skeleton[parent].WorldSpaceTransformation
        );
    }
}

Vector3 MultiplyVector3AndMatrix4x4( const Vector3& v1, const Matrix4x4& m2 )
{
    Vector3 result;
    for (int i=0 ; i<3 ; ++i)
    {
        result.v[i] = 0;
        for (int j=0 ; j<3 ; ++j)
        {
            result.v[i] += v1.v[j] * m2.m[j][i];
        }
        result.v[i] += m2.m[3][i];
    }
    return result;
}

Vector3 MultiplyVectorAndScalar( const Vector3& v, FLOAT f )
{
    Vector3 result;
    result.v[0] = v.v[0] * f;
    result.v[1] = v.v[1] * f;
    result.v[2] = v.v[2] * f;
    return result;
}

void UpdateSkinMesh_EvaluateVerticesPosition(void)
{
    Vector3 v1, v2, v3, v4;
    Vector3 h1, h2, h3, h4;

    // For every vertex in the skin mesh
    for (int i=0 ; i<NUMBER_OF_VERTICES_IN_SKIN_MESH ; ++i)
    {
        v1 = MultiplyVector3AndMatrix4x4( SkinMesh[i].LocalPos, Skeleton[0].WorldSpaceTransformation );
        v2 = MultiplyVector3AndMatrix4x4( SkinMesh[i].LocalPos, Skeleton[1].WorldSpaceTransformation );
        v3 = MultiplyVector3AndMatrix4x4( SkinMesh[i].LocalPos, Skeleton[2].WorldSpaceTransformation );
        v4 = MultiplyVector3AndMatrix4x4( SkinMesh[i].LocalPos, Skeleton[3].WorldSpaceTransformation );

        h1 = MultiplyVectorAndScalar( v1, SkinMesh[i].Weight1 );
        h2 = MultiplyVectorAndScalar( v2, SkinMesh[i].Weight2 );
        h3 = MultiplyVectorAndScalar( v3, SkinMesh[i].Weight3 );
        h4 = MultiplyVectorAndScalar( v4, SkinMesh[i].Weight4 );

        // Sum all vectors to get the final world positon for vertex
        for (int j=0 ; j<=2 ; ++j)                  
        {                          
            SkinMesh[i].WorldPos.v[j] = (h1.v[j] + h2.v[j] + h3.v[j] + h4.v[j]);                  
        }          
    }  
}  

void CreateVertexBufferForSkinMesh(void)  
{          
    g_pd3dDevice->CreateVertexBuffer(
            NUMBER_OF_VERTICES_IN_SKIN_MESH * sizeof( CUSTOMVERTEX ),
            0,
            D3DFVF_CUSTOMVERTEX,
            D3DPOOL_DEFAULT,
            &VertexBufferSkinMesh,
            NULL
                                    );
}

void DestroyVertexBufferForSkinMesh(void)
{
    VertexBufferSkinMesh->Release();
}

void PutSkinMeshVerticesIntoVertexBuffer(void)
{
    CUSTOMVERTEX *pVertices;
    VertexBufferSkinMesh->Lock( 0, 0, (void**)&pVertices, 0 );
    for (int i=0 ; i<NUMBER_OF_VERTICES_IN_SKIN_MESH ; ++i)          
    {         
        pVertices->x = SkinMesh[i].WorldPos.v[0];
        pVertices->y = SkinMesh[i].WorldPos.v[1];
        pVertices->z = SkinMesh[i].WorldPos.v[2];
        pVertices->color = 0xff0000ff;
        ++pVertices;
    }
    VertexBufferSkinMesh->Unlock();
}

void PutVertex( Vector3& v1, const Vector3& v2 )
{
    v1.v[0] = v2.v[0];
    v1.v[1] = v2.v[1];
    v1.v[2] = v2.v[2];
}

void EvaluateSkinWeightForVertex( SkinMeshVertex& v )
{
    const FLOAT vertexY = v.LocalPos.v[1];
    if (vertexY < 0.25f)
    {
        v.Weight1 = (1.0f-(vertexY*4.0f));
        v.Weight2 = (1.0f-(v.Weight1));
        v.Weight3 = (0.0f);
        v.Weight4 = (0.0f);
    }
    else if (vertexY < 0.50f)
    {
        v.Weight1 = (0.0f);
        v.Weight2 = (1.0f-((vertexY-0.25f)*4.0f));
        v.Weight3 = (1.0f-(v.Weight2));
        v.Weight4 = (0.0f);
    }
    else if (vertexY < 0.75f)
    {
        v.Weight1 = (0.0f);
        v.Weight2 = (0.0f);
        v.Weight3 = (1.0f-((vertexY-0.50f)*4.0f));
        v.Weight4 = (1.0f-(v.Weight3));
    }
    else
    {
        v.Weight1 = (0.0f);
        v.Weight2 = (0.0f);
        v.Weight3 = (0.0f);
        v.Weight4 = (1.0f);
    }
}

void CreateSkinMeshVertices(void)
{
    Vector3 v1, v2, v3, v4;

    FLOAT Y = 0.0f;
    const FLOAT YStepUp = 0.01f;

    FLOAT Thickness = 0.31f;
    const FLOAT ThickStepDown = 0.003f;

    for( int i=0 ; i<NUMBER_OF_VERTICES_IN_SKIN_MESH ; i+=6 )
    {
        v1.v[0] = (-Thickness);
        v1.v[1] = (Y);
        v1.v[2] = (0.0f);

        v2.v[0] = (+Thickness);
        v2.v[1] = (Y);
        v2.v[2] = (0.0f);

        v3.v[0] = (-Thickness);
        v3.v[1] = (Y+YStepUp);
        v3.v[2] = (0.0f);

        v4.v[0] = (+Thickness);
        v4.v[1] = (Y+YStepUp);
        v4.v[2] = (0.0f);

        // Triangle #1
        PutVertex( SkinMesh[i].LocalPos, v1 );
        PutVertex( SkinMesh[i+1].LocalPos, v2 );
        PutVertex( SkinMesh[i+2].LocalPos, v3 );

        // Triangle #2
        PutVertex( SkinMesh[i+3].LocalPos, v2 );
        PutVertex( SkinMesh[i+4].LocalPos, v4 );
        PutVertex( SkinMesh[i+5].LocalPos, v3 );

        EvaluateSkinWeightForVertex( SkinMesh[i] );
        EvaluateSkinWeightForVertex( SkinMesh[i+1] );
        EvaluateSkinWeightForVertex( SkinMesh[i+2] );
        EvaluateSkinWeightForVertex( SkinMesh[i+3] );
        EvaluateSkinWeightForVertex( SkinMesh[i+4] );
        EvaluateSkinWeightForVertex( SkinMesh[i+5] );

        Y += YStepUp;
        Thickness -= ThickStepDown;
    }
}

void CopyMatrix( Matrix4x4& m1 , const D3DXMATRIX& m2 )
{
    for (int i=0 ; i<4 ; ++i)
    {
        for (int j=0 ; j<4 ; ++j)
        {
            m1.m[i][j] = m2.m[i][j];
        }
    }
}

void CreateSkeleton(void)
{
    Skeleton[0].ParentBoneIndex=0;
    Skeleton[1].ParentBoneIndex=0;
    Skeleton[2].ParentBoneIndex=1;
    Skeleton[3].ParentBoneIndex=2;
}

void UpdateSkeleton_Movement(void)
{
    const UINT iTime1 = (timeGetTime()/3) % 1000;
    const UINT iTime2 = (timeGetTime()) % 1000;
    const UINT iTime3 = (timeGetTime()*2) % 1000;
    const FLOAT F1 = ((FLOAT)iTime1) / 1000.0f;
    const FLOAT F2 = ((FLOAT)iTime2) / 1000.0f;
    const FLOAT F3 = ((FLOAT)iTime3) / 1000.0f;
    // FX=<0..1>

    D3DXMATRIX mT, mR;
    D3DXMATRIX m1;

    D3DXMatrixTranslation( &m1 , 0 , -1.0f , 0 );
    CopyMatrix( Skeleton[0].LocalSpaceTransformation , m1 );

    D3DXMatrixTranslation( &mT , 0.0f , 1.25f , 0 );
    D3DXMatrixRotationZ( &mR , sin(2.0f*3.1415f*F1)*0.52f );
    D3DXMatrixMultiply( &m1 , &mT , &mR );
    CopyMatrix( Skeleton[1].LocalSpaceTransformation , m1 );

    D3DXMatrixTranslation( &mT , 0.0f , 0.80f , 0 );
    D3DXMatrixRotationZ( &mR , sin(2.0f*3.1415f*F2)*0.30f );
    D3DXMatrixMultiply( &m1 , &mT , &mR );
    CopyMatrix( Skeleton[2].LocalSpaceTransformation , m1 );

    D3DXMatrixTranslation( &mT , 0.0f , 0.60f , 0 );
    D3DXMatrixRotationZ( &mR , sin(2.0f*3.1415f*F3)*0.20f );
    D3DXMatrixMultiply( &m1 , &mT , &mR );
    CopyMatrix( Skeleton[3].LocalSpaceTransformation , m1 );
}

void SkeletalAnimationTechnique_INIT(void)
{
    CreateSkeleton();
    CreateSkinMeshVertices();
    CreateVertexBufferForSkinMesh();
}

void SkeletalAnimationTechnique_DEINIT(void)
{
    DestroyVertexBufferForSkinMesh();
}

void SkeletalAnimationTechnique_UPDATE(void)
{
    UpdateSkeleton_Movement();
    UpdateSkeleton_EvaluteWorldMatrices();
    UpdateSkinMesh_EvaluateVerticesPosition();
    PutSkinMeshVerticesIntoVertexBuffer();
}

void SkeletalAnimationTechnique_RENDER(void)
{
    g_pd3dDevice->SetStreamSource( 0, VertexBufferSkinMesh, 0, sizeof( CUSTOMVERTEX ) );
    g_pd3dDevice->SetFVF( D3DFVF_CUSTOMVERTEX );
    g_pd3dDevice->DrawPrimitive( D3DPT_TRIANGLELIST, 0, NUMBER_OF_VERTICES_IN_SKIN_MESH/3 );
}