www.xbdev.net xbdev - software development
Tuesday July 23, 2019
home | about | contact | Donations

     
 

3D File Formats

The bits and bytes...

 

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.
 

 







 

 
 Visitor: 9534626  { 209.237.238.175 } Copyright (c) 2002-2017 xbdev.net - All rights reserved.
Designated tutorial and software are the property of their respective owners.