DeePBSPV4 nodes
From DoomWiki.org
 | This article or section is a stub. Please help the Doom Wiki by adding to it. |
The DeePBSPV4 node format is an extension of the vanilla Doom node format.
It uses the same lumps as the original, NODES, SSECTORS and SEGS, though the binary structure itself is modified to support a greater number of elements in the BSP tree, by increasing index values from 16-bit integers to 32-bit integers—this generally increases the upper ceiling of total elements from 65536 to ~4.27 billion, or 32728 to ~2.14 billion.
However, this format does not address other limitations such as precision issues caused by the use of integer coordinates instead of fixed point coordinates.
Support[edit]
Due to the simplicity of this format, being mostly similar to that of the vanilla format, it has seen wide adoption in many actively developed engines. This includes the likes of Crispy Doom, PrBoom+, DSDA-Doom, Woof!, Doom Retro, Eternity Engine, Tartar, ZDoom, and UZDoom.
Historically, only the DeePBSP builder itself supported generating these structures. However, both VigilantBSP and ELFBSP would later go on to also adopt support for generating DeePBSPV4 format nodes.
Structure[edit]
Since the DeepBSPV4 node format does not change the lump order or structure of the map format, it is necessary to check the header of the NODES lump for the magic string "xNd4\0\0\0\0", or the byte sequence 0x784E643400000000. Such a combination which is normally impossible, or exceedingly unlikely, to be generated by any given node builder—that is to say, a partition line of length 0.
Nodes[edit]
Each node is 32 bytes long.
| Offset | Size (bytes) | C99 type | Description |
|---|---|---|---|
| 0 | 2 | int16_t | x coordinate of partition line start |
| 2 | 2 | int16_t | y coordinate of partition line start |
| 4 | 2 | int16_t | Change in x from start to end of partition line |
| 6 | 2 | int16_t | Change in y from start to end of partition line |
| 8 | 8 | int16_t [4] | Right bounding box |
| 16 | 8 | int16_t [4] | Left bounding box |
| 24 | 4 | int32_t | Right child |
| 28 | 4 | int32_t | Left child |
Subsectors[edit]
Each subsector is 6 bytes long.
| Offset | Size (bytes) | C99 type | Description |
|---|---|---|---|
| 0 | 2 | int16_t | Seg count |
| 2 | 4 | int32_t | First seg number |
Segments[edit]
Each segment is 16 bytes long.
| Offset | Size (bytes) | C99 type | Description |
|---|---|---|---|
| 0 | 4 | int32_t | Starting vertex number |
| 4 | 4 | int32_t | Ending vertex number |
| 8 | 2 | int16_t | Angle, full circle is -32768 to 32767 |
| 10 | 2 | int16_t | Linedef number |
| 12 | 2 | int16_t | Direction: 0 (same as linedef) or 1 (opposite of linedef) |
| 14 | 2 | int16_t | Offset: distance along linedef to start of seg |
Trivia[edit]
- While DeePBSPV4 nodes were designed as early as 2004, it was not until mid-April of 2010 when it saw wide adoption with support added in PrBoom+ and ZDoom, when the format was "rediscovered" during the development of Sunder.
- The creation of DeePBSPV4 happened alongside that of the GL V4 format.
See also[edit]
Sources[edit]
- Jack Vermeulen starts a discussion over the development of a new node format
- DeePsea 11.92f is released with support for DeePBSPV4 node format
- Andrey Budko unearths the node format, eventually leading to its wide adoption
- DeePBSP extended nodes specifications
