Lesson 9: Animation

Watch the video now!

3D Animation

3D animation is a nice thing to have in our programs. There are a couple of ways to do 3D animation. We'll do animation using frames. We'll have an external file that stores the positions of certain vertices in our model at particular times in a loop of animation. To draw the model at a particular time, we'll take the two frames nearest to the particular time and take a weighted average of the vertices' positions; that is, we'll interpolate between the two frames. There are more flexible approaches to animation, notably, skeletal animation. But we'll stick with the more straightforward approach. This lesson will be more complicated than previous lessons.

Saving and Loading 3D Animations

There are a bunch of file formats for representing 3D animations. We'll use MD2, the Quake 2 file format. Quake 2 may be old, but we'll use MD2 because the file format is open and straightforward and there are a bunch of MD2 files online that other people have made.

Another reason we're using MD2 is because Blender, an open-source 3D modeling program, is able to export to MD2. Professionals normally use 3ds Max or Maya for 3D modeling. But those programs cost money, so I'd rather stick with Blender.

Unfortunately, at present, the Blender MD2 exporter is quite temperamental and buggy. I couldn't get it to export animations in version 2.44, which is presently the newest version; I had to use version 2.42. Hopefully, the exporter will be improved in later versions of Blender.

Using Blender, I made the 3D guy for our program, including a texture for him. Our program has the guy walking, as shown below:

Animation program screenshot

This is what editing the guy in Blender looks like:

Editing an animation in Blender

Loading and Animating MD2 Files

So now that we've made an MD2 animation of our guy, we'll have to load it in and animate it. I looked online for the MD2 file format, so that I could figure out how to do that. In the rest of this lesson, we'll see how exactly the MD2 file format works.

We'll put all of the code specific to MD2 files in the md2model.h and md2model.cpp files. We'll have an MD2Model class that stores all of the information about an animation and takes care of drawing the animation. Let's look at the md2model.h file to see what the class looks like: 

struct MD2Vertex {
    Vec3f pos;
    Vec3f normal;
};

struct MD2Frame {
    char name[16];
    MD2Vertex* vertices;
};

struct MD2TexCoord {
    float texCoordX;
    float texCoordY;
};

struct MD2Triangle {
    int vertices[3];  //The indices of the vertices in this triangle
    int texCoords[3]; //The indices of the texture coordinates of the triangle
};

First, we have a few structures that our MD2Model class will use. We have vertices, frames, texture coordinates, and triangles. Each frame has a name, which usually indicates the type of animation in which it is (e.g. "run", "stand"). The frames just store the positions and normals of each of the vertices using a vertices array. Each frame has the same number of vertices, so that the vertex at index 5, frame 1, for instance, represents the same part of the model as the vertex at index 5, frame 2, but is in an different position. A triangle is defined by the indices of the vertices in the frames' vertices arrays, and the indices of the texture coordinates in an array that will appear in the MD2Model class. 

class MD2Model {
    private:
        MD2Frame* frames;
        int numFrames;
        MD2TexCoord* texCoords;
        MD2Triangle* triangles;
        int numTriangles;

Here are the main fields that we'll need to draw the model. We have an array of frames, texture coordinates, and triangles. 

        GLuint textureId;

Here, we have the id of the texture for the figure that we'll animate. 

        int startFrame; //The first frame of the current animation
        int endFrame;   //The last frame of the current animation

These are the starting and ending frames to use for animation. 

        /* The position in the current animation.  0 indicates the beginning of
         * the animation, which is at the starting frame, and 1 indicates the
         * end of the animation, which is right when the starting frame is
         * reached again.  It always lies between 0 and 1.
         */
        float time;

Er, just read the comments. 

        MD2Model();
    public:
        ~MD2Model();

Here are our constructor and destructor. The constructor is private, because only a special MD2Model method will be able to construct an MD2Model object. 

        //Switches to the given animation
        void setAnimation(const char* name);

This method will let us set the current animation, since the MD2 file can actually store several animations in certain ranges of frames. Our animation, for example, will occupy frames 40 to 45. Each frame has a name, which will enable us to identify the appropriate frames a the given animation string, as we'll see later. 

