8-bit Raycasting Quake Skies and Animated Textures

Monday, 20th August 2007

All of this Quake and XNA 3D stuff has given me a few ideas for calculator (TI-83) 3D.

One of my problems with calculator 3D apps is that I have never managed to even get a raycaster working. Raycasters aren't exactly very tricky things to write.

So, to help me, I wrote a raycaster in C#, limiting myself to the constraints of the calculator engine - 96×64 display, 256 whole angles in a full revolution, 16×16 map, that sort of thing. This was easy as I had floating-point maths to fall back on.

With that done, I went and ripped out all of the floating-point code and replaced it with fixed-point integer arithmetic; I'm using 16-bit values, 8 bits for the whole part and 8 bits for the fractional part.

From here, I just rewrote all of my C# code in Z80 assembly, chucking in debugging code all the way through so that I could watch the state of values and compare them with the results from my C# code.

The result is rather slow, but on the plus side the code is clean and simple. The screen is cropped for three reasons: it's faster to only render 64 columns (naturally), you get some space to put a HUD and - most importantly - it limits the FOV to 90°, as the classic fisheye distortion becomes a more obvious problem above this.

I sneaked a look at the source code of Gemini, an advanced raycaster featuring textured walls, objects and doors. It is much, much faster than my engine, even though it does a lot more!

It appears that the basic raycasting algorithm is pretty much identical to the one I use, but gets away with 8-bit fixed point values. 8-bit operations can be done significantly faster than 16-bit ones on the Z80, especially multiplications and divisions (which need to be implemented in software). You can also keep track of more variables in registers, and restricting the number of memory reads and writes can shave off some precious cycles.

Some ideas that I've had for the raycaster, that I'd like to try and implement:

• Variable height floors and ceilings. Each block in the world is given a floor and ceiling height. When the ray intersects the boundary, the camera height is subtracted from these values, they are divided by the length of the ray (for projection) and the visible section of the wall is drawn. Two counters would keep track of the upper and lower values currently drawn to to keep track of the last block's extent (for occlusion) and floor/ceiling colours could be filled between blocks.
• No texturing: wall faces and floors/ceilings would be assigned dithered shades of grey. I think this, combined with lighting effects (flickering, shading), would look better than monochrome texture mapping - and would be faster!
• Ray-transforming blocks. For example, you could have two 16×16 maps with a tunnel: the tunnel would contain a special block that would, when hit, tell the raycaster to start scanning through a different level. This could be used to stitch together large worlds from small maps (16×16 is a good value as it lets you reduce level pointers to 8-bit values).
• Adjusting floors and ceilings for lifts or crushing ceilings.

As far as the Quake project, I've made a little progress. I've added skybox support for Quake 2:

Quake 2's skyboxes are simply made up of six textures (top, bottom, front, back, left, right). Quake doesn't use a skybox. Firstly, you have two parts of the texture - one half is the sky background, and the other half is a cloud overlay (both layers scroll at different speeds). Secondly, it is warped in a rather interesting fashion - rather like a squashed sphere, reflected in the horizon:

For the moment, I'm just using the Quake 2 box plus a simple pixel shader to mix the two halves of the sky texture.

I daresay something could be worked out to simulate the warping.

The above is from GLQuake, which doesn't really look very convincing at all.

