Nightfire BSP Format

Jonathan Poncelet edited this page May 18, 2018 · 29 revisions

Nightfire BSP Format

Helpful Links

BSP File

Data is in little-endian format.

Header

Contains the BSP version, plus data about the offsets and lengths of all the other lumps in the file. Offsets are specified from the beginning of the file.

// Length: 8

struct Lump
{
  int Offset;
  int Length;
}

// Length: 148

struct Header
{
  int Version;
  Lump Entities;        // Lump 0
  Lump Planes;          // Lump 1
  Lump Textures;        // Lump 2
  Lump Materials;       // Lump 3
  Lump Vertices;        // Lump 4
  Lump ZeroVertices;    // Lump 5
  Lump DrawIndices;     // Lump 6
  Lump Visibility;      // Lump 7
  Lump Nodes;           // Lump 8
  Lump Surfaces;        // Lump 9
  Lump Lighting;        // Lump 10
  Lump Leaves;          // Lump 11
  Lump LeafSurfaces;    // Lump 12
  Lump LeafBrushes;     // Lump 13
  Lump Models;          // Lump 14
  Lump Brushes;         // Lump 15
  Lump BrushSides;      // Lump 16
  Lump Projections;     // Lump 17
}

0: Entities

This lump contains raw ASCII data and can be treated as a string, as per the length specified in the header. It is comprised of multiple keyvalue nodes, where the keyvalues for each entity are enclosed within a set of curly braces. For example:

{
"overbright" "192"
"MissionName" "austria"
"angles" "0 0 0"
"startdark" "1"
"sounds" "2"
"skycloudhigh_height" "1000"
"skycloudhigh_speed" "0.035  0.0029"
"skycloudlow_height" "800"
"skycloudlow_speed" "0.025  -0.0019"
"skyterrain" "Sky_terrain_Austria"
"skycloudlow" "Sky_lower_Austria"
"skydome" "Sky_dome_Austria"
"bsp_options" "-maxnodesize 2048"
"message" "M1_AUSTRIA04"
"MaxRange" "32767"
"skyname" "night_winter_"
"radfile" "m1_austria04.rad"
"rad_options" "-noslide -bounce 1 -chop 128 -smooth 75 -extra"
"vis_options" "-full"
"mapversion" "510"
"classname" "worldspawn"
}
{
"origin" "-112 4208 -96"
"_falloff" "2"
"angles" "-65 300 0"
"_light" "61 70 114 24"
"classname" "light_environment"
}

...

1: Planes

Planes correspond to world splits as computed by the BSP compilation stage of the map. They are used by Nodes (and indirectly by Leaves), Brush Sides and Surfaces.

The plane Type specifies which axis the normal lies along (or is closest to):

  • Values 0-2 specify that the plane is perfectly perpendicular to the X, Y or Z axis respectively.
  • Values 3-5 are similar, but mean that the plane is not exactly aligned perpendicular to an axis. A value of 3 means that the X axis is the largest magnitude component of the normal, and values 4 and 5 mean the same for Y and Z respectively.

Planes are specified in Hesse normal form, meaning they are described by a normal vector and a perpendicular distance from the origin. The point Distance * Normal lies on the plane, as do all other points p where dot(p, Normal) - Distance == 0.

// Length: 20

struct Plane
{
  float Normal[3];
  float Distance;
  int Type;
}

2: Textures

This lump holds texture path strings, which are referenced from the Surfaces property TextureIndex.

This lump implies that the full path to a texture (relative to the textures directory) can be no longer than 63 characters - the 64th character being the string's terminating null byte.

// Length: 64

struct Texture
{
  char[64] Path;
}

3: Materials

Holds rendering effects, eg. wld_lightmap or wld_fullbright. Used by Nightfire to specify things like envmapped glass, or other special effects.

// Length: 64

struct Material
{
  char[64] Path;
}

4: Vertices

Points in 3D space. Used for constructing faces in the map.

// Length: 12

struct Vertex
{
  float Point[3];
}

5: Zero Vertices

Matches Vertices in length but it is filled with null bytes. Reasons for its existence are currently unknown.

// Length: 12

struct ZeroVertex
{
  float Point[3];
}

6: Draw Indices

These are referenced by items in the Surfaces lump, corresponding to the DrawIndex property held by the item. Once a surface has retrieved its list of vertices from the Vertices lump, the draw indices will index this list. In order, the vertices indexed will build the trianges that form the surface.

// Length: 4

struct DrawIndex
{
  int TriangleCorner;
}

7: Visibility

For detailed information on how to interpret the visibility data format in traditional BSP files, see the Quake/Half-Life Visibility Data Format section.