        //Advances the position in the current animation.  The entire animation
        //lasts one unit of time.
        void advance(float dt);

This method will be used to advance the state animation. By repeatedly calling advance, we'll animate through the different positions of the 3D figure. 

        //Draws the current state of the animated model.
        void draw();

This method takes care of actually drawing the 3D model. 

        //Loads an MD2Model from the specified file.  Returns NULL if there was
        //an error loading it.
        static MD2Model* load(const char* filename);
};

The load method will load a given MD2 file. It's a static method, indicated by the keyword "static". This means that we can call it using MD2Model::load("somefile.md2"), and we don't need to call it on a particular MD2Model object. Basically, load is like a normal function, except that it can access the private fields of MD2Model objects.

That's the md2model.h file. Now let's look at md2model.cpp. 

namespace {
    //...
}

A little C++ nuance: we have to put all of the non-class constants and functions into this namespace { } block so we can have other constants and functions with the same name in different files. We could, for instance, have a function called "foo" both in this namespace block and in main.cpp. 

    //Normals used in the MD2 file format
    float NORMALS[486] =
        {-0.525731f,  0.000000f,  0.850651f,
         -0.442863f,  0.238856f,  0.864188f,
         //...
         -0.688191f, -0.587785f, -0.425325f};

Rather than storing normals directly, MD2 has 162 special normals and only gives the indices of the normals. This array contains all of the normals that MD2 uses.

When we load in the file, we're going to have to worry about a little thing called "endianness". When designing CPUs, the designers had to decide whether to store numbers with their most significant byte first or last. For example, the short integer 258 = 1(256) + 2 might be stored with the bytes (1, 2), with the most significant byte first, or with the bytes (2, 1), with the least significant byte first. The first means of storage is called "big-endian"; the second is called "little-endian". So, the people who designed CPUs, in their infinite wisdom, chose both. Some CPUs, including the Pentium, store numbers in little-endian form, and other CPUs store numbers in big-endian form. Stupid as it seems, which endianness is "better" has been the source of flame wars. So, we're stuck with both of them, a problem which has been annoying computer programmers for ages past.

What does this have to do with anything? The problem comes up when an integer that requires multiple bytes is stored in the MD2 file. It is stored in little-endian form. But the computer on which we load the file might not use little-endian form. So when we load the file, we have to write our code carefully to make sure that the endianness of the computer on which the program is running doesn't matter. 

    //Returns whether the system is little-endian
    bool littleEndian() {
        //The short value 1 has bytes (1, 0) in little-endian and (0, 1) in
        //big-endian
        short s = 1;
        return (((char*)&s)[0]) == 1;
    }

This function will check whether we are on a little-endian or big-endian system. If the first byte of the short integer 1 is a 1, then we're on a little-endian machine; otherwise, we're on a big-endian machine. 

    //Converts a four-character array to an integer, using little-endian form
    int toInt(const char* bytes) {
        return (int)(((unsigned char)bytes[3] << 24) |
                     ((unsigned char)bytes[2] << 16) |
                     ((unsigned char)bytes[1] << 8) |
                     (unsigned char)bytes[0]);
    }
    
    //Converts a two-character array to a short, using little-endian form
    short toShort(const char* bytes) {
        return (short)(((unsigned char)bytes[1] << 8) |
                       (unsigned char)bytes[0]);
    }
    
    //Converts a two-character array to an unsigned short, using little-endian
    //form
    unsigned short toUShort(const char* bytes) {
        return (unsigned short)(((unsigned char)bytes[1] << 8) |
                                (unsigned char)bytes[0]);
    }

