# Importing Quake 1 Level Geometry from .map Files

## Intro

I have this nostalgic relation with Quake/HL series, they were one of my greatest motivation towards game tech. I really admire how they built their worlds upon simple basic concepts, like plane bounded convex polyhedron, what they call “brushes”. The idea is to take a bunch of planes (in a mathematical sense), and use them as boundaries of a convex subspace, which is the intersection of the half-spaces behind them.

## Some Basics

The equation, $Ax + By + Cz - D = 0$ is one practical way to define a plane. Points $\bold{p} = (x, y, z)$ satisfying this equation lie on a plane in 3D Euclidean space, where $(A, B, C) = \bold{n}$ is the coordinates of the normal vector, perpendicular to the plane, and $D$ is the shortest signed distance to the plane from the origin. A different way to visualise it is to take a plane having normal vector $\bold{n}$, running through the origin, and then shift to the normal direction with $D/|\bold{n}|$ units. It is practical to keep the normal vector $\bold{n}$ unit length, that is, normalise the plane equation parameters.

Using a plane defined by this equation, we can classify the relation of a point to the plane. Substituting a $\bold{p_0}=(x_0, y_0, z_0)$ point to the equation $Ax_0 + By_0 + Cz_0 - D = d$ we will obtain a scalar value $d$, which is the shortest signed distance between the point and the plane. If it is positive, the point is in front of the plane, if it is negative, it is behind it. In some application, it makes sense to classify points whose distance is zero as they are on the plane. For us, it is unnecessary now. (By the way, due to the numeric inaccuracies of floating point arithmetic, it is not practical to test against exact zero values to determine whether a point lies on the plane. Instead we check if the signed distance is below a small threshold, $\epsilon$: $|Ax_0 + By_0 + Cz_0 - D| < \epsilon$.)

Now we have a simple, handy tool to classify points against planes, so we can move on to construct convex polyhedrons using it. We know, if a $\bold{p} = (x, y, z)$ point satisfies the inequality $Ax + By + Cz - D < 0$ we know that it lies behind the plane.

If we setup a system of $m$ inequalities using plane equations, we can define closed convex polyhedrons within 3D space:

$\begin{array}{rcr} A_1x + B_1y + C_1z - D_1 & < & 0 \\ A_2x + B_2y + C_2z - D_2 & < & 0 \\ \vdots & \vdots & \vdots \\ A_mx + B_my + C_mz - D_m & < & 0 \end{array}$

where the $i$th inequality represents a $\bold{P_i} = (A_i, B_i, C_i, D_i)$ plane. If a $\bold{p}=(x, y, z)$ point satisfies all the inequalities then the point is inside the polyhedron. We consider the subspace defined like this valid only if the subspace has a finite, positive volume. This excludes empty, or degenerate forms of subspaces.

## Map File Format

[2] gives a detailed description how brushes are defined in Quake 1 map files. .MAP files are simple text files, listing level brushes and entities in a simple structure. A brush consists of a list of face definitions. Each face definition contains three points $p_1, p_2, p_3$, and some additional properties – texture name, UV offsets, rotation, etc. The three points span the plane of the given face, but is not guaranteed that any of them is at the vertex position. To derive the vertices of the polyhedron, we have to convert these three points to plane equations first, calculating the  normal vector $\bold{n'} = (\bold{p_2} - \bold{p_1}) \times (\bold{p_3} - \bold{p_1})$, normalise it: $\bold{n} = (A, B, C) = \bold{n'} / |\bold{n'}|$, and calculate the parameter $D = -\bold{p_1}\bold{n}$.

## Converting Brushes to Meshes

Once we have the face planes ready, we should convert them to vertices and indices in order to make them suitable to render. [2] proposes a simple method, originated in the Q1 bsp tool: they take a large $[-4096..4096]^3$ cube, and “slice” it with all the planes of the brush into two parts, and keep only the part behind the bounding planes. What remains is the convex polyhedron we are looking for.

We start with a list of faces defined by vertices which form a closed (and convex) loop around the face. Two consecutive vertices define an edge. To slice a face against a plane, we test all the face edges against it. If both vertices are behind the plane, we keep both. If they are in front, then we omit them. If one of them is behind and the other is in front, we keep the one behind, and store the intersection point between the edge and the plane, instead of the vertex in front of the plane. (This method also provides an easy method to detect redundant planes, i. e. which does not influence the final brush geometry at all.)

This approach seems quite simple, but making it numerically was not entirely straightforward. After all, I came up with the following:

Let $M = \{ f_0, f_1, ... , f_m \}$ is an initial set of faces. Each face is defined by an ordered list of vertices $f_i = (v_{i0}, v_{i1}, .., v_{in})$$M$ initially contains faces of a $[-4096..4096]^3$ cube. Let $B = \{ p_0, p_1, ... , p_b, f'_0, f'_1, ..., f'_b \}$ is a set of $p_i$ planes of the input brush we want to convert, with the corresponding $f'_i$ faces, which are also an ordered list of vertices forming an edge loop around the face, initially empty. The clipping algorithm is:

For all $p_i \in B$:
Let $C$ is an ordered list of clipped vertices
// $C$ will contain the vertices of the edge loop
// of the new face we get after clipping
For all $f_j \in M$:
Let $V$ is an ordered list of vertices
// $V$ will contain the vertices of the edge loop
// around $f_j$ after the clipping is done
For all $v_k \in f_j:$
If $v_k$ is behind $p_i$:
Append $v_k$ to the end of $V$
If $v_{k+1}$ is on the opposite side of $p_i$ than $v_k$:
Let $v'_k$ the intersection point between $p_i$ and the section $\overline{v_kv_{k+1}}$.
Append $v'_k$ to the end of both $V$ and $C$
Replace vertices in face $f_j$ with $V$
If $C$ is not empty:
For all $c_i \in C$:
If $c_i \notin f_j$:
Insert it where it follows the previous vertices
in the right winding order

This will result in a set of faces with all the vertices in the right order, which is easy to assemble into an actual mesh.

Some images of the results, without any textures or materials for now:

The lights are simple point lights, with shadow maps using Poisson disc filter. The light energy and radius values are calculated by an empirical formula, hand tweaked to give somewhat similar results to the original lighting, using the light parameters specified the map file.

The next step is to import all the materials. To be continued….