The Nightfire visibility data is in a slightly different format to that described in the above section. The data is not run-length encoded, which makes interpreting it easier, but the size of each "record" is not necessarily minimal (ie. the floor of (numLeaves + 7) / 8). The size can be deduced by checking the lowest non-zero visibility offset in the leaves lump, as it does appear that all records are the same size. The extra padding on each record always appears to be zeroed, and it is suspected (but not confirmed) that rows are padded to be 4-byte aligned.

There is no vis record corresponding to leaf 0, and similarly no bits in any vis record represent visibility to leaf 0. This means that bit n represents whether or not the given leaf can see leaf n+1.

In the Leaves lump, leaf 0 is given a vis offset of zero. This should be ignored and treated as invalid.

8: Nodes

Each node represents one level in the BSP tree, corresponding to a planar split. It has two children that correspond to volumes either side of the split (if a node didn't have children it would be a leaf, and would belong in the Leaves lump).

The bounds here are assumed to encompass all children below this node in the tree.

// Length: 36

struct Node
{
  int PlaneIndex;
  int Child0; // negative numbers are -(leafs+1), not nodes
  int Child1;
  float Mins[3];
  float Maxs[3];
}

9: Surfaces

Describes an actual face (comprised of triangles) that is drawn in the map. VertexIndex indexes into the Vertices lump, and DrawIndex indexes into the Draw Indices lump. Each draw index is an index into the collection of vertices used by each item, between 0 and VertexCount - 1 inclusive.

It is assumed that all triangles on a surface lie exactly on the surface's plane, though it is not clear whether this is strictly required.

As a note, a surface has 3 * numLightStyles * X bytes of lightmap data. X depends on the lightmap density of the surface, and corresponds to the number of lightmap cells present. TODO: Perhaps provide a formula for this, when known? Is something to do with the surface extents.

Note that Nightfire surfaces can reference different textures while using the same texture projection. This is different to Half-Life, where a texture is tied to one projection (texinfo) only.

Note that unlike Half Life BSPs, Nightfire surfaces have independent projections for their texture and lightmap. This also means that multiple faces can reference the same projection, and that in theory the same projection could be used for both a texture and a lightmap. See the Projections lump for more information.

// Length: 48

struct Surface
{
  int PlaneIndex;
  int VertexIndex;
  int VertexCount;
  int DrawIndex;
  int DrawCount;
  unsigned int Flags;
  int TextureIndex;
  int MaterialIndex;
  int TextureProjection;
  int LightmapProjection;
  unsigned char Styles[4];  // TODO: Signed or unsigned? Suspected unsigned.
  int LightingOffset;
}

10: Lighting

Lighting data is essentially an RGB bitmap. It is indexed by Surfaces via their LightingOffset member, and beginning from this offset the face's lightmaps are stored consecutively. The number of lightmaps corresponds to the number of valid light styles the face has, and the dimensions of each lightmap are the same.

TODO: Need more information on how to calculate the dimensions of a lightmap. The calculations are related to the lightmap projection used by the face, and the real-world extents of the face itself.

// Length: 3

struct Lighting
{
  unsigned char RGB[3];
}

11: Leaves

This is a leaf in the BSP tree - a volume that is not subdivided further, so has no children. Each leaf references Leaf Surfaces and Leaf Brushes.

The leaf type in Nightfire appears to only ever be 1 or 2. 1 is an empty leaf, where the player can enter the leaf and where surfaces may be referenced for drawing. 2 is a solid leaf, which references no surfaces.

// Length: 48

struct Leaf
{
  int Type;
  int VisibilityOffset; // Offset into the Visibility lump for vis data.
  float Mins[3];
  float Maxs[3];
  int LeafSurfacesIndex;
  int LeafSurfacesCount;
  int LeafBrushesIndex;
  int LeafBrushesCount;
}

12: Leaf Surfaces

Indexes into the Surfaces lump. Each leaf references a block of leaf surfaces, which when read as a list provide all the surfaces that should be rendered from within the leaf.

// Length: 4

struct LeafSurface
{
  int SurfaceIndex;
}

13: Leaf Brushes

Indexed by Leaves. Each item indexes into the Brushes lump. TODO: Confirm.

// Length: 4

struct LeafBrush
{
  int BrushIndex;
}

14: Models

Defines a brush model within the map. The surfaces of the brush model must be consecutive in the surfaces lump, as unlike leaves there is no indirection lump to allow lists of random surfaces to be specified. This is OK - since brush models do not block visibility or form part of the immutable BSP tree, they do not need to adhere to the same structure as BSP surfaces.

Model 0 is the world; other models are brush entities.

Based on the Half Life map format, the array of 4 integers in the middle of the Model structure is suspected to be hulls. Hull indices in Nightfire maps are apparently always zero.

Unlike Half Life, Nightfire brush models also include extra information about the Brushes they reference (see Brushes and BrushSides). This information includes attributes about each of the brushes (TODO: what actually are these?), as well as texture indices and plane indices for each of the sides of a brush.

// Length: 56

struct Model
{
  float Mins[3];
  float Maxs[3];
  int Hulls[4];
  int BrushesIndex;
  int BrushesCount;
  int SurfacesIndex;
  int SurfacesCount;
}

15: Brushes

Defines a brush within the map. TODO: More information required.

// Length: 12

struct Brush
{
  int Attributes;   // What are these?
  int SidesIndex;
  int SidesCount;
}

16: BrushSides

Defines a side used by one (or more?) brushes. Each brush side corresponds to a plane in the Planes lump, and a shader from the Shaders lump.

// Length: 8

struct BrushSide
{
  int TextureIndex;
  int PlaneIndex; // Positive plane side faces out of the leaf
}

17: Projections

Defines a projection onto a face. These are used for both textures and lightmaps, as Nightfire allows a surface's lightmap grid to be rotated and scaled.

The projection is defined by two four-component vectors S and T. The first three components specify the axis in 3D space, and the fourth component specifies the translation of the texture along this axis.

TODO: Is this the texture translation or the face translation (in other words, which way is positive and which is negative)?

Note that Nightfire surfaces can reference different textures while using the same texture projection. This is different to Half-Life, where a texture is tied to one projection (texinfo) only.

// Length: 32

struct Projection
{ 
  float S[4];
  float T[4];
}

Indexing Lumps

Models         Index into: Brushes
                           Surfaces

Leaves         Index into: Leaf Surfaces
                           Leaf Brushes
                           Visibility

Brushes        Index into: Brush Sides

Leaf Surfaces  Index into: Surfaces

Leaf Brushes   Index into: Brushes

Brush Sides    Index into: Planes

Nodes          Index into: Planes
                           Leaves

Surfaces       Index into: Planes
                           Draw Indices
                           Materials
                           Textures
                           Vertices
                           Lighting
                           Projections
                           
Planes         Index into: None

Draw Indices   Index into: None

Materials      Index into: None

Textures       Index into: None

Vertices       Index into: None

Lighting       Index into: None

Projections    Index into: None

Entities       Index into: None

Visibility     Index into: None

Comparison between GoldSrc (v30) and Nightfire (v42) BSP lumps

GoldSrc (v30)       Nightfire (v42) Equivalent

(0)  Entities       (0)  Entities
(1)  Planes         (1)  Planes
(2)  Textures       (2)  Textures
(3)  Vertices       (4)  Vertices
(4)  Visibility     (7)  Visibility
(5)  Nodes          (8)  Nodes
(6)  Tex Info       (17) Projections
(7)  Faces          (9)  Surfaces
(8)  Lighting       (10) Lighting
(9)  Clip Nodes     (*)
(10) Leaves         (11) Leaves
(11) Mark Surfaces  (12) Leaf Surfaces
(12) Edges          (*)
(13) Surf Edges     (*)
(14) Models         (14) Models
(*)                 (3)  Materials
(*)                 (5)  Zero Vertices
(*)                 (6)  Draw Indices
(*)                 (13) Leaf Brushes
(*)                 (15) Brushes
(*)                 (16) Brush Sides

Drawing Triangles

The following gives an overview on how vertices, edges and faces are structured in a Half-Life BSP file:

Leaf
- Marksurfaces: index + count

Marksurface
- Single index into Faces

Face
- Surfedges: index + count

Surfedge
- Single index into Edges

Edge
- Two indices into Vertices

Vertex
- A point in space

The reason this structure exists is that vertices, edges and faces must be shared between items that reference them. For example, multiple faces may share the same edge, so rather than duplicating that edge's data in every face that references it, the edge is given an index. Faces can then refer to each edge by index, which only amounts to keeping a list of integers, rather than re-specifying each edge and thereby duplicating its data.

However, the one complication this introduces is that the amount of data that must be stored in a face is no longer uniform. A face made of three edges needs to store a list of three indices, and a face made of eight edges needs to store eight indices. To remedy this, the list of indices for each face is factored out into the Surfedges lump. Each face then only needs to store an offset and a count for its list of indices, keeping the size of each face item uniform.

The same concept applies for marksurfaces, which amount to a list of face indices that are used by each leaf.

Nightfire BSPs use a slightly different system to Half-Life BSPs: instead of using surfedges, each face contains an offset and count for the Draw Indices lump. Rather than storing edge information explicitly, each face just has a direct list of vertices that are used for drawing triangles.

Edge information can be calculated by iterating over all faces in the map, and keeping a hash table mapping a (vertex, vertex) pair to an index. Each vertex pair becomes an edge, and each index is used in a surfedge item for that edge. A Nightfire face with six draw indices (forming two triangles) corresponds to a Half-Life face with six surfedges, and utilises up to six unique edges in the Edges lump (five if the triangles share an edge).

Quake/Half-Life Visibility Data Format

The Visibility lump has the most complex structure of all the lumps. Each leaf in the Leaves lump holds an offset into the Visibility lump, and the data beginning from this offset is a bit array concerning which other leaves the given leaf can see.

For a bit n in the bit array, the given leaf:

  • Can see leaf n if bit n is 1.
  • Cannot see leaf n if bit n is 0.

For example, this bit array of 8 leaves:

01100000

implies that our given leaf can only see two other leaves - 1 and 2 - out of all leaves 0-7.

It should be noted that for any given leaf n, bit n should always be 1, as a leaf can always see itself. (If it were 0, the leaf would not be drawn when the player stands inside it.)

Since every leaf needs to store a bit corresponding to every other leaf, there are n^2 bits required to store information about n leaves. This gets large quickly. For example, m1_austria04, Nightfire's smallest map, has 1065 leaves; this equates to 1065 * 1065 = 1134225 bits, or 138KB, of raw visibility data in total.

To help reduce the amount of space required to store the visibility data, the data is run-length encoded. This takes advantage of the assumption that, on the whole, any given leaf should only be able to see a small fraction of the total number of leaves in the map. Because of this, we should expect that the vast majority of bits in each leaf's bit array will be zero. If these zeroes are run-length encoded, the amount of space required to store the visibility data can be significantly reduced.

Because bytes are the smallest units of memory a computer can process at a time, run-length encoding only works for zero bytes - ie., bytes where all eight of their bits are zeroes. The rule is that, if a zero byte is encountered within the visibility data, the following byte will always specify the run length of zero bytes. This secondary byte will never itself be zero. This means that a run of up to 255 consecutive zero bytes can be encoded in the visibility data using just two bytes - one original zero, and one specifying the run length.

Note that if even one bit in a given byte is not zero, the data cannot be run-length encoded. For example, the following raw data:

         |          Run of 4 bytes         |
01100000 00000000 00000000 00000000 00000000 00000001 10000000 10011010
	(60 00 00 00 00 01 80 9A) - 8 bytes

is run-length encoded to:

         | Zero    Count                   |
01100000 00000000 00000100 -------- -------- 00000001 10000000 10011010
	(60 00 04 01 80 9A) - 6 bytes

The following pseudo-C++ demonstrates how to interpret the visibility data:

// Assuming these are all initialised:
unsigned char* visLumpData = ... ;	// Raw vis data read in.
int visLumpDataLength = ... ;		// Length of the data.
int totalLeaves = ... ;				// Total number of leaves in the map.
Leaf ourLeaf = ... ;				// The leaf we're processing.

// We begin from the offset specified by ourLeaf.
int dataOffset = ourLeaf.visibilityOffset;

// Let's assume that leafVisibility is an object to keep track
// of the visibility of all other leaves, from the point of view
// of ourLeaf.
// Eg. you could ask whether a given leaf is visible by calling:
//
//     bool visible = leafVisibility.isLeafVisible(leafNumber);

// By default, leaves should not be considered visible.
leafVisibility.setAllLeavesNotVisible();

// Walk over the bit array.
int leafToCheck = 0;
while (leafToCheck < totalLeaves && dataOffset < visLumpDataLength)
{
	// Is there a run of zero bytes?
	if (visLumpData[dataOffset] == 0)
	{
		// Make sure we don't overrun.
		// If the BSP is written properly, this shouldn't happen.
		if (dataOffset + 1 >= visLumpDataLength)
		{
			break;
		}

		// Find out from the next byte how long it is.
		unsigned char runLength = visLumpData[currentOffset + 1];

		// We know that there will be runLength * 8 bits that are zero
		// in this run of zero bytes, therefore we can skip that many
		// leaves and leave them as not visible. (Remember, we marked
		// all leaves as not visible before we began.)
		leafToCheck += runLength * 8;

		// Skip past the 2 bytes denoting the run.
		dataOffset += 2;

		// Go round again.
		continue;
	}

	// There's at least one bit in this byte that's not zero.
	// Process all bits and record visibility information.
	for (int bit = 0; bit < 8; ++bit)
	{
		// Create a mask for the bit we're checking.
		unsigned char mask = 1 << bit;

		// See if there's any data at that bit.
		if (visLumpData[dataOffset] & mask)
		{
			// Mark the current leaf as visible.
			leafVisibility.markLeafAsVisible(leafToCheck, true);
		}

		// Record that we checked the leaf.
		++leafToCheck;
	}
}
You can’t perform that action at this time.
You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session.
Press h to open a hovercard with more details.