glBSP - The GL-Node Builder

SPECIFICATION for GL-Nodes

Version: 5.0

written by Andrew Apted   <ajapted@users.sourceforge.net>

Table of Contents

1. Introduction
2. Conventions
3. Level marker
4. Data lumps
   
   • GL_VERT
   • GL_SEGS
   • GL_SSECT
   • GL_NODES
   • GL_PVS (optional)
   • Extension lumps (optional)
5. GWA files
6. Version summary
7. Compliance tests

Introduction (why GL-Nodes are needed)

Walls are no trouble, but the floors and ceilings in DOOM levels are only roughly defined (as the gaps between walls). Thus an OpenGL port of DOOM (hereafter called the "engine") requires the floors and ceilings to be "polygonised", to make sure they are convex, and to find the precise edges.

An obvious way of polygonising a DOOM level is to use the BSP tree contained in the SEGS, SSECTORS and NODES lumps. The BSP tree already provides convex subsectors, so the main work is to determine all of the edges of these subsectors (since the BSP info in DOOM levels only includes edges which lie along linedefs).

The main problem with this approach is that some node builders create BSP trees where certain subsectors are not purely convex (especially when the segs are included as boundaries).

The other concern with polygonisation is that the process can be very time consuming. It should only be needed to be done once, and preferably by the author of the WAD file (and not the user).

Conventions for this Specification

All on-disk data structures use little endian format (i.e. the least significant byte comes first, the most significant byte comes last).

TERMINOLOGY

Engine

The game engine (or "source port") which reads the GL nodes.

Builder

The nodes builder which creates and writes the GL nodes.

Magic ID

The special sequence of bytes at the beginning of a file or lump which distinguishes the format of the file or lump. Often used when a new format is introduced for an existing lump. The magic identifiers for GL-Nodes are of the form "gNd" + digit.

char : 8 bits
short : 16 bits
int : 32 bits

Level Marker

When the normal level name is longer than 5 letters, then the marker name must be "GL_LEVEL" and the name is stored inside the marker lump (as described below).

Each GL level marker may contain some extra information. This information can be used with any version of GL-Nodes. The format is a simple text file. Text lines should be no longer than 250 characters, and are terminated either by a single LF character (0x0A in hex) or by a CR LF pair (0x0D 0x0A in hex). Each line must be of the following form:

   KEYWORD=VALUE

Since this data is not designed to be read or edited by users, it can be kept simple. There should not be any whitespace before the keyword or around the '=' character. There is no support for comments or blank lines. Keywords must be uppercase, but values may be in mixed case. Unknown keywords should be ignored. In the unlikely event more data is needed than can fit on a single line, the keyword "X" is reserved for adding extra data to the previous keyword.

Keywords:

LEVEL

For "GL_LEVEL" markers this gives the lump name of the normal level (e.g. MAP100). When present, this keyword must be first. The value should be uppercase, and must be between 6 and 8 characters.

BUILDER

Gives the program which built the GL nodes. Format is a single-word name (e.g. "glBSP"), followed by a space, and then a version number.

TIME

Gives the date and time when the GL nodes were built. Format is "YYYY-MM-DD hh:mm:ss.xxxx", where YYYY-MM-DD is the date (year, month, day), hh:mm:ss is the time (hours, minutes, seconds), and xxxx is the fraction of a second. This syntax is a subset of the ISO standard.

CHECKSUM

Gives a checksum over the level data. Format is an 8-digit hexadecimal number prefixed by "0x" (a 32-bit value). The checksum algorithm is Adler-32, which is described in RFC-1950. The method of generating the checksum is as follows:

1. begin Adler-32.
2. add the entire contents of the VERTEXES lump.
3. add the entire contents of the LINEDEFS lump.
4. finish Adler-32.

NOTE: when a Builder is creating both normal and GL nodes, it must use the final output version of the generated VERTEXES lump.

Example

LEVEL=MAP100 BUILDER=glBSP 2.14 TIME=2005-03-26 13:50:03.2500 CHECKSUM=0xABCDEF01

Data Lumps

The new lumps are:

The order of these lumps in the WAD file is important. First should come the normal level lumps (MAP01, THINGS, ...), followed by the GL lumps in this order: GL level marker (e.g. GL_MAP01), GL_VERT, GL_SEGS, GL_SSECT, and finally GL_NODES. These lumps can co-exist with the normal BSP tree information.

GL_VERT

This lump contains extra vertices that are needed by the GL BSP tree. Often a GL seg will begin and/or end someplace where there isn't a normal vertex (in the VERTEXES lump), and these GL vertices are stored here.

