4. Level Map Models

4.1 Description of .BSP Files

4.1.1 General description of level BSP Maps

The BSP maps are meant to be generated automatically. They are described here only for the purpose of helpin you write a BSP generation tool. If you are only interested in building Quake editors, please read the description of Level Maps instead.

The level BSP maps are stored in files with extension .BSP (for Binary Space Partition Tree). Those files need not necessarily contain level maps, they can also contain the definition of any entity that is not supposed to be modified during game play.

Since a BSP based model requires the calculation of a BSP tree, and this calculation is tedious, these models are not used to store definitions of monsters, players, or anything that can change shape during game play. But you could use them for a model of a big rock, because that rock isn't gonna be modified...

Moreover, there are no frames associated to a BSP based model, contrary to what happens for Alias models: it's just one single big frame. So you cannot animate them.

4.1.2 Description of the contents of .BSP files

The .BSP files contain all the information that is needed to display a level correctly, for the obvious reason that those files are meant to be distributed individually, or associated in multi-level maps without causing trouble. In DOOM, you had to take care that all the needed textures were available. Now, the textures are in the level itself.

One disadvantage of that format is that, contrary to DOOM, you cannot have a single set of textures for all your levels, or re-use textures in another level. Now guess why Quake will come on CD-ROM.

Here are the contents of levels:

  1. A list of entities that are present in the level.
  2. A description of the level map, in term of faces, edges, vertices, and textures on the faces. Actually, there might be more faces than really needed, because of the BSP tree that splits them.
  3. Some enormous amount of data to accelerate the rendering of levels, and which must be calculated off-line: a set of planes, models, BSP nodes, clip nodes, BSP leaves, visibility lists, and edge lists, face lists.

The format of level is pretty complicated, don't be disappointed if you don't understand everything on first try. Maybe you can imagine how hard it has been to hack it out of the BSP map.


4.2 The Format of BSP files

Beware: the description below is valid only for the version 0x1C of the BSP file format, used in Quake Shareware version, 22 June 96. Previous version of Quake used different formats. Future versions might differ again.

A BSP file starts with some sort of directory, of fixed size. As a matter of fact, the entries in a BSP file are always at the same place in the directory.

Here is the description of one directory entry:

typedef struct                 // A Directory entry
{ long  offset;                // Offset to entry, in bytes, from start of file
  long  size;                  // Size of entry in file, in bytes
} dentry_t;
Here is the BSP header itself, made of a version tag, and 15 entries:
typedef struct                 // The BSP file header
{ long  version;               // Model version, must be 0x17 (23).
  dentry_t entities;           // List of Entities.
  dentry_t planes;             // Map Planes.
                               // numplanes = size/sizeof(plane_t)
  dentry_t miptex;             // Wall Textures.
  dentry_t vertices;           // Map Vertices.
                               // numvertices = size/sizeof(vertex_t)
  dentry_t visilist;           // Leaves Visibility lists.
  dentry_t nodes;              // BSP Nodes.
                               // numnodes = size/sizeof(node_t)
  dentry_t texinfo;            // Texture Info for faces.
                               // numtexinfo = size/sizeof(texinfo_t)
  dentry_t faces;              // Faces of each surface.
                               // numfaces = size/sizeof(face_t)
  dentry_t lightmaps;          // Wall Light Maps.
  dentry_t clipnodes;          // clip nodes, for Models.
                               // numclips = size/sizeof(clipnode_t)
  dentry_t leaves;             // BSP Leaves.
                               // numlaves = size/sizeof(leaf_t)
  dentry_t lface;              // List of Faces.
  dentry_t edges;              // Edges of faces.
                               // numedges = Size/sizeof(edge_t)
  dentry_t ledges;             // List of Edges.
  dentry_t models;             // List of Models.
                               // nummodels = Size/sizeof(model_t)
} dheader_t;

All the offsets are counted from the start of the BSP files. The size can be 0, if the entry is not present. It must not be negative.

Basic data types

Before we start with the level entry structure, you will need to understand the following data types:

typedef float scalar_t;        // Scalar value,

typedef struct                 // Vector or Position
{ scalar_t x;                  // horizontal
  scalar_t y;                  // horizontal
  scalar_t z;                  // vertical
} vec3_t;

