QTEST

Tuesday, 31st July 2007

The unofficial Quake specs are a bit confusing on this matter. To get the size of the texture, find the bounding rectangle for the face (using the horizontal and vertical vectors to convert the 3D vertices to 2D in the same way as it's done for the texture coordinates). Then divide by 16 and add one, like this:

Width  = (Ceiling(Max.X / 16) - Floor(Min.X / 16)) + 1
Height = (Ceiling(Max.Y / 16) - Floor(Min.Y / 16)) + 1

It'd certainly work, but it'd probably look a bit odd (mixing and matching, that is - emulating the appearance of the software renderer on its own is very cool).

Quake II appears to contain a lump that maps 16-bit colour values to values in the palette. I don't know what that was used for, but you could probably use something similar to convert the truecolour textures to 8-bit textures.

Before Quake was released, ID released a deathmatch test program, QTEST. This featured the basic engine, three deathmatch levels and not a whole lot else.

However, the PAK files contained some rather interesting files, including a variety of models - some of which were later dropped from Quake entirely!

The model version is type 3, and I've made a guess at the differences between type 3 and type 6 (6 is the version of the models in retail Quake). Type 6 has 8 more bytes after the frame count in the model header. I skip the "sync type" and "flags" fields, as I don't know what these do anyway. Type 3 files don't have a 16 byte frame name, either (between the frame bounding box information and vertices in type 6).

The most impressive extra model is progs/dragon.mdl. It appears in this early screenshot:

One character which changed design considerably was progs/shalrath.mdl.

Appearing in registered Quake, it became the following (QPed seems to mangle the palette, sorry):

The charmingly-named progs/vomitus.mdl is likewise untextured:

The frame data appears to be corrupted here, so I don't think my model loader is working properly. However, you can still get the rough idea of what progs/serpent.mdl might have looked like:

The fish model is quite different, but like the above its last few frames appear corrupted.

A number of textures changed in the final release. Some model textures, such as the grenade and nail textures, were originally much larger.

   
The Ogre before and after his makeover

The original 'gib' textures, eventually unidentifiable meat, were also toned down quite a lot from the rather more graphic ones in the QTEST PAKs.

      

The screenshots (taken directly from QTEST - I can't load those BSPs myself) show a few other changes - billboarded sprites for torches and flames were replaced with 3D models, the teleporter texture was changed and the particle effects for explosions were beefed up with billboarded sprites.

Let There Be Lightmaps

Monday, 30th July 2007

Heh, you might like the Killer Quake Pack.

I've added some primitive parsing and have now loaded the string table, instructions, functions and definitions from progs.dat but can't do a lot with them until I work out what the instructions are. Quake offers some predefined functions as well (quite a lot of them) so that'll require quite a lot of porting.

I haven't looked at the data structures so could be making this up entirely: Quake does lighting using a colour map (a 2D structure with colour on one axis and brightness on the other). I'm assuming, therefore, that for the fullbright colours they map to the same colour for all brightnesses, rather than fade to black.

How could you simulate that? I guess that the quickest and dirtiest method would be to load each texture twice, once with the standard palette and once with the palette adjusted for the darkest brightness and use that as a luma texture. I believe Scet did some interesting and clever things with pixel shaders for DOOM, but that would end up playing merry Hell with 24-bit truecolour external textures.

Aye, it's fun.

 

The lightmaps are small greyscale textures applied to faces to provide high-quality lighting effects with a very small performance overhead. Most of the visible faces have a lightmap.

They are stored in the BSP file. Extracting them has been a little awkward, not helped by a very stupid mistake I made.

Each face has a pointer to its lightmap. To get a meaningful texture out of the BSP we also need to know its width and height, which are based on the bounds of the face's vertices.

However, a lightmap is a 2D texture, and a face occupies three dimensional space. We need to scrap an axis!

Each face is associated with a plane. Each plane has a value which indicates which axis it closest lies orthogonal to. I could use this property to pick the component to discard!

This didn't work too well. Most of the textures were scrambled, and most of them were the same width. This should have rung warning bells, but I ignored this and moved on to other things. The problem was that each face (made up of edges) specifies which of the level's global list of edges comes first, and how many edges it uses (edges are stored consecutively).

// My code looked a bit like this:
for (int i = 0; i < Face.EdgeCount; ++i) {
    Edge = level.Edges[i];
    //
}

// It should have looked like this:
for (int i = 0; i < Face.EdgeCount; ++i) {
    Edge = level.Edges[i + Face.FirstEdge];
    //
}

With that all in position, sane lightmap textures appear as if by magic!

The textures aren't really orientated very well. Some are mirrored, some are rotated - and the textures of some are still clearly the wrong width and height. This 3D-to-2D conversion isn't working very well.

Each face references some texture information, including two vectors denoting the horizontal and vertical axes for aligning the texture. This information can surely also be used to align the lightmaps correctly (where 2D.X = Vector2.Dot(3D, Horizontal), 2D.Y = Vector2.Dot(3D, Vertical))?

I now draw these textures after the main textures and before the luma textures.

Problem: There are typically > 4000 lightmap textures. Rendering all of the lightmaps drops the > 200FPS framerate down to about 35FPS. This isn't great!

Coupling this problem with the other problem that drawing non-world BSP objects (such as ammo crates) isn't very practical at the moment gives me a good excuse to write a new renderer.

Quake uses a BSP tree to speed up rendering. Each leaf has a compressed visibility list attached to it, indicating which other leaves are visible from that one. Each leaf also contains information about which faces are inside it, and so by working out which leaf the camera is in you can easily get a list of which faces are available.

/// <summary>Gets the leaf that contains a particular position.</summary>
/// <param name="position">The position to find a leaf for.</param>
/// <returns>The containing leaf.</returns>
public Node.Leaf GetLeafFromPosition(Vector3 position) {
	// Start from the model's root node:
	Node SearchCamera = this.RootNode;
	for (; ; ) {
		// Are we in front of or behind the partition plane?
		if (Vector3.Dot(SearchCamera.Partition.Normal, position) > SearchCamera.Partition.D) {
			// We're in front of the partition plane.
			if (SearchCamera.FrontLeaf != null) {
				return SearchCamera.FrontLeaf;
			} else {
				SearchCamera = SearchCamera.FrontNode;
			}
		} else {
			// We're behind the partition plane.
			if (SearchCamera.BackLeaf != null) {
				return SearchCamera.BackLeaf;
			} else {
				SearchCamera = SearchCamera.BackNode;
			}
		}
	}
}

The following three screenshots show a wireframe view of going around a sharp corner using the visibility list information from the level's BSP file.

   

Another fix in the new renderer is the correction of faces that don't have a lightmap texture. Some faces - such as those which are completely dark, or the faces used for the sky texture - don't have such information, and are currently rendered at full brightness.

   
Before and after the fix

If the renderer encounters a lightmap-less face, it enables lighting, sets the ambient light to the face's brightness level, draws the face, then disables lighting again. As you can see from the screenshots this looks a lot better.

The new renderer not only renders the levels using the BSP tree - it also breaks them down into individual models. A level file contains multiple models. The first model is the main level architecture. Other models form parts of the level that can be moved.

   
Models 0, 1 and 2 of The Slipgate Complex

Having multiple BSP renderer objects means that I can now render the ammo boxes and health packs.

maps/b_bh25.bsp

I'm not sure what advantage there is to using BSP models instead of Alias models for these items.

Place of Two Deaths has a Place of Two Medikits

High-Resolution/Luma Textures and Monsters

Thursday, 26th July 2007

Ah, makes sense! According to the Unofficial Quake Specs it's p-code, which at least makes parsing easier. Working out which opcodes do what will (I assume) require a perusal of the Quake/QuakeC compiler source.

Personally, I'm not too keen on these packs - high-resolution textures on low-poly structures emphasises their sharp edges, and texture alignment issues - Quake's textures are aligned pretty badly in places - are made even more obvious. In the same vein, low-resolution textures look very bad to me when magnified using a smoothing filter - I'd much rather see chunky pixels.

Anyway, adding support for them is very simple. When loading textures from the BSP, I simply check to see if a file textures/texturename.tga is available, and if so load that instead.

   

The Slipgate Complex with the original and high-resolution textures.

One advantage of these high resolution texture packs are their luma variations. These are available for certain textures that need to 'glow', such as lights, computer displays or runes. These are mostly black textures with the only the part that lights up drawn.

I draw the world geometry twice. The first time I draw it normally. The second time I disable lighting and fog, enable alpha blending, use an additive blend function and the luma textures instead of the regular textures.

   

The Abandoned Base before and after the addition of luma textures.

Quake's maps have limited support for animated textures. If the texture is named +0xyz (where xyz is the descriptive name of the texture) then chances there's a +1xyz, +2xyz (and so on) texture to go with it. Once a level's textures have been loaded, I go through looking for any names starting with +0. From this I can search for the indices of its other frames.

Texture2D OldFirstWall = this.WallTextures[ATD.TextureIds[0]];
Texture2D OldFirstLuma = this.LumaTextures[ATD.TextureIds[0]];
for (int i = 0; i < ATD.TextureIds.Length - 1; ++i) {
	this.WallTextures[ATD.TextureIds[i]] = this.WallTextures[ATD.TextureIds[i + 1]];
	this.LumaTextures[ATD.TextureIds[i]] = this.LumaTextures[ATD.TextureIds[i + 1]];
}
this.WallTextures[ATD.TextureIds[ATD.TextureIds.Length - 1]] = OldFirstWall;
this.LumaTextures[ATD.TextureIds[ATD.TextureIds.Length - 1]] = OldFirstLuma;

Once I've collected up the indices of each animated texture's frames, I simply rotate them using the code above.

The levels do look rather lonely without the various monsters patrolling them. This can be remedied by parsing the entities lump. In the true brute-force tradition, the models are loaded once (at startup), but to render them I just loop through the entire entities block (which contains many irrelevant entities) hunting for types referencing a model - if so, I pull out their angle and offset and render the model at the specified position.

      

Most of the items spread out throughout the level - powerups, weapons and armour - are represented by Alias models, so adding support for those is easy enough:

   

Some of the other items - such as ammo crates - are represented by BSP models, so are currently not supported.

Models

Wednesday, 25th July 2007

I'm not sure either (I haven't looked into it). As the source code for Quake and the QuakeC compiler have been released I might be able to do something. I have a hunch that said code is responsible for level events (switches, bridges, lifts, doors and so on) so it would seem pretty important.

So far I've had one minor problem that was resolved with a hex editor (something simple like a short becoming an int or vice-versa). I'll take a look at your MDL code - thank you!

   
zombie.mdl before and after texturing support.

Animation isn't handled very well just yet - the frames aren't grouped by action (such as the 'attack' animation, 'walk' animation and so on) and the Draw call just takes a frame number.

It'll do for the moment as a test.

I'm still having problems with textures not wrapping correctly.

As you can see the texture above the hand is distorted. I was pointed in the direction of a solution via the texture wrapping options, and have added these lines:

graphics.GraphicsDevice.SamplerStates[0].AddressU = TextureAddressMode.Wrap;
graphics.GraphicsDevice.SamplerStates[0].AddressV = TextureAddressMode.Wrap;

This, unfortunately, hasn't helped. Experimentation has shown that this does change something, and by using the TextureAddressMode.Mirror I get the following -

Note the orientation of the red symbols

I still can't get decent looking light maps out of the level - they all have the "diagonal stripes" effect that usually is caused by an erroneous width. I think I'll have to start trawling through Quake's source code.

Custom Levels and Model Skins

Tuesday, 24th July 2007

An XNA Quake implementation the way I intend on working - that is, to start from scratch - is not really worth it (as far as getting the gameplay 100% identical to DOS Quake).

As a learning project, there's a decent quantity of further material (as far as maps, high-resolution textures and so on go), and I intend on trying to learn how to write a 'FPS-friendly' 3D engine based around Quake's data. Whether I shoehorn some sort of game into that or not is yet to be decided.

Anyhow, I mentioned that I'd be moving on to light maps. Unfortunately the documentation I have is rather vague on this topic (the Unofficial Quake Specs), and I can't get meaningful data out of the BSP files.

I had a slight issue to resolve. Certain textures were appearing as a single colour, like the above. As far as I know this is a symptom of using crazy texture coordinates. I wrote a crude routine that attempts to shunt vertices into the 0..1 range, and the result looks a bit better:

As you can see, the top edge of the large texture is still badly distorted.

I modified the resource loader slightly to handle loading files outside the main pack files.

The result is that I can low load resource files - such as external levels - as you would any other resource, with a call to LoadResource<Data.Level>("maps/ikspq5.bsp"). The level loader also parses the entity declaration block inside the .bsp, putting the player in the correct starting place and - more noticably in the screenshots - finding out the title of the level.

I've made a start at loading the Alias .mdl files, but their structure is rather convoluted so the only visible result thus far is a dump of all of the skin pictures.

There doesn't seem to be much information about Quake BSPs (plenty on Quake 3 BSPs, however!) so if anyone has any recommendations I'd be grateful. Looking at flipcode's article on Quake 2 BSPs it would appear that they're not too different, so I'll have a go with that.

XNA Quake

Thursday, 19th July 2007

After pratting around with DOOM with MDX, it's logical to move up to Quake with XNA. After all, the levels are "true" 3D, and there's a healthy amount of new textures (including bump and gloss maps) so that it would make creating an advanced engine easier. My problem is always finding resources.

On the subject of resources, I'm using a system whereby the various classes for game resources (such as the Level or Model class) can implement ResourceLoader.ILoadable<T>, so I can do things like this:

ResourceLoader = new ResourceLoader(@"C:\Program Files\Quake\ID1");

Palette DefaultPalette = ResourceLoader.Load<Palette>("gfx/palette.lmp");
Level SomeLevel = ResourceLoader.Load<Level>("maps/start.bsp");

This way the ResourceLoader can handle dragging data out of multiple pack (.pak) files or loading override files.

First things first - loading levels. This is nice and easy (unlike DOOM) - the .bsp files contain a list of vertices and a list of edges (each edge contains a start and end vertex index). For testing purposes, I used the Graphics class to draw out each level in 2D:

Next up, I create a point list and render those in 3D:

...and now the edges as a line list:

That seems to be on its side. Quake uses (x, y) as a 2D floor plan and z for height, so I need to swap z and y (and negate y whilst we're at it).

Quake uses faces for solid walls, which are simply convex polygons made up from lists of the aforementioned edges (and may have more than three sides). I'm creating a simple triangle list, and applying some fog to make the world look 3D (there's no lighting):

   

Texturing would make a welcome addition. Quake uses a rather novel texture coordinate system (at least, I've never seen anything quite like it) whereby each face references a TextureInfo structure, which contains the index of the texture itself, a pair of vectors indicating the horizontal and vertical axis (for aligning the texture against the surface of the face) and an offset in texels (so the texture can be aligned to the edges of the face). Fortunately, the BSP documentation I have indicates how to use this information to calculate the texture offset per-vertex, and by dividing by the texture's width and height I can get "conventional" texture coordinates.

The real Quake textures would be nice, I suppose. As I break up the faces into triangle indices, I group them by texture index. The final triangle list is made up of groups of triangles by texture, so that (for example) triangles 0 to 10 will be texture 0, triangles 11 to 14 will be texture 1, triangle 15 will be texture 2 and so on. I also maintain a list of which triangles use which texture, so to render I simply set the texture, draw a range of triangles from the single list, then move on to the next texture.

   

   

It's all pretty brute-force stuff at the moment, but it's still very fast on modern hardware. Next up will be lightmaps.

Event-Driven Keyboard Input for XNA

Friday, 6th July 2007

Edit: The following code has a bug in it. Please make sure you use the corrected code!

/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
 * XnaTextInput.TextInputHandler - benryves@benryves.com                                     *
 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
 * This is quick and very, VERY dirty.                                                       *
 * It uses Win32 message hooks to grab messages (as we don't get a nicely wrapped WndProc).  *
 * I couldn't get WH_KEYBOARD to work (accessing the data via its pointer resulted in access *
 * violation exceptions), nor could I get WH_CALLWNDPROC to work.                            *
 * Maybe someone who actually knows what they're  doing can work something out that's not so *
 * kludgy.                                                                                   *
 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
 * This quite obviously relies on a Win32 nastiness, so this is for Windows XNA games only!  *
 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */

#region Using Statements
using System;
using System.Runtime.InteropServices;
using System.Windows.Forms; // This class exposes WinForms-style key events.
#endregion

namespace XnaTextInput {

	/// <summary>
	/// A class to provide text input capabilities to an XNA application via Win32 hooks.
	/// </summary>
	class TextInputHandler : IDisposable {

		#region Win32

		/// <summary>
		/// Types of hook that can be installed using the SetWindwsHookEx function.
		/// </summary>
		public enum HookId {
			WH_CALLWNDPROC = 4,
			WH_CALLWNDPROCRET = 12,
			WH_CBT = 5,
			WH_DEBUG = 9,
			WH_FOREGROUNDIDLE = 11,
			WH_GETMESSAGE = 3,
			WH_HARDWARE = 8,
			WH_JOURNALPLAYBACK = 1,
			WH_JOURNALRECORD = 0,
			WH_KEYBOARD = 2,
			WH_KEYBOARD_LL = 13,
			WH_MAX = 11,
			WH_MAXHOOK = WH_MAX,
			WH_MIN = -1,
			WH_MINHOOK = WH_MIN,
			WH_MOUSE_LL = 14,
			WH_MSGFILTER = -1,
			WH_SHELL = 10,
			WH_SYSMSGFILTER = 6,
		};

		/// <summary>
		/// Window message types.
		/// </summary>
		/// <remarks>Heavily abridged, naturally.</remarks>
		public enum WindowMessage {
			WM_KEYDOWN = 0x100,
			WM_KEYUP = 0x101,
			WM_CHAR = 0x102,
		};

		/// <summary>
		/// A delegate used to create a hook callback.
		/// </summary>
		public delegate int GetMsgProc(int nCode, int wParam, ref Message msg);

		/// <summary>
		/// Install an application-defined hook procedure into a hook chain.
		/// </summary>
		/// <param name="idHook">Specifies the type of hook procedure to be installed.</param>
		/// <param name="lpfn">Pointer to the hook procedure.</param>
		/// <param name="hmod">Handle to the DLL containing the hook procedure pointed to by the lpfn parameter.</param>
		/// <param name="dwThreadId">Specifies the identifier of the thread with which the hook procedure is to be associated.</param>
		/// <returns>If the function succeeds, the return value is the handle to the hook procedure. Otherwise returns 0.</returns>
		[DllImport("user32.dll", EntryPoint = "SetWindowsHookExA")]
		public static extern IntPtr SetWindowsHookEx(HookId idHook, GetMsgProc lpfn, IntPtr hmod, int dwThreadId);

		/// <summary>
		/// Removes a hook procedure installed in a hook chain by the SetWindowsHookEx function. 
		/// </summary>
		/// <param name="hHook">Handle to the hook to be removed. This parameter is a hook handle obtained by a previous call to SetWindowsHookEx.</param>
		/// <returns>If the function fails, the return value is zero. To get extended error information, call GetLastError.</returns>
		[DllImport("user32.dll")]
		public static extern int UnhookWindowsHookEx(IntPtr hHook);

		/// <summary>
		/// Passes the hook information to the next hook procedure in the current hook chain.
		/// </summary>
		/// <param name="hHook">Ignored.</param>
		/// <param name="ncode">Specifies the hook code passed to the current hook procedure.</param>
		/// <param name="wParam">Specifies the wParam value passed to the current hook procedure.</param>
		/// <param name="lParam">Specifies the lParam value passed to the current hook procedure.</param>
		/// <returns>This value is returned by the next hook procedure in the chain.</returns>
		[DllImport("user32.dll")]
		public static extern int CallNextHookEx(int hHook, int ncode, int wParam, ref Message lParam);

		/// <summary>
		/// Translates virtual-key messages into character messages.
		/// </summary>
		/// <param name="lpMsg">Pointer to an Message structure that contains message information retrieved from the calling thread's message queue.</param>
		/// <returns>If the message is translated (that is, a character message is posted to the thread's message queue), the return value is true.</returns>
		[DllImport("user32.dll")]
		public static extern bool TranslateMessage(ref Message lpMsg);


		/// <summary>
		/// Retrieves the thread identifier of the calling thread.
		/// </summary>
		/// <returns>The thread identifier of the calling thread.</returns>
		[DllImport("kernel32.dll")]
		public static extern int GetCurrentThreadId();

		#endregion

		#region Hook management and class construction.

		/// <summary>Handle for the created hook.</summary>
		private readonly IntPtr HookHandle;

		/// <summary>Create an instance of the TextInputHandler.</summary>
		/// <param name="whnd">Handle of the window you wish to receive messages (and thus keyboard input) from.</param>
		public TextInputHandler(IntPtr whnd) {
			// Create the keyboard hook:
			this.HookHandle = SetWindowsHookEx(HookId.WH_GETMESSAGE, new GetMsgProc(ProcessMessages), IntPtr.Zero, GetCurrentThreadId());
		}

		public void Dispose() {
			// Remove the hook.
			if (this.HookHandle != IntPtr.Zero) UnhookWindowsHookEx(this.HookHandle);
		}

		#endregion

		#region Message processing

		private int ProcessMessages(int nCode, int wParam, ref Message msg) {
			// Check if we must process this message (and whether it has been retrieved via GetMessage):
			if (nCode == 0 && wParam == 1) {

					// We need character input, so use TranslateMessage to generate WM_CHAR messages.
					TranslateMessage(ref msg);

					// If it's one of the keyboard-related messages, raise an event for it:
					switch ((WindowMessage)msg.Msg) {
						case WindowMessage.WM_CHAR:
							this.OnKeyPress(new KeyPressEventArgs((char)msg.WParam));
							break;
						case WindowMessage.WM_KEYDOWN:
							this.OnKeyDown(new KeyEventArgs((Keys)msg.WParam));
							break;
						case WindowMessage.WM_KEYUP:
							this.OnKeyUp(new KeyEventArgs((Keys)msg.WParam));
							break;
					}

			}

			// Call next hook in chain:
			return CallNextHookEx(0, nCode, wParam, ref msg);
		}

		#endregion

		#region Events

		public event KeyEventHandler KeyUp;
		protected virtual void OnKeyUp(KeyEventArgs e) {
			if (this.KeyUp != null) this.KeyUp(this, e);
		}

		public event KeyEventHandler KeyDown;
		protected virtual void OnKeyDown(KeyEventArgs e) {
			if (this.KeyDown != null) this.KeyDown(this, e);
		}

		public event KeyPressEventHandler KeyPress;
		protected virtual void OnKeyPress(KeyPressEventArgs e) {
			if (this.KeyPress != null) this.KeyPress(this, e);
		}

		#endregion
	}
}

Might be useful if your Windows game needs text input. Win32 veterans, feel free to lambast my lack of skills.