Node builder

Doom level format
Things Linedefs Sidedefs Vertices Segs Subsectors Nodes Sectors Reject Blockmap
Extensions: ACS Behavior Leafs Lights Macros Floors
Source port extensions: Extended nodes FraggleScript ExtraData Dialogue Lightmap

A node builder is a WAD authoring tool.

The VERTEXES, LINEDEFS, SIDEDEFS, and SECTORS lumps fully describe the structure of a map, and it is relatively straightforward for a level editor to create them. However, for rapid rendering and game simulation, the Doom engine needs information on how these structures interrelate. Depending on the algorithm and level of complexity, the binary space partition of the map, the REJECT data and the BLOCKMAP can take a long time to generate.

Using the basic lumps, a node builder creates the NODES, SEGS, SSECTORS, REJECT and BLOCKMAP lumps, and will also create additional vertices, normally appended to the VERTEXES lump. Having these structures precalculated and stored in the WAD file, rather than determining them at run time, is key to the speed of the engine.

The node builder used by id Software is called DoomBSP, but often referenced as idbsp due to an early port of the source code being called this.

The process of node building is described in some detail in the Unofficial Doom Specs. As detailed in that document, many different partitions of a level are possible, because the choice of partition lines is somewhat arbitrary. There are two competing goals when creating the BSP tree: to have a balanced tree (having about the same number of subnodes on each side) and to minimize the number of splits (breaking linedefs into multiple segs). Thus, different node builders will likely produce different results for a given level.

Hardware rendering

Hardware renderers have additional requirements for the BSP tree that the software renderers can ignore, as they are much stricter on their need for subsectors to be strictly convex, and coordinates precision is also important.

There a few commonly used techniques to help ports meet these strict polygonal requirements:

• The LEAFS lump provides additional, pre-computed information about vertices and segments associated with each subsector—without modifying the existing BSP tree data.
• The FLOOR series of lumps were used in the Nintendo 64 port of Hexen to generate a complete set of triangles for each sector in any given level.
• Some of the extended BSP formats provide "minisegs", additional dummy segments which are not associated to any linedef or sidedef. When combined with "real" segments, and strict clockwise angle sorting, they ensure subsectors are guaranteed to be fully convex polygons.
• If no additional data structure is provided, it is still possible for engines themselves to generate their own convex subsectors internally from existing BSP tree data, via polygon triangulation techniques.

These "hardware friendly", or "GL friendly", formats, while enabling hardware renderers to work properly with the BSP tree, do not necessarily hinder the functionality of software renderers—with the caveat that minisegs must be ignored, or removed, by the engine where applicable.

List of node builders

Operating system support across node builders

	DOS	Windows	Macintosh	*nix	OS/2	First release	Last updated
AJBSP	No	Yes	No	Yes	No	2018-06-02	2023-04-19
BSP	Yes	Yes	No	Yes	Yes	1994-03-28	2006-08-12
BSPCOMP	Yes	No	No	No	No	1995-11-13	1995-11-13
D64BSP	No	Yes	No	No	No
DeePBSP	Yes	Yes	No	No	No	1994
DoomBSP	No	No	No	Yes	No
DoomBSP 2.0	Yes	No	No	No	No
ELFBSP	No	Yes	Yes	Yes	No	2026-01-01	2026-03-22
glBSP	No	Yes	No	Yes	No
glVIS	No	Yes	No	Yes	No
H2BSP	No	No	No	Yes	No
IDBSP	Yes	No	No	No	No	1994
MacBSP	No	No	Yes	No	No
machexbsp	No	No	Yes	No	No
NanoBSP	No	No	No	No	No	2023-12-08
NBLD.EXE	Yes	Yes	No	No	No
PSXBSP	No	No	No	Yes	No
PSXBSP (GEC)	No	Yes	No	No	No
VigilantBSP	No	Yes	No	Yes	No	2022-04-05	2024-12-29
WARM	Yes	Yes	No	Yes	Yes	1995-01-30	1996-01-29
ZDBSP	Yes	Yes	No	Yes	No	2003-09-12	2016-01-07
ZDRay	No	Yes	No	No	No
ZenNode	No	Yes	Yes	Yes	No	1994-10-26	2004-05-30
ZokumBSP	No	Yes	No	Yes	No		2023-02-20

Standard formats

A standard Doom map format level, recompiled to use the XNOD format. In this format, the SEGS and SSECTORS lumps are intentionally left empty, as all data is stored in NODES.

A standard Doom map format level, recompiled to use the XGL3 format. Similarly to the XNOD format, all data is stored in a single lump.