typedef struct                 // Bounding Box, Float values
{ vec3_t   min;                // minimum values of X,Y,Z
  vec3_t   max;                // maximum values of X,Y,Z
} boundbox_t;

typedef struct                 // Bounding Box, Short values
{ short   min;                 // minimum values of X,Y,Z
  short   max;                 // maximum values of X,Y,Z
} bboxshort_t;

scalar_t is a scalar value, that is used to represent X,Y,Z coordinates, or distances. It is a 32bit, single precision floating point number, and it can be expected that in later version it will be replaced by some fixed point number, as is typical in DOS games (because the floating point unit of Intels just amazingly sucks).

vec3_t is a 3D vector, that is used to represent either 3D position in space, or vectors normal to planes. Usually, 3D positions in space will be integer values, though they are coded in floating point. Maybe a hint that the final engine will work only with integer of fixed point values, like DOOM did.

boundbox_t is a set of two vec3_t, that represents a bounding box in 3D space. The first vec3_t stores the minimum values, the second one stores the maximum values. These bounding boxes, though less elegant than a center point and a distance, allow for greater processing speed.

bboxshort_t is a set of six short integer, that represent a condensed form of boundbox_t, the ordinary bounding box.


4.3 Level layout definition

The basic level entries are those that define the geometrical structure of the level; i.e. those are the only ones a level editor should ever bother about.

Actually, this is not totally true, because those entries are intricately related to the BSP tree format, so an intermediate format shall be used, before calculating the BSP tree and the pre-calculated entries.

4.3.1 The Definitions of Models

The name Model refers here to either a big zone, the level, or smaller independent parts inside that zone, like the grid bars on level TEST1, that open with a push on the switch.

The level map is divided in one or more Models, which are independent areas, roughly bounded by two sets of Clip Nodes, and organised internally around a BSP Tree, that contains the BSP Leaves, which are the actual areas where entities can be found (like the sectors in DOOM).

typedef struct
{ boundbox_t bound;            // The bounding box of the Model
  vec3_t origin;               // origin of model, usually (0,0,0)
  long node_id0;               // index of first BSP node
  long node_id1;               // index of the first Clip node
  long node_id2;               // index of the second Clip node
  long node_id3;               // usually zero
  long numleafs;               // number of BSP leaves
  long face_id;                // index of Faces
  long face_num;               // number of Faces
} model_t;

About the Models

The first model is the whole level itself. The other models, smaller, represent door, switches, bars, that might move around the level.

A typical BSP model is only made of one single model, and only the level maps may eventually need more than one model.

About the different fields

The numleafs field is the number of leaves in the BSP tree. It is used to determine how much room each visilists requires when decompressed (better not put a wrong number there).

The node_id field is an index to the first node of the BSP tree that splits the model.

The bnode_id and bnode_id2 field is an index to the first node of two BSP tree that are used for early collision detection. There used to be only one of these trees. The purpose of the second tree is unknown (maybe it's not for collision detection after all).

The face_id and face_num fields refer to all the consecutive faces in the face list that belong to a given model.

4.3.2 List of Vertices

The vertices definitions are used for Edges, which are part of faces.

The order of vertices in the list is irrelevant.

typedef struct
{ float X;                    // X,Y,Z coordinates of the vertex
  float Y;                    // usually some integer value
  float Z;                    // but coded in floating point
} vertex_t;

The vertices are only used for texture mapping.

There must be only one given vertex definition, for any point in 3D space.

4.3.3 The Edges

This structure stores a list of pairs of indexes of vertices, each pair defining an edge of a face. That edge will generally be used by more than one face (two or three is typical).

Edges are referenced in List of edges, that represent the actual list of edges contained in each face. The edges are not directly referenced in faces, otherwise the face structure could not have a fixed size.

typedef struct
{ u_short vertex0;             // index of the start vertex
                               //  must be in [0,numvertices[
  u_short vertex1;             // index of the end vertex
                               //  must be in [0,numvertices[
} edge_t;

Note that the first edge in the list is never used: as a matter of fact, the List of Edges uses positive or negative numbers to indicate the edge sense, so number zero would be unsuitable.

4.3.4 The Texture Informations

The texture informations define how the textures are rendred on the faces (i.e. the Wall, Floors, Ceilings, Sky, and Water areas).

Since those surfaces can be of complex shape, they are split in simple convex Faces. But then, all those faces have a reference to the same texture information.

typedef struct
{ vec3_t   vectorS;            // S vector, horizontal in texture space)
  scalar_t distS;              // horizontal offset in texture space
  vec3_t   vectorT;            // T vector, vertical in texture space
  scalar_t distT;              // vertical offset in texture space
  u_long   texture_id;         // Index of Mip Texture
                               //           must be in [0,numtex[
  u_long   animated;           // 0 for ordinary textures, 1 for water 
} surface_t;

Texture orientation

The orientation of the texture, on the face, is defined by two vectors S and T) and two offsets along these vectors, distS and distT.
See the explanation of Texture Mapping below.