The V1 format of GL_VERT is the same as the normal VERTEXES lump.

Version 2 of these specs introduces a new format for GL_VERT. The new format is distinguished from the old format by a 4-byte magic identifier at offset 0, namely: "gNd2". Following the magic ID are the vertices, each vertex is just two 32-bit integers for X and Y (actually 16.16 fixed point).

Version 5 of these specs does not change the format of GL_VERT, but the magic identifier at offset 0 will be "gNd5" to indicate the presence of V5 GL nodes (and hence the format of the other GL lumps).

GL_SEGS

The GL_SEGS lump defines all the GL segs, which form the boundaries of each GL subsector. The format is different to the usual SEGS lump, but should look pretty familiar:

struct GLSeg1 {    unsigned short start_vertex;    unsigned short end_vertex;    unsigned short linedef;    unsigned short side;    unsigned short partner_seg; } #define VERT_IS_GL (1 << 15)

The start and end vertex values define precisely where the seg lies. There is no 'offset' or 'angle' fields like in the normal SEGS lump, it is assumed that the engine can trivially compute these. Bit 15 plays a special role: when 0, the vertex is a normal one (from VERTEXES), when 1 the vertex is a GL vertex (from GL_VERT lump).

The linedef number is the linedef that the seg lies along, or 0xFFFF if the seg does not lie along any linedef. Those segs are called "minisegs", since they are never drawn by the engine, they only serve to mark the boundary of the subsector (for creating plane polygons).

The side number is 0 if the seg lies along the RIGHT side of the linedef, or 1 if the seg lies along the LEFT side. This is the same as the 'direction' field in the normal SEGS lump. Ignored for minisegs.

The partner seg needs some explanation. For segs that lie along a one-sided linedef, this field is simply 0xFFFF. Otherwise this field contains the index for the GL seg in the adjacent subsector which borders on the current seg. There is guaranteed to be a one-to-one correspondence between the segs that lie on either side of the border between any two subsectors. A corollary is that a seg's start vertex is the same as its partner's end vertex, and vice versa.

Version 3 of these specs introduces a new format for GL_SEGS. The new format is distinguished from the old format by a 4-byte magic identifier at offset 0, namely: "gNd3". After the magic ID are the segs, and each seg has this format:

struct GLSeg3 {    unsigned int start_vertex;    unsigned int end_vertex;    unsigned short linedef;    unsigned short side;    unsigned int partner_seg; } #define VERT_IS_GL (1 << 30)

Bit 30 of the vertex number is used to indicate a GL Vertex (instead of bit 15 as in V1).

Version 5 of these specs introduces a small change to the V3 format. The main difference is that there is no magic ID at the start of the lump, you must check the GL_VERT lump instead. Each seg has this format:

struct GLSeg5 {    unsigned int start_vertex;    unsigned int end_vertex;    unsigned short linedef;    unsigned short side;    unsigned int partner_seg; } #define VERT_IS_GL (1 << 31)

Bit 31 of the vertex number is used to indicate a GL Vertex (instead of bit 30 as in V3).

An Engine may use the same code to read both V3 and V5 segs by checking the top two bits of the vertex number (for a GL vertex), and clearing both bits to get the index. Builders, however, must take care to set the correct bit.

GL_SSECT

This lump contains the info for all GL subsectors. Each GL subsector is made up of a sequence of GL segs (defined in the GL_SEGS lump).

The GL_SSECT lump has some important properties that the usual SSECTORS lump does not have:

1. All edges of the subsector are included, even those that do not lie along linedefs (i.e. the minisegs).

2. There is a strict ordering: all the segs are in clockwise order (when looking from above). In other words: one seg's start vertex is the same as the previous seg's end vertex.

3. The subsector must be closed: i.e. all the segs form a continuous path, and the last seg's end vertex is the same as the first seg's start vertex.

struct SubSector1 {    unsigned short count;    unsigned short first_seg; }

Version 3 of these specs introduces a new format for GL_SSECT. The new format is distinguished from the old format by a 4-byte magic identifier at offset 0, namely: "gNd3". It's just like the old format except that 32-bit values are used for everything (the seg count and first seg number) instead of 16-bit values, as shown below:

struct GLSubSector3 {    unsigned int count;    unsigned int first_seg; }

Version 5 of these specs introduces a small change to the V3 format. The only difference is that there is no magic ID at the start of the lump, you must check the GL_VERT lump instead.

GL_NODES