The following are commonly supported BSP tree formats. In contrast to the "deprecated" formats described below, these are characterized for only using the original lumps of the binary map formats.

Regular nodes

The nodes described in the NODES, SEGS and SSECTORS lumps, used by the original version of all Doom-engine games. They suffer from certain limitations, such as a limit of 32768 (or 65536) for the number of segs and vertices and a lack of precision for node coordinates (they are stored as integers, rather than fixed-point values) which results in many slime trails.

DeePBSPV4 nodes

Main article: DeePBSPV4 nodes

To remove the limits of regular nodes, the DeePBSP node builder uses a different format which can be recognized by a starting signature in the NODES lump. DeePBSPV4 uses 32-bit values to reference vertices, segments, subsectors and nodes, generally pushing the limits from 65536 to ~4.27 billion. However, they still suffer from lack of coordinate precision.

ZDoom nodes

Main article: ZDBSP nodes

ZDoom's ZDBSP introduced various new node formats, XNOD, XGLN, XGL2 and XGL3, as well as their respective zlib-compressed "Z"-variants, ZNOD, ZGLN, ZGL2 and ZGL3.

Similarly to DeePBSPV4 nodes, the XNOD format uses 32-bit integer indexes for referencing nodes, subsectors, segments and vertices—increasing their limits from the original engine's 16-bit integers. Unlike regular or DeePBSV4 nodes, the ZDoom formats will store all of the BSP tree data in a single lump, instead of spreading the data between VERTEXES, NODES, SSECTORS and SEGS.

Most notably, these formats also feature increased coordinate precision to significantly reduce instances of slime trails.

Deprecated formats

The following formats are not as widely used as the aforementioned "standard" ones. These were primarily early designs meant to address hardware rendering requirements without affecting the structure of the existing regular format nodes, by way of providing additional lumps and data which easily enabled hardware accelerated rendering. However, due to both technical and practical reasons, these formats did not see wide support.

LEAFS

Main article: LEAFS

A new data format introduced in PSX Doom, which was later also used in PSX Final Doom and Doom 64. The LEAFS lump is used to address the strict polygonal requirements for the hardware renderers of their respective console ports by extending the BSP tree further with additional information about segments and vertices for each subsector. The LEAFS lump has not seen any notable use in community-driven projects outside of those directly related to these console versions of Doom, such as PsyDoom and the Doom64 EX lineage.

FLOOR

Main article: FLOOR

The Nintendo 64 port of Hexen uses an additional lump, otherwise separated from the main binary map format lumps, which includes sets of triangular splits on each sector, in order to allow for proper hardware rendering. This is the only known use of this structure, and no builders are known to support it.

GL nodes

Main article: GL nodes

As per the glBSP specification on GL nodes, BSP-generated data comes in separate, "GL_"-prefixed lumps, distinct from the main map lumps. They operate under additional constraints which enable the BSP tree to be more compatible with hardware renderers.

While the glBSP specification has historically defined the active and deprecated GL formats, notably the use of V2 and V5 as the de-facto formats, they are all now functionally deprecated, due to both practical and technical issues which have hindered its wide adoption. The inclusion of the "GL_" lumps is almost never a concern of the mapper anymore.

• 

  Doom 64 map format level, featuring LEAFS.

• 

  N64 Hexen, preview of MAP01 and FLOOR01.

• 

  Standard Doom map format level using GL nodes.

Formats comparison

Here follows a brief list comparing the various binary node lump formats at a glance.

	Regular	DeepBSPV4	XNOD	XGLN	XGL2	XGL3	GL V1	GL V2	GL V3	GL V4	GL V5
Number of nodes	32768	32768	~2.15 billion	~2.15 billion	~2.15 billion	~2.15 billion	32768	32768	32768	32768	~2.15 billion
Node partition line coordinates	Integer	Integer	Integer	Integer	Integer	Fractional	Integer	Integer	Integer	Integer	Integer
Number of subsectors	32768	32768	~2.15 billion	~2.15 billion	~2.15 billion	~2.15 billion	32768	32768	32768	32768	~2.15 billion
Convex subsectors (minisegs)	No	No	No	Yes	Yes	Yes	Yes	Yes	Yes	Yes	Yes
Number of segments	65536	~4.27 billion	~4.27 billion	~4.27 billion	~4.27 billion	~4.27 billion	65536	65536	~4.27 billion	~4.27 billion	~4.27 billion
Seg angle/offset data	Yes	Yes	No	No	No	No	No	No	No	No	No
Partner segment	No	No	No	Yes	Yes	Yes	Yes	Yes	Yes	No	Yes
Number of map linedefs	65535	65535	65535	65535	~4.27 billion	~4.27 billion	65535	65535	65535	65535	65535
Number of total vertices	65535	~4.27 billion	~4.27 billion	~4.27 billion	~4.27 billion	~4.27 billion	65536	65536	~1.07 billion	~2.15 billion	~2.15 billion
BSP vertex coordinates	Integer	Integer	Fractional	Fractional	Fractional	Fractional	Integer	Fractional	Fractional	Fractional	Fractional

