[Question] Detailed origins of the ZDBSP node lump formats

[elf-alchemist]

Hello.

In the past few months I've taken to doing some research for the Doomwiki.org, in order to document the known BSP tree lump formats the best I can. I ended up not only emailing Andrew Apted for information on the origins of the old GL nodes format with its separate GL_VERT, GL_SEGS, etc lumps, and also scouring 15/20+ years old threads on Doomworld for the rest, including the various versions of the old GL nodes, DeePBSPV4 nodes and the ZDBSP family of nodes (ZNOD/XNOD, ZGLN/XGLN, ZGL2/XGL2, ZGL3/XGL3).

Of all these formats, I've been able to find some implicit or explicit reasoning from the developers involved in their creation, as to their design choices. GL V1 nodes with their convex minisegs were made to even allow (most) hardware ports to work without holes on the ground in the first place, GL V2 was created to have higher precision coordinates, GL V3/V4/V5 were addressing the upper indexing limits of large maps, DeePBSPV4 nodes were also made to address large maps generating a massive amount of BSP tree elements -- however, there are some gaps in the development of the ZDBSP nodes that I could not 100% ascertain as to why they were designed the way they were, or the specifics issues or series of events that prompted their creation.

To be specific, the creation of the "X" uncompressed variants came about in mid-April 2010 because Andrey Budko saw issues with the idea of requiring Zlib as a hard dependency for PrBoom+, hence Graf Zahl adding XNOD and XGLN to ZDBSP and ZDoom shortly after -- all of this happening during the development of Sunder, having also inadvertently brought up the DeePBSPV4 format to light and both developers adding it to their respective ports. Meanwhile, ZGL2/XGL2 had come about because of UDMF maps proving to push the unsigned 16 bit integer limits that used to be the norm in the old binary map formats. Those parts are pretty clear from the known publicly available context. The issue comes when trying to understand ZNOD, ZGL3/XGL3 and to a lesser extended ZGLN.

I tried looking back on all the existing commits I could find for both ZDoom and ZDBSP on both the ZDBSP and UZDoom repositories on GitHub, but the oldest commits present, dating back to the first SVN revisions, already include both ZNOD and ZGLN support with no obvious set reasoning for it. And on the other hand, the addition of the ZGL3/XGL3 nodes is slightly more confusing, as the only difference between ZGL2/XGL2 and the aforementioned is that node partition lines are now 32bit fixed-point fractional instead of 16bit integer values. The increased precision of the partition line is justifiable on paper, moving away from lower precision math is something most ports do for rendering, and sometimes playsim code too, but I'm not yet sure why node partition lines specifically needed this treatment, the node lines' bounding boxes, for example, seemingly don't need it. I'm tempted to think that the use of higher precision math in the ZDoom family has caused some kind of bug that prompted the addition of the lump format's fixed-point value for the tree node lines.

Now the creation of ZNOD and XGLN is a bit more murky, I'm familiar with the fact that Marisa worked on ZETH before creating ZDBSP, and I'm making a pretty big assumption that ZNOD was created after the idea of fixed-point fractional vertex coordinates being a strict need as established by GL V2, but the detail that I'm certainly not sure about is what exactly prompted the design of lumps binary structure to be not only A) all stored sequentially in a single lump, separating the BSP-generated vertices from the main map vertices in the binary formats and also B) what event exactly prompted the creation of the format, addressing so many problems at once (mainly the fixed point vertices, 32 bit indexes, but also the storage space concerns). The other half of this coin is only half a mystery, why change the lump for the HW-friendly minisegs-based ZGLN to be stored in the SSECTORS lump, instead of NODES like it was for ZNOD? part of me wants to assume this was born out of a desire to separate a non-HW BSP tree from a HW-friendly BSP tree on different lumps, much like how glBSP's old "GL nodes" operated by being stored in their own separate lumps, and yet that's not the behavior seen in practice, as all supporting builders make sure that when writing out ZDBSP lumps, that they always leave all other BSP lumps empty, so that's an unlikely answer, but otherwise it is understandable that outputting the full HW-friendly BSP tree on top of the already pretty damn good ZNOD format makes sense.

So in the end, my question for Marisa would be: What prompted the creation and design of these lumps the way they were? As in what problems, exactly, did you encounter or foresee that justified pushing for them to even happen?

