|See what's going on with flipcode!|
Quake 2 BSP File Format
by (07 June 2000)
|Return to The Archives|
The purpose of this document is to detail the structure of the BSP file format
used by Quake 2 to store maps; in particular, the focus is on rendering Quake 2
worlds. Although there is other information contained in the BSP file used for
other game elements (such as enemy AI, etc.), I don't have complete information
on them so I won't discuss these beyond mentioning them. If you have anything to
contribute on these parts please feel free to e-mail at the address listed
above. Also, although I've tried my best to minimize errors, if you find
anything that is incorrect please let me know.|
In addition to just a bare description of the BSP file format, this document also attempts explain the techniques which are at the core of the Quake rendering engine. In general it's assumed that the reader is familiar with the basic principles of 3D graphics, including the BSP tree data structure.
This document covers version 38 of the BSP file format which is the version used by Quake 2. This is also the version of the BSP file format used by Kingpin (which was created using the Quake 2 engine) and therefore all of the information contained is relevant to those files as well. While Quake 1 and Quake 3: Arena use similar BSP formats the formats are not directly compatible. However, because of the similarity in the structure and techniques, this document should be of some use to anyone interested in these formats as well.
My information about the Quake 2 BSP format was all learned by a lot of experimentation in implementing my own Quake 2 BSP renderer along with examining source code for Quake-like engines generously released into the public domain by their authors. These engines were the Twister Engine by Stefano Lanza, the Arnfold 2 Engine by Andrei Fortuna and the Poly Engine by Alexey Goloshubin. The source code for all three of these engines is freely available on the web; if you find something's missing out of this document, I recommend you check out these engines. Id Software has also released the source code for their Quake 2 tools, including the QBSP map file compiler which outputs BSP files, although I didn't find it to be particularly useful in my own exploration.
Using id Software file formats in a publicly distributed application always
seemed a little questionable to me in terms of legality. In preparation of this
document I contacted id Software to resolve the issue; John Carmack was kind
enough to send along this response:|
"We do not legally protect the file formats, but you can't use any of the released tools, or tools derived from them (except the GPL'd Quake 1 tools) to generate content for a commercial venture. If you are writing everything yourself, no problem."
To help make this document easier to read I've included C-syntax structures for
all of the file structures (with the assumption that there no extra padding
bytes between the fields). To simplify the notation and standardize the
meaning, the abbreviations int32 and uint32 are used for signed and unsigned
32-bit integers; similar abbreviations are used for 16-bit and 8-bit integers as
well. Also, the following two structures are used throughout the BSP file
format to store vertices and vectors:|
The second version is used in some places to conserve memory where the precision is unessential (like storing the bounding boxes) since it takes only 6 bytes compared with the 12 byte floating point version. These are regular integer representations, not fixed-point.
To give an introduction to the terminology used and the idea behind some of the
data structures, this section briefly describes the process of rendering a Quake
A Quake map is carved up into convex regions that become the leaves of the BSP tree, and anytime the camera is positioned within a level it is contained in exactly one of these convex regions. The leaves are grouped together with neighboring leaves to form clusters; exactly how these clusters are formed is determined by the tool that creates the BSP file. For each cluster, a list of all of the other clusters which are potentially visible is stored. This is referred to as the potentially visible set (PVS).
To render a Quake map, first the BSP tree is traversed to determine which leaf the camera is located in. Once we know which leaf the camera is in, we know which cluster it's in (remembering that each leaf is contained in exactly one cluster). The PVS for the cluster is then decompressed giving a list of all the potentially visible clusters from the camera location. Leaves store a bounding box which his used to quickly cull leaves that are not within the viewing frustum.
Many people incorrectly associate the BSP tree with the visibility algorithm
used by Quake and similar engines. As described above, the visible surface
determination is done using a precomputed PVS. The BSP tree is primarily used
to divide the map into regions and to quickly determine which region the camera
is in. As a result, it isn't that fundamental to any of the rendering
algorithms used in Quake and any data structure giving a spatial subdivision
(like an octree or a k-D tree) could be used instead. BSP trees are very simple
however, and they are useful for some of the other non-rendering tasks in the
Traditionally when discussing BSP trees a distinction is made between those BSP trees that store the faces in the leaves (leaf-based BSP trees) and those that store them in the internal nodes (node-based BSP trees). The variation of BSP tree Quake uses is actually both; the reason for this is the dual use of the BSP tree in both rendering and in collision detection. For the purpose of rendering, it is useful to have the faces stored in the leaves because of the way the PVS is used. If you're not interested in performing collision detection, the faces in the nodes can be completely ignored.
As far as I know all BSP files are stored in a little-endian (Intel) byte order
and converted as loaded when used on a big-ending platform. This allows the
same map files to be shared by Quake clients running on all different platforms.
If you're going to be loading BSP files on a big-endian machine -- like a
Macintosh or UNIX machine -- you're going to have to be careful about swapping
the byte order.|
The Quake BSP file format is organized around a directory structure, where all of the data is contained in "free floating" lumps within the file. There's a directory in the beginning of the file which tells the offset of the start of the lump and the length. This directory comes after the first 8 bytes of the file is a table of contents which gives the location and length of these lumps.
The format for the BSP file header is the bsp_header structure shown below:
The first four bytes of the BSP file is a tag which can be used to identify the file as an id Software BSP file. These bytes spell out "IBSP". Following that is a 32-bit unsigned integer specifying the version number. As mentioned earlier, the version described in this document is 38 (decimal).
Below is a table showing the different lumps contained in the BSP file and their index in the lump array in the header. The purpose of lumps marked with a question mark is not known (the names are derived from the QBSP source code), however they are not needed for constructing a simple Quake level renderer.
Index Name Description 0 Entities MAP entity text buffer 1 Planes Plane array 2 Vertices Vertex array 3 Visibility Compressed PVS data and directory for all clusters 4 Nodes Internal node array for the BSP tree 5 Texture Information Face texture application array 6 Faces Face array 7 Lightmaps Lightmaps 8 Leaves Internal leaf array of the BSP tree 9 Leaf Face Table Index lookup table for referencing the face array from a leaf 10 Leaf Brush Table ? 11 Edges Edge array 12 Face Edge Table Index lookup table for referencing the edge array from a face 13 Models ? 14 Brushes ? 15 Brush Sides ? 16 Pop ? 17 Areas ? 18 Area Portals ?Most of the lumps are stored as an array of structures where the structure has a fixed size. For instance the vertex lump is an array of point3f structures. Since each point3f is 12 bytes, the number of vertices can be computed by dividing the size of the vertex lump by 12. Similar computations can be done for the plane, node, texture information, faces, leaf and edge lumps.
In the following sections, the purpose and structure of the known lumps is discussed.
The vertex lump is a list of all of the vertices in the world. Each vertex is 3
floats which makes 12 bytes per vertex. You can compute the numbers of vertices
by dividing the length of the vertex lump by 12. |
Quake uses a coordinate system in which the z-axis is pointing in the "up" direction. Keep in mind that if you modify the coordinates to use a different system, you will also need to adjust the bounding boxes and the plane equations.
|Not only are vertices shared between faces, but edges are as well. Each edge is stored as a pair of indices into the vertex array. The storage is two 16-bit integers, so the number of edges in the edge array is the size of the edge lump divided by 4. There is a little complexity here because an edge could be shared by two faces with different windings, and therefore there is no particular "direction" for an edge. This is further discussed in the section on face edges.|
The face lump stores an array of bsp_face structures which have the following
The size of the bsp_face structure is 20 bytes, the number of faces can be determined by dividing the size of the face lump by 20.
The plane_side is used to determine whether the normal for the face points in the same direction or opposite the plane's normal. This is necessary since coplanar faces which share the same node in the BSP tree also share the same normal, however the true normal for the faces could be different. If plane_side is non-zero, then the face normal points in the opposite direction as the plane's normal.
The details of texture and lightmap coordinate generation are discussed in the section on texture information and lightmap sections.
Face Edge Lump
Instead of directly accessing the edge array, faces contain indices into the
face edge array which are in turn used as indices into the edge array. The face
edge lump is simply an array of unsigned 32-bit integers. The number of
elements in the face edge array is the size of the face edge lump divided by 4
(note that this is not necessarily the same as the number of edges).|
Since edges are referenced from multiple sources they don't have any particular direction. If the edge index is positive, then the first point of the edge is the start of the edge; if it's negative, then the second point is used as the start of the edge (and obviously when you look it up in the edge array you drop the negative sign).
The plane lump stores and array of bsp_plane structures which are used as the
splitting planes in the BSP. The format for for the bsp_plane structure is:|
Each bsp_plane structure is 20 bytes, so the number of planes is the size of the plane lump divided by 20.
The x, y and z components of the normal correspond to A, B, C constants and the distance to the D constant in the plane equation:
A point is on the plane is F(x, y, z) = 0, in front of the plane if F(x, y, z) > 0 and behind the plane if F(x, y, z) < 0. This is used in the traversal of the BSP tree is traversed.
The nodes are stored as an array in the node lump, where the first element is
the root of the BSP tree. The format of a node is the bsp_node structure:|
Each bsp_node is 28 bytes, so the number of nodes is the size of the node lump divided by 28.
Since a child of a node may be a leaf and not a node, negative values for the index are used to incate a leaf. The exact position in the leaf array for a negative index is computed as -(index + 1) so that the first negative number maps to 0.
Since the bounding boxes are axis aligned, the eight coordinates of the box can be found from the minimum and maximum coordinates stored in the bbox_min and bbox_max fields.
As mentioned earlier, the faces listed in the node are not used for rendering but rather for collision detection.
The leaf lump stores an array of bsp_leaf structures which are the leaves of the
BSP tree. The format of the bsp_leaf structure is:|
The bsp_leaf structure is 28 bytes so the number of leaves is the size of the leaf lump divided by 28.
Leaves are grouped into clusters for the purpose of storing the PVS, and the cluster field gives the index into the array stored in the visibility lump. See the Visibility section for more information on this. If the cluster is -1, then the leaf has no visibility information (in this case the leaf is not a place that is reachable by the player).
Leaf Face Lump
|Instead of directly accessing the face array, leaves contain indices into the leaf face array which are in turn used as indices into the face array. The face edge lump is simply an array of unsigned 16-bit integers. The number of elements in this array is the size of the leaf face lump divided by 2; this is not necessarily the same as the number of faces in the world.|
Texture Information Lump
Texture information structures specify all of the details about how a face is
textured. The structure of the a single texture information is the bsp_texinfo
The bsp_texinfo structure is 76 bytes, so the number of texture information structures is the size of the lump divided by 76.
Textures are applied to faces using a planar texture mapping scheme. Instead of specifying texture coordinates for each of the vertices of the face, two texture axes are specified which define a plane. Texture coordinates are generated by projecting the vertices of the face onto this plane.
While this may seem to add some complexity to the task of the programmer, it greatly reduces the burden of the level designer in aligning textures across multiple faces.
The texture coordinates (u, v) for a point(x, y, z) are found using the following computation:
My own experience has shown that it is perfectly reasonable to generate the coordinates in real-time rather than storing them.
The texture name is stored with a path but without any extension. Typically, if you are loading a Quake 2 map you would append the extension "wal" to the name and then load it from the PAK file. If you're loading a Kingpin map you would append the extension "tga" and then load if from disk (Kingpin stires the textures outside of the PAK file). See the section on the WAL texture format for more details.
Leaves are grouped into clusters for the purpose of storing the visibility
information. This is to conserve space in the PVS since it's likely that nearby
leaves will have similar potentially visible areas. The first 4 bytes of the
visibility lump is a 32-bit unsigned integer indicating the number of clusters
in the map, and after that is an array of bsp_vis_offset structures with the
same number of elements as there are clusters. The bsp_vis_offset structure
The rest of the visibility lump is the actual visibility information. For every cluster the visibility state (either visible or occluded) is stored for every other cluster in the world. Clusters are always visible from within themselves. Because this is such a massive amount of data, this array is stored as a bit vector (one bit per element) and 0's are run-length-encoded. Here's an example of a C-routine to decompress the PVS into a byte array (this was adapted from the "Quake Specifications" document):
Static lighting is handled in the Quake environment using lightmaps, which are
low resolution bitmaps that are combined with the texture when rendering a face.
Lightmaps are unique to a face (unlike textures which may be used on multiple
faces). The maximum size for any lightmap is 16x16 which is enforced by the BSP
creation tool by splitting faces which would require larger lightmaps. In Quake
1 lightmaps were limited to grayscale, however Quake 2 allows for 24-bit true
Lightmaps are applied either through multi-texturing or multi-pass rendering and should be multiplied with the texture for a face when rendering.
The lightmap lump contains the data for all of the lightmaps in the world stored consecutively. Faces store the offset of their lightmap in this lump in the bsp_face structure's lightmap_offset. The actual lightmap data is stored in a 24-bits-per-pixel RGB format in a left-right, top-down order starting at this offset.
The width and height of a lightmap isn't explicitly stored anywhere and must be computed. If max_u is the maximum u component of all of the texture coordinates for a face, and min_u is the minimum u component of all the texture coordinates for a face (and similarly for the max_v and min_v), then the width and height of the lightmap for the face is given by the computation:
For information on computing the texture coordinates for a face see the Texture Information Lump section.
WAL Image Format
Quake 2 stores textures in a proprietary 2D image format called WAL. While this
isn't actually part of the BSP file format, it's essential information for
loading Quake 2 maps so I've decided to include it. Note that this doesn't
apply to Kingpin maps which use textures stored as TGA files.|
WAL textures are stored in a 8-bit indexed color format with a specific palette being used by all textures (this palette is stored in the PAK data file that comes with Quake 2). Four mip-map levels are stored for each texture at sizes decreasing by a factor of two. This is mostly for software rendering since most 3D APIs will automatically generate the mip-map levels when you create a texture. Each frame of an animated texture is stored as an individual WAL file, and the animation sequence is encoded by storing the name of the next texture in the sequence for each frame; texture names are stored with paths and without any extension.
The format for the WAL file header is the wal_header structure:
The actual texture data is stored in an 8-bits-per-pixel raw format in a left-right, top-down order.
|The entity section of the BSP file is an ASCII text buffer, formatted in the same manner as the entities in the MAP file (recall that BSP files are compiled from MAP files). Entities are things like the player spawn points, lights, health, ammunition and guns. A comprehensive list of the entities used in Quake 1 (and because of the considerable overlap, Quake 2) is available in the MAP file format section of the "Quake Specifications" document.|