The animated field is just a boolean that is set to 1 when the texture is to be used with a swirling animated texture, like water, slime or lava. If it is not set to 1 with those textures, the game crashes, complaining that surface extent is invalid.

Mips mapping

The textures are rendered by using Mip Mapping: depending on the distance from the face to the player, a different texture is used for texture mapping, so as to reduce aliasing.

Since the Mip Mapping uses distance as a trigger, the bounding box of all face vertices (i.e. the face extent) must be smaller than 256, for any coordinate. Otherwise it would not be possible to select a Mip Mapping valid for all the texture.

Once the right texture is chosen, the face is rendered as an ordinary texture-mapped convex face.

Texture names

The Mip texture are referenced by texture_id, so that more than 256 textures can be used in a level. But it is expected that the more texture you use, the slower the game will be, so do not use more than 64 without very good reasons.

Depending on the name of the texture, a face will look like a sky, or a wall or floor (that can eventually be animated).

4.3.5 The Face

The face are convex polygons that cover the original surfaces (convex polygons are more convenient for 3D rendering, especially in hardware).

typedef struct  
{ u_short plane_id;            // The plane in which the face lies
                               //           must be in [0,numplanes[ 
  u_short side;                // 0 if in front of the plane, 1 if behind the plane
  long ledge_id;               // first edge in the List of edges
                               //           must be in [0,numledges[
  u_short ledge_num;           // number of edges in the List of edges
  u_short texinfo_id;          // index of the Texture info the face is part of
                               //           must be in [0,numtexinfos[ 
  u_char typelight;            // type of lighting, for the face
  u_char baselight;            // from 0xFF (dark) to 0 (bright)
  u_char light[2];             // two additional light models  
  long lightmap;               // Pointer inside the general light map, or -1
                               // this define the start of the face light map
} face_t;

The faces that lie in the same plane must be stored consecutively, because they will be referenced as a list in the definition of models.

Light level of the faces

The lightmap field is an offset into the Light Maps. If there is no light map, this pointer is -1.

The baselight field gives the base light level for the face, that is the minimum light level for the light map, or the constant light level in the absence of light map. Curiously, value 0xFF codes for minimum light, and value 0 codes for maximum light.

The typelight field indicates the kind of lighting that should be applied to the face:

Note that if you use values 1 to 8, you may wish to set baselight to 0.

Texture mapping

(Warning: texture mapping is totally different from early versions of the BSP model. Forget about those early versions.)

To paint a face with a given texture, it is required that a position (s,t) in texture space be associated to each vertex in 3D space.

But that would make a lot of data, because a given vertex is often used by more than one face, and each one require a special (s,t) coordinate. So it has been prefered to store only the S and T vectors, and to calculate the (s,t) coordinates on the fly, probably when loading the level.

For a given face, the (s,t) coordinates are calculated from the Vertex coordinates and the Texture definitions by a simple dot product with the S and T vectors:

s = dotproduct(Vertex,vectorS) + distS;    
t = dotproduct(Vertex,vectorT) + distT;

In theory, vectorS and vectorT should be orthogonal vectors, and always lie in the face plane (or rather, the face plane), so as to avoid any distortion when mapping the texture onto the face.

Actually, those two vectors are often chosen among the coordinate axis themselves (or their opposite), so that textures in adjacent wall remain naturally aligned, despite the possibly different orientation of the walls. There is distortion of course, but it's limited.