Here follows, to the best of my current asking-for-this-very-question knowledge, the complete history of the creation, design and adoption of the various BSP tree lump formats and the various sources for each in the few major, target ports I looked into. Most of these are source from one email exchange and various Git commits, SVN revisions & Doomworld threads. From a brief search on this forum, there's doesn't seem to be too many threads relevant to my way-too-specific question, mostly technical-issue-troubleshooting ones (at least those directly mentioning the formats by name). I'm also missing a handful of other details such as editor support in the Doom Builder lineage's "Nodes Viewer" tool, as well as some things regarding the console exclusive formats and support coming from the slightly less popular ports -- then again, not the main topic of this thread (though I'd still be happy to talk about anything in here!).

* 1999-09 — Andrew Apted starts working on glBSP and designing the earliest spec for GL nodes
* 2000-06 — releases EDGE, with support for GL nodes, rebuilding with internal builder if not present
* 2000-09-04 — Earliest SVN revision of glBSP, already contains V1 and V2 GL nodes
* 2003-09-24 — (from Marisa's devlog) adds support for ZNOD on ZDoom
* 2003-09-27 — (from Marisa's devlog) adds support for ZGLN on ZDoom
* 2004-04-30 — Deep (Jack) discusses on Doomworld the creation and design of a new node format
* 2004-07-13 — glBSP adds GL V3 nodes
* 2004-10-09 — DeePsea 11.92f (quietly) releases with DeePBSPV4 and GL V4 nodes support
* 2004-11-24 — Graf Zahl points out concerns over the limitations of the GL V3 spec, prompting the sharing of the GL V4 spec, and the later development of GL V5
* 2005-04-19 — Andrew Apted starts a discussion on the development of GL V5 nodes
* 2005-05-20 — glBSP adds GL V5 nodes
* 2005-05-20 — glBSP adds ZNOD support
* 2005-07-09 — GL V5 spec is publicly frozen
* 2006-02-24 — earliest SVN revision of ZDoom, already supports ZNOD and ZGLN nodes
* 2006-11-05 — Kaiser publishes the "Console Doom hacking project" thread, with the first description of the LEAFS lump
* 2009-03-17 — Marisa adds ZGL2 (with 32bit sidedef indexes to address large UDMF maps) to ZDoom/ZDBSP
* 2010-04-12 — Sunder's development unearths the DeePBSPV4 format and triggers a discussion for its wider adoption as well as the issues of the compressed ZDoom nodes
* 2010-04-15 — Andrey Budko adds DeePBSPV4 node support to PrBoom+
* 2010-04-17 — Graf adds DeePBSPV4 node support to ZDoom
* 2010-04-17 — Graf adds the uncompressed versions, XNOD, XGLN and XGL2, to ZDoom/ZDBSP
* 2010-04-18 — Andrey Budko adds support for XNOD
* 2012-12-07 — Marisa adds ZGL3 and XGL3 to ZDoom/ZDBSP, addressing coordinate precision on BSP nodes
* 2015-02-10 — Fabian adds support for DeePBSPV4, XNOD and ZNOD formats to Crispy-Doom
* 2016-11-30 — Apted adds XNOD support to Eureka
* 2019-06-14 — Fabian and Graf retroactively add ZNOD support to PrBoom+um
* 2019-10-20 — Apted adds XGL3 support to Eureka
* 2023-01-14 — Kraflab adds the reading of XGLN/ZGLN format in UDMF maps, without adding XGLN segs
* 2023-01-23 — Kraflab implements code for parsing XGLN/ZGLN Segs in DSDA
* 2023-01-23 — Roman Fomin adds DeePBSPV4, XNOD and ZNOD formats to Crispy-Heretic
* 2023-01-30 — Kraflab adds XGL2/ZGL2 and XGL3/ZGL3 support to DSDA, for UDMF maps and adds XGLN/2/3 node support to binary format maps
* 2026-04-01 — Elf-Alchemist adds all the remaining nodes to Crispy Doom, Heretic, Hexen and Strife

[randi]

Disclaimer: This is all stuff that happened over 20 years ago without any written record. You're relying strictly on what I can scrounge up in my memory.

@randi worked on ZETH before creating ZDBSP

Doom Wiki tells me I modified BSP for it too. I don't remember that at all, but I believe it. If it didn't support the Hexen map format, it wouldn't have been very useful. It really wasn't a progenitor for ZDBSP, though.

ZNOD was created after the idea of fixed-point fractional vertex coordinates being a strict need as established by GL V2

Was it? I don't remember the ordering of events, but I don't think that influenced me. What I remember is that there were no slime trails in MAP01 if I built nodes with the internal nodebuilder, and I worked out that it was because coordinates weren't truncated to integers.

I'm certainly not sure about is what exactly prompted the design of lumps binary structure to be not only A) all stored sequentially in a single lump, separating the BSP-generated vertices from the main map vertices in the binary formats and also B) what event exactly prompted the creation of the format, addressing so many problems at once (mainly the fixed point vertices, 32 bit indexes, but also the storage space concerns).

Okay, keep in mind that ZDBSP started life as ZDoom's internal nodebuilder for rebuilding maps when ZDoom needed to fix errors that would have prevented it from running certain maps. There were no original plans to make it an external tool, because why would you need to? Obviously, that decision changed at some point. Was it wanting a faster node builder for map editing, 32-bit vertex coordinates, being able to build nodes for larger maps that would have choked with the standard node format, or something else? Those all came into play, but I don't remember specifically how it got started.

The process for creating the node format was simple: I wanted to store the nodes on disk in a way that I could read them back into the engine and get the exact same results I would have gotten from the internal node builder with no compromises. Also, let's avoid wasting any space on things we don't need, like duplicating vertices that are already in the VERTEXES lump just to give them fraction bits that are all 0s. Hey! Can I actually make these smaller than standard nodes despite making them "better"? I like to save space. (I grew up around the Commodore 64 and Apple II, where you always need to be careful about how you use storage.) Oh, and since I'm already using zlib in ZDoom, let's compress them too, because there's a lot of repetitive data in here that should compress well. (Also, supposedly reading and decompressing data from a hard drive can be faster than straight up reading it uncompressed, though I never bothered to test that assertion for myself.)

Using a single lump was driven by my use of zlib to compress them, in fact. (At least, I think that's how it went down.) Using one stream means better compression overall, and the ZNOD equivalents of the existing BSP reading functions in ZDoom could just take the data stream as input and extract from it using the same code I already had for reading save games, picking up where the last function left off without any need to break it up into separate lumps.

ZDBSP only saved in this format automatically when it got nodes that were too big to work with vanilla Doom, so I wasn't concerned about needing to maintain compatibility with vanilla nodes. And if you used the command line option to force them, it was assumed that you were targeting ZDoom anyway. So because maintaining vanilla Doom compatibility wasn't a concern, I opted to put them where the regular nodes go instead of off in their own section like glBSP does. That way, other existing tools didn't need any changes to know anything about them to keep them together with their respective maps or to avoid stripping them when doing WAD processing.

why change the lump for the HW-friendly minisegs-based ZGLN to be stored in the SSECTORS lump, instead of NODES like it was for ZNOD? part of me wants to assume this was born out of a desire to separate a non-HW BSP tree from a HW-friendly BSP tree on different lumps

That's exactly it. GL nodes were added for ZDoomGL to use. ZDoom could ignore them and stick with the more efficient non-GL nodes until it eventually got the textured automap, which needs the GL nodes too. So you'd have a parallel set of nodes: standard nodes for ZDoom and GL nodes for ZDoomGL sitting next to them, analogous to the way glBSP nodes also don't replace the regular nodes.

all supporting builders make sure that when writing out ZDBSP lumps, that they always leave all other BSP lumps empty

ZDBSP only does this if you use the (until recently undocumented) -x option to exclusively build GL nodes. If you use -g, it builds both normal and GL nodes. (UDMF is an exception because Graf sensibly decided they should only have one set of nodes, and that's also where -x came from.)

the addition of the ZGL3/XGL3 nodes is slightly more confusing, as the only difference between ZGL2/XGL2 and the aforementioned is that node partition lines are now 32bit fixed-point fractional instead of 16bit integer values.

The set of splitters is chosen from the set of lines on a map. With UDMF, those lines can have fractional coordinates, hence, so too can the splitters.

the node lines' bounding boxes, for example, seemingly don't need it.

It hardly matters if a node's bounding box isn't exactly snug with its children by less than a full coordinate, so there's no need for them to have the extra precision. The bounding boxes are only used to quickly eliminate whole branches from the tree that aren't important for whatever traversal is happening.

Also, if you're thinking of ZGLN, ZGL2, ZGL3 as a procession of versions that superseded what came before, don't. They're all meant to be used equally, based on whatever is a best fit for the generated node data. There's no reason to choose ZGL3 just because it came last. The only reason to choose it should be because you gain something from using it.