GL-Nodes Specification

From 3DGE Wiki
Revision as of 14:26, 28 July 2015 by Corbin (talk | contribs) (Created page with "== Introduction (why GL-Nodes are needed) == OpenGL rendering requires all surfaces to be polygons. For DOOM and its derivatives (like Heretic & Hexen) this means the wa...")

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

Introduction (why GL-Nodes are needed)

OpenGL rendering requires all surfaces to be polygons. For DOOM and its derivatives (like Heretic & Hexen) this means the walls, floors and ceilings need to be made into polygons.

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

This specification assumes familiarity with the "DOOM Specs" by Matt Fell, and knowledge of the C programming language.

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.
TYPE SIZES

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


Level Marker

The GL-Nodes are stored in a series of lumps which begin with a special GL level marker. This level marker is the same as a normal level marker (e.g. "MAP01") but with the prefix "GL_" added (e.g. "GL_MAP01"). This allows the GL information to be stored in a separate file.

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

This specification defines four new lumps that are associated with each level in a WAD File. These lumps define a "GL-Friendly BSP", in which the hard work of polygonising subsectors (and ensuring there are no problem subsectors to cause holes) is done by an external utility: a "GL-Node Builder".

The new lumps are:

[#GL_VERT GL_VERT] - GL vertex information
[#GL_SEGS GL_SEGS] - GL seg information
[#GL_SSECT GL_SSECT] - GL subsector information
[#GL_NODES GL_NODES] - GL node information (the GL BSP tree)
[#GL_PVS GL_PVS] - Visibility information (OPTIONAL)

(the formats of these lumps are described below).

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.

The V1 format of GL_SSECT is the same as the normal SSECTORS lump, reproduced here for convenience:

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

Extension lumps are a mechanism for providing extra information (perhaps Engine-specific) which doesn't fit anywhere else. These lumps have names beginning with "GX_", and must immediately follow the last "GL_" lump. There can be any number of extension lumps, and they are all associated with the current map.

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

The original specifications only allowed the GL-Nodes to exist in the same WAD as the normal level information. But it became very convenient to store the GL information in a separate file, especially for the game's IWAD file (e.g. DOOM2.WAD).

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 GLSeg1]

GL_SSECT -

[#SubSector1 SubSector1]

GL_NODES -

[#Node1 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 GLSeg1]

GL_SSECT -

[#SubSector1 SubSector1]

GL_NODES -

[#Node1 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 GLSeg3]

GL_SSECT gNd3

[#GLSubSector3 GLSubSector3]

GL_NODES -

[#Node1 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 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 GLSeg5]

GL_SSECT -

[#GLSubSector3 GLSubSector3]

GL_NODES -

[#GLNode4 GLNode4]


(C) 2007 Andrew Apted Updated: July 2007

SourceForge