BSP (file format)

.BSP is a map file extension used in games such as the "Doom", "Quake", and games that use Quake-derived engines, such as the "Half-Life" series. .BSP files use binary space partitioning to generate levels that can be rendered quickly while minimizing the number of polygons that need to be redrawn every time the screen refreshes. One of the biggest problems with the .BSP file format is that large open areas do not work well due to the nature of the partitioning algorithm used.

Unlike the maps used in Unreal Tournament, .BSP files work by defining the edges of the map objects, as opposed to defining the hollow areas. .BSP files can be produced by compiling .MAP files using tools such as q3map2. .MAP files can be generated using exporters for such modelling tools as 3D Studio Max or using game-specific tools, like GtkRadiant. A .BSP file includes everything necessary to display the map, except the textures (with the exception of Quake and, optionally, Half-Life, BSP versions 29 and 30, respectively). Games such as Quake 3 and store the textures in separate assets files, contained in archive files such as .PAK, .PK3, .007, etc.

Lumps

Lumps are chunks of data, the offsets and lengths (in bytes) of which are defined in the file header, which may also contain the version of the BSP. The amount of lumps in a BSP differs from version to version, and the version used differs from game to game. For example, Quake II uses version 38 with 19 lumps, whereas uses version 42, with 18 lumps. For this reason, there are compatibility issues between games, and though conversion is possible, it is quite difficult.

Although the amount of lumps, and therefore their functions, changes from version to version, most versions of the BSP contain lumps with similar functions, and sometimes even have identical formats. These include:
* Entities – defines where objects such as weapons, enemies, etc. are placed, as well as containing the scripting information for AIs to follow, telling sounds to play, or even doors to open or close. They all are handled as a basic type called "entity".
* Planes – defines infinite planes, each one of which cuts the space it passes through into two spaces, hence binary space partitioning. The planes only divide the space within the node(s) that use them.
* Nodes – this lump simply makes use of the planes, and indexes the spaces created by them. If the index is positive, that space is partitioned further by one or more plane(s). If it's negative, it's indexed as a leaf.
* Leaves – These are the convex polygons that are the end result of the partitioning using planes. This lump defines what these polygons are made of (solid, liquid, empty, etc.), usually through use of another lump such as brushes. One major disadvantage of using this type of data structure, known as the BSP tree, is that concave polygons "cannot" be used, although they can be made out of convex polygons.
* Visibility – Since there can be a large number of leaves in a map, it could be quite costly for the hardware to redraw the entirety of them many times a second, because areas not seen would be drawn only to be overdrawn later. The visibility list reduces this by defining what is "potentially" visible to a player from a specific leaf. Since there can be a great number of leaves in a map, it is stored as a binary array, each bit defining whether any specific leaf is potentially visible or not (1 or 0, respectively), further RLE encoded. This method saves a great amount of space in temporary memory, as well as storage space of the map itself.
* Textures – this lump is a list of textures, which is indexed for ease of applying them to each individual leaf face.
* Faces – since leaves are many-sided polygons, any side, or faces, of that polygon can have a texture applied to it. This along with lighting effects, and other things that affect the look of the face is handled by this lump.
* Vertices and Meshes – These two lumps (or in some cases, one Meshverts lump) are used by faces to split textures into triangles for better application onto a face. These triangles don't necessarily have to be congruent, and this method is actually understandable. Triangles can be used to form any two-dimensional polygon.

Other lumps are used by different versions to manipulate these lumps in many ways, and can be used to get nearly, if not exactly, the same effect in any version of the BSP.

See also

* Binary space partitioning

External links

* [http://qxx.planetquake.gamespy.com/bsp/ BSP technical details for dummies]
* [http://www.gamers.org/dEngine/quake/spec/quake-spec34/qkspec_4.htm Quake 1/id Tech 1 BSP file format]
* [http://www.flipcode.com/archives/Quake_2_BSP_File_Format.shtml Quake 2/id Tech 2 BSP file format]
* [http://graphics.stanford.edu/~kekoa/q3/ Quake 3/id Tech 3 BSP file format]
* [http://www.geocities.com/cofrdrbob/bspformat.html Source Engine BSP file format]