Here, we have functions that will convert a sequence of bytes into an int, a short, or an unsigned short. They use the << bitshift operator, which basically just shoves some number of 0 bits into the end of the number. For example, the binary number 1001101 bit shifted by 5 is 100110100000. Any "extra" bits at the front are just removed. Note that the functions work regardless of the endianness of the machine on which the program is running. 

    //Converts a four-character array to a float, using little-endian form
    float toFloat(const char* bytes) {
        float f;
        if (littleEndian()) {
            ((char*)&f)[0] = bytes[0];
            ((char*)&f)[1] = bytes[1];
            ((char*)&f)[2] = bytes[2];
            ((char*)&f)[3] = bytes[3];
        }
        else {
            ((char*)&f)[0] = bytes[3];
            ((char*)&f)[1] = bytes[2];
            ((char*)&f)[2] = bytes[1];
            ((char*)&f)[3] = bytes[0];
        }
        return f;
    }

Not even floats are immune from the endianness issue. To convert four bytes into a float, we check whether we're on a little-endian machine and then set each byte of the float f as appropriate. 

    //Reads the next four bytes as an integer, using little-endian form
    int readInt(ifstream &input) {
        char buffer[4];
        input.read(buffer, 4);
        return toInt(buffer);
    }
    
    //Reads the next two bytes as a short, using little-endian form
    short readShort(ifstream &input) {
        char buffer[2];
        input.read(buffer, 2);
        return toShort(buffer);
    }
    
    //Reads the next two bytes as an unsigned short, using little-endian form
    unsigned short readUShort(ifstream &input) {
        char buffer[2];
        input.read(buffer, 2);
        return toUShort(buffer);
    }
    
    //Reads the next four bytes as a float, using little-endian form
    float readFloat(ifstream &input) {
        char buffer[4];
        input.read(buffer, 4);
        return toFloat(buffer);
    }
    
    //Calls readFloat three times and returns the results as a Vec3f object
    Vec3f readVec3f(ifstream &input) {
        float x = readFloat(input);
        float y = readFloat(input);
        float z = readFloat(input);
        return Vec3f(x, y, z);
    }

These functions make it convenient to read the next few bytes from a file as an int, short, unsigned short, float, or Vec3f. 

    //Makes the image into a texture, and returns the id of the texture
    GLuint loadTexture(Image *image) {
        //...
    }
}

Here's our loadTexture function from the lesson on textures. 

MD2Model::~MD2Model() {
    if (frames != NULL) {
        for(int i = 0; i < numFrames; i++) {
            delete[] frames[i].vertices;
        }
        delete[] frames;
    }
    
    if (texCoords != NULL) {
        delete[] texCoords;
    }
    if (triangles != NULL) {
        delete[] triangles;
    }
}

Here's the class's destructor, which frees the memory used by all of the vertices, frames, texture coordinates, and triangles. 

MD2Model::MD2Model() {
    frames = NULL;
    texCoords = NULL;
    triangles = NULL;
    time = 0;
}

The constructor initializes a few of the fields. The constructor doesn't do much; the action is in the load method. 

