=============================================================================
                   _             /////    /////   //////  /////   /////
  __ _ _   _  ___ | | _____    //        //  //  //     //      //
 / _` | | | |/ _ || |/ / _ \    /////   /////   ////// //       /////  3.1
| (_| | |_| | (_|||   (  __/       //  //      //     //           //
 \__, |\__,_|\___||_|\_\___|  /////   //      //////   /////  /////
    |_|
=============================================================================

             The Most Unofficial Quake Technical Specification.
                by Olivier Montanuy, with contributions from
   Brian Martin, Raphaël Quinet, John Wakelin, David Etherton and others
                               April 1, 1996

---------------------------------------------------------------------------

               Warning: This citation is morally challenged.

Ben là, je viens de terminer de lester le corps, tu vois ? [...] Tu vois,
il y a un barème quand tu lestes un corps, c'est-à-dire tu fais trois fois
son poids. Normalement un homme moyen, comme cette victime-ci, c'est trois
fois son poids. Et sinon, par exemple, ça change, hein. Tu vois, pour les
enfants ou pour les nains, ça change. Pour un enfant, c'est [...] quatre
fois son poids.
                           -- Body handling specifications, by Ben,
                              in "C'est Arrivé Près de Chez Vous" ("Man
                              Bites Dog")

---------------------------------------------------------------------------

List of Contents

 1. Introduction            1.1 Legal warning

                            1.2 Thanks
                            1.3 A word from the authors.
                            1.4 For more informations.
                            1.5 Typing conventions.

 2. The PACK files          2.1 The PACK file format

                            2.2 The Resources files
                            2.3 The Sound files
                            2.4 The Code lump

 3. The Level Map Models    3.1 Description of .BSP files

                            3.2 The format of .BSP files
                            3.3 Level layout definition
                            3.4 Bsp tree definition
                            3.5 Pre-calculated geometric entries
                            3.6 Entities definitions
                            3.7 Additional informations

 4. The Entity Alias Models 4.1 Presentation of Alias Models

                            4.2 Animating Alias Models
                            4.3 The Format of .MDL files

 5. The Sprites models      5.1 General description of Sprites

                            5.2 The Format of .SPR files

 6. New WAD file            6.1 The format of WAD2 files

                            6.2 Format of status bar pictures
                            6.3 Format of console lumps
                            6.4 Format of palettes

---------------------------------------------------------------------------

1. Introduction

1.1 Legal Warning

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.

---------------------------------------------------------------------------

1.2 Thanks

A lot of thanks to:

   * John Carmack and Mike Abrash of id Software, for leaking out enough
     details about the Quake engine to make this spec feasible.
   * Jay Wilbur of id Software, for tolerating all that Quake hacking
     madness, and keeping his lawyers tame.
   * The Vandals and Cavemens, for feats best not described.
   * Bernd Kreimeier for proofreading and handling all the mess caused by
     the specs.
   * Jens Hykkelbjerg for help with 3D and HTML.
   * Frans P. de Vries for his suggestions and for proofreading.
   * Luc Cluitmans for some insights with the code.
   * John Williston for the motivation.
   * Joost Schuur and the Quake Talk guys for all those rumors
     (some of which were really helpful).
   * All those who reported bugs in previous specs.

Contributors to this document:

   * Olivier Montanuy (Bsp models, various stuff)
     (Author of WinTex, Doom tool and BSP viewer for Quake)
   * Brian ZombyWoof Martin (Alias models).
     (Author of the MedDLe Alias model viewer for Quake)
   * Raphaël Quinet (Sprite models, HTML layout).
     (Main author of DEU and QEU, the Doom and Quake Editing Utilities)
   * John Wakelin and Mike Bond (definition of entities)
   * David Etherton (visibility lists, surfaces).
   * Stephen Crowley (checking of texture animations).

---------------------------------------------------------------------------

1.3 A word from the authors

This document is an updated version of the Unofficial Quake Specs 3.0, and
corrects many bugs and ommisions. All the informations presented here have
been tested and might eventually be somewhat limitedly trusted.

You will need some working knowledge of 3D geometry to understand this
specification, and a good deal of patience too, because some (if not all)
explanations may not be cristal clear.

Also, please do not make any full-featured editor publicly available for
Quake before id Software allows you to do so. The Quake specifications are
somewhat tolerated by id Software, but they are not a right. If editors are
released for QTEST1 and they harm future sales of Quake, chances are that
we will be in trouble with id Software and they could restrict the creation
or distribution of freeware/shareware Quake editors.

Last, if you enjoyed editing Quake, don't forget to support id Software and
to buy their products. Remember it's an investment in the future, since
part of their profits will be used to build the next generation of games
(hmmm... actually, it might also be invested in the current generation of
red sports car!).

The authors.

---------------------------------------------------------------------------

1.4 For more informations

1.4.1 How to get the last version of the specifications?

The latest version of this document will always be available on the
official Quake-editing support site,
http://www.nero.uni-bonn.de/~dn/q-sup/spec/qspec-current.html.

You will also find it at the following locations:

   * http://www.stud.montefiore.ulg.ac.be/ftp-mirror/quake/docs/
     (filename: qkspec??.html)
   * http://ftp.cdrom.com/pub/idgames2/docs/
     (in ZIP format, filename: qkspec??.zip).

Other sites will also have a copy of this document (according to the
distribution rights stated above) but we cannot guarantee that those sites
will have the most recent version. Usually, we upload the new versions on
www.stud.montefiore.ulg.ac.be first, then on the other sites on the same
day.

1.4.2 Informations about 3D rendering

   * The Difference Engine home page.
   * 3DGPL, a tutorial for 3D drawing functions, by Sergei Savchenko.
   * The list of 3D game engines.

1.4.3 Cool Quake related pages

   * id software
   * AfterShock, Joost's Quake Webzine.
   * Jens's Quake page.
   * Dr Sleep's Quake page.
   * Robert's Quake page.
   * Joost's Quake page on Doom Gate.
   * Colin's Quake page.
   * Jason's Unofficial Quake Homepage.
   * Joe's Quake Stuff and links.
   * Raphaël's game editing page.

1.4.5 Newsgroups

   * rec.games.computer.quake.announce, Info/FAQ/Announcements about Quake.
     (Moderated)
   * rec.games.computer.quake.editing, Editing and hacking Quake-related
     files.
   * rec.games.computer.quake.misc, General discussion of Quake.

---------------------------------------------------------------------------

1.5 Typing conventions

All the code structures are written in C, because C is all we talk. Well,
it could have been worse. We could have written that specification in
French.

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).

---------------------------------------------------------------------------

2. The PACK files

2.1 The PACK files format

The PACK format is used to emulate a Unix directory arborescence, and to
avoid putting some hundreds of files on the user's disk. It is not a
compressed format, and it's very similar to the WAD format of DOOM.

2.1.1 The PACK Header

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;

2.1.2 The PACK Directory

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(pakentry_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.

2.1.3 Determining the type of PACK Entries

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.

 .WAV  Sound files (RIFF/WAVE)
 .BSP  levels (map and textures)
 .MDL  3D models (Alias)
 .SPR  Sprite models
 .DAT  Pseudo-code
 .RC   Resources
 .WAD  WAD2 file

2.2 The resources files (.RC)

Those files are ordinary Text, in Unix format (LF only, no CR), so they
won't display correctly under DOS if you are using an old editor. They
contain only settings and definitions.

2.3 The sound files (.WAV)

The sound files are ordinary 16-bit RIFF WAVE files (the format commonly
used under Microsoft Windows, and now supported by many utilities under
different operating systems).

2.4 The code lump (.DAT)

The .DAT file contains some semi-compiled machine independent P-code,
instead of the Quake programming language .QC files.

This file contains the behavior associated to each of the entities. For
instance, this file contains the frame table that defines how and when each
frame of the Alias Models must be displayed.

This file also contains the light styles used to animate Surfaces of the
BSP models. Those light styles can be found as strings, among the other
character strings.

Here is a very partial description of that data lump. The only interesting
part is the list of text strings, because it gives the names of possible
spawning sequences for the Entities.

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 (frames?)
  codentry_t  table12;         // table of 3 long
  codentry_t  table12;         // table of 3 long
  codentry_t  table64;         // Table of 16 long
  codentry_t  strings;         // Character strings, separated by '\0'
  codentry_t  numeric;         // Constants and variable
} codehead_t;

Do not attempt to decompile the QC 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.

---------------------------------------------------------------------------

3. Level Map Models

3.1 Description of .BSP Files

3.1.1 General description of level Maps

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.

3.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.

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:

  1. A list of entities that are present in the level.
  2. A description of the level map, in term of surfaces, edges, vertices,
     and textures on the surfaces. Actually, there might be more surfaces
     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, hull
     definitions, BSP nodes, bound BSP nodes, BSP leaves, visibility lists,
     and various 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 TEST1.BSP map.

---------------------------------------------------------------------------

3.2 The Format of BSP files

Beware: the description below is valid only for the version 0x17 of the BSP
file format. Future versions will certainly differ.

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 14 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 surfaces;           // Map Surfaces.
                               // numsurfaces = size/sizeof(surface_t)
  dentry_t lightmaps;          // Wall Light Maps.
  dentry_t boundnodes;         // BSP bound nodes, for Hulls.
                               // numbounds = size/sizeof(hullbound_t)
  dentry_t leaves;             // 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.

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
{ 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.

---------------------------------------------------------------------------

3.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.

3.3.1 The Definitions of Hulls

The name Hull 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 Hulls, which are independent areas,
roughly bounded by Bound 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;                   // index of first BSP node
  long boundnode;              // index of first Bound BSP node
  long numleafs;               // number of 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.

Unknown fields

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.

3.3.2 List of Vertices

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

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.
The reason is the same as for Planes.

3.3.3 The Edges

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 by more
than one surface (two or three is typical).
These edges are the only structure that reference 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;         // index of the start vertex
                               //  must be in [0,numvertices[
  u_short endvertex;           // index of the start vertex
                               //  must be in [0,numvertices[
} edge_t;

Note that, because of the encoding of the List of Edges, the first edge in
the list is never used.

3.3.4 The Surfaces

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 vertically (in texture space)
                               // if bit 1==1 flip horizontally (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 typelight;            // type of lighting, for the surface
  u_char baselight;            // from 0xFF (dark) to 0 (bright)
  u_short unknown1;            // 0xFFFF, probably useless (padding)
  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.

Light level of the surface

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 surface, 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 surface:

   * value 0 is the normal value, to be used with a light map.
   * value 0xFF is to be used when there is no light map.
   * value 1 produces a fast pulsating light
   * value 2 produces a slow pulsating light
   * value 3 to 10 produce various other lighting effects, as defined in
     The code lump.

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

Texture names

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 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 its own set of edges, the Surface points
to a 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).

Texture mapping

The textures are rendered by using Mip Mapping: depending on the distance
from the surface 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
surface vertices (i.e. the surface 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 surfaces is rendered as an ordinary
texture-mapped polygon, but beware that this polygon may not be convex.

The texture mapping is a bit more difficult to understand than for Alias
models, because it takes the distance into account, and it doesn't use Skin
Vertices as anchor points for the texture.

For any given vertex, the position (S,T) in texture space is given by two
of the space 3D coordinates (X,Y,Z). That depends on the orientation of the
plane the texture is in, or more precisely on the plane type.

For instance, if the plane is oriented towards X (plane of type 0), then S
= Y + sofs and T = Z + tofs. X is discarded because it doesn't change fast
enough, in that surface.

Actually, the formula for S and T also takes into account the surface
flips.

Unknown field

There is one short integer that has not been identified, and experiment
showed that its value seems to be ignored by the engine. However, it is
safer to put value 0xFFFF there, because this is the default value used in
every surface.

3.3.5 The Mip Textures

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 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:

   * if it begins by * it will be animated like lava or water.
   * if if begins with sky if will double scroll like a sky.
     Beware that sky textures are made of two distinct parts.

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

---------------------------------------------------------------------------

3.4 Bsp tree definition

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

3.4.1 The BSP tree Nodes

The BSP tree nodes are used to partition one hull (from the List of Hulls)
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 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, 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
  boundbox_t box;              // Bounding box of node and all childs
} node_t;

The 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 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 surfaces,
and has a special type (-2) that means the BSP tree rendering must stop.

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.)

3.4.2 The BSP Tree Leaves

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

typedef struct
{ long type;                   // Special type of leaf
  boundbox_t bound;            // Bounding box of the leaf
  long vislist;                // Beginning of visibility lists
                               //     must be -1 or 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 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 surfaces and bound by the BSP
node split lines, appears in 3D space as a convex polytope.

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

   * -1: ordinary leaf, nothing happens
   * -2: the leaf is invalid, so the level is not displayed.
   * -3: Water, the vision is troubled.
   * -4: Acid, like water but green, and hurts the player.
   * -5: Lava, vision turns red and the player is badly hurt.
   * -6: Behaves like water, but is used for sky.
   * All types below -6 seem to be water (maybe they are not implemented
     yet)

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.

Unknown fields

The purpose of the flag, and zeroes fields is unknown and shall be
investigated.

3.4.3 The List of Surfaces

This structure stores a list of indexes of surfaces, 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 surfaces 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 number of surfaces was
not possible.

Also beware that a surface typically extends over more than just one BSP
tree leaf, and generally isn't convex at all. Actually a surface can have
pretty weird shapes.

Unknown fields

Strangely, a given surface may be referenced more than once in the list of
surfaces, especially if it is not convex.

However, experiment shows that a given surface need only be listed once for
any given BSP tree leaf: duplicate references just seem totally useless.
They don't even seem to slow down the engine.

3.4.4 The List of Edges

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

short lstedge[numlstedge];

All the edges in a Surface are stored consecutively, with the correct
orientation so that all the vertices in the surface are walked
counter-clockwise.

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

   * if lstedge[e] is positive, then lstedge[e] is an index to an Edge, and
     that edge is walked in the normal sense, from vertex0 to vertex1.
   * if lstedge[e] is negative, then -lstedge[e] is an index to an Edge,
     and that edge is walked in the inverse sense, from vertex1 to vertex0.

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

The simple surfaces are made of just one closed set of edges, or contour.
However, adjacent edges need not be stored in order.

Typically, however, each surface is composed of more than one closed set of
edges, and each set is not necessarily convex, so beware when you fill that
kind of polygon.

Unknown fields

The order of edges in a surface seems to be totally irrelevant, even in the
surface is not convex. Apparently, any order works.

3.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
      {
        for (bit = 0x80; bit > 0; bit = bit / 2, L++)
          {
            if (visisz[v] & bit)
              TagLeafAsVisible(L);
          }
      }
  }

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.

---------------------------------------------------------------------------

3.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 The Bound BSP Nodes with BSP tree nodes, they are not
used for the rendering of the level.

3.5.1 List of Planes

The plane definitions are used for Surfaces, BSP Nodes, Bound BSP 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:
                               // 0: facing toward X   3: toward -X
                               // 1: facing toward Y   4: toward -Y
                               // 2: facing toward Z   5: toward -Z
  long    firstsurf;           // index of 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.

3.5.2 The Bound BSP Nodes

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

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

The bound 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 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 top bound node as defined in the Hull.

   * If the value of front (resp. back) is positive, then it's the index of
     a child bound node.
   * If value -1 is met, then the front (resp. back) half space is outside
     of the hull, and collision is impossible.
   * If the value -2 is met, then the front (resp. back) half space is
     inside the hull, and the BSP nodes must be checked.

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

If you modify a 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.

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

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

3.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 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

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:

   * baselight is the base light level of each surface (the flat shading of
     the surface).
   * lightmap(X,Y,Z) results from the translation of the lightmap into 3D
     space (see below).
   * lightstyle is a table of available light styles, available in the code
     lump. The light style used depends on the typelight of the
     corresponding surface.
   * The exact lightstyle multiplier changes over time, so that it looks
     like the surface's light is pulsating.

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
Surface 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 surfaces's
bounding box, i.e. the bounding box of all the vertices contained in that
surface (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 surface'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 surfaces. 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 surface (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 surface 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.

3.6 Definition of entities

(Thanks to John Wakelin who wrote most of this section)

The entities define the monsters, things, but also the positions in space
where something must happen. So they are the Quake equivalent of both the
THINGS and the LINEDEF types from DOOM.

The entities are defined in the .BSP file in a series of simple text blocks
as shown below.

The entity definitions are made up of a series of specific details that
define what each is, where it starts, when it appears etc. Each specific is
followed by a modifier that arguments it. All definitions have the
classname specific that identifies that entity. The classname specifics
relate intimately with the code lump and are the names of functions written
in Quake C.

3.6.1 Format of entities definitions

I have chosen the terms ``specific'' and ``arg'' for the two different
parts of each detail of the definition. These terms may or may not suit
but, they will have to do until we learn what id calls them.

Line feeds (ASCII 0x0a) separate each definition and each line in the
definition. Spaces (ASCII 0x20) separate specifics from args. I tried
changing them around and it does not seem to matter what separates them as
long as it is white space.

The specifics and args are contained within double quotes. Each definition
is bounded by curly braces.

Like so:

  {
    "<specific>" "<arg>"
    "<specific>" "<arg>"
    ...
  }

3.6.2 Possible specifics

 specifics   args        Description
 classname   <name>      Type of entity to be defined (mandatory)
 origin      # # #       coordinates of where it starts in space
 angle       #           direction it faces or moves (sometimes in
                         degrees)
 light       #           used with the light classname (how bright?)
 target      <t#>        Matches a targetname & would appear to work
 targetname  <t#>        like a linedef tag
 wad         <filename>  ??? - The world
 spawnflags  #           Used to flag the definition of an object that is
                         to be different than the default behavior or type
                         for a classname. See item_health for a good
                         example of this
 model       *#          Tag to a moving shape/hull (see Models)

The following specifics are found only with the models.

 specifics  args  Description
 speed      #     How fast the model is moved
 wait       #     How long a pause between completion of movement and
                  return to the original position (in seconds I think)
 lip        #     Seems to be a means of adjusting the starting position
                  of model
 style      #     I am guessing that it is like the spawnflag arg in that
                  it may determine a different than default type.
 dmg        #     How much damage the model causes when it shuts on you?

3.6.3 Classnames

The following classnames are the name of a function in the Code Lump.

Note these are only the names that are known to work currently, but later
versions of Quake will probably use different names.

 Classnames              Associated        Description
                         specifics
 worldspawn              wad               ??? Pointer to a .wad file
                         angle             -
 light                   origin            Light source
                         light             Brightness -sometimes no light
                                           level is specified (default?)
 info_player_start       origin            Player starting coordinates
                         angle             -
 info_player_deathmatch  origin            Deathmatch start coordinates
                         angle             -

Weapons - take the origin additional specific (and sometimes angle but I
don't see why)

 weapon_supershotgun     Double barrel
 weapon_nailgun          Nailgun
 weapon_supernailgun     Chain Nailgun
 weapon_grenadelauncher  Grenade Launcher
 weapon_rocketlauncher   Rocket Launcher
 weapon_lightning        Lightning Gun (?)
 weapon_superlightning   Chain Lightning Gun (?)

These monsters appear to take the origin and angle specifics, but they
might also take other specifics as well.

 monster_knight    Slashes at you with sword
 monster_demon1    Jumps on you... then server crashes (out of area???)
 monster_wizard    Shoots ``caco'' lightning balls at you ... deadly aim
 monster_shambler  terrifying 10 foot tall beast with 3 clawed hands
 monster_ogre      Chainsaw *and* nailgun
 monster_army      looks like an untexture-mapped player
 monster_tarbaby   Blobbish thing that jumps up at you when close
 monster_fish      Swims after you ... should prob be in water
 monster_serpent   Looks like an untexture mapped stingray (crashes)
 monster_dragon    Nice looking Wayvern ... (crashes)
 monster_vomit     Untextured blob ... scary and fast
 monster_zombie    Untextured humaniod ... (crashes)

Items - Take the origin and spawnflags additional specifics

 item_health    25% with spawnflag 1(default)
                100% with spawnflag 2
                13% with spawnflag 3 (huh?)
 item_armor1    100% Armor (blue)
 item_armor2    150% (yellow)
 item_armorInv  200% (red) - why didn't they use spawnflags here?
 item_shells    Shotgun shells (ammo for shotguns)
 item_spikes    Nine inch Nails (ammo for nailguns)
 item_rockets   Rockets (ammo for grenade and rockt launchers)
 item_cells     (ammo for lightning weapons presumably)
 item_key       I assume it is a key but the game crashes hard if it is
                hacked in

These entities are always associated with models via targetnames.

 info_teleport_destination  origin      Teleport landing coordinates
                            angle       -
                            targetname  Same as trigger target
 path_corner                origin      -
                            target      Where the train came from
                            targetname  Where to send it next
                                        These are used to define the path
                                        of a func_train such as the one
                                        above the main room in test2.

Models - These classnames are used with the model-type of entities

 func_door         door
 func_door_secret  secret door
 func_button       button
 func_plat         Lifts
 func_train        Sliding platforms
 func_dm_only      Teleporters that only show up in deathmatch (may work
                   with other things but, no examples here)
 trigger_teleport  teleporter entrance (walk-over)
 trigger_multiple  Multiple actions that are activated by a walk over
                   rather than button type of switch.

Note: The term model specifies an entity that controls the actions of a
hull and its parameters. Do not confuse it with ordinary entity models.

The model numbers (*x) comes from the order in which the hulls are stored
in the hulls structure.

The first hull (*0) is a bounding box that defines the extents of the whole
world. The rest (starting at *1) make up the models.

The hulls are defined by a bounding box of the max and min(x,y,z).
Therefore they are always parrallel to the horizontal planes. This would
seem to exclude any ramp-like structures that move.

The specific classname, eg. func_button, tells Quake what type of action to
set up for this hull. The rest of the specifics in the model definition are
arguments to the function refered by the classname and define things like:
what direction to move, how long to wait between multiple actions, what tag
to use to associate the action with another model, how much damage it will
inflict if it closes on you, etc.

For more information, take a look in appendix A, that contains a list of
known models.

---------------------------------------------------------------------------

3.7 Additional Informations

3.7.1 Texture names

(Thanks to Stephen Crowley for experimenting with the names)

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.

The animated texture names have a name that begins with *. That's enough
for the texture to animate with vortex, like the lava, or the water.

The sky textures have a name that begin with sky. Such a texture will
animate with two scrolling planes, made out of two separate pictures that
are placed side to side in the texture map.

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 Surface flips is set when the
texture is supposed to be animated. But it must be an artifact, or a
discarded feature, since modifying this bit changes nothing to the texture
animation.

3.7.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...

---------------------------------------------------------------------------

4. The Entity Alias Models

(Thanks to Brian Martin who clarified most of this section)

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.

Importing models from 3DS or the likes is now quite easy. You'll just have
to work out a few things on your own (like calculation of the vertex
normals, matching them with the vertex normal table, finding the bounding
area of the object, and scaling the vertices to 8-bit values).

4.1 Presentation of Alias Models

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 in 3D space and the triangle on the
skin 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.

4.2 Animating Alias models

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 skeletal 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
hide the original triangle, by reducing it or by putting another triangle
in front.

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.

Or you can use separate models, like the player gibs, but then the original
part must be reduced to a very small size.

4.3 Alias Model .MDL file format

The .MDL files are collection of lumps, but contrary to .BSP files there
are no pointers to access the lumps directly, and it is suspected that
there will be, in future versions of the models.

Once you have the file header, you can find all the other parts, just by
calculating their position in the file.

A Model file contains:

  1. A skin texture, that describes the color of the skin and clothes of
     the creature, or whatever it can be wearing.
  2. A list of skin vertices, that are just the position of vertices on the
     skin texture.
  3. A list of triangles, the describe the general shape of the model.
  4. A list of animation frames.
     Each frame holds a list of the 3D vertices and the index of the
     precalculated vertex normal.

4.3.0 Alias Model Header

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).

4.3.1 Alias Model Skin

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;         // Always 0
  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 0xFF represents a transparent area, like
in level textures.

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 independent 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 along the vertical axis.

This design is used to allow the correct rendering of a seamless skin
texture, using Skin Vertices with onseam == 1, on the skin border.

4.3.2 Alias Model Skin Vertices

A .MDL file is made of a list of vertices. To each of these vertices
corresponds a 3D position, a normal, 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];

4.3.3 Alias Model Triangles

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 is on the front skin, 0 means that it is on
the back skin, so any skin vertex that is on seam must have its horizontal
value increased by skinwidth/2, so as to find its correct position on the
back skin.

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];

4.3.4 Alias Model Frames

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 its guts all over the
place...).

The frame vertices

Each frame vertex is defined by a 3D position and a normal 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;     // index of the vertex normal
} trivertx_t;

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] ) + origin[i]

Where scale, and origin can be found as vectors in the Model Header.

The Light Normal Indexes

The lightnormalindex field is used to represent the vertex normal vector.
The normal vector of a given vertex is the average of the normal vectors of
all the faces that contain this vertex.

This information is necessary to calculate the Gouraud shading of the
faces, but actually a crude estimation of the actual vertex normal is
sufficient. That's why, to save space and to reduce the number of
computations needed, it has been chosen to approximate each vertex normal.

The ordinary values of lightnormalindex are comprised between 0 and 161,
and directly map into the index of one of the 162 precalculated normal
vectors that can be found in Appendix B.

However, value 255 of lightnormalindex is a bit special, in the sense that
a vertex taged with that value will always look dark, whatever the light
level around.

Experiments show that value 255 should be used for dull object, while
values from 162 to 254 could be used for bright object, however it could
just be an artifact, don't rely on it.

The frames

The beginning 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
  trivertx_t min;              // minimum values of X,Y,Z
  trivertx_t max;              // maximum values of X,Y,Z
  trivertx_t frame[numverts];  // array of vertices
} frame_t;

The number of vertices is numverts, and to each of the vertex declared here
corresponds a Skin Vertex with the same index.

The frame header contains two vertex definitions, min and max, that define
a bounding box around the whole frame: all the other vertices must be
inside that bounding box.

However, that bounding box is only used for collision detection, so if you
make it smaller than it should be the model will still display fine, but
you can get very close to it before hitting it.

To get the floating point values corresponding to min and max, treat them
as if they were ordinary vertex positions.

Unknown fields

The first filed of the header is always zero, and there's no explanation
for it. It cannot be a time stamp, since frame animations is in fact coded
in the Code lump.

The lightnormalindex of min and max have irrelevant values, and are
apparently not used. They only pad the structure to 4 bytes.

---------------------------------------------------------------------------

5. The Sprite models

(Thanks to Raphaël Quinet who wrote most of this section)

General description of Sprites

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 beginning of the sequence.

5.2 The Format of .SPR files

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.

5.2.1 Sprite file header

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.

5.2.2 Sprite frames

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?

5.2.3 Pictures

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.

typedef struct
{ 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)
} picture;

---------------------------------------------------------------------------

6. The WAD2 files

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.

6.1 The format of WAD2 files

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.

6.1.1 The WAD2 file header

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;

6.1.2 The WAD directory

The entries in the WAD2 directory are 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 amounts of unused data, if one
is not careful enough when building WAD2 files.

6.1.3 Determining the type of directory entries

The field type in the directory identifies the entry. It's a single byte,
which give 256 possibilities. Only 3 are currently used.

 0x40=  '@'=  Color Palette
 0x42=  'B'=  Pictures for status bar
 0x44=  'D'=  Used to be Mip Texture
 0x45=  'E'=  Console picture (flat)

6.2 Format of status bar pictures

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;

6.3 Format of console lumps

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 array

The console characters:

char  CChars [128][128];       //This means it's a 128x128 array

6.4 Format of Palettes

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.

---------------------------------------------------------------------------

Appendix A. Model Examples

These examples of the model types may help to explain their use a little
better. They were extracted from the three levels included in QTEST1.

A.1 Map TEST1

           Models            Hull Bounding box Co-ordinates
 {                          min: x = 412, y = 1352, z = -144
   "model" "*1"             max: x = 428, y = 1368, z =  -24
   "angle" "-2"
   "classname" "func_door"
   "targetname" "t2"
 }

 {                          min: x = 448, y = 1352, z = -144
   "model" "*2"             max: x = 464, y = 1368, z =  -24
   "angle" "-2"
   "classname" "func_door"
   "targetname" "t2"
 }

 {                          min: x = 500, y = 1240, z = -104
   "model" "*5"             max: x = 512, y = 1256, z =  -88
   "classname" "func_button"
   "target" "t2"
 }

These are the columns that block the path to the teleport. *1 is the left
column (looking from outside the room by the button) and *2 is the one one
the right. *5 is the button that lowers the two columns.

Note the targetname t2 for both columns and the same one for the button
(model *5) This is what ties the button to the lowering of the columns.

The angle specific here describes the direction to move the column.
Changing it to "0" moves the column to the right instead of down (looking
at it from by the button). The angle is in degrees for objects moving
parallel to the normal line of sight but for movements perpendicular to
this ``horizontal plane'', "-1" and "-2" are used for up and down
respectively.

Note: When the angle of model *1 was changed to "-1", it moved up instead
of down... After jumping through the teleporter the column could be seen
protruding though the floor upstairs. This is important in that it showed
that the model was in fact a 3D object that is simply being moved in the
manner defined and not just some textures being manipulated in such a way
as to make them appear to be solid.

                   Models                    Hull Bounding box Co-ordinates
 {                                          min: x = 244, y = 1576, z = -136
   "model" "*3"                             max: x = 284, y = 1624, z =  -40
   "target" "t1"
   "classname" "trigger_teleport"
 }

 {                                          (Not a model, just a target)
   "targetname" "t1"
   "angle" "90"
   "origin" "448 1028 16"
   "classname" "info_teleport_destination"
   "light" "250"
 }

Model *3 is the teleporter. The target specific points it to the
info_teleporter_destination entity with the same tag (t1).

              Model              Hull Bounding box Co-ordinates
 {                               min: x = 448, y = 668, z =   8
   "model" "*4"                  max: x = 512, y = 684, z =  88
   "classname" "func_door_secret"
   "angle" "180"
 }

This is the ``secret'' door that leads out onto the ledge with the 100%
health. Again the angle just tells the function which way to move it.

            Model
                             Hull Bounding box Co-ordinates
 {
   "model" "*6"
   "classname" "func_door"
   "angle" "180"
   "spawnflags" "1"
   "targetname" "t3"
   "speed" "175"
   "wait" "8"
 }
                            min: x = -304, y = 1360, z = -16
                            max: x =  -64, y = 1472, z =  -4

 {
   "model" "*7"
   "classname" "func_button"
   "target" "t3"
   "angle" "-2"
   "lip" "4"
   "wait" "10"
 }
                            min: x = -400, y = 1564 z =  -4
                            max: x = -344, y = 1616 z =   4

These are the bridge to the 150% armor and the button on the floor that
causes it to extend. Note the lip arg in model *7, this defines the
starting position in some way related to the surface that the model is
being moved into or out of.

It is also notable that the buttons are activated by touch (walking over
this one is as good as bumping model *5. Presumably you could put a button
on the ceiling and have the player jump up into it.

A.2 Map TEST2

There are a lot of models/hulls in test2 (lots of moving stuff) and it is
here that we start to see some of the real possibilities inherent in the
engine.

            Model
                              Hull Bounding box Co-ordinates
 {
   "model" "*7"
   "speed" "200"
   "classname" "func_door"
   "angle" "0"
   "targetname" "t3"
   "spawnflags" "4"
   "dmg" "1000"
 }
                            min: x = 1112, y = -1024, z =   0
                            max: x = 1240, y =  -832, z = 112

 {
   "model" "*9"
   "speed" "200"
   "dmg" "1000"
   "targetname" "t3"
   "angle" "180"
   "spawnflags" "4"
   "classname" "func_door"
 }
                            min: x = 2120, y = -1024, z =   0
                            max: x = 2248, y =  -832, z = 112

These are the walls that make up the two crushing traps on either side of
the starting room that allow you to kill anyone who goes for the yellow
armor in the cages.

Here is the first use of the dmg arg that defines how badly it hurts you if
it closes on you. There are some doors that will hurt you slightly (3-5%)
if they catch you as they are closing. There might be a default dmg value
for certain types of doors but, clearly, setting this at 1000 as it is
here, will kill you in one hit.

            Model
                               Hull Bounding box Co-ordinates
 {
   "model" "*11"
   "target" "t4"
   "classname" "func_train"
 }
                             min: x = 1792, y = -1064, z = 304
                             max: x = 1888, y =  -984, z = 320

 {
   "target" "t5"
   "targetname" "t4"
   "origin" "1792 -1064 304"
   "classname" "path_corner"
 }
                             (Not a model, just a target)

 {
   "target" "t4"
   "targetname" "t5"
   "classname" "path_corner"
   "origin" "1472 -1064 304"
 }
                             (Not a model, just a target)

This is that sliding platform that goes back and forth above the starting
room and carries you to the grenade-launcher and back again.

The model is the ferry itself and I have included it's two path_corners
that define the extents of its route. The thing to note here is how the
targets are set up pointing to each other's targetname to keep the platform
moving to and fro. I imagine that if you were to set up a series of these
corners, that just kept pointing to the next one in line, that you could
have one of these things follow a long complex path through the level.

            Model
                              Hull Bounding box Co-ordinates
 {
   "model" "*1"
   "classname" "func_door"
   "angle" "180"
   "targetname" "t1"
 }
                            min: x = 1392, y = -1272, z = -16
                            max: x = 1696, y =  -840, z =  -4

 {
   "model" "*2"
   "classname" "func_door"
   "angle" "0"
 }
                            min: x = 1696, y = -1272, z = -16
                            max: x = 2000, y =  -840, z = -4

 {
   "model" "*3"
   "classname" "func_button"
   "angle" "90"
   "target" "t1"
 }
                            min: x = 1288, y = -832, z = 16
                            max: x = 1336, y = -816, z = 56

 {
   "model" "*4"
   "spawnflags" "4"
   "targetname" "t1"
   "classname" "func_door"
   "angle" "270"
   "wait" "4"
 }
                            min: x = 1632, y = -1408, z = -16
                            max: x = 1760, y = -1288, z =  -4

 {
   "model" "*5"
   "classname" "func_door"
   "spawnflags" "4"
   "angle" "90"
   "targetname" "t1"
   "lip" "0"
   "wait" "4"
 }
                            min: x = 1632, y = -824, z = -16
                            max: x = 1760, y = -688, z =  -4

 {
   "model" "*8"
   "target" "t1"
   "angle" "90"
   "classname" "func_button"
 }
                            min: x = 2024, y = -832, z = 16
                            max: x = 2072, y = -816, z = 56

Models *1 and *3 somehow define the targetname for model *2.

These are all the definitions that handle the two buttons in the yellow
armor cages and the four floor surfaces that they cause to open. Notice
that there are only five target/targetname specifics (t1) in the group.

Every once in a while, when calling two models into action, one of the
targetnames will be missing. It turns out that you can wrap at least one
targetname-less model in between two models that are targeted at one
another. Quake, apparently, will assume that you mean to apply the action
to the middle one as well.

              Model
                                  Hull Bounding box Co-ordinates
 {
   "model" "*25"
   "targetname" "t15"
   "angle" "180"
   "classname" "func_door"
 }
                                 min: x = 2336, y = -568, z = 32
                                 max: x = 2400, y = -552, z = 96

 {
   "model" "*26"
   "classname" "func_door"
 }
                                 min: x = 2400, y = -568, z = 32
                                 max: x = 2464, y = -552, z = 96

 {
   "model" "*27"
   "target" "t15"
   "classname" "trigger_multiple"
 }
                                 min: x = 2336, y = -616, z = 56
                                 max: x = 2464, y = -560, z = 64

Here is another example of the dropped targetname whilst wrapping, using
the trigger_multiple classname. This is the small double doors that let you
out of the secret room with the red armor. Model *27 is walk-over activated
(as are all triggers) and opens the doors when you approach them.

            Model
                             Hull Bounding box Co-ordinates
 {
   "model" "*31"
   "classname" "func_plat"
 }
                            min: x = 1248, y = -704, z = 160
                            max: x = 1392, y = -576, z = 320

func_plats are the elevator/lifts that automatically rise as you step on
them. If they have the angle arg included it would seem to be an indicator
of the direction from which it is activated.

A.3 Map TEST3

             Model
                                Hull Bounding box Co-ordinates
 {
   "model" "*5"
   "classname" "func_dm_only"
 }
                               min: x = 1184, y = -960, z = -48
                               max: x = 1200, y = -848, z =  48

 {
   "model" "*6"
   "classname" "func_dm_only"
 }
                               min: x = -576, y = -496, z = -40
                               max: x = -560, y = -400, z =  64

Map three is the only one that has these ... these models are obviously the
two teleporters that are only available during deathmatch.

A.4 List of Hulls

This is all of the hulls from all three worlds and their bounding box
coordinates.

A.4.1 TEST1.BSP

Number of hulls = 8

world   : min: x = -720, y =  512, z = -256; max: x = 1184, y = 1696, z =  336
Model #1: min: x =  412, y = 1352, z = -144; max: x =  428, y = 1368, z =  -24
Model #2: min: x =  448, y = 1352, z = -144; max: x =  464, y = 1368, z =  -24
Model #3: min: x =  244, y = 1576, z = -136; max: x =  284, y = 1624, z =  -40
Model #4: min: x =  448, y =  668, z =    8; max: x =  512, y =  684, z =   88
Model #5: min: x =  500, y = 1240, z = -104; max: x =  512, y = 1256, z =  -88
Model #6: min: x = -304, y = 1360, z =  -16; max: x =  -64, y = 1472, z =   -4
Model #7: min: x = -400, y = 1564, z =   -4; max: x = -344, y = 1616, z =    4

A.4.2 TEST2.BSP

Number of hulls = 35

world    : min: x = -2160, y = -3912, z = -256; max: x = 3104, y =  1312, z = 784
Model  #1: min: x =  1392, y = -1272, z =  -16; max: x = 1696, y =  -840, z =  -4
Model  #2: min: x =  1696, y = -1272, z =  -16; max: x = 2000, y =  -840, z =  -4
Model  #3: min: x =  1288, y =  -832, z =   16; max: x = 1336, y =  -816, z =  56
Model  #4: min: x =  1632, y = -1408, z =  -16; max: x = 1760, y = -1288, z =  -4
Model  #5: min: x =  1632, y =  -824, z =  -16; max: x = 1760, y =  -688, z =  -4
Model  #6: min: x =  1280, y = -1072, z =   24; max: x = 1344, y = -1040, z =  40
Model  #7: min: x =  1112, y = -1024, z =    0; max: x = 1240, y =  -832, z = 112
Model  #8: min: x =  2024, y =  -832, z =   16; max: x = 2072, y =  -816, z =  56
Model  #9: min: x =  2120, y = -1024, z =    0; max: x = 2248, y =  -832, z = 112
Model #10: min: x =  2016, y = -1056, z =   24; max: x = 2080, y = -1040, z =  40
Model #11: min: x =  1792, y = -1064, z =  304; max: x = 1888, y =  -984, z = 320
Model #12: min: x =  2704, y =   -64, z =  -96; max: x = 2720, y =   -48, z =   0
Model #13: min: x =  2704, y =   -32, z =  -96; max: x = 2720, y =   -16, z =   0
Model #14: min: x =  2880, y =   -64, z =  -96; max: x = 2896, y =     0, z =   0
Model #15: min: x =  2232, y =  -256, z = -136; max: x = 2280, y =  -240, z = -88
Model #16: min: x =  2384, y = -2240, z =   72; max: x = 2480, y = -2016, z =  88
Model #17: min: x =  2152, y = -2400, z =   80; max: x = 2200, y = -2384, z = 120
Model #18: min: x =  2240, y = -2016, z =   96; max: x = 2272, y = -1952, z = 256
Model #19: min: x =  2608, y = -2008, z =  112; max: x = 2624, y = -1960, z = 152
Model #20: min: x =  2880, y = -1936, z =   80; max: x = 3008, y = -1792, z =  96
Model #21: min: x =  2880, y = -2080, z =   80; max: x = 3008, y = -1936, z =  96
Model #22: min: x =  2680, y = -1936, z =  128; max: x = 2728, y = -1920, z = 168
Model #23: min: x =  1936, y = -1760, z =  -16; max: x = 2032, y = -1600, z =   0
Model #24: min: x =  2400, y = -2552, z =   96; max: x = 2464, y = -2536, z = 192
Model #25: min: x =  2336, y =  -568, z =   32; max: x = 2400, y =  -552, z =  96
Model #26: min: x =  2400, y =  -568, z =   32; max: x = 2464, y =  -552, z =  96
Model #27: min: x =  2336, y =  -616, z =   56; max: x = 2464, y =  -560, z =  64
Model #28: min: x =  1840, y = -1760, z =  -16; max: x = 1936, y = -1600, z =   0
Model #29: min: x =  2408, y =  -864, z =   96; max: x = 2424, y =  -800, z = 192
Model #30: min: x =  2560, y =  -688, z =   88; max: x = 2656, y =  -656, z = 104
Model #31: min: x =  1248, y =  -704, z =  160; max: x = 1392, y =  -576, z = 320
Model #32: min: x =  1808, y =  -760, z =    8; max: x = 1824, y =  -712, z =  56
Model #33: min: x =  1808, y = -1528, z =    8; max: x = 1824, y = -1480, z =  56
Model #34: min: x =  2432, y = -1024, z =    0; max: x = 2560, y =  -896, z =  96

A.4.3 TEST3.BSP

Number of hulls = 8

world   : min: x = -1000, y = -976, z = -448; max: x = 2064, y = 1152, z =  512
Model #1: min: x =   592, y =  656, z = -292; max: x =  656, y =  720, z = -128
Model #2: min: x =   592, y =  832, z = -128; max: x =  656, y =  896, z =    0
Model #3: min: x =   448, y =  832, z =   16; max: x =  576, y =  896, z =  192
Model #4: min: x =  1168, y = -928, z =  -16; max: x = 1192, y = -880, z =   16
Model #5: min: x =  1184, y = -960, z =  -48; max: x = 1200, y = -848, z =   48
Model #6: min: x =  -576, y = -496, z =  -40; max: x = -560, y = -400, z =   64
Model #7: min: x =  -520, y = -472, z =    0; max: x = -496, y = -424, z =   48

---------------------------------------------------------------------------

Appendix B. Table of normal vectors

This table is used in the Entity models to code the normal vector of each
vertex, in each frame (the lightnormalindex value).

Since it doesn't seem to be derived from a regular polygon, there is no
known formula to calculate it, so we can only list here all the values.

Take care to normalise all those vectors to 1, before using them.

To select the right vector from the list, just take the one whose dot
product with the actual normal vector of the vertex gives the greater
positive result. It's not too important that it differs a bit from the
actual normal vector of the vertex, Gouraud shading tollerates a fair bit
of imprecision.

vector_t normals[162]=
{{-0.5257,0.0000,0.8507},{-0.4429,0.2389,0.8642},{-0.2952,0.0000,0.9554},
 {-0.3090,0.5000,0.8090},{-0.1625,0.2629,0.9511},{0.0000,0.0000,1.0000},
 {0.0000,0.8507,0.5257},{-0.1476,0.7166,0.6817},{0.1476,0.7166,0.6817},
 {0.0000,0.5257,0.8507},{0.3090,0.5000,0.8090},{0.5257,0.0000,0.8507},
 {0.2952,0.0000,0.9554},{0.4429,0.2389,0.8642},{0.1625,0.2629,0.9511},
 {-0.6817,0.1476,0.7166},{-0.8090,0.3090,0.5000},{-0.5878,0.4253,0.6882},
 {-0.8507,0.5257,0.0000},{-0.8642,0.4429,0.2389},{-0.7166,0.6817,0.1476},
 {-0.6882,0.5878,0.4253},{-0.5000,0.8090,0.3090},{-0.2389,0.8642,0.4429},
 {-0.4253,0.6882,0.5878},{-0.7166,0.6817,-0.1476},{-0.5000,0.8090,-0.3090},
 {-0.5257,0.8507,0.0000},{0.0000,0.8507,-0.5257},{-0.2389,0.8642,-0.4429},
 {0.0000,0.9554,-0.2952},{-0.2629,0.9511,-0.1625},{0.0000,1.0000,0.0000},
 {0.0000,0.9554,0.2952},{-0.2629,0.9511,0.1625},{0.2389,0.8642,0.4429},
 {0.2629,0.9511,0.1625},{0.5000,0.8090,0.3090},{0.2389,0.8642,-0.4429},
 {0.2629,0.9511,-0.1625},{0.5000,0.8090,-0.3090},{0.8507,0.5257,0.0000},
 {0.7166,0.6817,0.1476},{0.7166,0.6817,-0.1476},{0.5257,0.8507,0.0000},
 {0.4253,0.6882,0.5878},{0.8642,0.4429,0.2389},{0.6882,0.5878,0.4253},
 {0.8090,0.3090,0.5000},{0.6817,0.1476,0.7166},{0.5878,0.4253,0.6882},
 {0.9554,0.2952,0.0000},{1.0000,0.0000,0.0000},{0.9511,0.1625,0.2629},
 {0.8507,-0.5257,0.0000},{0.9554,-0.2952,0.0000},{0.8642,-0.4429,0.2389},
 {0.9511,-0.1625,0.2629},{0.8090,-0.3090,0.5000},{0.6817,-0.1476,0.7166},
 {0.8507,0.0000,0.5257},{0.8642,0.4429,-0.2389},{0.8090,0.3090,-0.5000},
 {0.9511,0.1625,-0.2629},{0.5257,0.0000,-0.8507},{0.6817,0.1476,-0.7166},
 {0.6817,-0.1476,-0.7166},{0.8507,0.0000,-0.5257},{0.8090,-0.3090,-0.5000},
 {0.8642,-0.4429,-0.2389},{0.9511,-0.1625,-0.2629},{0.1476,0.7166,-0.6817},
 {0.3090,0.5000,-0.8090},{0.4253,0.6882,-0.5878},{0.4429,0.2389,-0.8642},
 {0.5878,0.4253,-0.6882},{0.6882,0.5878,-0.4253},{-0.1476,0.7166,-0.6817},
 {-0.3090,0.5000,-0.8090},{0.0000,0.5257,-0.8507},{-0.5257,0.0000,-0.8507},
 {-0.4429,0.2389,-0.8642},{-0.2952,0.0000,-0.9554},{-0.1625,0.2629,-0.9511},
 {0.0000,0.0000,-1.0000},{0.2952,0.0000,-0.9554},{0.1625,0.2629,-0.9511},
 {-0.4429,-0.2389,-0.8642},{-0.3090,-0.5000,-0.8090},{-0.1625,-0.2629,-0.9511},
 {0.0000,-0.8507,-0.5257},{-0.1476,-0.7166,-0.6817},{0.1476,-0.7166,-0.6817},
 {0.0000,-0.5257,-0.8507},{0.3090,-0.5000,-0.8090},{0.4429,-0.2389,-0.8642},
 {0.1625,-0.2629,-0.9511},{0.2389,-0.8642,-0.4429},{0.5000,-0.8090,-0.3090},
 {0.4253,-0.6882,-0.5878},{0.7166,-0.6817,-0.1476},{0.6882,-0.5878,-0.4253},
 {0.5878,-0.4253,-0.6882},{0.0000,-0.9554,-0.2952},{0.0000,-1.0000,0.0000},
 {0.2629,-0.9511,-0.1625},{0.0000,-0.8507,0.5257},{0.0000,-0.9554,0.2952},
 {0.2389,-0.8642,0.4429},{0.2629,-0.9511,0.1625},{0.5000,-0.8090,0.3090},
 {0.7166,-0.6817,0.1476},{0.5257,-0.8507,0.0000},{-0.2389,-0.8642,-0.4429},
 {-0.5000,-0.8090,-0.3090},{-0.2629,-0.9511,-0.1625},{-0.8507,-0.5257,0.0000},
 {-0.7166,-0.6817,-0.1476},{-0.7166,-0.6817,0.1476},{-0.5257,-0.8507,0.0000},
 {-0.5000,-0.8090,0.3090},{-0.2389,-0.8642,0.4429},{-0.2629,-0.9511,0.1625},
 {-0.8642,-0.4429,0.2389},{-0.8090,-0.3090,0.5000},{-0.6882,-0.5878,0.4253},
 {-0.6817,-0.1476,0.7166},{-0.4429,-0.2389,0.8642},{-0.5878,-0.4253,0.6882},
 {-0.3090,-0.5000,0.8090},{-0.1476,-0.7166,0.6817},{-0.4253,-0.6882,0.5878},
 {-0.1625,-0.2629,0.9511},{0.4429,-0.2389,0.8642},{0.1625,-0.2629,0.9511},
 {0.3090,-0.5000,0.8090},{0.1476,-0.7166,0.6817},{0.0000,-0.5257,0.8507},
 {0.4253,-0.6882,0.5878},{0.5878,-0.4253,0.6882},{0.6882,-0.5878,0.4253},
 {-0.9554,0.2952,0.0000},{-0.9511,0.1625,0.2629},{-1.0000,0.0000,0.0000},
 {-0.8507,0.0000,0.5257},{-0.9554,-0.2952,0.0000},{-0.9511,-0.1625,0.2629},
 {-0.8642,0.4429,-0.2389},{-0.9511,0.1625,-0.2629},{-0.8090,0.3090,-0.5000},
 {-0.8642,-0.4429,-0.2389},{-0.9511,-0.1625,-0.2629},{-0.8090,-0.3090,-0.5000},
 {-0.6817,0.1476,-0.7166},{-0.6817,-0.1476,-0.7166},{-0.8507,0.0000,-0.5257},
 {-0.6882,0.5878,-0.4253},{-0.5878,0.4253,-0.6882},{-0.4253,0.6882,-0.5878},
 {-0.4253,-0.6882,-0.5878},{-0.5878,-0.4253,-0.6882},{-0.6882,-0.5878,-0.4253}
};
