============================================================================= _ ///// ///// ////// ///// ///// __ _ _ _ ___ | | _____ // // // // // // / _` | | | |/ _ || |/ / _ \ ///// ///// ////// // ///// 3.0 | (_| | |_| | (_||| ( __/ // // // // // \__, |\__,_|\___||_|\_\___| ///// // ////// ///// ///// |_| =============================================================================
The Most Unofficial Quake Technical Specification.
Derived from the Quake release QTEST1
by Olivier Montanuy, Brian Martin and Raphaël Quinet
March 7, 1996
This document is incomplete. If you have additional information, or found errors, or have other interpretations, please send to Bernd Kreimeier, maintainer of the Quake Developers mailing list (for discussion of tools/utils only). Include name and full references, for credits. You are also encouraged to discuss Quake editing techniques as well as the contents of this document in the newsgroup rec.games.computer.quake.editing.
This document is an updated version of the Unofficial Quake Specs 2.2. There are similarities, but also lots of changes. Later versions of this specification may show even more changes.
Quake and Doom are trademarks of id Software Inc., Mesquite, Texas. This document is not a publication of id Software, who should not be associated with it. id Software will not answer any questions related to this document.
This document is Copyright (C) 1996 by Olivier
Montanuy.
All rights reserved.
Permission to use, copy and distribute unedited copies of this whole document is hereby granted, provided that no fee is charged for the use or availability of this document (other than the normal connection costs for on-line services, if applicable). The above copyright notice and this permission notice must be left intact in all copies of this document. Short excerpts of this document may be quoted in discussion groups or mailing list articles, as long as a reference to the full document is given.
Commercial distribution of this document, in whole or in part, requires prior agreement with the author. Commercial distribution includes any means by which the user has to pay either for the support (e.g. book, newsletter or CD-ROM) or for the document itself. Unauthorized commercial distribution is prohibited.
Disclaimer: this document describes the Quake file formats as we understand them, but we cannot guarantee that anything is correct. In fact, we could be totally wrong. We cannot be held responsible for any consequences of the use or misuse of the information contained herein. You have been warned.
All the code structures are written in C, because C is all I
talk.
Well, it could have been worse. I could have written that
specification in French.
If you're used to Pascal, that's too bad poor dude.
If you're using Java, beware of unsigned integers and 8-bit characters.
If you're used to Basic, I just laugh in your face.
If you're using Python, you'll just laugh in mine :(
0xABCD = hexadecimal number ABCD, in C convention. char = 8 bit signed integer, u_shar = 8 bit unsigned integer (BYTE), short = 16 bit signed integer, u_short = 16 bit unsigned integer (WORD), long = 32 bit signed integer, u_long = 32 bit unsigned integer (DWORD), float = 32 bit single precision real (floating point).
I guess that the PACK files are the new distribution method of id Software. The WAD files were the last legacy of their Apogee days. Didn't you hate it to see the same WAD handling routines in Duke Nukem 3D and DOOM?
Anybody who has ever seen a WAD can hack similar formats in 2 minutes. Well, I'll try to spare you those 2 minutes. Or whatever.
The PACK format is used to emulate a Linux (Unix) directory arborescence, and to avoid putting some hundreds of files on the user's disk. It is not a compressed format, and in some ways it's very similar to the WAD format. It can be edited just like a WAD, if needed.
The PACK file starts with a header, that indicates where to find the directory, and the size of that directory. The number of entries can be deduced by dividing by sizeof(pakentry_t) = 0x40
typedef struct { u_char magic[4]= "PACK"; // Name of the new WAD format long diroffset; // Position of WAD directory from start of file long dirsize; // Number of entries * 0x40 (64 char) } pakheader_t;
The PACK directory is made of a list of consecutive entries, each with the following format:
typedef struct { u_char filename[0x38]; // Name of the file, Unix style, with extension, // 50 chars, padded with '\0'. long offset; // Position of the entry in PACK file long size; // Size of the entry in PACK file } pakentry_t;
At offset diroffset in the PACK file, you will find:
pakentry_t dir[dirsize/sizeof(packentry_t)]; // Directory
The directory is preferably placed at the end of the PACK file, but it could actually be anywhere. The entries could also be scattered all around the PACK file, leaving large gaps. If you write a PACK hacking utility, you must take care not to introduce too many empty space. Also, you should never assume that the entries are stored in the same order as in the directory (they could be in reverse order, for example). If you want to add some data after the last entry, make sure that you are really at the end of the file.
Since PACK files are a bit like WAD, it is possible to use the same tricks that were used by tools such as DeuSF and NWT to modify the PACK file reversibly. It is hoped, however, that Quake is flexible enough so that this trick is not needed.
Contrary to the WAD2 files, there is no tag giving the type of each entry. However, they can be safely recognized by the extension, and it's the method used by Quake itself.
|
Those files are ordinary Text, in Unix format, so they won't display correctly under DOS if you are using an old editor. They contain only settings and definitions. Too boring and too unstable to be described here.
The sound files are ordinary 16-bit WAV files. Apparently, DDT upgraded the Sound code, because they used to be 8-bit only.
The .DAT file contains some semi-compiled machine independent code, instead of the expected Quake programming language .QP files.
So the nice Quake C-like interpreted code seems now to be replaced by some P-Code, a bit like the HeXen Behavior lumps. Or maybe it's a Java Applet? ;-)
I derived this partial information from a mail of the HeXen behavior specialist, Luc Cluitmans (author of DEACC).
typedef struct { long offset; long size; } codentry_t; typedef struct { long version; // 3 long program; // offset to start of P-CODE codentry_t table12; // table of 1 long and 4 short codentry_t table12; // table of 3 long codentry_t table12; // table of 3 long codentry_t table64; // Table of 64 bytes entries codentry_t strings; // Character strings, separated by '\0' codentry_t numeric; // Constants and variable } codehead_t;
The only interesting thing in that code lump are the strings, because they give the names of the possible spawning sequences for the Entities.
Do not attempt to decompile the QP code: most probably, this language is still totally unstable, so any efforts to hack would be a waste. And id Software will probably provide examples of source code, not only compiled stuff.
Anyway, there is no compiler, contrary to HeXen, so what's the use or getting the source?
The level 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.
In the terminology of id Software, the BSP-based models are called Brush Models. (might be: paint brush models. DDT mentioned once, with a source file format example, that it's just a surface and some brush to paint a texture on it. Anyone knows if this makes sense?)
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.
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.
This is a very good reason to maintain our own file format, and create BSP, WAD2, PAK as needed from one repository/tree.
Here are the contents of levels:
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 TEST1.BSP map.
Beware: the description below is valid only for the version 0x17 of the BSP file format.
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. The problem is that, contrary to DOOM, those entries have no name, so some names had to be guessed. They are probably either wrong or ridiculous.
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 14 entries:
typedef struct // The BSP file header { long version; // Model version, must be 27. 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; // Hull BSP Nodes. // numnodes = size/sizeof(node_t) dentry_t surfaces; // Map Surfaces. // numsurfaces = size/sizeof(surface_t) dentry_t lightmaps; // Wall Light Maps. dentry_t hullbound; // BSP to bound Hulls. // numbounds = size/sizeof(hullbound_t) dentry_t leaves; // Hull BSP Leaves. // numlaves = size/sizeof(leaf_t) dentry_t lstsurf; // List of Surfaces. dentry_t edges; // Original surface Edges. // numedges = Size/sizeof(edge_t) dentry_t lstedges; // List of surfaces Edges. dentry_t hulls; // List of Hulls. // numhulls = Size/sizeof(hull_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.
The level entries are listed in the order they are found in the directory. This is not a logical order. If you want to start from the highest level description, and go down to the details, just go to the Definition of Hulls.
Yet, I doubt you understand all that description on first sight.
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 { vec3_t min; // minimum values of X,Y,Z vec3_t max; // maximum values of X,Y,Z } boundbox_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.
This is a simple text file, that contains definitions of entities
Here an example of entry in that file:
{ "light" "300" "classname" "light" "origin" "136 -86 22" }
Here are some obvious info. All the rest is unknown to me, since I didn't even try to hack it out.
If you know something about this, please send it.
The plane definitions are used for Surfaces, Hull BSP Nodes, Hull Bound BSP Nodes.
The order of planes in list is irrelevant.
typedef struct { vec3_t normal; // Vector orthogonal to plane (Nx,Ny,Nz) // with Nx²+Ny²+Nz² = 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: // 0: facing toward X 3: toward -X // 1: facing toward Y 4: toward -Y // 2: facing toward Z 5: toward -Z long firstsurf; // first surface in that plane // must be in [0,numsurfaces[ long numsurf; // nb of consecutive surfaces in that plane } plane_t;
The planes are used as split planes in the BSP tree nodes, and as reference plane in the Surfaces.
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 surface, 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 surface, 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.
The Mip textures definitions are used only in Surfaces, and are referenced by index, not by name.
There is a maximum of 256 Mip Textures in a level, because of indexing.
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 begining 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; // -> u_char Pix[width * height] u_long offset2; // -> u_char Pix[width/2 * height/2] u_long offset4; // -> u_char Pix[width/4 * height/4] u_long offset8; // -> u_char Pix[width/8 * height/8] } miptex_t;
The Mip texture header is followed by (width * height * 2) pixels, with offset1 (resp. 2, 3, 4) pointing to the begining of the color indexes of the picture scaled by 1 (resp. 1/2, 1/4, 1/8). These pointers are relative to the begining of miptex_t.
The name of the texture is rather irrelevant, except that if it begins by ``*'' it may be used in animations.
An individual Mip textures occupies 33% more space than a simple flat texture would. This is the cost of anti-aliasing.
The vertices definitions are used for Edges, which are part of Surfaces.
The order of vertices in the list is irrelevant.
typedef struct { float[3]; // X,Y,Z coordinates of the vertex }vertex_t;
The vertices are only used for texture mapping.
There must be only one given vertex definition, for any point in 3D space. The reason is the same as for Planes.
The visibility lists are used by BSP Leaves, to determine which other leaves are visible from a given BSP Leaves.
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]; // Bit mask
Basically, the visibility list is an array of bits, one array per tree leaf. The bit number N, if set to 1, tells that when laying in the tree leaf, one can see the leaf number N.
When the player is in a leaf, the engine finds all the leaves that are visible from that leaf, and tag those leaves. Then it tags back all the nodes that are above the tagged leaves. That way, only the part of the BSP tree that is really visible will actually be tagged, and later displayed.
Here is a rule for the use of visibility lists:
For each couple of BSP tree leaves (Leaf0,Leaf1), with row = (Nb of leaves + 7 )/8 with byte = Leaf1 + Leaf0 *(( NbOfLeaves + 7)/8); with bit = Leaf1 & 7; if (vislist[byte] & bit) then Leaf0 can see Leaf1. (bit is 1) if !(vislist[byte] & bit) then Leaf0 cannot see Leaf1. (bit is 0)
Visibility lists are accessed via a pointer in BSP Leaves, and after that pointers, numleaves/8 bytes must be read. If this goes beyond the end of the lump, then it probably means that all the other bits are all one.
Thanks to this pointer mechanism, the visibility lists can be packed. Otherwise they would be of size numleaves * numleaves / 8.
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.
The Hull BSP tree nodes are used to partition one hull (from the List of Hulls) into independant 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 hull. But of course no index should point to nodes that are part of another BSP tree.
typedef struct { long planenum; // The plane that splits the node // must be in [0,numplanes[ u_short front; // If bit15==0, id of Front child node // must be in [0,numnodes[ // If bit15==1, !front = id of child leaf // must be in [0,numleafs[ u_short back; // If bit15==0, id of Back child node // must be in [0,numnodes[ // If bit15==1, !back = id of child leaf // must be in [0,numleafs[ boundbox_t box; // Bounding box of node and all childs } node_t;
The Hull BSP tree nodes are part of a BSP tree, valid only inside a given hull.
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 a pointer to the front (resp. back) node child.
If the bit 15 is set, then the child is in fact a BSP tree leaf, and the number of this leaf is obtained by inverting all the bits of front (resp. back).
Warning: the value -1 (that the above rules translates into the child Leaf index 0) indicates in fact that there is nothing below that child node. No node, no leaf, nothing. Rendering stops there. And that's why the first Child Leaf must contain a void list of surfaces.
The bounding box of the node must be large enough to contain all the tree leaves in all the child nodes of this node.
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).
During game play, every entity present in a BSP tree leaf will be split according to that BSP tree, and decomposed into entity fragments, rendered separately. The idea is to get the least possible number of fragments, because they slow down the engine.
The surfaces define the Wall, Floors, Ceilings, Sky areas.
The surfaces are part of List of Surfaces, which are contained in BSP tree Leaves.
typedef struct { u_short planenum; // The plane in which the surface lies // must be in [0,numplanes[ u_short side; // 0 if in front of the plane, 1 if behind the plane u_char texnum; // id of Mip Texture // must be in [0,numtex[ u_char sofs; // horizontal offset (in texture space) u_char tofs; // vertical offset (in texture space) u_char flips; // if bit 0==1 flip verticaly (in texture space) // if bit 1==1 flip horizontaly (in texture space) // if bit 2==1 exchange vertical and horizontal coordinates long firstedge; // first edge in the List of edges // must be in [0,numedges[ long numedge; // number of edges in the List of edges u_char light; // base light level for the surface u_char unknown0; // 0xFF u_short unknown1; // 0xFFFF u_long lightmap; // Pointer inside the general light map, or -1 // this define the start of the surface light map } surface_t;
The surfaces that lie in the same plane must be stored consecutively, because they will be referenced as a list in the definition of Planes.
The lightmap pointer is an offset into the Light Maps. If there is no light map, this pointer is -1.
When a lightmap exists, the code is -256, otherwise it's -1. The meaning of that code is unknown. It's maybe some constant light level for the surface.
The Mip texture are referenced by a number between 0 and 256, which is largely sufficient. The texture offsets move the texture picture in texture space, they don't move it directly on the surface itself.
The texture mapping is not an application of the texture on the
surface, like with 3D models. Rather, imagine the texture was made
3D, by extending it along one axis (X,Y or Z, that depends on the plane type). Then this extended 3D texture is sliced
by the 2D surface.
In other words, that means only two of the X,Y or Z coordinates are
used to determine what point of the texture we are in.
The rendering of surfaces necessitates to determine the position of Vertices, or rather, of Edges. Since those edges are common to more than one surface, but each surface has it's own set of edges, the Surface st either vertices or edges, it points to List of Edges, that are oriented counter-clockwise, around the surface.
The surfaces represent the visible boundaries of a tree leaf. The surfaces are the Quake equivalent of the Sidedefs of DOOM, in the sense that they tell what sector boundaries look like.
Depending on the name of their texture, they will appear as a sky texture, or as a wall or floor (that can eventually be animated). Note also that though the skies are ordinary wall textures, they are drawn in a very special way, that make them look like skies. That is basically the same trick as in DOOM (it doesn't take the player position into account when texture mapping, only the orientation of view).
The surfaces will be rendered as a texture-mapped polygon. The texture somewhat takes into account the distance, for better realism. Technically, the polygon is split based on the inverse of the distance, and fragments are mapped linearly.
The texture mapping also takes into account the orientation of the surface, because calculations of points in texture space is done by selecting only 2 coordinates among the three coordinates of the points. So depending on the orientation of the surface, the most representative set of coordinates must be chosen.
Yeah I know, it's pretty complicated, and rather obscure...
There are three u_char that have not been identified. I don't know what they mean, but if you don't put value 0xFF there, you can violently screw up the display of that particular face, and affect everything around. It seems vertex-dependant, or edge-dependant, so it might be a bit mask.
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 Surface, so that two surfaces 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
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 maybe:
light(x,y) = lightmap(x,y) * lightstyle[style] + base lightThe base light level is defined for each surfaces, so that many surfaces can use the same light maps.
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.
The size of a given light map is given by the width
and height of the corresponding Surface
texture.
Actually, it is the width and height divided by 16. A light level is
only provided every 16 pixels, and bilinear approximation is used
inside the delimited squares of 16x16 pixels, so that the light map
always look smooth, even if you put extreme values.
Experiment has shown that the light maps are stored like flat
pictures, or textures: row by row.
The apparent size of the lightmap seems to be somewhat smaller than what could be expected, probably because the lightmaps are packed, by using pointers, like the visilists. The compression method seems to be simply to detect that a given light map (or at least it's begining) is the same as part of another light map (or the end part of that light map). I let you imagine an optimal compression algorithm for this.
This structure is used to give a rough and somewaht exagerated boundary to a given hull. It does not separate hulls from each others, and is not used at all in the redering of the levels
Actually, the hull bound nodes are only used as a first and primitive collision checking method.
The hull bound nodes are much simpler than the Hull 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 hull // If -1, the Front part is outside the hull short back; // If positive, id of Back child node // If -2, the Back part is inside the hull // If -1, the Back part is outside the hull } dhullbound_t;
The engine starts from the hull bound top node as defined in the Hull.
There is no bounding box defined for those nodes, because the bounding box is that of the Hull bounding boxes.
If you modify a hull bound BSP node, for instance by changing the plane definitions or by putting -1 values for each child, then the hull becomes totally pass-through. That's a very funny special effect.
Note that the Hull Bound Nodes does not tighly bound a Hull. The bounded area is bigger than the Hull itslef. Here is an example for the grid bars: 16 in X,Y, and 24 in Z.
The BSP tree leaves are children of BSP tree Nodes and indicate which Surfaces are contained inside a BSP tree leaf.
typedef struct { u_long code; // in range [-6,-1], Unknown purpose boundbox_t bound; // Bounding box of the leaf u_long vislist; // Begining of visibility lists // must be in [0,numvislist[ long firstsurf; // First item of the list of surfaces // must be in [0,numsurfaces[ long numsurf; // Number of surfaces in the list u_long zeroes[3]; // Always 0, purpose unknown u_short zero; // Always 0, purpose unknown u_short flag; // Always 0xFFFF (-1), purpose unknown } dleaf_t;
Because of the special encoding of the void leaf in the BSP tree nodes, the first BSP tree leaf in the list (index 0) is never used, and must contain a void list of surfaces.
The BSP tree leaf contains a reference to a set of consecutive entries in the list of surfaces.
The bounding box must contain all the surfaces in the leaf.
The leaf contains a pointer to the Visibility Lists that describe which other leaves are visible from that leaf. This is used to accelerate the rendering.
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 surfaces and bound by the BSP node split lines, appears in 3D space as a convex polytope.
Think of them as big rooms without any corners where you can hide from any part of the room. (Sorry, I'm just trying to be AOLicaly correct).
Well, if you don't understand the above, I'm real sorry but the best you can do is go ask your mother for a system upgrade.
The purpose of the flag, code, zeroes fields is unknown and shall be investigated.
It is highly recommened to put in code the values -1, or maybe anything down to -6. Value -256 crashes Quake with a page fault, so chances are that this code is in fact a negative index to some structure.
This structure is stores list of indexes of surface, so that a list of surfaces can be conveniently associated to each BSP tree leaf.
u_short lstsurf[numlstsurf]; // each u_short is the index of a Surface
The list of surface is only used by the BSP tree leaf. This intermediary structure was made necessary because the surfaces are already referenced by Planes, so a simple reference by first surface and numbr of surfaces was not possible.
This structure stores a list of pairs of indexes of vertices, each
pair defining an edge of a polygon. That edge will generally be used
my more than one surface (two or three is typical).
These edges are the only structure that reference index of
vertices.
The edges are not referenced directly by Surfaces, but rather they are referenced via the List of edges, because the edges need to be oriented.
typedef struct { u_short startvertex; // id of the start vertex // must be in [0,numvertices[ u_short endvertex; // id of the start vertex // must be in [0,numvertices[ } edge_t;
This structure stores indexes of edges, possibly inverted, so that Surfaces can be reconstituted.
u_short lstedge[numlstedge]; // if bit15=0, lstedge[] = id of Edge // and the edge is used from start to end // must be in [0,numedges[ // if bit15=1, !lstedge[] = id of Edge // and the edge is used from end to start // must be in [0,numedges[
All the edges in a Surface are stored consecutively, with the correct orientation so that all the vertices in the surface are walked counter-clockwilse.
For that purpose, if bit 15 is not set, as tested by (value & 0x8000) == 0, the the edge is used in the normal sense.
If bit 15 is set, then the edge is used in the inverse sense.
That way, the same edge can be used for two surfaces with different orientations.
The fact that all edges are walked in a counter-clockwise order is critical so that the polygon clipping process be simplified to a maximum.
As a matter of fact, the polygons that represent the faces often get clipped by 3D planes. They need not be convex, but their edges must be ordered.
There might be other reasons for the existence of a structure that stores each eedges once and for all. It can be hinted that, like vertices are typically cached during rendering, edges could also be cached (so as to calculate or split them at most once).
The name Hull refers here to either a big zone, the level, of smaller independant 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 Hulls, which are independant areas, roughtly bounded byHull Split 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 Hull long zero[3]; // Always 0, purpose unknown long node; // id of first Hull internal BSP node long boundnode; // id of first Hull Bound BSP node long numleafs; // number of Hull BSP leaves long firstsurface; // id of Surfaces long numsurfaces; // number of Surfaces } dhull_t;
It had first been imagined that Hulls were some kind of big zones, each with a local BSP tree. It might still be true, but experience shows that the first hull is the whole level itself, and that other hulls, smaller, are in fact the various moving parts of the level, like doors, grid bars, switches.
A typical BSP model is only made of one single hull, and only the
level maps may eventually need more than one hull.
The purpose of the three zero fields is unknown. Apparently, it's not a good idea to use another value than 0 there.
The numleafs field seems to make sense as the number of leaves in the tree, but it's not totally sure. If you put low values in this field, though, the game will crash at startup, and that could be caused by troubles with the size of visilists.
I place here information that is related to levels, but copied from the old specifications 2.2. I cannot be too sure this information is still valid.
The names of textures can contain up to 16 characters.
If the texture is not animated, the name can be anything, provided the first character is not ``*'', the asterisk.
If the texture is animated:
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...
Here is how the right texture is selected in Quake:
int R_MipLevelforScale(float scale) { if(scale>= 1) return 0; // 1 and above. no aliasing. if(scale>= 0.4) return 1; // shouldn't it be 1/2 ? if(scale>= 0.2) return 2; // shouldn't it be 1/4 ? return 3; // down to 1/8 (below, aliasing!) }
(Thanks to Jens for some critical reflections)
I'm not going to explain in details how the Quake 3D engine works. It wouldn't be fair to id Software, and anyway I still don't understand a lot of critical features. Also, if such an explanation was to be read by the conceptors of Quake, chances are that they would die laughing, and I don't want to take that risk.
Let's say only that the Quake 3D engine looks like an ordinary texture-mapped polygon engine, where the polygon sorting is not done via classical backface elimination and distance sorting, but by using a BSP tree. Well, actually, now it uses many smaller BSP trees, basically one for each hull in the level.
In Quake, contrary to DOOM, there is no ray-casting, so some surfaces are sometime rendered, then later overwritten by closer surfaces. Hence the visibility list is critical for this engine, otherwise it might really crawl.
Alias models can be used for entities, like players, objects, or monsters. Some entities can use sprite models (that are similar in appearance to those of DOOM, though the structure is totally different) or even maybe models similar to those of the levels.
As of now, importing models from 3ds or the likes is almost impossible. The reason: we don't fully understand the frame headers or know the data structure of the vertex normals. Of course you can make models, and save the data, but there missing parts and the end result will be a model with incorrect light shading and maybe strange video output. Remember, object lighting is dynamic. Too bad, so sad.
You need not bother too much about the way Alias Models are rendered, just keep in mind that the more simple the model, the faster the game will be.
Here is an attempt at describing what the different parts of the model represent. This description is a bit outdated, though.
First imagine a wireframe model of the entity, made of triangles. This gives the general shape of the entity. For instance, imagine you have the general shape of a cow, made of triangles in 3D space.
The 3D vertices define the position of triangles, and contrary to level models, there is no need for elaborate stuff like nodes, planes, polygon surfaces. Only triangles and vertices.
Now, there is something missing: the skin. A cow without skin looks pretty ugly.
Imagine that you have a flat carpet made of the skin of an unlucky cow. All you need to do is put some parts of this carpet at the relevant place on the wireframe model of the cow, and you'll get a fairly realistic (though a bit polygonal) cow. Actually, you will need two carpets: one for the upper part and one for the lower part.
For each triangle in the wireframe model of the cow, there will be a corresponding triangle cut from the skin picture. Or, in other words, for each 3D vertex of a triangle, there will be a corresponding 2D vertex positioned on the skin picture.
It is not necessary that the triangle is 3D space and the triangle on the skin picture have exactly the same shape (in fact, it is not possible for all triangles) but they should have shapes roughly similar, to limit distortion and aliasing.
By the way: there is no Mip mapping on the Alias models, so they don't look very good in distance, which is not too bad since they are constantly supposed to be moving or changing. If you want then to look fine, do them with BSP models. But then they won't move.
The Alias Model animation is based on frames (in DOOM, sprites were also animated by frames). So the deformations are defined once and for all, and there is no squeletal model or any similar physical model involved in the deformations... well, at least not in real time.
Once the general shape of the model (for instance, a cow) is defined, and the skin is mapped correctly on that shape, animation is pretty straightforward: just move the triangles around and it will seem to move.
To move the triangle, you need only modify the position of the 3D vertices that are part of it. For instance, to move the leg of the cow, you will move the vertices that define the endpoints of the legs. You will also move the other vertices a bit, so that the movement looks less mechanical.
Chances are that creating a fine looking animation is gonna be a very tough job, a bit like with the DOOM sprites. I would bet that the quality of the animation will be the most critical point.
Note that the animation consists only in changing vertex positions (and that's why there is one set of vertices for each animation frame).
The skin of the cow is not modified, neither are the definition of the triangles. If you want blood stains to appear on the skin, you'll have to replace one of the triangles by another one that will correspond to another part of the skin picture, with stains.
Along the same idea, if you want parts of the models, like head, weapons and the like, to go flying away when they are cut, then they must be defined using parts of the skin that are separate from the parts used for the body.
The .MDL files are collection of lumps, but contrary to .BSP files there are not pointers to access directly to the lumps, and it is suspected that there will be, in future versions of the models.
Once you have the level header, you can find all the other parts, just by calculating their theorical position in file.
A Model file contains:
Here is the format of the .MDL file header:
typedef struct { long id; // 0x4F504449 = "IDPO" long version; // Version = 3 vec3_t scale; // Scale factor, for x,y,z vec3_t origin; // Model origin: point for x=0,y=0,z=0 scalar_t radius; // Model radius, maybe useless now. vec3_t offsets; // (?)Integer offsets long numskins ; // the number of skin textures long skinwidth; // Width of skin texture // must be multiple of 8 long skinheight; // Height of skin texture // must be multiple of 8 long numverts; // Number of vertices long numtris; // Number of triangles surfaces long numframes; // Number of frames long unknown; // 0 }mdl_t;
The size of this header is 0x4C bytes (76).
This is simply a flat picture, stored as a collection of 8-bit color indexes.
At offset baseskin = 0x4C in the .MDL file you will find:
typedef struct { long unknown; // 0, maybe a time stamp u_char skin[skinwidth*skinheight]; // the skin picture } skin_t skins[numskins]; // numskins pictures
There might be more than on skin texture, as indicated by numskins. They all have the same size.
It is suspected that color index 0 represents the transparency.
Note that the skin pictures are a bit particular: as a matter of fact, they are not made of one piece, but of at least two pieces: one for the front of the model, the other for the back of the model.
Actually, there may be as many pieces as there are independant parts in the model, and even more for special animations.
Note that the back skin of a given sprite part must be on the same height, but translated width/2, relatively to the front skin part. The back skin part must also be inverted.
This design is used to allow the correct rendering of a seamless skin texture, using Skin Vertices with onseam == 1, on the skin border.
A .MDL file is made of a list of vertices. To each of these vertices corresponds a 3D position, a light level, and a position on the skin picture, for texture mapping.
The list of skin vertices indicates only the position on texture picture, not the 3D position. That's because for a given vertex, the position on skin is constant, while the position in 3D space varies with the animation.
The list of skin vertices is made of these structures:
typedef struct{ long onseam; // 0 or 1 long s; // position, horizontally // in range [0,skinwidth[ long t; // position, vertically // in range [0,skinheight[ }stvert_t
onseam is a boolean, and if non zero it means that the vertex is on the boundary between the skin part that is applied on the front of the sprite, and the skin part that is applied on the back of the sprites (i.e. on the edge).
s and t are (X,Y) position on the skin picture.
At offset baseverts = baseskin + (4 + skinwidth * skinheight) * numskins in the .MDL file, you will find:
stvert_t vertices[numverts];
An alias Model is made of a set of triangle facets, with vertices at the boundaries.
Only vertices index are stored in triangles. the normal vector of the surface is reconstituted from the vertex position.
Here is the structure of triangles:
typedef struct { long facesfront; // boolean long vertices[3]; // Index of 3 triangle vertices // in range [0,numverts[ }itriangle_t;
The boolean facesfront indicates if the triangle is part of the front or the back skin. 1 means that it's on the front skin, 0 means that it's on the back skin, so the face normal is be inverted. This information may be useful when texture mapping the model.
Note that the index of a given vertex is the same in the skin vertex table and in the frame table.
At offset basetri = baseverts + numverts * sizeof(stvert_t) in the .MDL file, you will find:
itriangle_t triangles[numtris];
An Alias Model contains a set of animation frames, which can be used in relation with the behavior of the modeled entity, so as to display it in various postures (walking, attacking, spreading it's guts all over the place...).
Each frame vertex is defined by a 3D position and a light level for each of the vertices in the model.
typedef struct { u_char packedposition[3]; // X,Y,Z coordinate, packed on 0-255 u_char lightnormalindex; // related to the light level } trivertx_t;
The lightnormalindex field is some index into a set of normal vectors (that are yet to be identified).
To get the real X coordinate, from the packed coordinates, multiply the X coordinate by the X scaling factor, and add the X origin. Both the scaling factor and the origin can be found in the Model Header.
The currently suggested formula for calculating positions is:
vec3_t real[i] = scale[i] * ( packedposition[i] + offset[i] ) + origin[i]Where scale, offset and origin can be found as vectors in the Model Header.
the begining of the frames can be found in the .MDL file, at offset baseframes = basetri + numtris * sizeof(itriangle_t);.
The size of each frames is sizeframe = 0xC + numverts * trivertx_t;.
The frame fram can be found in the .MDL file at offset baseframe = baseframes + sizeframe * fram, with fram in the range [0,numframes[.
Each frame is a structure made of a header and an array:
typedef struct { long unknown; // Always zero u_char unknown7[7]; // strange values u_char code; // always 0x2F trivertx_t frame[numverts]; // array of vertices }
The number of vertices is numverts, and to each of the vertex declared here corresponds a Skin Vertex with the same index.
The first field in the header, is always zero. It is suspected that it could be either a time stamp or time duration indicator, or even a link to another animation frame
There are two additional vertex definitions in the header, for an unknown reason. Well, at least they look like valid vertex definitions. Whoever can figure out why will be welcome...
The sprites are used in Quake to represent objects that could not be rendered properly using polygons (because of a shape with too many small details) or that were not worth the trouble of using polygons (they render faster than Alias models or BSP based models).
The sprites are essentially designed for stuff like explosions, fire, magical effect, or the like. They can also be used for simple objects that have a vertical axis of rotation, like torches or barrels.
The format of the sprites is rather simple. Basically, this is a list of 2D pictures (flat bitmaps) organized in lumps.
Some frames are grouped in animation sequences, that start with the first picture in the animation and automatically proceed to the next, at the time values indicated in the begining of the sequence.
The sprite files (.SPR) begin with a header, which is immediately followed by the list of frames. There are no pointers to the individual pictures, which means that the engine probably reads and parses the whole file once and for all, because the only way to access a given picture is to read all previous frames and know their width and height.
Here is the format of the .SPR file header:
typedef struct { char name[4]; // "IDSP" long ver1; // Version = 1 long ver12; // 1 or 2 (maybe minor version number?) float radius; // Radius of the largest frame long maxwidth; // Width of the largest frame long maxheight; // Height of the largest frame long nframes; // Number of frames long uk0; // ? (always 0) long uk01; // ? (0 or 1) }spr_t;
The size of this header is 0x24 bytes.
There are two types of frames. Most of them contain a single picture, but some of them (in s_torch.spr and shots.spr) contain multiple pictures associated with floating point values.
The first kind of frames are marked with a leading (long) zero, followed by the picture data:
long marker; // Always 0 for single-picture frames picture pic; // Picture data, see below
The second kind of frames are marked with a leading 0x1 or 0x10000000, followed by the number of pictures, a list of floating point values, and a list of pictures:
long marker; // 0x1 or 0x10000000 long npics; // Number of pictures float times[npics]; // 0.0, 0.2, 0.3, ... picture pic[npics]; // Pictures
The times are offsets that describe when the corresponding picture shall be displayed, relative to an animation frame that repeats regularly. 0.0 means start of the animation frame, and 1.0 is the end. So if you have npics pictures, and want a regular sequence of pictures, you will start from 0.0 and regularly increase the dates by 1/npics.
By the way... the above is just a wild guess. But what the heck can it be, if it's not time stamps?
The format of each individual picture is given below. It contains the X and Y offsets, the width and height of the picture, followed by the list of pixels. The reference to the Quake palette is implicit and the value 0xff denotes a transparent pixel.
picture { long ofsx; // horizontal offset, in 3D space long ofsy; // vertical offset, in 3D space long width; // width of the picture long height; // height of the picture char Pixels[width*height]; // array of pixels (flat bitmap) };
The index for transparency is 0xFF.
The WAD2 format is only used for the graphic .WAD, that stores general information like the palette and the status bar items.
It is believed that this format was the original distribution file intended for Quake, but since then id Software probably realised they needed a file format that allowed a more direct mapping of their development directories, so they chose the PACK format instead.
The structure of the WAD2 files is almost exactly the same as that of DOOM's PWAD and IWAD files. Only the size of the directory entries is a bit different.
typedef struct { u_char magic[4]; // "WAD2", Name of the new WAD format long numentries; // Number of entries long diroffset; // Position of WAD directory in file }wadhead_t;
The entries in the WAD2 directory is a bit bigger than in PWAD and IWAD:
typedef struct { long offset; // Position of the entry in WAD long dsize; // Size of the entry in WAD file long size; // Size of the entry in memory char type; // type of entry char cmprs; // Compression. 0 if none. short dummy; // Not used char name[16]; // 1 to 16 characters, '\0'-padded } wadentry_t;
At offset diroffset in file, you will find the WAD directory itself:
wadentry_t dir[numentries]; // like in DOOM
This directory then contains pointers to all the entries in the WAD2 file, and like with PACK file there can be large amount of unused data, if one is not careful enough when building WAD2 files.
The field type in the directory identifies the entry. It's a single byte, which give 256 possibilities. Only 3 are currently used.
|
The pictures will probably used for everything concerning the status bar (animations, numbers, ...). They are not used for sprites, countrary to DOOM.
These files are just like DOOM flats, but with a header to indicate width and height.
typedef struct { long width; // Picture width long height; // Picture height u_char Pixels[height][width] } pichead_t;
The console lumps are just flat pictures, similar to DOOM flats, without any formatting, and using one byte per pixel. The color palette is that of the PALETTE lump.
The console background:
char Screen [200][320]; //This means it's a 320x200 arrayThe console characters:
char CChars [128][128]; //This means it's a 128x128 array
All the pictures, textures, sprites and alias model skins use color indexes in a 256-color table, and it can be expected that only a limited set of color palettes will be used. Maybe just one. At least, it's pretty sure that there is only one color palette for all the textures.
This format is Exactly the same as in DOOM:
struct RGB {char R; char G; char B;} Palette[256];Internally, the color palette is translated into a much bigger structure, that takes into account the light level, just like in DOOM. This structure depends on the number of colors available on the display, so it might be calculated by the engine at startup.
This document is the result of several days of hacking frenzy, and should be considered with care and limited trust. Most of the informations reported here result more from savage intuitions than scientific investigations. As a matter of fact, we only began modifying levels once the specificiation was almost complete.
However, it seems to work, so we expect you'll have loads of fun with QTEST1.
Don't forget to continue supporting id Software, and please buy the final product, whatever it's name, be it only because it's an investment in the future. The more money they get, the more people they can hire, and the faster they will build their next game.
The authors,
Olivier Montanuy, The Arrogant Frog (Author of the DOOM tools WinTex and DeuTex) Brian K. Martin, ZombyWoof (Author of the inner_o WAD and the MedDLe viewer for Quake) Raphaël Quinet (Main author of DEU and QEU, the Doom and Quake Editing Utilities)The latest version of this document will always be available on the official Quake-editing support site, www.gamers.org. You will also find it at the following locations: http://www.stud.montefiore.ulg.ac.be/ftp-mirror/quake/docs/ (filename: qkspec??.html) and http://ftp.cdrom.com/pub/idgames2/docs/ (in ZIP format, filename: qkspec??.zip).