# Path tracing Quake in Blender

## Introduction

This week twenty-five years ago, Quake broke new ground in game engine realism. It was one of the first commercial games to have fully texture mapped 3D scenes rendered in real-time, with pre-computed lightmaps adding an extra layer of atmosphere.

Still, the requirement that the game run in real time on meagre 1996 hardware, placed massive constraints on graphical realism. In this post I want to explore how the game can be made to look better, with modern hardware and offline rendering.

I am going to talk about how I wrote a script for converting Quake demo files into Blender scenes. Blender is a free and open source 3D modelling and rendering application. Its renderer, Cycles, is a path tracer capable of producing photorealistic imagery, supporting features such as motion blur, depth of field, a comprehensive shader system, and much more. By exporting to Blender we get to use all of these features for free, without having to write a new renderer. My objective is to use the original game assets as much as possible, while relying on Blender’s accurate lighting simulation to improve realism.

Throughout this post I will be linking to the source code, which is part of my pyquake repository. If you want to have a go at importing your own demos into Blender, I have put together some instructions, but I probably won’t respond to any issues or PRs. I encourage you to make a fork if you are interested in maintaining this project.

## Parsing demos

A demo file is a compact recording of a Quake game, for the purposes of sharing with other players, or for personal review. Being a multiplayer game, the game is split into client and server components. The demo is essentially a recording of the traffic that goes from server to client during the game. Given a demo, and an installation of Quake, it is then possible to reproduce exactly what the player saw at the time of recording:

Note that even in single player mode, there are still client and server components in the code, with the network layer replaced by a simple memory transfer, which means demos can be recorded in this setting too.

Since the demo file format is closely related to the Quake protocol, it can be understood by reading the appropriate layer of Quake’s networking code. It is then relatively straightforward, if a little laborious, to write a parser for the demo file format in Python.

When parsed, the demo file can be read a little like a script for a play. The initial commands set the scene, telling us which assets — the level, models, and sounds — will be used throughout the demo:

Next comes a series of baseline commands, which define a set of entities, each of which is associated with one of the aforementioned models, like a cast list in a play. Entities represent all objects in the game. An entity might be a monster, the player, a health pack, a lift, a button. Everything except for the static parts of the level:

Finally, a series of update and time commands provides the entities’ position, angle, and pose at the given time; in the play analogy, this is like a series of stage directions:

The above sequence repeats for every frame in the demo, with each frame containing a ServerMessageUpdate command for each entity.

My Python code for parsing demo files can be found here.

## Parsing assets

The level itself is defined in a .bsp file. This gives the geometry and texture information for the level, along with some other data structures which we will come onto later. The file format is well documented and, with a little effort, can be parsed into Python classes. Similarly, the models which represent things like monsters, weapon models and so on, are defined in .mdl files, which is also well documented. This project doesn’t handle sound (for the video at the top I simply dubbed a recording from the game), so there is no need to parse sound assets.

My Python code for parsing .bsp and .mdl files can be found here (.bsp) and here (.mdl).

Blender has a rich Python scripting interface. In fact, Blender’s GUI works by interacting with a Python API, and so anything that can be done through the UI can also be scripted. Using this Python interface, I made a script to import the .bsp files and models parsed above into Blender. For most of the concepts in the Quake assets there are direct analogues in Blender:

• Quake models and map geometry can be represented as Blender meshes.
• Model poses in Quake models can be represented with shape-keys in Blender.
• Quake texture data can be represented as images.
• Texture coordinates can be encoded as Blender UV maps.
• Effects such as warping water, animated textures, and sky boxes can be implemented as shaders.

My code for importing the parsed .mdl and .bsp files into Blender is here (.mdl) and here (.bsp).

Importing the parsed demo consists of reading the intro section to tell us which game assets (models and map) to convert into Blender assets, and then animating them according to the baseline / update sections. I make use of Blender’s animation support to do this. More specifically, I insert position, orientation, and shape-key keyframes for every ServerMessageUpdate command in the parsed demo. I also keyframe animated shaders such as warping water so that they move according to the current game time. Below is a recording showing the result of importing a demo from the first level in the game. My code for importing demos files into Blender can be found here.

## Lighting

At this point we have our geometry loaded and animated, with some textures applied. Still, we are missing light sources. When the Quake levels were designed, lights were defined as point light sources scattered throughout the level. A compilation process then converts these point light sources into light maps. This process works by assigning a low resolution texture to each surface in the level, and calculating how much each texel is directly illuminated by these point light sources. Since this process only measures direct illumination, level designers included secondary light sources to fake the effects of bounced light.

Since the original map sources are available, I could use these lights to illuminate my scene. However, because Blender can do accurate multi-bounce illumination by itself, including all of these original Quake lights would mean doubling up on bounced light, which would give an over illuminated scene.

