Doom 2 Map09 'slime trails' fixed. Bug found in BSP, DoomBSP, Zennode. Fixed in ZokumBSP 1.0.10-beta11.

[zokum]

I've been looking into the cause of slime trails. It seems that at least one known occurence was a different error, caused by bad angles in the SEGS data structure in the map format. Mosst known slime trails are still most likely related to integer rounding, more research is needed. A page about this new bug has been added in the Doom Wiki: https://doomwiki.org/wiki/Bad_seg_angle

I coded a tool to compute new angles for me and checked out the problematic star strucure near the exit on map09 in Doom 2 and found out many of the values are wrong.

You can edit this manually with SLADE with these updated values to check it for yourself, change the number from A to B for all 8 segs and play the map.

 

seg 325: angle from 30214 to 30147
seg 327: angle from -2553 to -2621

seg 328: angle from 30203 to 30709
seg 330: angle from -2564 to -2059

seg 337 angle from -30214 to -30148
seg 338 angle from   2553 to   2620

seg 341 angle from -30203 to -30710
seg 342 angle from   2564 to 2048

This fixes two rendering errors in that area, on two sides of the star.
 

As far as I can tell, Id software's DoomBSP tool only gets the angle wrong on segs that are split. So to fix this type of slime trails I used this recipie:

Find the linedef that seems to be the problem in an editor.
Verify it has been split by finding a seg with an offset other than 0 that references this linedef.
Go through the list of segs in Slade, find the start and end vertices, get coordinates from the vertexes data structure.
Compute all the correct angles based on the coords of the two vertices per seg.
Update the segs entry with Slade or another editor with the (usually) 4 new values. More if the line has been split more than once.

This will usually be two vertices that are sharded with linedefs and one that is not shared with a linedef and has a higher number. This is due to node build splitting adding new vertices at the end of the vertices list,  and those naturally have higher numbers. For Linedef 616 on map09, the vertices were 496, 497 and 566. 566 is then the one added by the node builder. Almost all vertices in the original maps are on a grid of 8, except the ones added as part of the node builder process.

The angle of split segs is also known to be wrong in BSP and Zennode. Many node builders are based on these two code bases and are most likely affected by this bug. ZokumBSP has a this fixed in version 1.0.10-beta11

Since this is a purely visual bug and the vertices aren't changed, I really doubt this would affect demo compatibility.

 

The tool I used to compute this was written in C(++), here's the source code:

#include <memory.h>
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>


#define M_PI                3.14159265358979323846

// taken from BSP
unsigned int ComputeAngle(int dx, int dy) {
        double w;
        w = (atan2( (double) dy , (double) dx) * (double)(65536/(M_PI*2)));
        if(w<0) w = (double)65536+w;
        return (unsigned) w;
}

int main ( int argc, const char *argv [] ) {

        if (argc != 5) {
                printf("Expected 4 arguments, startx starty endx endy\n");
                return 1;
        } else {
                int sx = atoi(argv[1]);
                int sy = atoi(argv[2]);
                int ex = atoi(argv[3]);
                int ey = atoi(argv[4]);

                int angle = ComputeAngle(ex - sx, ey - sy);
                int backside = (angle + 32768) % 65536;

                int sladeAngle = angle;
                int sladeBackside = backside;

                if (angle > 32767) {
                        sladeAngle = angle - 65536;
                }
                if (backside > 32767) {
                        sladeBackside = backside - 65536;
                }
                printf("Frontside angle: %5d. Backside %5d\n", angle, backside);
                printf("Signed BAM:      %5d.          %5d\n", sladeAngle, sladeBackside);
        }
}

Compile with gcc -lm bamutil.cpp

Signed BAM is the format Slade expects. Simply run it with 4 vertex coordinate numbers as input to get the front and backside angles of that line. Here's an example of what it should look like:

./a.out 1359 -259 1344 -256
Frontside angle: 30709. Backside 63477
Signed BAM:      30709.          -2059

 

Edited June 9, 2018 by zokum

[Linguica]

Is it really possible that in 24 years no one ever noticed that node builders didn't properly update the "angle" field of a seg when splitting it?

[zokum]

58 minutes ago, Linguica said:

Is it really possible that in 24 years no one ever noticed that node builders didn't properly update the "angle" field of a seg when splitting it?

Yes. It seems both ZenNode, BSP and DoomBSP gets it wrong. ZokumBSP already has a fix in place, and since the "cat" is out of the bag, i'll release a public beta with the fix in place.

Here it is:

http://doom2.net/zokum/zokumbsp/releases/zokumbsp-1.0.10-beta11-win32-mingw.zip

Please note that the previous beta 10 had a minor bug in it, leftover from some testing I did. Beta 11 should work better :)

Edited June 8, 2018 by zokum

[Linguica]

Here is an omgifol script to rebuild seg angles for all segs in a map. This is not particularly well tested.

 

from __future__ import print_function
from sys import argv
from omg import *
from omg.mapedit import *
import math

def newsegs(map):
    ed = MapEditor(map)
    for seg in ed.segs:
        seg.angle = angle((ed.vertexes[seg.vx_b].x - ed.vertexes[seg.vx_a].x),
                          (ed.vertexes[seg.vx_b].y - ed.vertexes[seg.vx_a].y))
    return ed.to_lumps()

def angle(dx, dy):
    w = math.atan2(dy, dx) * (65536/(math.pi*2))
    if (w < 0):
        w = 65536 + w
    return w

def main(args):
    if (len(args) < 2):
        print("    Omgifol script: recalculate seg angles\n")
        print("    Usage:")
        print("    newsegs.py input.wad output.wad [pattern]\n")
        print("    Recalculate seg angles on all maps or those whose name match the given pattern")
        print("    (eg E?M4 or MAP*).")
    else:
        print("Loading %s..." % args[0])
        inwad = WAD()
        outwad = WAD()
        inwad.from_file(args[0])
        pattern = "*"
        if (len(args) == 3):
            pattern = args[2]
        for name in inwad.maps.find(pattern):
            print("Rebuilding seg angles for %s" % name)
            outwad.maps[name] = newsegs(inwad.maps[name])
        print("Saving %s..." % args[1])
        outwad.to_file(args[1])

if __name__ == "__main__": main(argv[1:])

 

[esselfortium]

Woah, that seems like a huge revelation. I'm continually amazed by the new things people are still discovering about Doom nearly 25 years later.

[riderr3]

Bravo! That's a huge cause for moving to ZokumBSP. Except the fact that GZDB-BF does not support this BSP...

[zokum]

@riderr3: It's supported in Doombuilder X. Besides, you can just rename zokumbsp.exe to zennode.exe and it should work just fine. It's backwards compatible.

[Linguica]

We should point out that this does not appear to fix the E1M1 slime trail.

[zokum]

1 minute ago, Linguica said:

We should point out that this does not appear to fix the E1M1 slime trail.

Yeah, it only seems to fix one kind of slime trail. As a bonus, split segs (walls) should now be rendered more accuratly.

[kb1]

4 hours ago, zokum said:

Yes. It seems both ZenNode, BSP and DoomBSP gets it wrong. ZokumBSP already has a fix in place, and since the "cat" is out of the bag, i'll release a public beta with the fix in place.

Here it is:

http://doom2.net/zokum/zokumbsp/releases/zokumbsp-1.0.10-beta11-win32-mingw.zip

Please note that the previous beta 10 had a minor bug in it, leftover from some testing I did. Beta 11 should work better :)

Wow, great work! Doom's looking better and better!

 

2 hours ago, Linguica said:

We should point out that this does not appear to fix the E1M1 slime trail.

Maybe that slime trail is the fractional intercept issue, as it's the other half of the equation. The angle fix should bring the E1M1 issue into high relief, and make the math easier to investigate.

[zokum]

1 hour ago, kb1 said:

Wow, great work! Doom's looking better and better!

 

Maybe that slime trail is the fractional intercept issue, as it's the other half of the equation. The angle fix should bring the E1M1 issue into high relief, and make the math easier to investigate.

The e1m1 one is a true slime trail. The map09 is a different problem as far as I can tell. True slime trails manifest as strips of the floor or ceiling texture being rendered. The problem on map09 is caused by the angle being wrong and the seg being viewed almost parallell to the player's line of sight. Since the precomputed angle is wrong, the resulting texture rendering is also wrong. This type of error needs a new name, it's not a slime trail at all.

"Bad seg angle" might be an ok name for this map09 problem.

Edited June 8, 2018 by zokum

[kb1]

Good find. For a long time, I think, people have been using these tools, just assuming that they were doing the right thing. Thanks for questioning that assumption. We're really moving towards exorcising the remaining stubborn bugs in Doom, and it's only taken a quarter century :)

 