I've reimplemented the texture animation system in the new BSP renderer, including support for Quake 2's animation system (which is much simpler than Quake 1's - rather than have magic texture names, all textures contain the name of the next frame in their animation cycle).

QuakeC VM

Wednesday, 15th August 2007

I've started serious work on the QuakeC virtual machine.

The bytecode is stored in a single file, progs.dat. It is made up of a number of different sections:

• Definitions data - an unformatted block of data containing a mixture of floating point values, integers and vectors.
• Statements - individual instructions, each made up of four short integers. Each statement has an operation code and up to three arguments. These arguments are typically pointers into the definitions data block.
• Functions - these provide a function name, a source file name, storage requirements for local variables and the address of the first statement.

On top of that are two tables that break down the definitions table into global and field variables (as far as I'm aware this is only used to print "nice" names for variables when debugging, as it just attaches a type and name to each definition) and a string table.

The first few values in the definition data table are used for predefined values, such as function parameters and return value storage.

Now, a slight problem is how to handle these variables. My initial solution was to read and write types strictly as particular types using the definitions table, but this idea got scrapped when I realised that the QuakeC bytecode uses the vector store opcode to copy string pointers, and a vector isn't much use when you need to print a string.

I now use a special VariablePointer class that internally stores the pointer inside the definition data block, and provides properties for reading and writing using the different formats.

/// <summary>Defines a variable.</summary>
public class VariablePointer {

	private readonly uint Offset;

	private readonly QuakeC Source;

	private void SetStreamPos() { this.Source.DefinitionsDataReader.BaseStream.Seek(this.Offset, SeekOrigin.Begin); }

	public VariablePointer(QuakeC source, uint offset) {
		this.Source = source;
		this.Offset = offset;
	}

	#region Read/Write Properties

	/// <summary>Gets or sets a floating-point value.</summary>
	public float Float {
		get { this.SetStreamPos(); return this.Source.DefinitionsDataReader.ReadSingle(); }
		set { this.SetStreamPos(); this.Source.DefinitionsDataWriter.Write(value); }
	}

	/// <summary>Gets or sets an integer value.</summary>
	public int Integer {
		get { this.SetStreamPos(); return this.Source.DefinitionsDataReader.ReadInt32(); }
		set { this.SetStreamPos(); this.Source.DefinitionsDataWriter.Write(value); }
	}

	/// <summary>Gets or sets a vector value.</summary>
	public Vector3 Vector {
		get { this.SetStreamPos(); return new Vector3(this.Source.DefinitionsDataReader.BaseStream); }
		set {
			this.SetStreamPos();
			this.Source.DefinitionsDataWriter.Write(value.X);
			this.Source.DefinitionsDataWriter.Write(value.Y);
			this.Source.DefinitionsDataWriter.Write(value.Z);
		}
	}

	#endregion

	#region Extended Properties

	public bool Boolean {
		get { return this.Float != 0f; }
		set { this.Float = value ? 1f : 0f; }
	}

	#endregion

	#region Read-Only Properties

	/// <summary>Gets a string value.</summary>
	public string String {
		get { return this.Source.GetString((uint)this.Integer);  }
	}

	public Function Function {
		get { return this.Source.Functions[this.Integer]; }
	}

	#endregion
}

If the offset for a statement is negative in a function, that means that the function being called is an internally-implemented one. The source code for the test application in the screenshot at the top of this entry is as follows:

float testVal;

void() test = {
	dprint("This is a QuakeC VM test...\n");
	
	testVal = 100;
	dprint(ftos(testVal * 10));
	dprint("\n");
	
	while (testVal > 0) {
		dprint(ftos(testVal));
		testVal = testVal - 1;
		dprint("...\n");
	}
	dprint("Lift off!");
	
};

There's a huge amount of work to be done here, especially when it comes to entities (not something I've looked at at all). All I can say is that I'm very thankful that the .qc source code is available and the DOS compiler runs happily under Windows - they're going to be handy for testing.

Vista and MIDI

Tuesday, 14th August 2007

I have a Creative Audigy SE sound card, which provides hardware MIDI synthesis. However, under Vista, there was no way (that I could see) to change the default MIDI output device to this card, meaning that all apps were using the software synthesiser instead.

Vista MIDI Fix is a 10-minute application I wrote to let me easily change the default MIDI output device. Applications which use MIDI device 0 still end up with the software synthesiser, unfortunately.

To get the hardware MIDI output device available I needed to install Creative's old XP drivers, and not the new Vista ones from their site. This results in missing CMSS, but other features - such as bass redirection, bass boost, 24-bit/96kHz output and the graphical equaliser - now work.

The Creative mixer either crashes or only displays two volume sliders (master and CD audio), which means that (as far as I can tell) there's no easy way to enable MIDI Reverb and MIDI Chorus.

Quake 2 PVS, Realigned Lightmaps and Colour Lightmaps

Friday, 10th August 2007

Quake 2 stores its visibility lists differently to Quake 1 - as close leaves on the BSP tree will usually share the same visibility information, the lists are grouped into clusters (Quake 1 stored a visibility list for every leaf). Rather than go from the camera's leaf to find all of the other visible leaves directly, you need to use the leaf's cluster index to look up which other clusters are visible, then search through the other leaves to find out which reference that cluster too.

In a nutshell, I now use the visibility cluster information in the BSP to cull large quantities of hidden geometry, which has raised the framerate from 18FPS (base1.bsp) to about 90FPS.

I had a look at the lightmap code again. Some of the lightmaps appeared to be off-centre (most clearly visible when there's a small light bracket on a wall casting a sharp inverted V shadow on the wall underneath it, as the tip of the V drifted to one side). On a whim, I decided that if the size of the lightmap was rounded to the nearest 16 diffuse texture pixels, one could assume that the top-left corner was not at (0,0) but offset by 8 pixels to centre the texture. This is probably utter nonsense, but plugging in the offset results in almost completely smooth lightmaps, like the screenshot above.

   
Before and after - coloured lightmaps.

I quite like Quake 2's colour lightmaps, and I also quite like the chunky look of the software renderer. I've modified the pixel shader for the best of both worlds. I calculate the three components of the final colour individually, taking the brightness value for the colourmap from one of the three channels in the lightmap.

float4 Result = 1;

ColourMapIndex.y = 1 - tex2D(LightMapTextureSampler, vsout.LightMapTextureCoordinate).r;
Result.r = tex2D(ColourMapSampler, ColourMapIndex).r;

ColourMapIndex.y = 1 - tex2D(LightMapTextureSampler, vsout.LightMapTextureCoordinate).g;
Result.g = tex2D(ColourMapSampler, ColourMapIndex).g;

ColourMapIndex.y = 1 - tex2D(LightMapTextureSampler, vsout.LightMapTextureCoordinate).b;
Result.b = tex2D(ColourMapSampler, ColourMapIndex).b;

return Result;

Journals need more animated GIFs

Thursday, 9th August 2007

Pixel shaders are fun.

I've implemented support for decoding mip-maps from mip textures (embedded in the BSP) and from WAL files (external).

Now, I know that non-power-of-two textures are naughty. Quake uses a number of them, and when loading textures previously I've just let Direct3D do its thing which has appeared to work well.

However, now that I'm directly populating the entire texture, mip-maps and all, I found that Texture2D.SetData was throwing exceptions when I was attempting to shoe-horn in a non-power-of-two texture. Strange. I hacked together a pair of extensions to the Picture class - GetResized(width, height) which returns a resized picture (nearest-neighbour, naturally) - and GetPowerOfTwo(), which returns a picture scaled up to the next power-of-two size if required.

All textures now load correctly, and I can't help but notice that the strangely distorted textures - which I'd put down to crazy texture coordinates - now render correctly! It turns out that all of the distorted textures were non-power-of-two.

The screenshots above demonstrate that Quake 2 is also handled by the software-rendering simulation. The current effect file for the world is as follows:

uniform extern float4x4 WorldViewProj : WORLDVIEWPROJECTION;

uniform extern float Time;
uniform extern bool Rippling;

uniform extern texture DiffuseTexture;
uniform extern texture LightMapTexture;

uniform extern texture ColourMap;

struct VS_OUTPUT {
	float4 Position : POSITION;
	float2 DiffuseTextureCoordinate : TEXCOORD0;
	float2 LightMapTextureCoordinate : TEXCOORD1;
	float3 SourcePosition: TEXCOORD2;
};

sampler DiffuseTextureSampler = sampler_state {
	texture = <DiffuseTexture>;
	mipfilter = POINT;
};

sampler LightMapTextureSampler = sampler_state {
	texture = <LightMapTexture>;
	mipfilter = LINEAR;
	minfilter = LINEAR;
	magfilter = LINEAR;
};

sampler ColourMapSampler = sampler_state {
	texture = <ColourMap>;
	addressu = CLAMP;
	addressv = CLAMP;
};

VS_OUTPUT Transform(float4 Position : POSITION0, float2 DiffuseTextureCoordinate : TEXCOORD0, float2 LightMapTextureCoordinate : TEXCOORD1) {

	VS_OUTPUT Out = (VS_OUTPUT)0;

	// Transform the input vertex position:
	Out.Position = mul(Position, WorldViewProj);
	
	// Copy the other values straight into the output for use in the pixel shader.
	Out.DiffuseTextureCoordinate = DiffuseTextureCoordinate;
	Out.LightMapTextureCoordinate = LightMapTextureCoordinate;
	Out.SourcePosition = Position;

	return Out;
}

float4 ApplyTexture(VS_OUTPUT vsout) : COLOR {

	// Start with the original diffuse texture coordinate:
	float2 DiffuseCoord = vsout.DiffuseTextureCoordinate;

	// If the surface is "rippling", wobble the texture coordinate.
	if (Rippling) {
		float2 RippleOffset = { sin(Time + vsout.SourcePosition.x / 32) / 8, cos(Time + vsout.SourcePosition.z / 32) / 8 };
		DiffuseCoord += RippleOffset;
	}

	// Calculate the colour map look-up coordinate from the diffuse and lightmap textures:
	float2 ColourMapIndex = {
		tex2D(DiffuseTextureSampler, DiffuseCoord).a,
		1 - (float)tex2D(LightMapTextureSampler, vsout.LightMapTextureCoordinate).rgba
	};
	
	// Look up and return the value from the colour map.
	return tex2D(ColourMapSampler, ColourMapIndex).rgba;
}

technique TransformAndTexture {
	pass P0 {
		vertexShader = compile vs_2_0 Transform();
		pixelShader  = compile ps_2_0 ApplyTexture();
	}
}

It would no doubt be faster to have two techniques; one for rippling surfaces and one for still surfaces. It is, however, easier to use the above and switch the rippling on and off when required (rather than group surfaces and switch techniques). Given that the framerate rises from ~135FPS to ~137FPS on my video card if I remove the ripple effect altogether, it doesn't seem worth it.

Sorting out the order in which polygons are drawn looks like it's going to get important, as I need to support alpha-blended surfaces for Quake 2, and there are some nasty areas of Z-fighting cropping up.

Alpha-blending in 8-bit? Software Quake didn't support any sort of alpha blending (hence the need to re-vis levels for use with Quake GL as underneath the opaque waters were marked as invisible), and Quake 2 has a data file that maps 16-bit colour values to 8-bit palette indices. Quake 2 also had a "stipple alpha" mode used a dither pattern to handle the two translucent surface opacities (1/3 and 2/3 ratios).