Vertex / Mesh Animation
Author : Jack Hoxley
Written : 31st December 2000
Contact : [Web] [Email]
Download : Graph_10.Zip [181 Kb]

Contents of this lesson:
1. Introduction
2. Manual Tweening / Linear Interpolation
3. Vector Interpolation
4. Keyframe Interpolation

1. Introduction

Welcome back to part 3 of the advanced 3D geometry section. This lesson will cover one of the most essential features of any modern game - animation. Just read a preview or review of one of the upcoming first person shooter games and you'll see that their putting a lot of emphasis on the player detail - and how they move. Once you have learnt how to do animation you'll be well on your way to being able to create a fully interactive game environment, most things beyond this point are just additions - not requirements.

Animation in 3D can come in several different forms, depending on how you wish your engine and tools to be developed you will need to choose one that'll suit you the best. There are 3 main types of animation, or course there is nothing stopping you from developing your own types...
• Manual Tweening / Linear Interpolation
• Vector Interpolation
• Keyframe interpolation

This lesson will cover all 3 of the above animation models, by the end you should be able to choose one to best suit your needs.

2. Manual Tweening / Linear Interpolation

This is one of the easiest types of animation to use, which is why I'll cover it first. The only downside being that it's almost useless when you're dealing with very complicated models - or models with lots and lots of vertices. This is a type of tweening where it would definately benefit from using index buffers.

Interpolation is basically how something changes over a certain time or space. So far we've seen Direct3D interpolate colour across a triangle - the way it smoothly fades from colour to colour. Linear interpolation is the same but you know that it'll go in a straight line from A to B, as opposed to a quadratic interpolation which will take a weighted/curved route from A to B. Tweening is the same again really.

In order to interpolate from one position to another we need to use this formula:

(B * V) + A * (1.0 - V)

Where A is the source, of any value; B is the destination, of any value; and V is the interpolant - a value between 0.0 and 1.0, where 0.0 is at A and 1.0 is at B. Straight away you should realise that this is a fairly complicated formula - applying this to 800 vertices on every frame is going to hurt your frame rate. If you have the ability, creating an ActiveX DLL to do the work, or better yet a C/C++ DLL to do all the maths.

All we're going to do is write a function that takes 2 vertices, an interpolant value and then spits out another vertex. We'll then run all our vertices through this function on every frame.

This is the interpolating function:

There, not greatly complicated at all, if you were using unlit vertices - vertices with a normal vector - you would need to modify this code so that it also tweened from the source normal to the destination normal - but all that requires is 3 almost identical lines of code. Note that we have to set the colour of the vertex as well - because of the way that VB does it's functioncalling we have to recreate the entire vertex - a proper tweening function would also tween the colours, texture coordinates and specular values - we'll do that later on; but it isn't really very complicated.

There is one huge limitation to this method - and it's deceptively simple; it's linear. If you were trying to model a human walking around you may well find that linear interpolation doesn't really look quite right - we dont move our limbs in perfectly straight lines from A to B. But you'll just have to test it and see how badly it affects your models.

Now that we have the tweening function we're going to do something to it. Remember the cube example from the last lesson - the one that uses indices. We're going to create 3 cubes - a source, destination and current. we'll then interpolate between them.

Not greatly complicated either - only the last cube has been altered, we didn't really need to set the CubeVertices( ) array as the first loop would have set it to be the CubeVerticesSource( ) array; but for clarity I've left it in there.

Now that we have the relevent arrays ready, we need to know how to update them - again, not greatly complicated; but you can easily see how processing a 1000-2000 vertex model will severely hurt your frame rate.

This procedure is going to be called on every loop, and it will run through every vertex (we only have 8) and alter it - then plug it back into the vertex buffer.

