Project 2: Quaking in Your Boots

Due by: Wednesday, November 1, 2023 at 11:59 p.m.

Introduction

Quake 3 sits somewhere between the most primitive First Person Shooters like Doom and much more graphically advanced ones like...Doom (2016). Unlike the original Doom, Quake 3 was designed with 3D hardware acceleration in mind. Nevertheless, the system used for storing the models is relatively simple. Emphasis should be placed on relatively.

The Mission

You must write a MonoGame-based C# program that can load a Quake 3 model (in the MD3 model format) and display the model on the screen. Doing so involves loading separate model files for the upper body, lower body, head, and gun as well as skin files and an animation file. You must load textures specified by the skin files and display a texture-mapped model, fully animated and rotatable by the user.

Specification

I've broken down the project into a number of relatively independent tasks, listed below.

• Loading a Model
• Loading a Skin
• Animations
• Linking Models
• Updating Model State
• Setting up MonoGame
• Rendering Models
• User Input

Loading a Model

The MD3 file format was designed to hold the player models in the game Quake 3 by id Software. The file format describes a 3D object in terms of frames (where a series of frames describes an animation), tags (linking the 3D object to other 3D objects, putting the head on top of the torso, for example), and meshes (giving the actual triangles that make up the object in each frame and the way textures should be mapped to them).

A great deal of the work in this project is loading the models from their files. Although the models do, of course, contain 3D information, most of the work in this section is a lot of file operations.

While you do not need to understand it completely, the more that you understand the MD3 file format, the easier your job will be. A good description of the layout of the file can be found here. Note that the provided data structures are very similar, with appropriate changes for C# and different names for the fields.

The LoadModel() method

I suggest that you create a class called Model to hold the individual models. A normal Quake 3 player has three parts: lower body, upper body, and head. I recommend that your Model class has the following members.

MD3Header header;
Frame[] frames;
Tag[] tags;
Mesh[] meshes;
Model[] links;
GraphicsDevice device;

int startFrame;
int endFrame;
int nextFrame;
float interpolation;
int currentFrame;

List<Texture2D> textures;
static Vector3[,] normals;

You should write a LoadModel() method that takes a string giving the name of an MD3 file. To load the model, follow the following steps.

Open the file

Open the file to read in binary mode using a BinaryReader object. Your code should be similar to the following.

BinaryReader reader = new BinaryReader(File.Open(file, FileMode.Open));

Read the header

Read the header information so that you know how many elements will be inside of this model. Unfortunately, this task was easier in C++ than it is in C#. In C++, it was possible to dump an entire chunk of memory into a struct with the appropriate size. Although doing so is possible in C#, it uses advanced features of the language. It is simpler to read in the appropriate data field by field.

I recommend using a struct like the following to hold the header information.

struct MD3Header
{
	public string ID;       	//  4 bytes "IDP3"
	public int version;		//  15
	public string file;		//  64 bytes
	public int flags;
	public int frameCount;
	public int tagCount;
	public int meshCount;
	public int skinCount;
	public int frameOffset;
	public int tagOffset;
	public int meshOffset;
	public int fileSize;
};

If you are unfamiliar with reading binary files, it is not like reading a text file. In a text file, an int could be specified with a variable number of bytes. The values 2, -14, and 300947 take 1, 3, and 6 bytes, respectively, ignoring any whitespace delimiters that are necessary to mark where these numbers begin and end.

In a binary file, an int value takes 4 bytes because the the 32 bits needed to represent the int appear in the file exactly as they do in memory. The following table gives a listing of the types you will want to read and the appropriate BinaryReader method to do so.

Type	Method	Size in Bytes
byte	ReadByte()	1
short	ReadInt16()	2
int	ReadInt32()	4
float	ReadSingle()	4
Vector2	ReadSingle() called twice	8
Vector3	ReadSingle() called 3 times	12
Matrix	ReadSingle() called 9 times	36
string	ReadBytes()	variable