Also, though the skies are ordinary wall textures, they are drawn in a very special way, that make them look like skies. That is probably the same trick as in DOOM: it doesn't take the player position into account when texture mapping, only the orientation of view, so that the sky appears to be far away.

4.3.6 The Mip Textures

The Mip textures definitions are used only in Texture info, and are referenced by index, not by name.

The Mip Texture definition is a structured file, that contains a list of individual Mip Textures, each one accessed via an offset.

typedef struct                 // Mip texture list header
{ long numtex;                 // Number of textures in Mip Texture list
  long offset[numtex];         // Offset to each of the individual texture
} mipheader_t;                 //  from the beginning of mipheader_t

Each individual texture is also a structured entry, that indicates the characteristics of the textures, and a pointer to scaled down picture data.

typedef struct                 // Mip Texture
{ char   name[16];             // Name of the texture.
  u_long width;                // width of picture, must be a multiple of 8
  u_long height;               // height of picture, must be a multiple of 8
  u_long offset1;              // offset to u_char Pix[width   * height]
  u_long offset2;              // offset to u_char Pix[width/2 * height/2]
  u_long offset4;              // offset to u_char Pix[width/4 * height/4]
  u_long offset8;              // offset to u_char Pix[width/8 * height/8]
} miptex_t;

The Mip texture header is generally followed by (width * height) * (85 / 64) bytes, that represent the color indexes of the textures pixels, at different scales. Do not rely on that size however, rather consider the offsets described below.

The pixels are accessed by offsets, with offset1 (resp. 2, 3, 4) pointing to the beginning of the color indexes of the picture scaled by 1 (resp. 1/2, 1/4, 1/8). These offsets are relative to the beginning of miptex_t.

The name of the texture is rather irrelevant, except that:

An individual Mip texture occupies 33% more space than a simple flat texture would. This is the cost of anti-aliasing.

4.3.7 The list of entities

The format of the entity definitions is the same as in the Map specifications, with the exception however that the entities that were defined by brushes in the Map file are now defined as an index into the list of BSP models that are part of the level BSP model.


4.4 Bsp tree definition

These are the entries that are related to the BSP tree that is used for rendering the level.

4.4.1 The BSP tree Nodes

The BSP tree nodes are used to partition one model (from the List of models) into a set of independent convex BSP tree Leaves.

All the BSP tree nodes are stored in that same BSP tree node structure, Though there is in fact one BSP tree per model. But of course no index should point to nodes that are part of another BSP tree.

typedef struct
{ long    plane_id;            // The plane that splits the node
                               //           must be in [0,numplanes[
  u_short front;               // If bit15==0, index of Front child node
                               // If bit15==1, ~front = index of child leaf
  u_short back;                // If bit15==0, id of Back child node
                               // If bit15==1, ~back =  id of child leaf
  bboxshort_t box;             // Bounding box of node and all childs
  u_short face_id;             // Index of first Polygons in the node
  u_short face_num;            // Number of faces in the node
} node_t;

Organisation of the BSP tree

The BSP tree nodes are part of a BSP tree, valid only inside a given model.

The front (resp. back) value is the equivalent of the right (resp. left) of node, in DOOM. Actually, even in DOOM it was the front (resp. back) of a linedef, if it had been extended vertically.

If the bit 15 is not set, as detected by (value & 0x8000) == 0, then the number is the index to the front (resp. back) child node.

If the bit 15 is set, then the child is in fact a BSP tree leaf, and the index of this leaf is obtained by inverting all the bits of front (resp. back).

In particular, the value -1 translates into leaf index 0. But actually it means that there is no leaf. Leaf 0 is a dummy leaf, contains no faces, and has a special type (-2) that means the BSP tree rendering must stop.

The role of BSP tree nodes

The nodes are the Quake equivalent of the DOOM nodes and also of the DOOM blockmaps. They are parts of a 3D BSP tree, not a 2D BSP tree like in DOOM.

The nodes are used for level display, placements of entities and second-level collision detections.

The front child node (and all the nodes below it) is entirely contained in the half-space that is in front of the split plane.

The back child node (and all the nodes below it) is entirely contained in the half-space that is in the back of the split plane. (The 'front' and 'back' of a split planes are defined by the plane equation giving a positive or negative result for any given vertex.)