//Loads the MD2 model
MD2Model* MD2Model::load(const char* filename) {
    ifstream input;
    input.open(filename, istream::binary);
    
    char buffer[64];
    input.read(buffer, 4); //Should be "IPD2", if this is an MD2 file
    if (buffer[0] != 'I' || buffer[1] != 'D' ||
        buffer[2] != 'P' || buffer[3] != '2') {
        return NULL;
    }
    if (readInt(input) != 8) { //The version number
        return NULL;
    }

Here's the method that loads in an MD2 file. First, we check that the first four bytes of the file are "IPD2", which must be the first four bytes of every MD2 file. Then, we check that the next four bytes, interpreted as an integer, are the number 8, which they must be for the MD2 files that we're loading. 

    int textureWidth = readInt(input);   //The width of the textures
    int textureHeight = readInt(input);  //The height of the textures
    readInt(input);                      //The number of bytes per frame
    int numTextures = readInt(input);    //The number of textures
    if (numTextures != 1) {
        return NULL;
    }
    int numVertices = readInt(input);    //The number of vertices
    int numTexCoords = readInt(input);   //The number of texture coordinates
    int numTriangles = readInt(input);   //The number of triangles
    readInt(input);                      //The number of OpenGL commands
    int numFrames = readInt(input);      //The number of frames

The MD2 file format dictates that next in the file, there should be certain information about the animation in a certain order. We read in this information and store it into variables. Some of the information we don't need, so we don't store it anywhere. 

    //Offsets (number of bytes after the beginning of the file to the beginning
    //of where certain data appear)
    int textureOffset = readInt(input);  //The offset to the textures
    int texCoordOffset = readInt(input); //The offset to the texture coordinates
    int triangleOffset = readInt(input); //The offset to the triangles
    int frameOffset = readInt(input);    //The offset to the frames
    readInt(input);                      //The offset to the OpenGL commands
    readInt(input);                      //The offset to the end of the file

Next in the MD2 file should be certain values indicating the number of bytes from the beginning of the file where certain data appear. 

    //Load the texture
    input.seekg(textureOffset, ios_base::beg);
    input.read(buffer, 64);
    if (strlen(buffer) < 5 ||
        strcmp(buffer + strlen(buffer) - 4, ".bmp") != 0) {
        return NULL;
    }
    Image* image = loadBMP(buffer);
    GLuint textureId = loadTexture(image);
    delete image;
    MD2Model* model = new MD2Model();
    model->textureId = textureId;

We go to where the texture is indicated, and load in the next 64 bytes as a string. The string is a filename where the texture for the model is. We make sure that the texture is a bitmap and load it in. 

    //Load the texture coordinates
    input.seekg(texCoordOffset, ios_base::beg);
    model->texCoords = new MD2TexCoord[numTexCoords];
    for(int i = 0; i < numTexCoords; i++) {
        MD2TexCoord* texCoord = model->texCoords + i;
        texCoord->texCoordX = (float)readShort(input) / textureWidth;
        texCoord->texCoordY = 1 - (float)readShort(input) / textureHeight;
    }

Next, we load in the texture coordinates. Each texture coordinate is represented as two shorts. To get from each short to the appropriate float, we have to divide by the width or height of the texture that we found at the beginning of the file. For the y coordinate, we have to take 1 minus the coordinate because the MD2 file measures the y coordinate from the top of the texture, while OpenGL measures it from the bottom of the texture. 

    //Load the triangles
    input.seekg(triangleOffset, ios_base::beg);
    model->triangles = new MD2Triangle[numTriangles];
    model->numTriangles = numTriangles;
    for(int i = 0; i < numTriangles; i++) {
        MD2Triangle* triangle = model->triangles + i;
        for(int j = 0; j < 3; j++) {
            triangle->vertices[j] = readUShort(input);
        }
        for(int j = 0; j < 3; j++) {
            triangle->texCoords[j] = readUShort(input);
        }
    }

Now, we load in the triangles, which are just a bunch of indices of vertices and texture coordinates. 

    //Load the frames
    input.seekg(frameOffset, ios_base::beg);
    model->frames = new MD2Frame[numFrames];
    model->numFrames = numFrames;
    for(int i = 0; i < numFrames; i++) {
        MD2Frame* frame = model->frames + i;
        frame->vertices = new MD2Vertex[numVertices];
        Vec3f scale = readVec3f(input);
        Vec3f translation = readVec3f(input);
        input.read(frame->name, 16);
        
        for(int j = 0; j < numVertices; j++) {
            MD2Vertex* vertex = frame->vertices + j;
            input.read(buffer, 3);
            Vec3f v((unsigned char)buffer[0],
                    (unsigned char)buffer[1],
                    (unsigned char)buffer[2]);
            vertex->pos = translation + Vec3f(scale[0] * v[0],
                                              scale[1] * v[1],
                                              scale[2] * v[2]);
            input.read(buffer, 1);
            int normalIndex = (int)((unsigned char)buffer[0]);
            vertex->normal = Vec3f(NORMALS[3 * normalIndex],
                                   NORMALS[3 * normalIndex + 1],
                                   NORMALS[3 * normalIndex + 2]);
        }
    }

Now, we load in the frames. Each frame starts with six floats, indicating vectors by which to scale and translate the vertices. Then, there are 16 bytes indicating the frame's name. Then come the vertices. For each vertex, we have two unsigned characters indicating the position, which we can convert to floats by scaling and translating them. Then, we have an unsigned character which gives the normal vertor as an index in the NORMALS array that we saw earlier. 

    model->startFrame = 0;
    model->endFrame = numFrames - 1;
    return model;
}

