ZDBSP nodes
From DoomWiki.org
 | This article or section is a stub. Please help the Doom Wiki by adding to it. |
The ZDBSP nodes, also known as ZDoom nodes, are a family of related formats created in the ZDBSP node builder to support maps with more geometry elements and larger BSP trees, as well as address precision issues which create slime trails. Additionally, there are also compressed variants of each format, aiming to reduce storage space needed for large levels.
These format are identified by their magic header signature, XNOD, XGLN, XGL2 and XGL3, as well as their zlib-compressed "Z"-variants, ZNOD, ZGLN, ZGL2 and ZGL3.
Contents
Single lump[edit]
When storing BSP tree data in any of the ZDBSP formats, all of the tree is contained within a single lump, leaving the other two BSP lumps empty.
The XNOD and ZNOD versions are stored in the NODES lump, leaving SSECTORS and SEGS empty. Meanwhile, all of XGLN, XGL2, XGL3, ZGLN, ZGL2 and ZGL3 are stored in the SSECTORS lump, leaving NODES and SEGS empty.
Compression[edit]
When encountering a compressed "Z"-variant, the supporting engine must decode all the bytes following the header as a zlib stream into their respective uncompressed "X"-variants internally, before proceeding with the remaining parsing of the binary data as if it were the uncompressed counterpart.
Hardware rendering[edit]
Starting with XGLN, the ZDBSP formats are required to met the strict polygonal requirements needed for subsectors to be strictly convex, by following the same rules as the GL nodes formats.
- The inclusion of "minisegs", segments which do not reference any linedef.
- All segments, both real and minisegs, in a given subsector are sorted along a clockwise orientation.
- Segments along double-sided linedefs are given a "partner" segment, that being the segment on the other side of the line.
Some hardware accelerated supporting engines may not be able to support XNOD, and may instead strictly require the hardware-friendly formats, XGLN, XGL2 or XGL3. This is the case for later versions of ZDoom and its descendant ports, which require support for the textured automap feature even in software rendering mode.
UDMF[edit]
While the base 1.1 UDMF specification does not strictly specify which format to use for the BSP tree, the ZDBSP formats have become the de-facto standard for all UDMF capable engines. The lump is expected to be named "ZNODES" and will be parsed just the same as any other binary map format.
Support[edit]
While, historically, the use of other formats (such as GL nodes) did not see widespread adoption, the ZDBSP nodes went on to be more widely supported by various engines.
|
|
Structure[edit]
Each format is based on the previous entry in the family, with respectively named changes below, i.e. XGLN is based on XNOD with some differences, XGL2 is based on XGLN and XGL3 is based on XGL2.
Vertex (XNOD)[edit]
ZDBSP separates the BSP-generated vertices, created from segment splitting during the node building process, from the main VERTEXES lump. This frees up the main lump to only store vertices associated with the main map geometry and not BSP data. ZDBSP's vertices are also in full 32 bits fixed point fractional coordinates, helping prevent many slime trails, compared to the regular and DeePBSPV4 node format. Each vertex is 8 bytes long.
| Offset | Size (bytes) | C99 type | Description |
|---|---|---|---|
| 0 | 4 | int32_t | x position |
| 4 | 4 | int32_t | y position |
Node (XNOD)[edit]
Nodes are mostly similar to the vanilla Doom format, however they are modified to support 32-bit indexes, instead of vanilla's 16-bit indexes. This removes the limit of nodes and subsectors, from 32767 each, to ~2.14 billion each. 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 |
Subsector (XNOD)[edit]
Subsectors no longer store a starting seg index, only the number of total segs per subsector. Segments are thus required to be strictly sorted, and starting indexes are read implicitly from this sorting. Each subsector is 4 bytes long.
| Offset | Size (bytes) | C99 type | Description |
|---|---|---|---|
| 0 | 4 | int32_t | Seg count |
Segment (XNOD)[edit]
Segments are significantly reduced from their vanilla counterpart. These no longer store angle or offset data, requiring the supporting engine to compute both at load time. Vertex indexing is now done via 32-bit integers, instead of vanilla's 16-bit indexes. Each segment is 11 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 | Linedef number |
| 10 | 1 | int8_t | Direction: 0 (same as linedef) or 1 (opposite of linedef) |
Segment (XGLN)[edit]
Starting with XGLN, minisegs are now included in the total list of segments stored in the BSP tree, due to this and the required subsector clockwise sorting, the second vertex can be easily implied from the starting vertex of the next segment in the respective subsector. Partner segs are also included. Each XGLN segment is 11 bytes long.
| Offset | Size (bytes) | C99 type | Description |
|---|---|---|---|
| 0 | 4 | int32_t | Starting vertex number |
| 4 | 4 | int32_t | Partner seg number |
| 8 | 2 | int16_t | Linedef number |
| 10 | 1 | int8_t | Direction: 0 (same as linedef) or 1 (opposite of linedef) |
Segment (XGL2)[edit]
The XGL2 format was devised shortly after the UDMF spec was finalized. Due to UDMF's support for more map elements than can fit in 16-bit integers, this was needed to increase the maximum supported number of linedefs in a map. Each XGL2 segment is 13 bytes long.
| Offset | Size (bytes) | C99 type | Description |
|---|---|---|---|
| 0 | 4 | int32_t | Starting vertex number |
| 4 | 4 | int32_t | Partner seg number |
| 8 | 4 | int32_t | Linedef number |
| 12 | 1 | int8_t | Direction: 0 (same as linedef) or 1 (opposite of linedef) |
Node (XGL3)[edit]
The XNOD nodes have been enhanced in the XGL3 format to support fractional coordinates for node partition lines, via 32-bit fixed point numbers. Each XGL3 node is 40 bytes long.
| Offset | Size (bytes) | C99 type | Description |
|---|---|---|---|
| 0 | 4 | int32_t | x coordinate of partition line start |
| 4 | 4 | int32_t | y coordinate of partition line start |
| 8 | 4 | int32_t | Change in x from start to end of partition line |
| 12 | 4 | int32_t | Change in y from start to end of partition line |
| 16 | 8 | int16_t [4] | Right bounding box |
| 24 | 8 | int16_t [4] | Left bounding box |
| 32 | 4 | int32_t | Right child |
| 36 | 4 | int32_t | Left child |
Formats overview[edit]
| XNOD | XGLN | XGL2 | XGL3 | |
|---|---|---|---|---|
| Magic header string | "XNOD" | "XGLN" | "XGL2" | "XGL3" |
| Magic header bytes | 0x584E4F44 | 0x58474C4E | 0x58474C32 | 0x58474C33 |
| Lump holding magic header | NODES | SSECTORS | SSECTORS | SSECTORS |
| Vertices | Vertex XNOD | Vertex XNOD | Vertex XNOD | Vertex XNOD |
| Nodes | Nodes XNOD | Nodes XNOD | Nodes XNOD | Nodes XGL3 |
| Subsectors | Subsectors XNOD | Subsectors XNOD | Subsectors XNOD | Subsectors XNOD |
| Segments | Segments XNOD | Segments XGLN | Segments XGL2 | Segments XGL2 |
Sequence[edit]
Due to the structural similarity between all formats listed above, it is common for implementing engines to parse ZDBSP nodes in a single multi-parsing function, or procedure, that selects the correct segment or node structure. Thus, apart from the decompression step, any implementing engine can internally treat these formats as simply different "versions".
The following is the structure sequence for the base XNOD format, actual byte sizes may differ on the later versions.
| Size | Type | Description |
|---|---|---|
| 4 | char[4] | Magic header ID, i.e "XNOD", "ZNOD", "XGLN", "ZGLN", etc |
| 4 | int32_t | Number of "old" vertices, from the main map geometry |
| 4 | int32_t | Number of "new" vertices, generated from splitting segs on the BSP tree |
| 8 * number of new vertices | Vertex (XNOD) | All "new" vertices |
| 4 | int32_t | Number of subsectors |
| 4 * number of subsectors | Subsector (XNOD) | All subsectors |
| 4 | int32_t | Number of segments |
| 11 * number of segment | Segment (XNOD) | All segments |
| 4 | int32_t | Number of nodes |
| 32 * number of nodes | Node (XNOD) | All nodes |
See also[edit]
External links[edit]
- ZDoom nodes specifications at the ZDoom wiki