Instead, I am going to illuminate the scene directly from the texture information. All textures in Quake are composed using a 256 colour palette:

The last 32 colours in this palette are special in that they always appear as fullbright, that is to say, even when in shadow they still appear fully illuminated:

In my system, I treat these fullbright colours as being emissive, so that they illuminate the space around them as well as appearing bright to the camera:

In addition, I treat select models as being emissive, for example the flame models that are used in the non-tech levels.

So our scene is now set — our geometry is in place, textures are applied, and lighting is defined. Let’s render an image and see what we get:

Oh dear! This single frame took around 20 seconds to render on my GeForce RTX 2060, and it is still incredibly grainy! Even applying Blender’s bundled denoiser can’t recover a clean image. Blender can normally handle scenes of this complexity with no issues, so what’s going on?

## Importance sampling

When Blender wishes to work out how well a point is illuminated, it (by default) randomly samples from all light sources in the scene, and averages the contribution from each light source. For most levels, there are far more light sources in the scene than are visible at any given time. This means that the contribution from most light sources is zero, and so the result is highly noisy, depending on whether a visible light happened to be sampled.

To illustrate this idea, say there are 100 lights in our scene, each one a single square in the below 10x10 grid. The camera’s location is shown as the green cross. Ignore the red box for now (we will come onto that later). For a particular point that our camera can see, the contribution of each light is represented by the brightness of the square. Due to occlusion by level geometry, only fifteen lights contribute to the illumination of the point.

We could just take the average value of all of these 100 lights to get an exact answer, but there are two problems with this:

• Sampling all the lights might take a really long time.
• In reality, each individual light is not uniform in contribution: the intensity might vary depending on where on the light we sample. Imagine a long flourescent tube that is partially occluded by a wall, or a light texture that is not uniformly emissive. In this case, taking just 100 samples would not be enough.

To avoid these issues, we use a stochastic approach known as Monte Carlo integration which works by random sampling. Let’s say we take 32 samples in order to measure the contribution to the point in question. We draw 32 times from the 100 lights, replacing each time, and average the resulting value, to give the sample mean. The answer we get is random, since it is dependent on the values we draw. Here is a plot that shows the distribution of these sample means after drawing 100,000 samples:

You can see that there is some variance here: the sample mean can realistically land between 0 and 0.3. This variance is undesirable, and manifests itself as noise in the resulting image.

Is there a way to reduce the variance of the sample mean, while still keeping the same mean (of the sample means)? It turns out there is a simple scheme we can use, a type of importance sampling. If we know a priori that none of the lights outside of the red box contribute to the final image, then we can simply draw our 32 samples from this 5x5 box instead. Since we are now drawing from 25 values rather than 100, we would expect the sample mean to be four times larger than when drawing from the full set of lights. We then correct for this by dividing our sample mean by four. Here is the distribution of the corrected means using this new scheme:

As you can see, the variance is reduced, but the mean (of the sample means) stays the same, so we get a less noisy but still correct (in expectation) image.

This is a simplification of how Blender samples lights, but the essence is still the same: noise can be reduced if we avoid sampling lights that do not contribute to the final image. Blender has a inbuilt method to exclude lights from being sampled, referred to as Multiple Importance Sampling in the UI, and sample_as_light in the code. This flag can be animated with keyframes, so we can make it change depending on the current player position and view angle.

The task then, is to come up with a heuristic to cull lights which do not influence the current view (or as many as is feasible). In other words, we want to avoid sampling lights that cannot be reached after a single bounce from the camera.

## BSP visibility data

Fortunately .bsp files come with built-in data structures for solving a similar problem. One of the great innovations that enabled Quake to run efficiently on 1996 hardware is that of visible-surface determination, that is to say, working out which parts of the level are visible from any given player position.

In order to solve this problem, the .bsp file divides the level into a set of disjoint volumes called leaves. Each leaf contains a handful of faces.

The visibility information in the BSP is a large (but compressed) pre-computed 2D bitmap telling us which leaves can potentially see each other. The set of leaves that a given leaf can potentially see is known as its potentially visible set, or PVS:

In the game, surfaces that lie outside of the camera’s PVS are not drawn. Our problem is slightly different in that we also need to sample lights that are invisible to the camera, but that are visible from at least one point that is visible to the camera.

Let’s take an example where the light influences the image. Here is an external shot of the first corridor in the game, with a light, indicated by the orange star, just around the corner from the player, indicated by the lighter orange pyramid1.

As a first approximation, we can simply sample a light if and only if the camera’s PVS has any leaves in common with the light’s PVS. If we now draw the PVS of the light and the camera, we can see that there is in fact an intersection, so this light would be sampled with this method:

This works well, and does improve the situation a bit. However, there is more that we can do. The problem is that the PVS is too conservative, meaning that there are still lots of fully occluded leaves that could be omitted but nevertheless appear in the PVS. Similarly, there are points in the light’s PVS that have very little illumination owing to limited power of the light and the inverse-square law. The net effect is that we still end up sampling many lights that have no contribution to the scene.