Finally, we set the starting and ending frames and return the model. 

void MD2Model::setAnimation(const char* name) {
    /* The names of frames normally begin with the name of the animation in
     * which they are, e.g. "run", and are followed by a non-alphabetical
     * character.  Normally, they indicate their frame number in the animation,
     * e.g. "run_1", "run_2", etc.
     */
    bool found = false;
    for(int i = 0; i < numFrames; i++) {
        MD2Frame* frame = frames + i;
        if (strlen(frame->name) > strlen(name) &&
            strncmp(frame->name, name, strlen(name)) == 0 &&
            !isalpha(frame->name[strlen(name)])) {
            if (!found) {
                found = true;
                startFrame = i;
            }
            else {
                endFrame = i;
            }
        }
        else if (found) {
            break;
        }
    }
}

This function figures out the start and end frames for the indicated animation using the names of the different frames, which follow the pattern suggested by the comment. 

void MD2Model::advance(float dt) {
    if (dt < 0) {
        return;
    }
    
    time += dt;
    if (time < 1000000000) {
        time -= (int)time;
    }
    else {
        time = 0;
    }
}

Now, we have a method for advancing the animation, which we do by increasing the time field. To keep it between 0 and 1, we use time -= (int)time (unless the time is REALLY big, in which case we might run into problems converting it into an integer). 

void MD2Model::draw() {
    glEnable(GL_TEXTURE_2D);
    glBindTexture(GL_TEXTURE_2D, textureId);
    glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_MIN_FILTER, GL_LINEAR);
    glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_MAG_FILTER, GL_LINEAR);

Here's where we draw the 3D model. We start by telling OpenGL the texture and the type of texture mapping that we want to use. 

    //Figure out the two frames between which we are interpolating
    int frameIndex1 = (int)(time * (endFrame - startFrame + 1)) + startFrame;
    if (frameIndex1 > endFrame) {
        frameIndex1 = startFrame;
    }
    
    int frameIndex2;
    if (frameIndex1 < endFrame) {
        frameIndex2 = frameIndex1 + 1;
    }
    else {
        frameIndex2 = startFrame;
    }
    
    MD2Frame* frame1 = frames + frameIndex1;
    MD2Frame* frame2 = frames + frameIndex2;

Now, using the time field, we figure out the two frames between which we want to interpolate. 

    //Figure out the fraction that we are between the two frames
    float frac =
        (time - (float)(frameIndex1 - startFrame) /
         (float)(endFrame - startFrame + 1)) * (endFrame - startFrame + 1);

Now, we figure out what fraction we are between the two frames. 0 means that we are at the first frame, 1 means that we are at the second, and 0.5 means that we are halfway in between. 

    //Draw the model as an interpolation between the two frames
    glBegin(GL_TRIANGLES);
    for(int i = 0; i < numTriangles; i++) {
        MD2Triangle* triangle = triangles + i;
        for(int j = 0; j < 3; j++) {
            MD2Vertex* v1 = frame1->vertices + triangle->vertices[j];
            MD2Vertex* v2 = frame2->vertices + triangle->vertices[j];
            Vec3f pos = v1->pos * (1 - frac) + v2->pos * frac;

Now, we go through the triangles, and for each vertex, take the position to be an interpolation between their positions in the two frames. 

            Vec3f normal = v1->normal * (1 - frac) + v2->normal * frac;
            if (normal[0] == 0 && normal[1] == 0 && normal[2] == 0) {
                normal = Vec3f(0, 0, 1);
            }
            glNormal3f(normal[0], normal[1], normal[2]);

We do the same thing for the normal vectors. If the average happens to be the zero vector, we change it to an arbitrary vector, since the zero vector has no direction and can't be used as a normal vector. Actually there's a better way to average two directions, but we'll stick with a linear average because it's easier. 

            MD2TexCoord* texCoord = texCoords + triangle->texCoords[j];
            glTexCoord2f(texCoord->texCoordX, texCoord->texCoordY);
            glVertex3f(pos[0], pos[1], pos[2]);
        }
    }
    glEnd();

