Binary Space Partition - Version 42

From NFBSP

Contents 1 Header 2 Entities 3 Planes 4 Textures 5 Materials 6 Vertices 7 Normals 8 Draw Indices 8.1 Explaination of Draw Indicies 9 Visibility 9.1 Explaination of Visibility 10 Nodes 11 Surfaces 12 Lighting 13 Leaves 14 Leaf Surfaces 15 Leaf Brushes 16 Models 17 Brushes 18 Brush Sides 19 Texture Matrix 19.1 Explanation of Texture Maps 19.2 Method of reading Texture Maps 20 See also

Header

struct Header { // Length: 148 
  int Version;
  int EntitiesOffset;
  int EntitiesLength;
  int PlanesOffset;
  int PlanesLength;
  int TexturesOffset;
  int TexturesLength;
  int MaterialsOffset;
  int MaterialsLength;
  int VerticesOffset;
  int VerticesLength;
  int NormalsOffset;
  int NormalsLength;
  int DrawIndicesOffset;
  int DrawIndicesLength;
  int VisibilityOffset;
  int VisibilityLength;
  int NodesOffset;
  int NodesLength;
  int SurfacesOffset;
  int SurfacesLength;
  int LightingOffset;
  int LightingLength;
  int LeavesOffset;
  int LeavesLength;
  int LeafSurfacesOffset;
  int LeafSurfacesLength;
  int LeafBrushesOffset;
  int LeafBrushesLength;
  int ModelsOffset;
  int ModelsLength;
  int BrushesOffset;
  int BrushesLength;
  int BrushSidesOffset;
  int BrushSidesLength;
  int TextureMatrixOffset;
  int TextureMatrixLength;
}

Entities

The only pure ASCII portion of the BSP. It has no associated structure and can simply be treated as a string according to the length specified in the header. For a list of classnames that may be found in this lump, see the List of Entities by name or type.

Planes

The plane 'Type' associates the plane with the axis parallel to it's normal. Non-axial planes are snapped to nearest ('_any').

struct Plane { // Length: 20 
  float NormalX;
  float NormalY;
  float NormalZ;
  float Distance;
  int Type; // plane_x 0, plane_y 1, plane_z 2, plane_anyx 3, plane_anyy 4, plane_anyz 5 
}

Textures

struct Texture { // Length: 64 
  byte[64] Texture;
}

Materials

struct Material { // Length: 64 
  byte[64] Name;
}

Vertices

struct Vertex { // Length: 12 
  float X;
  float Y;
  float Z;
}

Normals

A normal for each vertex found in vertices. Apparently filled with null bytes. Possibly unused?

struct Normal { // Length: 12 
  float X;
  float Y;
  float Z;
}

Draw Indices

struct DrawIndex { // Length: 4 
  int TriangleCorner;
}

Explaination of Draw Indicies

A row from Faces:

6B1D 0000 AEE7 0000 0400 0000 F854 0100 0600 0000 0000 0000 3300 0000 0000 0000 D74E 0000 1300 0000 00FF FFFF 68A5 1900
                  a         b         c         d

a = 59310 (vert index)
b = 4     (vert count)
c = 87288 (draw indices index)
d = 6     (draw indices count)

To convert index to offset, we take the index number times size of each item. For verts, it is 12; for draw indices, it is 4.

59310 * 12 = 711720
87288 * 4 = 349152

Data from verts lump:
 0000 F044 0000 C8C2 0000 4042
 0080 EE44 0000 C8C2 0000 4042
 0080 EE44 0000 C8C2 0000 A042
 0000 F044 0000 C8C2 0000 A042

Data from draw indices lump:
 0000 0000
 0100 0000
 0200 0000
 0000 0000
 0200 0000
 0300 0000

Now, lets assume that the verts are loaded into an array using default key numbers. All array keys start from zero.

Key  Hex data stored in the array 
  0  0000 F044 0000 C8C2 0000 4042 
  1  0080 EE44 0000 C8C2 0000 4042 
  2  0080 EE44 0000 C8C2 0000 A042 
  3  0000 F044 0000 C8C2 0000 A042 

Now, since it loaded 6 points, that means it is forming 2 triangles using slightly varying verts.