For string values, a block of bytes is set aside in the file. There will always be that many bytes in the file, but they may not all be filled with useful data. Use the ReadBytes() method to read in the bytes into a byte array. Then, one by one, cast them to a char and concatenate them into the final string. Stop if you run past the length of the array or if you hit the null character, which has value 0, which can be written '\0' as well.

Allocate appropriate memory

Allocate space to hold frames, tags, and meshes. The number of frames is given by the frameCount member of the header. There are tags for every frame, so the number of tags is the frameCount member multiplied by the tagCount member. The number of meshes is given by the meshCount member.

Read in the frames and tags

I recommend using the following struct definitions to hold frames and tags.

public struct Frame
{
	public Vector3 minimums;
	public Vector3 maximums;
	public Vector3 position;
	public float scale;
	public string creator;		//  16 bytes
};

public struct Tag
{
	public string name;		//  64 bytes
	public Vector3 position;
	public Matrix rotation;
};

Because binary files must have rigidly ordered sequences of bytes, it is possible to seek to specific locations inside the file. By recording offset values, a header in a binary file format can say exactly where important data starts.

Seek to the frame offset in the file and then read in all the frames at once. Then, seek to the tags offset in the file and read all of them at once.

To seek to a location inside a binary file, you call the Seek() method on the BaseStream property inside your BinaryReader object. Such a call will probably look like the following.

reader.BaseStream.Seek(offset, SeekOrigin.Begin);

Read in the meshes

Meshes are more complex than frames and tags, because their size depends on the number of triangles they have. Use the following struct definitions for meshes.

public struct Skin
{
	public string name;
	public int index;
};

public struct Vertex
{
	public Vector3 vertex;	// stored as three 2-byte shorts
	public byte[] normal;
};

public struct MeshHeader
{
	public string ID;    	//  4 bytes
	public string name;  	//  64 bytes
	public int flags;
	public int frameCount;
	public int skinCount;
	public int vertexCount;
	public int triangleCount;
	public int triangleOffset;
	public int skinOffset;
	public int textureVectorStart;
	public int vertexStart;
	public int meshSize;
};

public struct Mesh
{
	public MeshHeader header;
	public Skin[] skins;
	public int[] triangleVertices;
	public Vector2[] textureCoordinates;
	public Vertex[] vertices;
	public int texture;
};		

Keep track of your current offset in the file. By reading past the frames and tags, you should arrive at the mesh data, but it is safest to seek to the meshOffset member given in the header.