Now, we just find the appropriate texture coordinate and call glTexCoord2f and glVertex3f.

Our Main Program

That does it for the MD2 file format. Let's take a look at main.cpp. 

const float FLOOR_TEXTURE_SIZE = 15.0f; //The size of each floor "tile"

This is the size of each "tile" on the floor; that is, each copy of the floor image that you saw in the program's screenshot. 

float _angle = 30.0f;
MD2Model* _model;
int _textureId;
//The forward position of the guy relative to an arbitrary floor "tile"
float _guyPos = 0;

Here are some variables that will store the camera angle, the MD2Model object, the id of the floor texture, and how far the guy has walked, modulo the size of the floor tile. 

void initRendering() {
    //...
    
    //Load the model
    _model = MD2Model::load("tallguy.md2");
    if (_model != NULL) {
        _model->setAnimation("run");
    }
    
    //Load the floor texture
    Image* image = loadBMP("vtr.bmp");
    _textureId = loadTexture(image);
    delete image;
}

In our initRendering function, we load the model and the floor texture. 

void drawScene() {
    //...
    
    //Draw the guy
    if (_model != NULL) {
        glPushMatrix();
        glTranslatef(0.0f, 4.5f, 0.0f);
        glRotatef(-90.0f, 0.0f, 0.0f, 1.0f);
        glScalef(0.5f, 0.5f, 0.5f);
        _model->draw();
        glPopMatrix();
    }

Here's where we draw the guy. We have to translate, rotate, and scale to make him the right size, at the right position, and facing in the right direction. I found out the appropriate translation and scaling factor by trial and error. The correct numbers depend on the actual vertex positions that I set up when I created the model in Blender. 

    //Draw the floor
    glTranslatef(0.0f, -5.4f, 0.0f);
    glEnable(GL_TEXTURE_2D);
    glBindTexture(GL_TEXTURE_2D, _textureId);
    glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_MIN_FILTER, GL_LINEAR);
    glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_MAG_FILTER, GL_LINEAR);
    
    glBegin(GL_QUADS);
    
    glNormal3f(0.0f, 1.0f, 0.0f);
    glTexCoord2f(2000 / FLOOR_TEXTURE_SIZE, _guyPos / FLOOR_TEXTURE_SIZE);
    glVertex3f(-1000.0f, 0.0f, -1000.0f);
    glTexCoord2f(2000 / FLOOR_TEXTURE_SIZE,
                 (2000 + _guyPos) / FLOOR_TEXTURE_SIZE);
    glVertex3f(-1000.0f, 0.0f, 1000.0f);
    glTexCoord2f(0.0f, (2000 + _guyPos) / FLOOR_TEXTURE_SIZE);
    glVertex3f(1000.0f, 0.0f, 1000.0f);
    glTexCoord2f(0.0f, _guyPos / FLOOR_TEXTURE_SIZE);
    glVertex3f(1000.0f, 0.0f, -1000.0f);
    
    glEnd();
    
    //...
}

Now, we draw the floor. The floor will just be a quadrilateral that extends very far in each direction. To make the guy appear to move forward, we set the texture coordinates so that the floor tiles appear to move in the appropriate direction. 

void update(int value) {
    _angle += 0.7f;
    if (_angle > 360) {
        _angle -= 360;
    }
    
    //Advance the animation
    if (_model != NULL) {
        _model->advance(0.025f);
    }
    
    //Update _guyPos
    _guyPos += 0.08f;
    while (_guyPos > FLOOR_TEXTURE_SIZE) {
        _guyPos -= FLOOR_TEXTURE_SIZE;
    }
    
    glutPostRedisplay();
    glutTimerFunc(25, update, 0);
}

Now we have our update function. We just increase the camera angle and the guy's position, and call advance on the MD2Model object. I figured out the rate at which to increase the _guyPos variable using trial and error.

And with that code, we have created a 3D walking guy.

Next is "Lesson 10: Collision Detection".