Private Sub UpdateAnimation()
Dim I As Integer
'//Update the position and/or Direction
If AnimTweenDir = True Then
    AnimTweenFactor = AnimTweenFactor + (((GetTickCount() - LastTimeTweened) / 1000) * 1#)
    LastTimeTweened = GetTickCount
    If AnimTweenFactor >= 1# Then
        AnimTweenFactor = 1#
        AnimTweenDir = False
    End If
Else
    AnimTweenFactor = AnimTweenFactor - (((GetTickCount() - LastTimeTweened) / 1000) * 1#)
    LastTimeTweened = GetTickCount
    If AnimTweenFactor <= 0# Then
        AnimTweenFactor = 0#
        AnimTweenDir = True
    End If
End If
'//Update the current vertices
For I = 0 To 7
    CubeVertices(I) = TweenVertices(CubeVerticesSource(I), CubeVerticesDest(I), AnimTweenFactor)
Next I
'//Update the vertex buffer...
    If D3DVertexBuffer8SetData(VBuffer, 0, Len(CubeVertices(0)) * 8, 0, CubeVertices(0)) = D3DERR_INVALIDCALL Then GoTo BailOut:
Exit Sub
BailOut:
Debug.Print "Error occured whilst updating the animation..."
End Sub

Most of the work here is done by the little function we designed earlier; all this part does is work out what the new tweening value should be and then plug the processed vertices into the vertex buffer again. You may well be a little confused about the (((GetTickCount() - LastTimeTweened) / 1000) * 1#) part - this is time based animation.

There are two types of animation - frame based and time based. Frame based is where you increment the frame number by a fixed amount each time - 1 frame every cycle for example. BUT, if you do this slow computers will get jerky animation and fast computers will get animations that go too fast - you could limit the frame rate to 33fps if you wanted - but that's only a half measure, slow computers will still get poor animations. On the other hand you could design your game using time based animations - which I strongly advise that you do. Time based animations, rather than say "1 frame every cycle" are "move 30 frames every second", and you then calculate it so that if the frame rate is low it goes jerky and if it is high it goes perfectly smooth - but in both cases slow and fast we get from the same point to the same point at the same point in time. We do this by calculating the time that has passed since we last updated something - then divide this by 1000 (1 second) and then multiply it by the constant we want the animations to run at. For example, say we want it to go at 30fps, and it's been half a second since we last updated (ultra low frame rate) the current frame will be 0.5 * 30 = 15, the correct frame to be on half way through 1 second. If it's going ultra fast and has only been 10ms since we last called the function we will have 0.1 * 30 = 3, which is correct for only 10ms through the second....

Okay, we've done a whistle stop tour through custom interpolation and time based animations - experiment with this method and see how the frame rate drops when you alter a large model. And if you're keen to do extra work try and alter the TweenVertices( ) code so that it tweens between the colours, diffuse and specular and alters the texture coordinates as well. One last note before we move on - should you want to use this method it would be advisable to write an algorithm that ONLY updates vertices that need updating - there's no point in calculating the new value if the source and destination are the same....

3. Vector Interpolation

Vector interpolation is almost identical to the above method - except Direct3D does the TweenVertices( ) part for you - so you may well see a little bit of a speed improvement when using it. On top of this we also have access to several other types of tweening via the D3DX library...

Using the D3DX library we can do linear interpolation for all the main parts of a vertex that we use, the following list are the ones I'd choose for blending my vertices:

D3DXVec3Lerp( VOut as D3DVECTOR, V1 as D3DVECTOR, V2 as D3DVECTOR, S as Single)
- VOut = The result of the interpolation
- V1 = The source coordinates
- V2 = The destination coordinates
- S = The interpolation amount - between, but not limited to, 0.0 - 1.0 scale; where 0 is the source and 1 is the destination
- Uses = Perfect for interpolating the actual position and normals.

D3DXColorLerp( COut as D3DCOLORVALUE, C1 as D3DCOLORVALUE, C2 as D3DCOLORVALUE, S as Single)
- COut = The resulting colour
- C1 = The source colour
- C2 = The destination colour
- S = The interpolant, on a 0.0 to 1.0 scale
- Uses = Perfect for interpolating the colours of vertices. The example will show you how to use D3DCOLORVALUEs to store the vertex colour

D3DXVec2Lerp( VOut as D3DVECTOR2, V1 as D3DVECTOR2, V2 as D3DVECTOR2, S as Single)
- VOut = The result of this interpolation
- V1 = The source coordinates
- V2 = The destination coordinates
- S = The interpolant, on a 0.0 to 1.0 scale
- Uses = This interpolates a 2D coordinate, which is what texture coordinates are - so, perfect for blending the texture coordinates

There isn't anything else that you're likely to use that doesn't fall into any of these catergories, but there are a few alternatives that you can use, the simplest one being:

D3DXVec3Hermite( VOut as D3DVECTOR, V1 as D3DVECTOR, T1 as D3DVECTOR, V2 as D3DVECTOR, T2 as D3DVECTOR, S as Single)
- VOut = The Result
- V1 = The Source Coordinate
- T1 = The Tangent at the Source coordinate, this is the direction and speed the line will leave the source point.
- V2 = The Destination Coordinate
- T2 = The Tangent at the Destination coordinate, this is the direction and speed the line will enter the destination point.
- S = The Interpolant Value
- Uses = This generates a curved path that goes through the two control points.

To alter the code we have to use the D3DX library we need to change our vertex description, we're going to embed an additional ARGB value in each vertex, whilst Direct3D shouldn't pay any attention to it it's incredibly useful for what we want to do with colours.

now that's prepared we also need to alter the way we blend our vertices - this is the revised version:

Private Function TweenVertices(Source As LITVERTEX, Dest As LITVERTEX, TweenAmount As Single) As LITVERTEX
Dim vResult As D3DVECTOR
Dim vResult2 As D3DVECTOR2
    '//1. Tween the positions of the vertices
    D3DXVec3Lerp vResult, MakeVector(Source.X, Source.Y, Source.Z), MakeVector(Dest.X, Dest.Y, Dest.Z), TweenAmount
    TweenVertices.X = vResult.X
    TweenVertices.Y = vResult.Y
    TweenVertices.Z = vResult.Z
        '//1a. Tween the normals
            ' - Same as above, but not used in this sample
    '//2. Tween the Texture Coordinates
    D3DXVec2Lerp vResult2, MakeVector2D(Source.tu, Source.tv), MakeVector2D(Dest.tu, Dest.tv), TweenAmount
    TweenVertices.tu = vResult2.X
    TweenVertices.tv = vResult2.Y
    '//3. Tween the Colour values
    D3DXColorLerp TweenVertices.ColorEx, Source.ColorEx, Dest.ColorEx, TweenAmount
    With TweenVertices.ColorEx
        TweenVertices.color = RGB(.B * 255, .G * 255, .R * 255)
    End With
End Function

There are two things to watch out for here - firstly we need to dereference a vector to a vertex, we cant pass a vertex to the D3DX functions, so we pass a vector and then extract the information that we want from it. Secondly, if you notice the colours of the vertex appear to be slightly wrong - the RGB( R, G, B ) function is actually RGB( B, G, R ) - this is because Direct3D stores it's colours slightly differently to the way RGB( ) does, but reversing the colour orders works out fine.

You'll also need to alter the way that the vertices are created - so that we encode this new type of colour information, if you cant work it out yourself it's in the source code for this lesson; but for time and space I haven't stuck it in here....

4. Keyframe Interpolation

Keyframe interpolation is probably the type of animation that you're going to use. When we're doing complicated animations with lots and lots of geometry saving a snapshot of every frame would use up gigabytes of storage space - per animation. Instead we simplify the process, using the techniques you've already learnt we take a series of keyframes and predict the frames in the middle.

To better illustrate this think about it this way; we have a coke can that starts normal and ends up, 50 frames later flat (because someone stood on it). In our 3D editor we just scaled the object down, or moved the vertices/faces downwards to simulate it being smaller, we then stored all 50 frames in a file. Say we use one line in the file for every face, and there are 1000 faces in the coke can model; we'd therefore have to store 50,000 lines of data for a relatively simple animation - not very clever. How about we store a keyframe at the start (as a normal coke can) and at the end (as a flat coke can), that means we only store 2000 lines of data - quite an improvement (4% of the size). Surprisingly it would probably be much much faster as well. Imagine loading 50,000 lines of data into memory, or loading each frame as we go - either very slow or very jerky.

In order to do keyframe interpolation all we need to know is the vertex data at each keyframe, and at each keyframe what the current time is, then we can work out the rest. Unfortunately it also means storing 10 or so files for every animation - but if we use archives and/or compression it shouldn't be a problem at all.

This example wont load animation data from a file (except for the objects themselves), so all keyframe time constants will be built into the program. As well as this, you should also consider writing a class module to handle generic animations - it's not difficult, but it's a little big for this lesson. The class should be able to import a standardised file format (that you can make up), load the relevent objects and textures, then animate itself automatically so to speak - and the host application need only call an update or render procedure for it to calculate everything.

The theory behind keyframe animation is very simple, we gather the required information, then on each pass we calculate how long it's been since the animation has started - and therefore what position we are in the animation; we then calculate what the previous keyframe and the next keyframe will be - then work out how far between them we are. Finally we do a normal interpolation, and put the data back into a mesh object and render it. More on the specifics of this in a minute...

I've already mentioned that we're going to load objects from a file, this isn't going to be any different from what we've done in previous lessons (lesson 08 to be precise), but we're going to have to learn how to get the vertex data from the D3DXMESH object. Luckily the D3DX library helps us out here - with two very neat, and very, very useful functions:

Getting Data:
D3DXMeshVertexBuffer8GetData( D3DXMeshobj As Unknown, Offset As Long, Size As Long, Flags As Long, Data As Any) As Long
- D3DXMeshobj As Unknown = A D3DXMESH object that you want to extract the data from.
- Offset As Long = How far into the vertex buffer we want to start reading, 0 is the beginning
- Size As Long = Size of the vertex buffer, this will be Len(D3DVERTEX) * Mesh.GetNumVertices
- Flags As Long = A combination of the CONST_D3DLOCKFLAGS, leave as 0.
- Data As Any = The first element in the array that you want the data to be read into, should be an array of D3DVERTEX vertices
- Return Code As Long = Returns D3D_OK for success, or either of D3DERR_INVALIDCALL or E_INVALIDARG for an error

Setting Data:
D3DXMeshVertexBuffer8SetData( D3DXMeshobj As Unknown, Offset As Long, Size As Long, Flags As Long, Data As Any) As Long
- D3DXMeshobj As Unknown = The D3DXMESH object that defines where you want the data to be placed
- Offset As Long = How far into the Destination vertex buffer you want to place the data
- Size As Long = The Size of the buffer in bytes, this will be Len(D3DVERTEX) * Mesh.GetNumVertices
- Flags As Long = A Combination of the CONST_D3DLOCKFLAGS, leave as 0
- Data As Any = The first element in the array of data you want placed in the mesh's vertex buffer
- Return Code As Long = D3D_OK for success or D3DERR_INVALIDCALL or E_INVALIDARG for failure

We now have all the information that we need to perform keyframe animation. We can load objects, from .X files, into D3DXMESH objects, we can access the raw vertex data for these objects, and we can interpolate between keyframes (unless you fell asleep earlier!). So we now need to make some code out of all of this.

First off the pure maths parts - as mentioned earlier. We'll assume that our animation always runs from time 0 until time n, and it'll be measured in milliseconds - so we can easily use GetTickCount( ) for our timing functions. We'll also design a structure for each keyframe:

Not too complicated really, we also want to write a function that'll fill one of these structures for us - if we give it the file name. We'll use this function:

'//CreateKeyFrameFromFile()
'   - Filename = A valid filename for a .X file 3D object
'   - TexturePrefix = the folder, terminating in a "\" where textures for this object can be loaded
'   - Time = The time index for this keyframe.
'
'   Output = a filled, valid structure.
'
Private Function CreateKeyFrameFromFile(Filename As String, TexturePrefix As String, Time As Long) As KeyFrame
On Error GoTo ErrOut: '//Our error handler
'//0. Any variables required
        Dim I As Long
        Dim XBuffer As D3DXBuffer
        Dim TextureFile As String
        Dim hResult As Long
'//1. Load the X-File into memory
        Set CreateKeyFrameFromFile.Mesh = D3DX.LoadMeshFromX(Filename, D3DXMESH_MANAGED, D3DDevice, Nothing, _
						   XBuffer, CreateKeyFrameFromFile.nMaterials)
        If CreateKeyFrameFromFile.Mesh Is Nothing Then GoTo ErrOut:  '//Dont continue if the above call did not work
'//2. Generate materials and textures
        ReDim CreateKeyFrameFromFile.MatList(CreateKeyFrameFromFile.nMaterials) As D3DMATERIAL8
        ReDim CreateKeyFrameFromFile.TexList(CreateKeyFrameFromFile.nMaterials) As Direct3DTexture8
        For I = 0 To CreateKeyFrameFromFile.nMaterials - 1
        '//Get D3DX to copy the data that we loaded from the file into our structure
        D3DX.BufferGetMaterial XBuffer, I, CreateKeyFrameFromFile.MatList(I)
        '//Fill in the missing gaps - the Ambient properties
        CreateKeyFrameFromFile.MatList(I).Ambient = CreateKeyFrameFromFile.MatList(I).diffuse
        '//get the name of the texture used for this part of the mesh
        TextureFile = D3DX.BufferGetTextureName(XBuffer, I)
        '//Now create the texture
        If TextureFile <> "" Then 'Dont try to create a texture from an empty string
            Set CreateKeyFrameFromFile.TexList(I) = D3DX.CreateTextureFromFileEx(D3DDevice, TexturePrefix & TextureFile, _
							D3DX_DEFAULT, D3DX_DEFAULT, D3DX_DEFAULT, 0, _
							D3DFMT_UNKNOWN, D3DPOOL_MANAGED, _
							 D3DX_FILTER_LINEAR, D3DX_FILTER_LINEAR, 0, _
							ByVal 0, ByVal 0)
        End If
        Next I
'//3. Extract raw vertex data
        ReDim CreateKeyFrameFromFile.VertexList(CreateKeyFrameFromFile.Mesh.GetNumVertices) As D3DVERTEX
        hResult = D3DXMeshVertexBuffer8GetData(CreateKeyFrameFromFile.Mesh, 0, Len(CreateKeyFrameFromFile.VertexList(0)) * _ 
				       CreateKeyFrameFromFile.Mesh.GetNumVertices, 0, CreateKeyFrameFromFile.VertexList(0))
        If Not (hResult = D3D_OK) Then GoTo ErrOut: '//Break out if we could not extract the data...
        CreateKeyFrameFromFile.TimeIndex = Time '//Last thing to do - fill the time index for this keyframe.
'//NB: At this point we have filled the structure with all the information that we need.
Exit Function
ErrOut:
Debug.Print "An error occured while generating a keyframe from the file: " & Filename
End Function

There isn't anything very new in this function, object loading has been covered before, and extracting the raw data has just been explained. From this code we can now create several keyframes, this example will use 4 keyframes; you can quite easily re-engineer this to be whatever number you want...

In the Initialise( ) function we'll stick these lines of code:

Note that I've specified the time index when creating the keyframes in relation to the "kfAnimLength" variable; this is only for convenience - I can change the "kfAnimLength" variable and the rest of the animation would scale accordingly. If you were writing a generalised version of this code (for a class) then you may well want to specify time indices on a 0.0 to 1.0 scale - to act as a multiplier for the animation length constant; but that's completely up to you.

Now, if we ran the program it'd trundle away loading the data - then do nothing; we now need to rewrite the code so it actually displays our animation. The first part is to set up some code that works out which key frames we need to use, and what time index we're at.

The maths for this will be:

CurrentTimeIndex = GetTickCount( ) - AnimLastStartAt

Then with this value we'll scan through our array and calculate which is the nearest, previous keyframe:

At this point we'll now know which frames to blend between; we finally need to work out by how much we interpolate.

'//Where STime, eTime and cTime are Start, End and Current respectively...
'//Calculate the Time Values
sTime = kfAnim(PrevFrame).TimeIndex
eTime = kfAnim(NextFrame).TimeIndex
cTime = CurrentTimeIndex
eTime = eTime - sTime
cTime = cTime - sTime
sTime = sTime - sTime 'simplifies to 0
InterpolateAmount = cTime / eTime

Now all we need to do is interpolate the vertex data - something we've done a million times aleady this lesson (maybe a few less, really). It's at this point that we MUST assume that all the models have the same amount of vertex data - one less and we get a subscript error, one more and we'll get a vertex that doesn't move. It would be ideal to perform some kind of test on the models first - comparing the number of vertices, faces, textures and so on ...

For I = 0 To kfCurrent.Mesh.GetNumVertices '//Cycle through every vertex
   '//2a. Interpolate the Positions
      D3DXVec3Lerp vTemp3D, MakeVector(kfAnim(PrevFrame).VertexList(I).X, kfAnim(PrevFrame).VertexList(I).Y, _ 
	             kfAnim(PrevFrame).VertexList(I).Z), MakeVector(kfAnim(NextFrame).VertexList(I).X, kfAnim(NextFrame).VertexList(I).Y, _
	             kfAnim(NextFrame).VertexList(I).Z), InterpolateAmount
      kfCurrent.VertexList(I).X = vTemp3D.X
      kfCurrent.VertexList(I).Y = vTemp3D.Y
      kfCurrent.VertexList(I).Z = vTemp3D.Z
   '//2b. Interpolate the Normals
      D3DXVec3Lerp vTemp3D, MakeVector(kfAnim(PrevFrame).VertexList(I).nx, kfAnim(PrevFrame).VertexList(I).ny, _ 
	             kfAnim(PrevFrame).VertexList(I).nz), MakeVector(kfAnim(NextFrame).VertexList(I).nx, kfAnim(NextFrame).VertexList(I).ny, _
	             kfAnim(NextFrame).VertexList(I).nz), InterpolateAmount
      kfCurrent.VertexList(I).nx = vTemp3D.X
      kfCurrent.VertexList(I).ny = vTemp3D.Y
      kfCurrent.VertexList(I).nz = vTemp3D.Z
   '//2c. Interpolate the Texture Coordinates
      D3DXVec2Lerp vTemp2D, MakeVector2D(kfAnim(PrevFrame).VertexList(I).tu, kfAnim(PrevFrame).VertexList(I).tv), _
	            MakeVector2D(kfAnim(NextFrame).VertexList(I).tu, kfAnim(NextFrame).VertexList(I).tv), InterpolateAmount
      kfCurrent.VertexList(I).tu = vTemp2D.X
      kfCurrent.VertexList(I).tv = vTemp2D.Y
Next I

okay, so we now have the data prepared - we just need to place it back in where we can use it - the current mesh; so, using one of our new techniques we'll copy all our data back in:

Not greatly complicated really; if we now render "kfCurrent.Mesh" we should see our animation in progress - perfect. With the code that I've just been through it's not too difficult to add more keyframes and quite easily alter the speed that the animation runs at. The only major improvement that I haven't mentioned yet is about textures; currently we have only 4 keyframes - each with it's own copy of the texture; what if there were 15 keyframes, each with 4 medium sized textures - you're holding 56 too many textures - why store multiple copies? A later tutorial will cover the design of a texture pool class - so we only need to store one copy of each texture.

So, 10 lessons down now - From this point onwards you should easily be able to create a simple graphics engine for your game. If you're feeling brave maybe you should - but dont even begin to think about the next Quake game that you'd love to make; go for something simple like pong, tetris or space invaders...

Later on in this series I might upgrade this last keyframe method to use a C++ DLL component; the tutorial is already written for making something like this, but I might be kind enough to create it for you - and design a global, general class for all keyframe animation... but you'll have to wait and see :)

I strongly suggest that you download the source code for this lesson from the top of the page - whilst all the major code has been covered there are still a few very small things that I've left out...

Assuming you've swallowed all of this lesson, onto Lesson 11 : Advanced Geometry part 4 - Using point sprites for particle effects