A design bug in the BSP nodebuilder, which has probably existed forever and may also exist in other node builders, has recently [1997] been found and fixed.
Symptoms of this bug include many common wad problems:
Whenever a SEG is incident to (overlaps) a nodeline, it is sometimes partitioned on the wrong side of the nodeline.
A SEG is a line segment similar to a linedef, which the node builder and Doom use for all line calculations. Every SEG is incident to an associated linedef.
A nodebuilder initially creates the SEGS from the linedefs, with one SEG for each sidedef.
A one-sided linedef creates one SEG, a normal one:
| |
*-------------* *------------* flip=0
linedef SEG
A two-sided linedef creates two SEGS, a normal one and a flipped one:
|
| *-------------* flip=0
*-------------* SEGS
linedef *-------------* flip=1
|
Every SEG is either "flipped" or not, indicated by a "flip" flag.
"Flipped" means it is associated with the second sidedef of a
linedef, rather than the first.
A node builder successively divides the level map in half, until nothing but convex SSECTORS remain. To do that, it must at each stage in the Binary Space Partitioning process pick a SEG known as the nodeline, to divide the map in half. All SEGS on the left side of the nodeline go into the left child of the node, and all SEGS on the right side of the nodeline go into the right child of the node.
At times, a node builder must split SEGS into two, because a nodeline cuts across the middle of a SEG. Node builder heuristics are designed to reduce the chances of these splits from happening.
When a SEG is split, it becomes two SEGS, both having the same properties as before except for the starting and ending vertices, and the distance from the start of the associated linedef.
An SSECTOR (simple sector) is a collection of SEGS which make up a convex polygon. Convex means no interior angles exceed 180 degrees, or equivalently, that every SEG that makes up the SSECTOR is on the same side as every other.
All SEGS inside an SSECTOR are supposed to come from the same SECTOR, but this is not absolutely necessary, and special effects such as transparent doors make use of the fact that Doom uses the lowest numbered SEG inside the SSECTOR to determine which SECTOR it corresponds to.
Back to the BSP bug:
BSP has had a bug, where if a nodeline is selected which cuts across another SEG incident to it, then that SEG is not properly partitioned sometimes:
| |
*--------------* .... *---------------*
nodeline SEG
BSP had used the flip flags, which indicate which sidedefs the
SEGS correspond to, to determine whether a incident SEG should
go on the left or right side of a node line. This is clearly
wrong, as this example shows:
| incident SEG
*--------------* flip=0 *---------------* flip=1
nodeline |
The BSP algorithm chose to put the incident SEG on the right side
of the nodeline if and only if the SEG's flip flag was equal to the
node line's flip flag.
But this is wrong, because you can flip a linedef (swap its sidedefs and vertices) and this changes nothing about the geometry of the map or the sectors, and yet it toggles the flip bits of that linedef's SEGS, changing how BSP chooses to divide the incident line.
This is probably why some bugs in wads, such as shoot-through-walls, could be fixed simply by flipping the linedefs.
Whether a SEG is flipped (corresponds to either the left or right sidedef of the corresponding linedef) does not change the basic geometry, or whether a SEG incident to another one is on its left or right side.
What BSP should have done instead, is to consider the relationship between the vertices of the nodeline and SEG, without regard to the flip flags. A incident SEG is either on the left or right side of a nodeline depending on whether the lines go in the opposite or same direction, respectively. It has nothing to do with whether the SEG is flipped from its original linedef or not.
If it should have happened that the incident SEG in question was in the same direction as the nodeline when it had the same flip bits, or if the SEG had the same sector (or sectors with the same properties) on both sides of its associated linedef, then this bug went unnoticed. This is certainly common in many Doom structures, such as along walls which have incident linedefs all pointing in the same direction, and in convex sectors with extra linedefs in the middle (such as walk triggering linedefs).
Invisible barriers were caused whenever a incident SEG was placed on the wrong side of a node line, and it corresponded to a linedef separating two sectors of different floor heights. The SSECTOR in the invisible barrier area got a SEG with the wrong flip, and thus the wrong sidedef and sector were used to render that SSECTOR. Things were placed at the floor height of the sector on the wrong side of the linedef. The barrier was invisible because there were no other SEGS in the SSECTOR, nor did the rest of the nodes structure imply that there was any sort of closed polygon in there. So the entire SSECTOR was simply an invisible floor raised to the height of an adjacent sector, indicated by one bad SEG.
Disappearing Things occurred whenever a sector became out of view due to line-of-site calculations Doom performed, but there was still a SEG inside the SSECTOR that the Thing resided in, which referred incorrectly to that sector. As soon as the sector that the Thing supposedly resided in became blocked from view, all SSECTORS which had SEGS that pointed to that sector, stopped having Things drawn in them. This is normally good, for obvious Doom efficiency reasons -- why spend time rendering a Thing which is not even visible to the player?
This bug is fixed in version 2.1x and later of BSP.
The node line picker, and more importantly, the SEG partitioning routine, have both been changed to use vertex geometry instead of flip flags to decide what side of a node line a incident SEG is on.
Credit should go to Jan Van der Veken, for providing me with a wad and a LMP that clearly illustrated the disappearing Things bug.
NodeNav was also helpful as a debugging tool.
Lee Killough