Draw indicies are just key values. When it says 0, it is loading the data stored at key 0 which in this example is 0000 F044 0000 C8C2 0000 4042.

Key  Raw Hex                        Ordered Pairs 
 
First Triangle: 
  0  0000 F044 0000 C8C2 0000 4042  (1920, -100, 48) 
  1  0080 EE44 0000 C8C2 0000 4042  (1908, -100, 48) 
  2  0080 EE44 0000 C8C2 0000 A042  (1908, -100, 80) 
 
Second Triangle: 
  0  0000 F044 0000 C8C2 0000 4042  (1920, -100, 48) 
  2  0080 EE44 0000 C8C2 0000 A042  (1908, -100, 80) 
  3  0000 F044 0000 C8C2 0000 A042  (1920, -100, 80) 

These two triangles form a square. It is easy to see that these triangles only have two varying dimensions, making them two-dimensional.

Though most sets have two triangles, they do NOT have to fit together to make a square. They can make any geometric shape that two triangles can make. Also, two or more sets of meshes can be used together to make more complex shapes.

Visibility

struct Visibility { // Length:? 
  // Unknown 
}

Explaination of Visibility

Leaves are grouped into clusters for the purpose of storing the visibility information. This is to conserve space in the PVS since it's likely that nearby leaves will have similar potentially visible areas. The visibility lump contains an array of bsp_vis_offset structures with the same number of elements as there are clusters. The bsp_vis_offset structure format is:

struct bsp_vis_offset { 
  uint32 pvs; // offset (in bytes) from the beginning of the visibility lump
  uint32 phs; // ?
}

The rest of the visibility lump is the actual visibility information. For every cluster the visibility state (either visible or occluded) is stored for every other cluster in the world. Clusters are always visible from within themselves. Because this is such a massive amount of data, this array is stored as a bit vector (one bit per element) and 0's are run-length-encoded. Here's an example of a C-routine to decompress the PVS into a byte array (this was adapted from the "Quake Specifications" document):

int v = offset;
memset(cluster_visible, 0, num_clusters);
for (int c = 0; c < num_clusters; v++) {
  if (pvs_buffer[v] == 0) {
    v++;
    c += 8 * pvs_buffer[v];
  } else {
    for (buint8 bit = 1; bit != 0; bit *= 2, c++) {
      if (pvs_buffer[v] & bit) {
        cluster_visible[c] = 1;
      }
    }
  }
}

Nodes

struct Node { // Length: 36 
  int PlaneIndex;
  int Child0; // negative numbers are -(leafs+1), not nodes
  int Child1;
  float MinX;
  float MinY;
  float MinZ;
  float MaxX;
  float MaxY;
  float MaxZ;
}

Surfaces

struct Surface { // Length: 48 
  int PlaneIndex;
  int VertexIndex;
  int VertexCount;
  int DrawIndex;
  int DrawCount;
  SurfaceFlags Flags;
  int TextureIndex;
  int MaterialIndex;
  int TexMatrixIndex;
  int FogIndex;
  sbyte[] Styles = new sbyte[4]; // #define MAXLIGHTMAPS 4
  int LightingOffset; // start of [numstyles * ? * 3] samples
}

Lighting

struct Lighting { // Length: 3 
  byte Red;
  byte Green;
  byte Blue;
}

Leaves

struct Leaf { // Length: 48 
  int Type; // 1 loads face and brush information, 2 does not.
  int VisibilityOffset;
  float MinX;
  float MinY;
  float MinZ;
  float MaxX;
  float MaxY;
  float MaxZ;
  int LeafSurfacesIndex;
  int LeafSurfacesCount;
  int LeafBrushesIndex;
  int LeafBrushesCount;
}

Leaf Surfaces

struct LeafSurface { // Length: 4 
  int SurfaceIndex;
}

Leaf Brushes

struct LeafBrush { // Length: 4 
  int BrushIndex;
}

Models

struct Model { // Length: 56 
  float MinX;
  float MinY;
  float MinZ;
  float MaxX;
  float MaxY;
  float MaxZ;
  int Unknown0; // null
  int Unknown1; // null
  int Unknown2; // null
  int Unknown3; // null
  int LeavesIndex;
  int LeavesCount;
  int SurfacesIndex;
  int SurfacesCount;
}