The Bounding Boxes of nodes

The Bounding box of the node is presented in a packed format, bboxshort_t, that only contains short integer instead of floats.

That bounding box slightly exagerates the actual size of the node and all it's childs. Each bounding box boundary seems to be rounded to the next multiple of 16, so that the bounding box is at least 32 units larger than it should be.

That means that the level coordinates must all remain roughly between -32700 and +32700.

4.4.2 The BSP Tree Leaves

The BSP tree leaves are children of BSP tree Nodes and indicate which faces are contained inside a BSP tree leaf.

typedef struct
{ long type;                   // Special type of leaf
  long vislist;                // Beginning of visibility lists
                               //     must be -1 or in [0,numvislist[
  bboxshort_t bound;           // Bounding box of the leaf
  u_short lface_id;            // First item of the list of faces
                               //     must be in [0,numlfaces[
  u_short lface_num;           // Number of faces in the leaf  
  u_char sndwater;             // level of the four ambient sounds:
  u_char sndsky;               //   0    is no sound
  u_char sndslime;             //   0xFF is maximum volume
  u_char sndlava;              //
} dleaf_t;

The first leaf (index 0) is always totally solid, so that in the BSP tree nodes, a value of zero points to a solid leaf (i.e. a leaf that need not be rendered).

The BSP tree leaf contains a reference to a set of consecutive entries in the list of faces.

The bounding box must contain all the faces in the leaf.

The leaf contains an index to the Visibility Lists that describe which other leaves are visible from that leaf. If this index is -1, then all the other leaves are visible.

The tree leaves are the Quake equivalent of the sectors in DOOM. You can imagine them as rooms, or part of rooms, where the monsters, players and object will be placed.

Actually the tree leaves are the equivalent of the Sub Sectors: each sector in DOOM is decomposed by the BSP into smaller and simpler convex sub sectors, that contain only part of the sector lines.

Technically, each tree leaf, made of some faces and bound by the BSP node split lines, appears in 3D space as a convex polytope.

Leaf types

The type field describes what happens when the player is into that precise leaf. Here are the known values (negative):

Note that this field is only taken into account when the player is in the leaf, so if you're in a leaf full of water you'll see the world blurred, but players outside will see you perfectly.

4.4.3 The List of Faces

This structure stores a list of indexes of faces, so that a list of faces can be conveniently associated to each BSP tree leaf.

u_short lface[numlface];   // each u_short is the index of a Face

The list of faces is only used by the BSP tree leaf. This intermediary structure was made necessary because the faces are already referenced by Nodes, so a simple reference by first face and number of faces was not possible.

4.4.4 The List of Edges

This structure stores indexes of edges, possibly inverted, so that faces can be reconstituted.

short lstedge[numlstedge];

All the edges in a face are stored consecutively, with the correct orientation so that all the vertices in the face are walked clockwise.

But since the edges are used for more than one face, there is a trick to ensure that the edge of a given face is always referenced with the correct orientation:

The fact that all edges are walked in a clockwise order is critical for the face rendering process (rasterisation).

The faces are made of just one closed set of edges, or contour. Those edges seem to be always stored in the right order.

4.4.5 Visibility Lists

(Thanks to David Etherton for determining the precise formula)

The visibility lists are used by BSP Leaves, to determine which other leaves are visible from a given BSP Leaf.

The Visibility list can be of size 0, in that case it will not be used. The game will crawl if there is no visibility list in a level.

u_char vislist[numvislist];    // RLE encoded bit array

Basically, the visibility list is an array of bits. There is one such array of bits for each BSP Leaf. They are all stored in the vislist array, and each leaf has an index to the first byte of it's own array

The bit number N, if set to 1, tells that when laying in the tree leaf, one can see the leaf number N.

The only complication is that this bit array in run-length encoded: when a set of bytes in the array are all zero, they are coded by zero followed by the number of bytes is the set (always more than 1).

Normally, the size of the bit array associated to a leaf should be (numleafs+7)/8, but in fact due to the run lenght encoding, it's usually much less.

When the player is in a leaf, the visibility list is used to tag all the leaves that can possibly be visible, and then only those leaves are rendered.