The GL_NODES lump contains the information for the GL BSP tree. An important property which the normal NODES lump lacks is that the bounding boxes are guaranteed to cover the whole subsector, not just the segs that lie along linedefs (as happens with NODES).

The format of GL_NODES is the same as the normal NODES lump, reproduced here for convenience:

struct Node1 {    short x; // partition line    short y;    short dx;    short dy;    short right_bbox[4];    short left_bbox[4];    unsigned short right_child;    unsigned short left_child; } #define CHILD_IS_SUBSEC (1 << 15)

Version 5 of these specs introduces a new format for GL_NODES which makes the child indices 32-bits instead of 16-bits. Each node has the following new format:

struct GLNode4 {    short x; // partition line    short y;    short dx;    short dy;    short right_bbox[4];    short left_bbox[4];    unsigned int right_child;    unsigned int left_child; } #define CHILD_IS_SUBSEC (1 << 31)

GL_PVS

The GL_PVS lump was developed by Janis Legzdinsh for the Vavoom engine. It contains a Potentially Visible set (something similar to the REJECT information, but indexed by GL subsectors). The format of this lump is described on the Vavoom homepage.

This lump is optional, and is allowed to be absent, though it's recommended that Builders simply write an empty GL_PVS lump.

Extension Lumps

Any tool which can copy the GL-Nodes (e.g. from one WAD into another) should also copy these extension lumps. Engines may ignore them.

At this time, no extensions are defined by this specification.

GWA Files

This specification defines a new file type, which has the ".GWA" extension (short for 'GLWAD'). This GWA file is just a normal PWAD, but contains nothing else except the GL level markers and the GL lumps. It serves as a companion file to the 'WAD' file which contains the actual level info.

When the engine loads a ".WAD" file, it should check for the existence of the same file but with the ".GWA" extension, and load it as well, unless the timestamp on the GWA file says that it is older than the WAD file (to prevent problems with PWADs that have been edited, which would invalidate the GL-Nodes in the GWA file).

In the case where GL-Nodes exists for a level in both the WAD and a GWA file, the GWA data should generally override the WAD data, but the Engine may have enough information to choose the correct one (e.g. via timestamps or checksums).

Version Summary

V1

Version 1 was the initial public version, and is considered obsolete now. No implementation is required to support it, but Engines should at least recognise V1 to prevent crashes.

lump	magic id	format name
GL_VERT	-	Vert1
GL_SEGS	-	GLSeg1
GL_SSECT	-	SubSector1
GL_NODES	-	Node1

V2

Version 2 added 16.16 fixed point coordinates for the GL vertices (in the GL_VERT lump), and is the format which became widely adopted. It is still the preferred format. All conforming implementations must support V2.

lump	magic id	format name
GL_VERT	gNd2	GLVert2
GL_SEGS	-	GLSeg1
GL_SSECT	-	SubSector1
GL_NODES	-	Node1

V3

Version 3 extended the GL_SEGS and GL_SSECT lumps to handle more than 65534 segs and more than 32767 vertices. V3 was only needed when the level overflowed the normal limits. It has been superceded by V5, and it should not be used anymore. All Engines should at least recognise V3 to prevent crashes.

NOTE: to properly check for V3, you must check the magic ID in the GL_SEGS lump.

lump	magic id	format name
GL_VERT	gNd2	GLVert2
GL_SEGS	gNd3	GLSeg3
GL_SSECT	gNd3	GLSubSector3
GL_NODES	-	Node1

V4

Version 4 was developed by Jack Vermeulen (sbsoftware.com), using V2 as the basis. V4 added support for more than 65534 segs and more than 32767 vertices, extended the GL_NODES format to handle more than 32767 nodes/subsectors, removed the partner segs from GL_SEGS, and used a more economical format for GL_SSECT.

V4 was only needed when the level overflowed the normal limits. It has been superceded by V5, and should not be used anymore. All Engines should at least recognise V4 to prevent crashes.

lump	magic id	format name
GL_VERT	gNd4	GLVert2
GL_SEGS	-	GLSeg4
GL_SSECT	-	GLSubSector4
GL_NODES	-	GLNode4

V5

Version 5 is the latest version of GL-Nodes, as documented here. It uses V4 as the basis, hence it removes all the limits, but adds the partner segs back in. V5 only needs to be used when a level overflows the normal limits (otherwise stick to V2). All conforming implementations must support V5.

lump	magic id	format name
GL_VERT	gNd5	GLVert2
GL_SEGS	-	GLSeg5
GL_SSECT	-	GLSubSector3
GL_NODES	-	GLNode4

Compliance Tests

(C) 2007 Andrew Apted

Updated: July 2007