For every single mesh (you've got meshCount of them), do the following.

1. Read in the mesh header
2. Seek to your current offset plus the offset for the triangles
3. Allocate enough space for this mesh's triangles (triangles are stored as three sequential indexes into the list of vertices)
4. Read the data into this mesh's triangles
5. Seek to your current offset plus the offset for the skins
6. Allocate enough space for this mesh's skins
7. Read the data into this mesh's skins (ironically, this data is not used)
8. Seek to your current offset plus the offset for the texture coordinates
9. Allocate enough space for this mesh's texture coordinates
10. Read the data into this mesh's texture coordinates
11. Seek to your current offset plus the offset for the vertices
12. Allocate enough space for this mesh's vertices (the vertexCount multiplied by the frameCount)
13. Read the data into this mesh's vertices (noting that vertex location is stored as three short values)
14. Set the texture member of the mesh to -1 (which means undefined: textures are given as indexes into the list of textures)
15. Increase your current offset by the size of the current mesh so that you are ready to read in the next mesh.

After reading in the meshes, close the file. Note that most (if not all) of those seeks should be unnecessary. If you read each part of the file in sequentially, a well-formatted MD3 file should have you reading each part after the previous part. However, the seeks make the input process more robust.

Loading a Skin

Unlike models, skins are stored in human-readable text files. Examine a skin file such as head_default.skin to get a good idea how it works. Write a LoadSkin() method to load a skin for a Model object.

Each line gives information about which texture to use on a mesh. If the line is blank or starts with tag_, ignore it (since tags don't have textures).

If the line is not blank, get the mesh name by taking the line up to the first comma. Then, loop through the meshes you've got until you find one that matches the name. Load the texture specified by the path given in the rest of the line and put that into your list of textures. Set the texture index of your mesh to be the matching index (the newly created last index in the list).

Note: The process outlined above suggests that you add each texture to the texture list. As it happens, some of the textures are usually repeated. Thus, you could save system and graphics memory by keeping track of the textures you've already added and using that index instead of re-loading the texture. However, this optimization is unnecessary. Consider doing this only if you have already finished the rest of the project.

Of course, there is an extra wrinkle. MonoGame can't load .tga files using the Texture2D.FromStream() method. To simplify this process, I'm providing you with the following method that can read textures from .jpg, .png, and .tga files.

public static Texture2D LoadTexture(GraphicsDevice device, string texturePath)
{
	Texture2D texture;
	
	if (texturePath.ToLower().EndsWith(".tga"))
	{
		TargaImage image = new TargaImage(texturePath);
		texture = new Texture2D(device, image.Header.Width, image.Header.Height);
		Color[] data = new Color[image.Header.Height * image.Header.Width];
		for (int y = 0; y < image.Header.Height; y++)
			for (int x = 0; x < image.Header.Width; x++)
			{
				System.Drawing.Color color = image.Image.GetPixel(x, y);
				data[y * image.Header.Width + x] = new Color(color.R, color.G, color.B, color.A);
			}
		image.Dispose();
		texture.SetData(data);
	}
	else
	{
		FileStream stream = new FileStream(texturePath, FileMode.Open);
		texture = Texture2D.FromStream(device, stream);
		stream.Close();
	}

	return texture;
}

Unfortunately, it also requires a special Targa image reader I found on Code Project. To use the method above, download TargaImage.cs and add it to your project. Then, put using Paloma; at the top of the file where you put this method.

Animations

Like skins, animations are specified in human-readable text files. Normal MD3 characters have 25 different animations, listed in the following enum.

enum AnimationTypes
{
	BOTH_DEATH1 = 0,
	BOTH_DEAD1  = 1,
	BOTH_DEATH2 = 2,
	BOTH_DEAD2  = 3,
	BOTH_DEATH3 = 4,
	BOTH_DEAD3  = 5,

	TORSO_GESTURE = 6,
	TORSO_ATTACK  = 7,
	TORSO_ATTACK2 = 8,
	TORSO_DROP    = 9,
	TORSO_RAISE   = 10,
	TORSO_STAND   = 11,
	TORSO_STAND2  = 12,

	LEGS_WALKCR   = 13,
	LEGS_WALK     = 14,
	LEGS_RUN      = 15,
	LEGS_BACK     = 16,
	LEGS_SWIM     = 17,
	LEGS_JUMP     = 18,
	LEGS_LAND     = 19,
	LEGS_JUMPB    = 20,
	LEGS_LANDB    = 21,
	LEGS_IDLE     = 22,
	LEGS_IDLECR   = 23,
	LEGS_TURN     = 24,

	MAX_ANIMATIONS
};

I suggest you write an MD3 class whose responsibility is to coordinate the four different Model objects together. Since setting animations is a key part of this task, the LoadAnimation(), SetAnimation(), and IncrementAnimation() methods should be defined in this class. I recommend the following members for the MD3 class.

Model           lowerModel;
Model           upperModel;
Model           headModel;
Model           gunModel;
Animation[]	animations;
int		currentAnimation;	

Loading Animations

Each of the 25 animations are given as four numbers: the first frame, the total number of frames, looping frames, and frames per second. Although you should read it in and store this value, we will not use looping frames in this project. All animations are assumed to loop infinitely (because this is a viewer and not a real game).

The animation information can be stored in a simple struct like the following:

public struct Animation
{
	public int firstFrame;
	public int totalFrames;
	public int loopingFrames;
	public int FPS;
};

Each line of the file specifies the values for the next animation. Lines that begin with a //, are empty, or start with anything other than four numbers should be ignored. For our purposes, checking to see if the first char on a line is a digit should be sufficient to see if a line contains animation information.

After reading in all 25 animations, it is necessary to go back and adjust the animations from LEGS_WALKCR onward. You should subtract the difference between the firstFrame value of LEGS_WALKCR and the firstFrame value of TORSO_GESTURE from all of the LEGS_ animations. The BOTH_ animations apply to the lower body and the upper body, but the TORSO_ animations only apply to the upper body. Because there's not a big gap of wasted frames in the lower body models, the LEGS_ animations should start on the same frame as the TORSO_ animations (right after the BOTH_ animations). Frankly, I don't know why they don't.

Setting Animation

I suggest writing a SetAnimation() method in the MD3 class to set the appropriate Model values for animation as well as updating the current animation in the MD3.

When you set the animation in the Model, you should update its startFrame, endFrame, and nextFrame values and set currentFrame to the startFrame.

In the SetAnimation() method, you will not always set the animations for both the upper and lower body models to the given animation. If the animation index is less than or equal to BOTH_DEAD3, you will set both. If the animation index is greater than BOTH_DEAD3 but less than or equal to TORSO_STAND2, set the upper body to the given animation and the lower body to LEGS_WALK. If the animation index is greater than TORSO_STAND2, set the lower body to the given animation and the upper body to TORSO_STAND.

Linking Models

Many things must be done to link all the models together. Remember, we want the lower body, upper body, head, and gun all to move smoothly as if they were connected.

First of all, the four models should be loaded, with skins loaded and an animation set before linking them together. Then, the three lines that should appear next in the MD3 initialization code are as follows.

lowerModel.Link("tag_torso", upperModel);		
upperModel.Link("tag_head", headModel);		
upperModel.Link("tag_weapon", gunModel);		

We will specify the position for the lower model. The first method call will link the lower model to the upper model so that the tag specified by tag_torso will be the same location on both models. Note that a tag is a one way connection: the lower model is connected at tag_torso to the upper model, but the upper model is not connected back.

The second and third method calls connect the upper model to the head and the gun. When we go to render the player, we will only render the lower model. It will scan through its tags and render all the connected models (with locations updated appropriately), which will then render the upper model, which will also scan through its tags and render the head and the gun.

The Link() method in the Model class simply scans through one frame's worth of tags and points the corresponding link to the input model if the tag names match.

Updating Model State

For smooth animation, you should perform updates based on the amount of time passed. The gameTime.ElapsedGameTime.Milliseconds property will give you the elapsed time since the last update in milliseconds. Call the MD3 method Update() with the elapsed time scaled to seconds (divide by 1000.0f). If you wish the animation to run faster, you can divide by a larger number. My sample uses 1500.0f.

The Update() method multiplies this value by the FPS of the current animation, giving the fraction of a frame that has passed. Then, you call UpdateFrame() on each of the Model objects, with this fraction as input.

The UpdateFrame() method adds this fraction to the interpolation member, which keeps track of where the current model is between frames. If interpolation is greater than 1, reset it to 0 (or mod it by 1 to make interpolation into the next frame smoother), set the current frame to the next frame and increment the next frame. If the new next frame is greater than (or equal to) the end frame, set the next frame to the first frame.

That's all that's necessary. Rendering the model will take care of interpolating between the frame locations.

Setting up MonoGame

But before we can render, we have to make sure that MonoGame is properly set up. The models are quite large. I recommend scaling the models to 1/64 their size. The best way to do this is with a scaling matrix. Likewise, models are oriented so that you're looking at the tops of their heads. A rotation or two should fix it, and the scaling and rotations are the only things you'll need in your world transform. Given the scale of the MD3 models, a view transform with the camera 100 units away is about right. Consequently, the perspective transform can keep the near plane at 0.01f, but the far plane should be between 200f and 1000f.

You also need to set up certain static members in the Model class. I recommend using the following code.

public static void SetUp()
{
	for (int i = 0; i < 256; i++)
	{
		for (int j = 0; j < 256; j++)
		{
			float alpha = (float)(2.0 * i * Math.PI / 255);
			float beta = (float)(2.0 * j * Math.PI / 255);
			normals[i, j].X = (float)(Math.Cos(beta) * Math.Sin(alpha));
			normals[i, j].Y = (float)(Math.Sin(beta) * Math.Sin(alpha));
			normals[i, j].Z = (float)(Math.Cos(alpha));
		}
	}
}

This code sets up the normals that will be used later. Computing sine and cosine functions can be expensive. The MD3 system precomputes 65,536 normals ahead of time. Then, the code only needs to index into the table of normals to get those values.

Before Rendering

Make sure you set up an appropriate BasicEffect object to use for rendering. I recommend enabling lighting and texturing, but disabling colored vertices (since we'll be using VertexPositionNormalTexture).

You may choose lighting that you think is suitable. However, I will suggest reasonable values since unreasonable ones can make your rendering look terrible. A diffuse color of (.5, .5, .5) is reasonable with a direction pointing into negative x and negative z. A specular color of (.25, .25, .25) is also reasonable. As is an ambient color of (0.2, 0.2, 0.2).

Rendering Models

Inside the method in your main game class, you should call the Render() method in the MD3 class and give it your BasicEffect object as an argument. This method should be simple. All it does is call the DrawAllModels() method on the lowerModel object. You should pass in two matrices (current and next) giving current location and orientation, but these two matrices should start as identity matrices. In a real game, these would give location and orientation of your character and the location and orientation of the next frame as well, as the character jumps around and flips through the air.

The DrawAllModels() method

The DrawAllModels() method first calls DrawModel() on itself. Then, it loops through all the links in the model. Each non-null link points at another model we want to render. However, we don't want to render those models at the same location as the current model. Instead, we use the tag data to see what relative position and orientation from the current location we're at should be.

The current tag can be found by multiplying the current frame of animation by the tag count and then adding the specific link. So, if we were on the k^th link, we would add k to the multiplication to find the current tag. (Every frame has a full complement of tags, and we want to find the right one from the list of tags.) We also need to find the tag for the next frame of animation, also with the offset of k.

If you read the values into the Tag objects correctly, you'll have Matrix objects for the current tag (I'll call it m) and the next tag (I'll call it mNext).

Finally, we multiply m by current to get the location and orientation matrix for the model on the current frame and multiply nextM by next to get the location and orientation matrix for the model on the next frame. Then we call DrawAllModels() with these matrices as input on the model given by link k.

Although we only call DrawAllModels() once from the MD3 object, it recursively calls all the linked models so that they render themselves. It is crucial that the links from the linking stage are not bi-directional. Otherwise, the DrawAllModels() recursion will continue indefinitely.

The DrawModel() method

Finally, we get to the point where we actually draw a model on the screen. You will need to loop through all of the meshes in the model. If the mesh texture is initialized (not equal to -1), then set the texture with that index as the current texture.

Find the current offset vertex by multiplying the current frame by the per-frame vertex count. Also, find the next offset vertex by multiplying the next frame by the per-frame vertex count. It may have been confusing why we have been so interested in the current vertex and the next vertex, the current transform matrix and the next transform matrix, but this method is where the two will finally come together.

Create an array of VertexPositionNormalTexture values big enough to hold all the vertices in the current mesh (three times the number of triangles).

Then, loop over all the triangles in the mesh. Within each triangle, loop over all its vertices (of which there are 3). Find the index for the current vertex.

Now, create a vector giving the position of the current vertex. To do this, you will need to add the current vertex index you have found to the current offset vertex. That will give you the index into the correct vertex inside the current mesh.

Then, do exactly the same thing again, except adding the current vertex index to the next offset vertex. This position vector will give the position for the next frame.

Once you have the current and the next position vectors, you will need to transform them based on the current and next transform matrices. Call Vector3.Transform() once with the current position and the current transform and once with the next position and next transform.

Now, you have to do something similar with the normals. Get the normal indexes from the current vertex normal[0] and normal[1] values. Use these to index into the static table of normals created earlier. Then, do exactly the same thing again, except getting the normal for the next vertex. Transform these using the Vector3.TransformNormal() method.

Next, you find the interpolated positions by linearly interpolating between the current and the next. Likewise, you find the interpolated normals by linearly interpolating between them. The Vector3.Lerp() method makes this particularly easy.

Then, you must find the texture coordinates for the current vertex. Put all this information (position, normal, texture) into the next vertex that goes into the array.

After all the data from a particular mesh has been put into the vertex array, create a VertexBuffer of the appropriate size and kind and set its data using the SetData() method to be the array you've been filling with vertex data. You should use the primitive drawing techniques discussed in class to draw this vertex buffer using code very much like the following.

device.SetVertexBuffer(vertexBuffer);

foreach (EffectPass pass in basicEffect.CurrentTechnique.Passes)
{
	pass.Apply();
	device.DrawPrimitives(PrimitiveType.TriangleList, 0, triangles);
}

Remember, this code should run for each mesh in each model. Below is a screen shot of a model rendering.

User Input

Displaying an animated MD3 model is pretty cool, but it's more interesting if the user can interact with it. Every time the Update() method is called in your main game class, you should read data from the keyboard. With a KeyboardManager object, you can get the current state with the GetState() method. With a KeyboardState object, you can test to see if any particular key is down using the IsKeyDown() method.

At the minimum, your program should rotate the camera around the y-axis when the left or right arrow keys are pressed. Also, your program should cycle to the next animation out of 25 (and then loop) whenever the enter key is pressed.

For rotation, checking the state of the left and right arrow keys is enough. Updating based on the state of those keys can allow a smooth rotation, provided that the rotation increment is small (and multiplied by the elapsed milliseconds). The enter key poses a bigger problem, since it reports that it is being pressed constantly, leading to switching between animations too quickly. Keep a bool value that knows whether the enter key has been pressed. If the enter key is down and this value is false, set it to true and increment the animation. If the enter key is not down, set it to false. In this way, the animation will only increment once per press of the enter key.

Provided Files

The following model (and skin) files are provided for your use. (Unzip them into your project directory.) You may download other MD3 models from the Internet, but you may have to unpack them from inside of their PAK files using a utility like 7-Zip.

The model.txt file gives sample input for the program, loading the necessary lower, upper, head, and gun models and their appropriate skins as well as an animation file. Your program should read such a file as input. Of course, while you're developing your code, it is reasonable to hardcode the file paths.

• models.zip
• model.txt

Turn In

Your solution and project should both be called Project2. Zip up your entire project and solution and upload the zip file into Blackboard. All work must be submitted before Wednesday, November 1, 2023 at 11:59 p.m. unless you are going to use a grace day.

Only the team leader should turn in the final program. You should clean your solution before submitting it. I should be able to open your solution and run it without any compilation problems.

All work must be done within assigned teams. You may discuss general concepts with your classmates, but it is never acceptable for you to look at another team's code. Please refer to the course policies if you have any questions about academic integrity. If you have trouble with the assignment, I am always available for assistance.

Grading

Your grade will be determined by the following categories:

Category	Weight
Loading models	25%
Loading skins	10%
Loading animations	5%
Linking models	5%
Updating models	5%
Rendering models	25%
Reading (and using) user input	10%
Visual polish and smoothness of animation	10%
Style and comments	5%

Under no circumstances should any member of one group look at the code written by another group. Tools will be used to detect code similarity automatically.

Code that does not compile will automatically score zero points.