## Frustum culling

To improve things, we again take inspiration from Quake’s visibility calculations and apply what’s known as frustum culling. With the camera we can associate a viewing frustum, that is to say, a volume whose faces correspond with the edges of the screen projected out from the camera’s origin. Any point lying outside of the viewing frustum will be invisible to the camera, and so we can exclude these leaves from the PVS. This has the effect of hiding leaves that are behind the player, or otherwise outside the bounds of the camera’s field of view.

A similar concept can be applied to the light’s PVS: practically, a light’s sphere of influence is bounded by the inverse-square law, and so we can place a bounding box around each light, whose size is determined by how bright the light is. We can therefore reduce the light’s PVS by intersecting with this bounding box.

The final system I use is based on seeing whether these two reduced PVS volumes intersect:

In this case they still do, however you can imagine if the player were turned to face the opposite direction then the intersection would now be nil and the light would (correctly) not be sampled.

This works better than unreduced system, and as you can see, a lot better than the system that simply samples all lights:

Applying Blender’s noise reduction system to the above yields an even cleaner looking image:

One caveat about this scheme for selecting lights to sample is that it ignores the potential for influence from multiple light bounces — a bright light at the end of a serpentine corridor might still illuminate the other end via multiple bounces, yet the above method would not sample this light. While this is an issue in theory, it doesn’t appear to be an issue in practice.

## Finishing touches

There are a few extra bits required to produce the final result:

• In order to look correct, different light textures need different intensities. For example, a floodlight texture should be a lot brighter than a backlit sign. This information isn’t encoded in the game and so my system reads in a config file that contains, among other things, some good-looking intensity values for each texture.
• I treat the sky texture as emissive, using Blender’s sun light.
• Even though lights are independent of textures in the original game, the artists generally motivated a particular light source by placing it near a would-be emissive model or texture, so that visually the lighting makes sense. Despite this, there are still some areas in the original game that have unmotivated lights and so would be too dark in my rendering. To account for this I add in a select few lights from the original map sources to illuminate these areas. These light locations and intensities go into the config file mentioned above.
• The original game has a particle system used for explosions, teleport effects, and so on. I use Blender’s own particle system to display these.

There is still more that could be added in:

• Viewport gun. The original game shows the current weapon at the bottom of the screen.
• Lightning effects. As visible in the lightning gun, and in the final level of episode one.
• Sprites. There are a few sprites in the game, used for things such as the explosion effect (separate to the particles), and bubbles.
• Animated lights. The original game’s lightmaps could be animated, useful for things like flickering bulbs, or to have lights turned on and off by in-game triggers.

## Conclusion

I have produced a system that imports Quake demo files and all the associated assets into Blender. In many ways this has been a case of replicating a decent chunk of Quake’s client into Python, replacing the rendering portion with code that duplicates the game’s state into Blender. This took a long time, so perhaps it would have been more efficient to re-use some of Quake’s code and introduce my code at a lower level. On the other hand, I have built up a library of code for interfacing with several of Quake’s file formats, and some supporting code (eg. a simplex solver). These might be useful for other projects within the Quake community.

Speaking of other uses, the scene produced by Blender could be used for player analysis. Speedruns of the game are often won or lost by small fractions of a second. Being able to load up multiple demos into the same scene and track exactly who is ahead at what point could give insight into where time can be gained.

While doing this project, one comparison that has been at the back of my mind is that of real-time renderers, particularly the Quake II RTX (Q2RTX) project. Even with all of my optimizations, rendering still takes several seconds per frame, whereas Q2RTX runs in real-time. Blender also supports hardware ray-tracing, so why is it still so much slower? I can think of a few possible reasons for this:

• Q2RTX employs temporal filtering to smooth its images. This means that samples from earlier frames contribute to the current frame. Blender doesn’t yet fully support temporal filtering, so I had to render each frame independently.
• My system has to determine lights to sample on a per-frame basis. An RTX based system could decide lights to sample on a per-path basis. Only a direct (zero bounce) PVS calculation needs to be done for each surface point whose incoming light is being integrated. This would naturally lead to fewer lights being sampled per pixel. From my reading I can’t confirm this to be the case with Q2RTX, but it seems likely.
• Blender’s path-tracing renderer, Cycles, is very general in that it has to be able to cope with a wide variety of scene types — different complexities of geometry, different number of lights, and so on. In contrast, Q2RTX is a very specialized renderer and can thus be optimized for the specific task of rendering Quake levels.

## Footnotes

1. If you are familiar with this level you will know that there is a door that normally blocks this passage. For the purposes of this discussion we assume the door is open.

If you enjoyed this post, please consider supporting my efforts:

Share on: