Lee Killough
Visplane overflows have long been a mystery (and a source of controversy) in the Doom editing community.
Here's my best theory to-date about the real cause of visplane overflows:
Too many changing ssectors (sub-sectors) in view at once, with different floor and/or ceiling properties. Floors and ceilings count separately towards the limit, and only when each is actually visible to the player. Two flats are considered compatible if they have the same texture, the same lighting level, and the same height (unless the texture is F_SKY1, in which case height does not matter). If two visible flats are compatible, and they are only separated by a 2s linedef or by flats that are not visible, then the visible flats are merged into the same visplane.
However, there are some limiting factors -- factors that the number of visplanes cannot exceed a constant multiple of:
If you reduce either of these, you lower the maximum (not actual) number of visplanes that can be generated, but neither of these factors are the sole causes of visplane overflows.
Also, there is direct evidence that a node builder can make a difference, and thus, how ssectors are built can make a difference. When a node line cuts across a wide open sector, splitting it into two sectors, this usually increases the visplane count. A Doom node builder is free to choose any node line, as long as there is at least one seg on either side of it, so there is considerable freedom to choose node lines and to minimize splitting large sectors with node lines.
From direct evidence, I know that:
--- --- --- --- --- ---
| A | B | A | B | A | B |
--- --- --- --- --- ---
| B | A | B | A | B | A |
--- --- --- --- --- --- . . .
| A | B | A | B | A | B |
--- --- --- --- --- ---
| B | A | B | A | B | A |
--- --- --- --- --- ---
.
.
.
-----------
| A |
-----------
| B |
-----------
| A |
-----------
| B |
-----------
| A |
-----------
| B |
-----------
| A |
-----------
.
.
.
--- --- ---
| B | C | B |
--- --- ---
| A | B | A |
--- --- ---
| B | C | B |
--- --- ---
|
--- --- --- --- --- ---
| B | C | B | | B | C | B |
--- --- --- --- --- ---
| A | C | A | --| A | A | A |--
--- --- --- --- --- ---
| B | C | B | | B | C | B |
--- --- --- --- --- ---
|
C's merge A's merge
I have one example wad in which visplane overflows occur when sector B's flats are made visible, even when the flats are the same as either A's or C's -- this is direct evidence of multiple merges being able to take place across invisible regions. If B is made visible and made to look like A, then you basically have:
--- --- ---
| A | C | A |
--- --- ---
| A | A | A |
--- --- ---
| A | C | A |
--- --- ---
See CONDUITS.WAD for an example. No visplane overflows occur despite the differences in floor textures and the rapidity of their change, until the 'conduit' sectors are raised (central switch), and this occurs even though the raised sector has the same floor texture as one of the adjacent ones. The visplane overflow occurs because the visibility of the raised sector removes its ability to act as a conduit for all the other sectors.
The heuristic attempts to balance the number of sectors (rather than the number of segs) on either side of a node line, and also tries to avoid picking node lines which cut across wide open areas. This leads to another observation I have made: visplane overflows can sometimes be introduced by a node builder picking node lines that cut across a wide open area. The best theory I have to explain this, is that during back-to-front rendering of flats, some static information is kept and as you move from one sub-sector to another, changes in flats tend to increase the visplane count. A node line cutting across a wide open area, makes one side of the node line get drawn first, then the other side, and if the node line cuts across a sector in that wide open area, it can artificially break up an otherwise single visplane into multiple visplanes because of the resulting order in which the flats are drawn. Here's an example:
---------------
| | |
| A | B | ----
| | | | |
--------------- ----
---------------
| | |
....|...A...|...B...|....----......> node line
| | * | | |
--------------- ----
* = player If no node line splits room: draw A, then B.
If node line splits room: draw back of A, then
back of B, then front of A, then front of B,
causing flats to alternate more often.
Had the node line not been added in this way, cutting across sectors A and B, then sectors A and B might have been sub-sectors and Doom could simply draw each one once. But since there is this extra node line, Doom must draw all of the back side first, which involves drawing part of A and then part of B, and then the front part, which again involves drawing part of A and part of B. This causes the flats being drawn to change more rapidly in the standard BSP ordering, which seems to be another factor contributing to visplane overflows. The more rapidly the flats change during BSP traversal, the greater the chances of visplane overflows.
This suggests that node lines should be chosen in such a way that they do not cause splits in sectors. Already most node builders try to avoid splitting segs, but this is apparently not as important for visplane overflows, as trying to avoid splitting a sector. Therefore, BSP has been modified to optionally use sectors, rather than segs, as the main criterion for choosing a node line. The -vp option selects this alternative.
The heuristic used in BSP to detect cuts across wide open areas is the proportion of the node line which is incident with existing segs, relative to its total length inside the bounding box, which is simply the sum of the lengths of all segs incident to the node line, divided by the total length of the node line inside the current bounding box. BSP considers more costly the node lines which make this ratio small, since a smaller value is correlated with a higher probability of splitting a wide open area. However, there's no easy way I can think of, to tell null space apart from normal space, at this stage in the node building process, so sometimes a node line will be rejected even though it cuts across null space, which is not important.
Note: I have tried measuring sector splits by considering them as happening when one or more linedefs that share the same sector are split by a node line, but this does not appear to be the correct measure to reduce visplane overflows. The best heuristic I've come up with to date is the one above, and since it has removed visplane overflows in at least 5 wads, I see no reason to change it, even though it is not easily explained why it works.
See VISAREA.WAD for player visibility metrics.
Since the Doom source code may be released soon, and this visplane overflow limit will either be removed or will be fully understood, I am going to go ahead and release this version of BSP now. Keep in mind that the detector is not perfect, and that it's only the result of around 4 months of part-time work. I only wish I had done this two or three years ago...
It had to do with how Doom merged compatible visplanes.
Some terms: A span is a horizontal interval (x1,x2). Doom uses spans to describe sprite and flat clipping. A "clip range" is a set of spans which indicate which parts of a Doom scanline have been drawn by non-transparent texture columns.
Example: Two floor triangles being drawn:
span 1 span 2
*---------* *---------*
. . . .
. . . .
. . . .
. . . .
. .. .
*.
Or:
span2 span1 span2
*-----*-------*-------*
. . . .
. . . .
. . .
. . .
*
The spans are each (x1,x2) intervals. The union and intersection of the two
spans are computed. If no flats (only possibly wall textures) have been
previously drawn anywhere inside the interval of intersection, then the two
triangles can be merged into one bigger triangle, whose span is the union
of the two original ones:
for (x=intrl ; x<= intrh ; x++)
if (pl->top[x] != 0xff)
break;
if (x > intrh)
{
pl->minx = unionl;
pl->maxx = unionh;
// use the same one
return pl;
}
// make a new visplane
lastvisplane->height = pl->height;
lastvisplane->picnum = pl->picnum;
lastvisplane->lightlevel = pl->lightlevel;
pl = lastvisplane++;
This explains why invisible (clipped) flats can separate identical flats, and not cause visplanes to add up, because the invisible regions correspond to areas drawn by wall textures, not flats, and as long as the intersection of the two spans contains only wall textures, the compatible flats can be merged into the same visplane.
The spans are horizontal, which explains why changes in flats occurring orthogonal to the direction the player is facing, are worse than changes in flats occurring parallel to the direction the player is facing, and why the trick of trying to prevent a nodesbuilder from breaking up space with node lines orthogonal to the player's view, in a dangerously high visplane area, works to reduce the chances of visplane overflow.
for (check=visplanes; check<lastvisplane; check++)
{
if (height == check->height
&& picnum == check->picnum
&& lightlevel == check->lightlevel)
{
break;
}
}
if (check < lastvisplane)
return check;
if (lastvisplane - visplanes == MAXVISPLANES)
I_Error ("R_FindPlane: no more visplanes");
Whether this kind of error will occur, is not simply testable by static checks of the level, such as the maximum number of distinct flats that are visible at any point reachable by the player -- it depends on the order in which the flats get drawn, which in turn depends on how the nodes get built. Also, this type of visplane overflow depends on the topology of the map, such as whether wall textures are all that separate two otherwise compatible flats in the viewer's framebuffer.
if (lastvisplane - visplanes > MAXVISPLANES)
I_Error ("R_DrawPlanes: visplane overflow (%i)",
lastvisplane - visplanes);
The reason a "visplane overflow" seems to have a random value greater than 128 printed with the error message, is that the overflow is detected post mortem -- way after the fact -- after all of the flats have been drawn. This means that even more visplanes can be drawn between the time of the initial overflow, and the time Doom detects that an overflow occurred, which is at the end of its flats rendering cycle. Doom only checks whether an overflow occurred after it has finished drawing all of the flats. Conceivably, Doom could corrupt memory and cause something like a venetian blinds crash too, if the visplane overflow was large enough that Doom started hammering away at memory way past the 128th visplane, before it realized that an overflow had taken place.
for (check=visplanes; check<lastvisplane; check++)
{
if (height == check->height
&& picnum == check->picnum
&& lightlevel == check->lightlevel)
{
break;
}
}
This means it compares a potentially new visplane with all previously
created visplanes, one by one, until it finds a match or reaches the end
of the list. This process is time-consuming when the number of visplanes
grows large. I've heard rumors that the reason the visplane limit was not
increased, was that this linear search would slow Doom down too much if
the limit was increased. But that's not a valid reason, because the
slowdown is proportional to the number of visplanes in the list, not the
limit, so there would be no slowdown compared to a version of Doom with
a lower visplane limit, unless the extra visplanes were actually used.