Quake 3 BSP Level File Layout
Author bkenwright@xbdev.net
The file format isn't that bad!...well it is if you don't know basic 3D
maths and things.
struct stLump
{
int fileofs;
int filelen;
};
struct stHeader
{
int id;
int ver;
stLump lumps[];
}; |
| Lump |
Name |
Information |
| 0 |
Entities |
All platforms, enemies, items, in a big
text lump |
| 1 |
Shader References |
Contains all texture information |
| 2 |
Planes |
All planes used in the level |
| 3 |
Nodes |
BSP tree nodes |
| 4 |
Leaves |
BSP tree leaves (contains convex object
information) |
| 5 |
Leaf Faces |
Faces of leaves (an index value to an
actual face) |
| 6 |
Leaf Brushes |
Brushes of leaves (not sure what they are
used for) |
| 7 |
Models |
All models stored within the level
(torches, teleporters, etc) |
| 8 |
Brushes |
Not too sure where they come in (but not
necessarally essential) |
| 9 |
Brush Sides |
Not too sure where they come in (but not
necessarally essential) |
| 10 |
Vertices |
All vertices used in the level |
| 11 |
Elements |
Once again, not sure, but not essential. |
| 12 |
Fog |
Fog related info. |
| 13 |
Faces |
All faces used in the level |
| 14 |
Lightmaps |
All the lightmaps used in the level |
| 15 |
Light Grid |
??? |
| 16 |
Visibility Lists |
PVS for any given leaf (PVS of all other
leaves) |
| 17 |
Number of Lumps |
The number of lumps (may be more than 18). |
|
Type Definitions:
typedef float Vector2[2];
typedef float Vector3[3];
typedef float Vector4[4];
typedef float TexCoord[2];
typedef int nBBox[6]; // Integer bounding box (mins, maxs)
typedef float fBBox[6]; // Float bounding box
| Lump 0 |
Entities |
| char * entities; // Null Terminated
String |
| Lump 0 |
Entities |
Lump 1
Shader References
struct stShaderRef
{
char name[64]; // Texture name
int surface_flags; // Type of surface (See Surface Flags below)
int content_flags; // Leaf content (See Content Flags below)
}; |
| Lump 0 |
Entities |
Lump 2
Planes
struct stPlane
{
vec3_t normal; // Normal vector for plane
float dist; // Distance from plane to origin
}; |
| Lump 0 |
Entities |
Lump 3
Nodes
struct stNode
{
int plane; // Space partitioning plane
int children[2]; // Back and front child nodes
bbox_t bbox; // Bounding box of node
} node_t; |
| Lump 0 |
Entities |
Lump 4
Leaves
struct stLeaf
{
int cluster; // Visibility cluster number
int area; // Volume of the leaf
bbox_t bbox; // Bounding box of leaf
int firstface, numfaces; // Lookup for the face list (indexes are for faces)
int firstbrush, numbrushes; // Lookup for the brush list (indexes are for
brushes)
}; |
| Lump 0 |
Entities |
Lump 5
Leaf Faces
int *lfaces; // a pointer to a series of indexes to a face list
|
| Lump 0 |
Entities |
Lump 6
Leaf Brushes
int *lbrushes; // a pointer to a series of indexes to a brush list |
| Lump 0 |
Entities |
Lump 7
Models
struct stModel
{
bboxf_t bbox; // Bounding box of model
int firstface, numfaces; // Lookup for the face list (indexes are for faces)
int firstbrush, numbrushes; // Lookup for the brush list (indexes are for
brushes)
};
|
| Lump 0 |
Entities |
Lump 8
Brushes
struct stBrush
{
int firstside, numsides;
int contents;
}; |
| Lump 0 |
Entities |
Lump 9
Brush Sides
struct stBrushside
{
int planenum; // Lookup for plane
int content;
}; |
| Lump 0 |
Entities |
Lump 10
Vertices
struct stVertex
{
vec3_t v_point; // World coordinates
texcoord_t tex_st; // Texture coordinates
texcoord_t lm_st; // Lightmap texture coordinates
vec3_t v_norm; // Normal vector (used for lighting ?)
colour_t colour; // Colour used for vertex lighting
}; |
| Lump 0 |
Entities |
Lump 11
Elements
int *elems;
|
| Lump 0 |
Entities |
Lump 12
Fog
Not much is known about this "fog".
|
| Lump 0 |
Entities |
Lump 13
Faces
struct stFace
{
int shader; // Refers to a shader
int unknown1; // Unknown
int facetype; // Type of Face
int firstvert, numverts; // Reference to vertices
int firstelem, numelems; // Reference to elements
int lm_texnum; // Lightmap texture info
int lm_offset[2]; // X,Y offset for lightmaps
int lm_size[2]; // Size of lightmap
vec3_t v_orig; // Face Origin
bboxf_t bbox; // Bounding box of face
vec3_t v_norm; // Face normal
int mesh_cp[2]; // ?
}; |
| Lump 0 |
Entities |
Lump 14
Lightmaps
unsigned char *lightmaps; // Lightmap data stored RGB
|
| Lump 0 |
Entities |
Lump 15
Light Grid
Unknown |
| Lump 0 |
Entities |
Lump 16
Visibility Lists
struct stVisibility
{
int numclusters;
int rowsize;
unsigned char data[1];
}; |
| Lump 0 |
Entities |
Lump 17
Number of Lumps |
Traversing the a Quake 3 BSP Tree Example.
Below is some pseudo c code to illustrate how you would traverse the BSP tree.
WalkTree(int NodeNr)
{
if (NodeNr < 0)
{
idx = ~NodeNr;
if (LeafIsVisible (idx))
{
for (i = 0; i
< leafs[idx].numfaces; i++)
{
Drawface ();
}
return;
}
if (ViewerInFront(NodeNr))
{
WalkTree(nodes[NodeNr].children[1]);
WalkTree(nodes[NodeNr].children[0]);
}
else
{
WalkTree(nodes[NodeNr].children[0]);
WalkTree(nodes[NodeNr].children[1]);
}
}
This roughly illustrates how the algorithm works. ViewerInFront would return
‘true’ if our position is in front of the split plane, and ‘false’ if it is
behind.
Collision Detection
There is a very simple way of performing collision detection. Simply find out
what leaf your position is in by traversing the BSP tree and advancing to the
child of the side of the node that your position is on. Once you reach a
terminal leaf, check the area of the leaf you are in if it is –1 then it is a
solid leaf (maybe a wall or floor, anything solid). Ideally, you would test the
position of where you plan to be at the end of the frame and not your current
position, for obvious reasons.
|