Here is an example of decoding of visibility lists:

// Suppose Leaf is the leaf the player is in.
v = Leaf.vislist;
for (L = 1; L < numleaves; v++)
  {
    if (visisz[v] == 0)           // value 0, leaves invisible
      {
        L += 8 * visisz[v + 1]    // skip some leaves
        v++;
      }
    else                          // tag 8 leaves, if needed
      {                           // examine bits right to left
        for (bit = 1; bit != 0; bit = bit * 2, L++)
          {
            if (visisz[v] & bit)
              TagLeafAsVisible(L);
          }
      }
  }
Lots of thanks to Tony Myles who fixed the bit mask formula.

There is no necessity to unpack the visibility list in memory, because the code to read them is fast enough.

If you put a few badly placed zero bits in the visibility lists, some of the leaves will turn into totally grey areas, and that's rather funny. If you put all bits to zero for a given leaf, then every player in that sector will become temporarily blind: he will get a fully grey screen. I wonder what use you can make of this in level design, though. If only it had been black...

The visibility list structure is the Quake equivalent of the REJECT map of DOOM, except that now it's also used for level rendering. It eliminates leaves that can't be seen, whereas in DOOM it was just use to speed up monster line of sight calculations.


4.5 Pre-calculated geometric entries

Those entries can all be automatically calculated from the Level layout definition, and are not related to the Bsp tree definition.

Do not confuse the Clip Nodes with the BSP tree nodes, they are not used for the rendering of the level.

4.5.1 List of Planes

The plane definitions are used for faces, BSP Nodes, Clip Nodes.

The order of planes in list is irrelevant.

typedef struct
{ vec3_t normal;               // Vector orthogonal to plane (Nx,Ny,Nz)
                               // with Nx2+Ny2+Nz2 = 1
  scalar_t dist;               // Offset to plane, along the normal vector.
                               // Distance from (0,0,0) to the plane
  long    type;                // Type of plane, depending on normal vector.
} plane_t;

Plane types:

The planes are used as split planes in the BSP tree nodes, and as reference plane in the faces.

They are the Quake equivalent of the DOOM Linedefs and Segments.

The planes are defined by a normal vector and a distance. This normal vector must be of norm 1.

The plane equations are used for distance calculation and to determine if a given vertex (of a face, or an entity) is on the front side or the back side of the plane.

Some of the planes, especially the first ones in the list, are not associated to any face, but rather to BSP nodes split planes. So they show numsurf = 0.

There must be only one given plane definition, for any plane in 3D space. That's because the calculations of the translation and rotation of plane normal vector are cached, so if you put redundant planes definitions you'll contribute to slowing down the engine. Definitely not an option.

4.5.2 The Clip Nodes

This structure is used to give a rough and somewhat exaggerated boundary to a given model. It does not separate models from each others, and is not used at all in the rendering of the levels

Actually, the clip nodes are only used as a first and primitive collision checking method.

The clip nodes are much simpler than the BSP nodes, so it makes collision detection faster, most of the time. In the same idea, DOOM defined a BLOCKMAP for faster collision detection.

typedef struct
{ u_long planenum;             // The plane which splits the node
  short front;                 // If positive, id of Front child node
                               // If -2, the Front part is inside the model
                               // If -1, the Front part is outside the model
  short back;                  // If positive, id of Back child node
                               // If -2, the Back part is inside the model
                               // If -1, the Back part is outside the model
} clipnode_t;

The engine starts from the top bound node as defined in the Model.

There is no bounding box defined for those nodes, because the bounding box is that of the model bounding boxes.

If you modify a clip node, for instance by changing the plane definitions or by putting -1 values for each child, then the model becomes totally pass-through. That's a very funny special effect.

The Clip Nodes do not tightly bound a model, so you should never use planes from the model as clip node split planes. Actually, the clip node planes should be distant from the model by at least 16 in X,Y, and 24 in Z.

Also take care that the Clip Node planes should be oriented toward the exterior of the model, not the interior. If you change the orientation, then the player can go through the model as if it did now exist... even falling through the floor.

4.5.3 The Light Maps

The light maps are special arrays that indicate the brightness of some points in the Mip Texture pictures.