The next step is to fix the angles upon port map load, to make the "bad angle" issue disappear. I'm pretty sure it doesn't affect sync in any way - it's only used by the renderer.

Edited June 8, 2018 by kb1

[zokum]

Recomputing all the angles would probably be nice. A lot of the id-computed angles are off by 1 BAM. I haven't looked into what is mathematically correct, but 1 BAM is a fairly low error in any case. It might be something as simple as a higher precision algorithm is used today for computing the angles than what DoomBSP had in 1993.

I wonder how many other maps than map09 suffer from this error, and how many pwads. Maybe @Linguica could conjure up some stats and locations of the troublesome spots with his omgiflol script for doom.wad and doom2.wad. It shouldn't be that hard to output the sector and linedef # of an affected seg. Maybe someone could do some before and after screenshots of fixed rendering.

I think segs have to be really short for this to actually matter rendering wise in an easily noticable way. Wall rendering should change slightly on many walls though, would be interesting to see if there's a noticable difference.

[kb1]

What is most correct is, of course, what renders the best. I'm thinking about adding a couple cheats to my port: Recalc angles using round-to-zero, and recalc using round-to-nearest, and just trying it in various places. This function could also output statistics of the most-incorrect angle in the map, which could tell you where to look, and how widespread the issue is.

 

If this empirical testing provides some solid conclusions, the recalc could become a standard map loading task, which would be most convenient. It's pretty exciting to be crushing one more Doom rendering bug!

[zokum]

Round to nearest will give the best result. A two-sided linedef like on the star structure on map09 can be viewed from both sides. So if you were able to "hide" any imperfection better on one side, you will make it more obvious when viewed from the other side (180 degrees).

The precision on angles is quite good and this was only a problem on short lines. With a round to nearest int, the error is at most 0.5 / 65536. The error on the star structure were over 500 BAMs. That means the angle was off by over 1000 times the worst theoretical error when computed correctly.

With longer lines the deviation would naturally be smaller and lowering the chance of bad rendering. Over a certain length the problem most likely goes away even if the angle is slightly off.

A lot of lines in the game are off by 1 BAM, most likely due to rounding / different algorithms. This isn't noticable as far as I can tell, but might be on really long lines, I haven't checked. Just use lrint() with bsp's algorithm for computing angles. The one ZenNode used was a lot less readable.

Edited June 12, 2018 by zokum

[kb1]

What you don't want is that "accounting rounding" stuff (or whatever it's called) where 2.5 ~= 3, and 3.5 ~= 3 (odd rounds up, even rounds down), or I may have it backwards. Int(Value + 0.5) works for me. Wow, I didn't realize the star angle was that far off. I'd really like to know how it got that way. I don't really believe in HDD errors, though they do happen. More likely, some weird bug in DoomBSP shit the bed on the star. I wonder if a rebuild with DoomBSP would yield the same results.

 

Really, I want to know how prevalent the bug is: Is it a one in a million type thing, or does it occur everywhere? Is the bug limited to a single node builder, or every node builder derived for a certain bad node builder? But, the cat's out of the bag, now, huh?

[zokum]

ZenNode and BSP have similar errors. Most likely due to copying the behaviour of DoomBSP. The error is present on pretty much every map in the game, but whether it is noticable depends on a few factors. With a bit of tweaking, the omgiflol script in this thread can easily tell you how common this is. The error happens whenever a diagonal line is split and the intersection is not on an integer coordinate. This is a fairly  common occurence, but it will only cause problems when one ends up with short segs as the rounding error is generally bigger then.

[andrewj]

Boom and MBF contain code to detect when a seg vertex is "off" a linedef, and to correct the position to be "on" the linedef.  For MBF, see the P_RemoveSlimeTrails() function in p_setup.c.

 

Interestingly, neither of them fix the angle.  Hence it is quite possible that if a node builder sets the "angle" to be exactly correct for a seg, then the code in Boom and MBF (and other ports that adopted it) will now be producing segs with a bad angle, and causing the same issue you were trying to fix.

[zokum]

As far as I understand, most ports do not use the angle field. When moving the vertex, it would be logical to assume the precomputed angle can no longer be counted on to be correct. I could be wrong, but from what I have seen so far, it seems to have been generally assumed that the angle fits the seg, not the parent linedef.