Map format support

Builders work primarily with the basic level geometry contained in the VERTEXES, LINEDEFS, SIDEDEFS and SECTORS lumps, or TEXTMAP in the case of UDMF levels, making it a mostly seamless experience to support all three major formats, but there are still some limitations and differences to be taken into consideration. Notably, the Hexen map format introduced a different format for linedefs and Things, which included parameterized action specials for both, as well as the introduction of polyobjects.

Normally, when generating the necessary data for polyobjects, in any given supported map format, node builders must be aware of the marking line specials, the Thing types which mark the placement of such objects and ensure that the polyobject BSP tree limitations are respected.

Builders must also be capable of handling different editor numbers for polyobjects, since the original Hexen's polyobjects' editor numbers conflict with editor numbers in the other base games, notably with Doom's imp and Strife's reaver both using the 3001 number.

Due to certain source port extensions, it possible for these ports to circumvent the strict need for node builder polyobject awareness—this is most notable in the case of the Eternity Engine, which supports polyobjects in the Doom map format via the ExtraData extension, which would otherwise require bespoke support by builders.

Type	Hexen	ZDoom
Anchor	3000	9300
Spawn PolyObj	3001	9301
Crushing PolyObj	3002	9302
Harmful PolyObj		9303

Name	Special	Arg 1	Arg 2	Arg 3	Arg 4	Arg 5	Description
PolyObj_StartLine	1	PolyObj ID	Mirror PolyObj ID	SNDSEQ ID	Line ID		Marks the given line as the start of the polyobject.
PolyObj_ExplicitLine	5	PolyObj ID	Rendering order	Mirror PolyObj ID	SNDSEQ ID	Line ID	Explicitly marks the given line as part of the given polyobject.

Map format support across node builders

	Doom	Hexen	UDMF	Hexen PolyObj	ZDoom PolyObj	Notes
AJBSP	Yes	Yes	Yes	Yes	Yes	Tries to autodetect ZDoom's polyobject editor numbers, when reading Hexen-format maps, using their Hexen counterpart otherwise. Always assumes ZDoom values for UDMF maps, ignoring the provided namespace.
BSP	Yes	No	No	N/A	N/A
BSPCOMP	Yes	No	No	N/A	N/A
DeePBSP	Yes	Yes	No	?	?
DoomBSP	Yes	No	No	N/A	N/A
ELFBSP	Yes	Yes	Yes	Yes	Yes	Uses ZDoom polyobject editor numbers by default, on both Hexen and UDMF maps. Can be toggled to use Hexen's editor numbers with the --polyobj parameter.
glBSP	Yes	Yes	No	Yes	Yes	Tries to autodetect ZDoom's polyobject editor numbers, when reading Hexen-format maps, using their Hexen counterpart otherwise.
glVIS	Yes	Yes	No	N/A	N/A	Being a builder for the GL_PVS lump, building BSP trees is out of its scope.
H2BSP	No	Yes	No	No	No	Despite being the node builder used for Hexen's development, it did not actually support active polyobject awareness.
IDBSP	Yes	No	No	N/A	N/A
MacBSP	Yes	No	No	N/A	N/A
machexbsp	No	Yes	No	?	?
NanoBSP	N/A	N/A	N/A	No	No	NanoBSP is designed to be an internal builder first and foremost, using the internal formats to execute the building process; the actual level lumps are, then, not in its scope.
NBLD.EXE	Yes	No	No	N/A	N/A
VigilantBSP	Yes	Yes	No	Yes	Yes
WARM	Yes	Yes	No	No	No
ZDBSP	Yes	Yes	Yes	Yes	Yes
ZDRay	Yes	Yes	Yes	Yes	Yes
ZenNode	Yes	Yes	No	No	No
ZokumBSP	Yes	Yes	No	No	No

Internal builders

Some source ports include built-in builders, which will directly generate the needed nodes, subsectors and segments in the expected internal format, under their own conditions.