Different light maps can be associated to each face, so that two faces with similar textures can still look different, depending on the light level.

The light maps are simply:

u_char lightmap[numlightmap];  // value 0:dark 255:bright

Light levels

The u_char value that the lightmap gives at any point is directly a light level value, from 0 to 255. If you put zero, it will be utter darkness, and if you put 255 if will be totally bright.

The formula for calculating light level is something like:

light(X,Y,Z) = lightmap(X,Y,Z) * lightstyle(typelight, time) - baselight
where, as a rough explanation:

Note that the textures's color and light are translated into a final color by using a pre-calculated color palette. Direct RGB calculations would be too costly and not very suitable for 256 color displays. This is the same trick as used when gouraud shading the Alias models.

Translation of lightmaps into 3D space

Well the exact formula seems rather hard to determine experimentally, so don't expect this explanation to be accurate.

The size and layout of a lightmap, on texture space, is not related to the texture but only to the face extent, in 3D space. You can change the texture without having to recalculate light maps.

Each light maps seem to be stored as a simple

u_char light[width*height];
where width and height are determined by the extents of the faces's bounding box, i.e. the bounding box of all the vertices contained in that face (or, rather, all the Edges).

Since such a bounding box is essentially 3D, and the lightmap is only 2D, one coordinate has to be discarded. The coordinate to remove depends on the orientation of the face's plane, as given by the Plane Type.

This mapping from 3D to 2D, by discarding one coordinate, is exactly the same as the one used for Texture Mapping the faces. You can probably consider the lightmaps as ``alpha-channel textures'' which modify the intensity of the real textures on which they are applied.

Note that the extents of the bounding box (i.e. the difference between maximum and minimum values) must be divided by 16 to give the width and height, because a lightmap value is only calculated every 16 steps, for every coordinate.

Calculating only every 16 steps make the radiosity calculation 256 times less tedious, and ensures that the lightmap will look nice and smooth on the face (because bilinear interpolation is used between known lightmap values).

Unknown Fields

I'm aware that the above explanation is rather obfuscated, and may not cover all cases. It's savagely hacked out of some experimental results and some considerations on the convenience of calculations.

Note also that the lightmap are oriented in regard to the 3D coordinates, and do not seem to care about the face orientation. So if you modify a lightmap, chances are that your modifications will happen is some unexpected place (like, at the bottom instead of at the top...).

Last, in case you wonder where the lightstyle table is defined, the answer is: no idea.


4.6 Additional Informations

4.6.1 Texture names

(Thanks to Stephen Crowley for experimenting with the names)

The names of textures can contain up to 16 characters.

The animation of the texture is entirely determined by it's name: there are three special names, that make different animations. All the other names mean that the texture is not animated.

Here are the animated textures:

Currently, no other combination works.

When displaying an animated texture, the lightmap and light levels are not taken into account. Those textures are always rendered at full brightness, probably because the face cache would be saturated if every animation frame had to fit into it.

Note that sky textures have an extent that make them too big to display as an ordinary wall texture, and that if you turn an ordinary texture into a sky texture, it will look fairly weird.

Also, for some strange reason, bit 4 of the face flags is set when the texture is supposed to be animated. If you replace an animated texture by an ordinary texture, and forget to set this bit to zero, then there will be an error like: SurfExtent>256.

4.6.2 Texture Anti-aliasing

This is an attempted explanation for the curious structure of the Mip Texture.

The sampling theorem states that when you sample any signal (sound, picture, anything) the highest frequency contained in this signal must be at most one half of the sampling frequency. If there is any frequency above that, the sampling process will map it into a lower frequency, thus creating a terrible mess into the sampled signal. This mess is called Aliasing.

When you try to display a picture on a smaller space, you increase all the frequencies contained in that picture, and thus risk Aliasing. That's basically what happened in DOOM at long distance.

Now, all you need is only to low-pass filter the picture, with a cut frequency equal to half the sampling frequency. Easy! But... There is no DSP on the video memory, so those calculations would take too much time. It's much easier to pre-calculate 4 scaled down pictures, that can be used across the most common range of scales:
infinity-1, 1-1/2, 1/2-1/4, 1/4-1/8.
Below 1/8, there will be some aliasing...