Brushes

struct Brush { // Length: 12 
  int Attributes;
  int SidesIndex;
  int SidesCount;
}

Brush Sides

struct BrushSide { // Length: 8 
  int SurfaceIndex;
  int PlaneIndex; // positive plane side faces out of the leaf
}

Texture Matrix

struct TexMatrix { // Length: 32 
  float SX;
  float SY;
  float SZ;
  float SShift;
  float TX;
  float TY;
  float TZ;
  float TShift;
}

Explanation of Texture Maps

The texture map is split in to two components, S and T, which define the texture plane. These components provide the two dimensions along which the texture can be applied to the face. The vectors given by S and T are always necessarily at right-angles (so as to provide 2 independent dimensions). The length of the S and T vectors are the inverse of the texture scale along that direction. Rotation merely rotates the vectors about their common normal (they remain part of the same plane as before), whilst keeping their length constant. One way to understand this would be to imagine that the texture starts at the world origin (0, 0, 0) and extends along the plane defined by the S and T vectors from the origin. From any point on the surface of the brush, the normal of that side is projected on to this plane, to determine the part of the texture shown on that part of the side. The plane equation Intersect = (0, 0, 0) + u(SX, SY, SZ) - v(TX, TY, TZ) can use the co-ordinates of intercept with the normal of a brush side corner, giving values for u and v for that vertex. These can be multiplied by the squares of the lengths of S and T respectively, then added to the SShift and TShift respectively, and then divided by the width and height respectively of the image, to obtain the U V coordinates (used in the MDL & SMD file formats). (This is shown in more detail below.)

Method of reading Texture Maps

By vector methods, we can convert these to a 'UV' coordinate system like that in the MDL format, where each vertex has its own coordinates on the texture. Firstly, the normal of the two vectors must be found (the cross product).

int32[3] vecS; // { SX, SY, SZ }
int32[3] vecT; // { TX, TY, TZ }
int32[3] norm;
norm[0] = (vecS[1] * vecT[2]) - (vecS[2] * vecT[1]);
norm[1] = (vecT[0] * vecS[2]) - (vecT[2] * vecS[0]);
norm[2] = (vecS[0] * vecT[1]) - (vecS[1] * vecT[0]);

Now, if the location of the point on the surface we wish to read the texture for is x, y, z, we can create an equation of vectors. We know that the plane PI, defined by S and T and which passes through (0, 0, 0), has the equation PI = u(SX, SY, SZ) - v(TX, TY, TZ), where u and v are variables. This equation will equal the coordinates of any point on the plane (if we replace the left-side with a set of 3d coordinates). This will then lead to: The position of the corner point of the side, plus a* the side normal, equals a point on the plane or:

[x, y, z] + a*norm = u*vecS - v*vecT, where a, u and v are variables.

With this system, the values of a, u and v can be found using a matrix operation. The math is shown below.

Position + a*Normal = u*vecS - v*vecT (: a point on the plane which passes through 0, 0, 0)
Position = u*vecS - v*vecT - a*Normal (now turn this in to a 3x3 matrix and 3x1 matrix of variables)
Position = 
 * Position = 

Using mathematical methods, this system can be solved and the values of u and v obtained. It is then possible to convert them in to the U and V values used in the MDL file structure, by multiplying the u and v values by the lengths of the squares of the S and T vectors respectively, then adding the S and T shifts respectively, and dividing by the width and height of the image respectively. This is shown below.

float utemp; // 'u' solution to the above matrix equation.
float vtemp; // 'v' solution to the above matrix equation.
int32 width; // Image width
int32 height; // Image height
float lengthS = Math.Sqrt((vecS[0] * vecS[0]) + (vecS[1] * vecS[1]) + (vecS[2] * vecS[2]));
float lengthT = Math.Sqrt((vecT[0] * vecT[0]) + (vecT[1] * vecT[1]) + (vecT[2] * vecT[2]));
float U;
float V;
U = (utemp * Math.Pow(lengthS, 2) + SShift) / width;
V = (vtemp * Math.Pow(lengthT, 2) + TShift) / height;

See also

• Quake 2 BSP Format