Most source ports will include internal REJECT matrix padding and BLOCKMAP generation, this is notably present in Boom, MBF and most of their descendant projects—it is also important to note that, for ports that aim for vanilla accuracy or demo compatibility, demos may otherwise de-sync if the algorithms used may generate differently formatted data structures. This is most notable in the case of the blockmap and subsectors, both of which are used in Doom's playsim code.

Internal building support across ports

	BSP generation	Reject padding	Blockmap generation	Notes
Boom			Boom	Notably, the source code includes two iterations of the blockmap builder, the earlier being rejected in favor of the later, due to better performance. Which itself was later superseded by Lee Killough's MBF implementation. The internal building of the blockmap can be triggered by either supplying the -blockmap parameter, or if the size of the BLOCKMAP lump is considered invalid—that is, if the lump's size in bytes, when divided by half, goes over 65536 (or 0x10000). This behavior is retained in all descendant ports. Later on, most descendants also check if the lump is too short, fewer than 8 bytes.
Chocolate Doom		PrBoom+
Crispy		PrBoom+	MBF	Blockmap building is currently only executed on Crispy-Doom and Crispy-Heretic.
DelphiDoom	glBSP	DelphiDoom	Boom	An array bounds check is performed when reading the reject matrix, functionally padding short matrices with zero-bytes.
DoomRetro		DoomRetro	MBF	The reject matrix is just padded with zero-bytes.
DSDA-Doom		PrBoom+	Boom	Being based on PrBoom+, and having not introduced relevant changes, the same information still applies.
EDGE-Classic	AJBSP		EDGE-Classic	Reject matrices are always ignored, the blockmap is always rebuilt and only XGL3 (or ZGL3) BSP trees will be read from the map's lumps, always rebuilding the BSP tree otherwise.
Eternity Engine		PrBoom+	Boom & MBF	The Eternity Engine uses the Boom blockmap generator only for playing back older demo versions, and MBF's implementation otherwise.
Helion	ZDBSP	Helion	Helion	Helion does not use traditional, BSP-based rendering. Instead, the BSP tree is used only for certain use-cases, such as compatible automap drawing or determining the sector that a Thing belongs in (this behavior is already present in the base game). Previously, for one past version release, any hardware-friendly format would be used, and nodes would be built otherwise. This is no longer the case, as the internal ZDBSP is now used to always build nodes, and the map lumps are always ignored. An array bounds check is performed when reading the reject matrix, functionally padding short matrices with zero-bytes.
MBF			MBF	Despite much of its code being later back-ported to PrBoom+, MBF's blockmap builder was not.
Odamex			Boom	Empty or invalid REJECT lumps will be ignored, and the internal matrix will go unused—this is functionally identical to having a completely zeroed out matrix.
PrBoom+		PrBoom+	Boom	Later versions of the hardware renderer introduced a somewhat novel technique to ensure convex subsectors on the engine's internals, without the existence of minisegs. Both this, and the fact that demo compatibility is a primary goal of the PrBoom port lineage, have limited the need for rebuilding the BSP tree. Despite back-porting much of the code from MBF, the simpler and faster blockmap generator implementation was not carried over. Earlier versions of PrBoom+ would pad the reject matrix with positive bytes, 0xFF, marking all padded lines of sight as non-visible, making all enemies "blind". A later update rectified this by padding with zero-bytes, 0x00, and introducing a new CLI parameter, -reject_pad_with_ff, to maintain demo-compatibility. The reject padding itself also performs vanilla overflow emulation. All ports that subsequently adopted PrBoom+'s implementation also pulled both the -reject_pad_with_ff parameter and overflow emulation, also in order to preserve demo-compatibility across the relevant ports.
ZDoom, GZDoom, UZDoom and Zandronum	ZDBSP	ZDoom	ZDoom	The BSP tree will always be rebuilt if it is found to not have hardware-friendly nodes for rendering or the textured automap, that is to say, if the subsectors are not strictly convex—this is validated internally by checking for the presence of at least one miniseg in the list of loaded segments.
Woof	NanoBSP	PrBoom+	Boom (previously MBF)	Due to the need for demo-compatibility, NanoBSP generation is only provided via the -bsp CLI parameter. Earlier versions of the port used the blockmap building algorithm from MBF, later changing to the Boom blockmap builder, instead, also for the sake of keeping demo accuracy.

See also

• Doom rendering engine
• Slime trail

External links

• DeePBSP extended nodes specifications
• GL nodes specifications
• ZDoom nodes specifications at the ZDoom wiki