Help needed: Slime trails in the original IWADs.

I am working on a small project related to the computed angles stored in the segs lump for each map. My hypothesis is that using angles based on the linedef instead of the seg can cause problems when a linedef is split into several segs due to the partition line crossing the linedef.

To make it a bit easier to understand. Let's assume we have a linedef going from 0,0 to 9,1. If we were to split this into two and round it to the nearest integer, we might end up with a linedef segment 1 going from 0,0 to 4,0 and segment 2 going from 4,0 to 9,1.

I want to know if doomers out there could list any other slime trails other than the e1m1 and map09 ones in the original maps, Doom 2 preferably. I want to check and see if any of them are due to problematic angle values. It should be noted that most source ports have various tweaks that fixes slime trails, so this is only really possible to find in source ports that haven't modified the rendering code much. I suggest doom2.exe or Chocolate Doom.

I also hope to update the wiki with a bigger list of known slime trails and maybe expanding on the article. Even if it turns out this hypothesis is false, that is important information for the wiki.

The question I eventually want answered is: What should the value of the angle that is precomputed during the nodebuilding be based on? Should SEGS have their angle from the linedef, or should they have the angle from the seg line? ZokumBSP, based on ZenNode currently, uses the angle from the linedef. In 1.0.10 there will be an option to instead use the angle that corresponds to the direction of the seg. It should be noted that the "error" in the angle is usually pretty low, but that it can be quite high on short segs. I've seen errors of over 500 BAMs (binary angle measurement, doom's internal format for degrees). Doom uses 16bit precision on the angle, so an angle of 512 is about 2.8 degrees in the circle is 360 degrees system.

In general longer lines get smaller errors due to there being less loss of precision when converting vertex-coordinates to integer values. The angle value of a line going from 0,0 to 1,128 will hardly change if split into a line going from say 0,0 to 0,64 and 0,64 to 1,128.

As a reference for what a badly computed angle looks like I have modified zokumbsp to add 256 to every angle in the map for idmap01.wad. That error will be pretty noticable on long segments. Have a look at it and you'll see why I think there might be cases where the wrong angle might lead to slime trails.

I had to rebuild the map, here's my rebuild data:


Here's a link to the file. http://oppetid.no/zokum/doom/idmap01x.wad (Update: fixed permissions on the file.)

If you have problems finding slime trails in this map, look at the BFG area.

5 minutes ago, zokum said:

I want to know if people know about any other slime trails other than the e1m1 and map09 ones.

The Map09 "slime trail" is a little more complex...

Yeah, I know, about map09 being a bit odd. That is why I needed other slime trails. Slime trails seem to be several different problems that all look similar visually. It would be nice to get all of ths information into the wiki.

v1.9 E1M5 star secret

Map30 Icon of Sin wall

That's all I can remember right now.

I think the big issue is when a split creates an intersection point with coordinates that have a large fractional component. These coordinates are rounded when saved, which creates a gap. At one time, I had considered adding or subtracting 0.5 before rounding, in the direction towards the split, theorizing that overlay was better than a gap.

Another idea is to reject splits that generate a large fractional component in either the X or Y coordinate. This might require trial and error, or starting split testing at integral intersections and moving outwards.

I am interested to know the results of your experimentation, and I am encouraged to know that someone is taking a fresh look at the process, at a microscopic level of detail.

26 minutes ago, kb1 said:

v1.9 E1M5 star secret

Map30 Icon of Sin wall

 

That's all I can remember right now.

I couldn't find anything on map30. The closest I got was the odd looking wall that portrudes 2 units out and adds a 2px unit wall.

There's a topic about the map30 slime trail. If I remember correctly, it's a full screen slime trail, near the left edge of the Icon of Sin. Can't say I've seen it myself, but I haven't yet looked.

I think they can be detected programmatically, by calculating the floating-point intersection point and comparing it to the segs, or even:

MAX((IntersectionPointX) - INT(IntersectionPointX), (IntersectionPointY) - INT(IntersectionPointY))

The larger the number, the greater chance of there being a slime trail. And, if it's >= 0.5, the rounding mode used in the node builder might make a big difference. Comparing a well-calculated intersection point to the actual segs may reveal that they were rounded to zero, which could cause them to be off by almost an entire unit.

I can't remember: Do the segs involved in a split share endpoints? I do know that the renderer considers the pixel's center to be at the upper-left corner (or upper right if the texture is being drawn right-to-left.) This may be enough to exasperate the situation. Can you tell?: I'd love to be researching this myself :)

Good luck!

I haven't looked into what rounding doombsp uses. ZenNode simply calls lrint(). Rounding to the nearest integer instead of flooring is a fairly basic operation that would yield better accuracy, so I doubt Carmack screwed it up.

Split segs usually share end/start points, but it isn't actually enforced in any way. The engine has no concept of a split, only segs with a non-0 texture offset.

1 hour ago, zokum said:

I haven't looked into what rounding doombsp uses. ZenNode simply calls lrint(). Rounding to the nearest integer instead of flooring is a fairly basic operation that would yield better accuracy, so I doubt Carmack screwed it up.

I don't think I'd consider it a "screw-up" either way, and, we know that slime trails are real. At this stage, the question is: How can we improve the situation? It may have been required to truncate the coords, for some mundane reason - I can't claim to know either way. But it's worth investigating.

Quote

Split segs usually share end/start points, but it isn't actually enforced in any way. The engine has no concept of a split, only segs with a non-0 texture offset.

No, the engine doesn't know about splits, but it does use the results of splits, and it assumes that they have been done properly.

My guess is that, while round to nearest may be the closest possible, mathematically, that may not do enough to solve slime trails. Most likely, the split lines used must be chosen carefully to minimize the fractional component of the intersection points, which may result in a less than ideal tree, and may make the process take an excessive amount of time. A "High quality" slow build option could alleviate the latter issue. Like most things in life, there's a trade-off to consider. Killough's work in BSP included a heuristic for avoiding splits that caused excessive visplanes, and another to minimize splits that caused slime trails. I don't know how well they worked.

The first thing to do is, of course, to fully understand what specifically causes each type of slime trail. This will open the door to what can be done to reduce/eliminate the problem.

My suggestion, (calculating the intercepts and comparing them to the segs) was proposed as a tool to automate the finding slime trails in published wads. It was simply an idea to help you find slime trails, to assist in your investigation.

Please note that some ports use the line angle, and others use the seg angle. I don't know which is which, but I do know that ZDoom used a different one than vanilla used. In fact, for a short while, ZDBSP did not populate both angles, causing maps to fail in some ports, but play fine with ZDoom. This issue was soon fixed.

I wasn't aware that these angles were often a bit different - that's interesting. It would be interesting to add an "angle bump" keyboard bind into a source port, so the effect of the angle could be studied in real-time. Unfortunately, as you state, angle precision is bad, just like integer coord round-off is bad. Neither of those can be improved with vanilla-format map data structs. Because of this, I still believe that the only remedy is choosing split lines where each intersection occurs on or near integer coordinates.

EDIT: Oops, I was thinking of Map09's star, not E1M5's.

Actually, the precision on the angle is quite good. There are 65536 different values for an angle. This will only turn problematic on really long walls that are also diagonal and using coordinates that don't map well to the angle computed. And in most cases, such walls will have a split and this will usually greatly reduce the problem.

It could be possible to have a nodebuilder split very long segments and reduce the problem, but I have yet to come over a map where lack of BAM precision is a problem, but then again, I have never been looking for it.

I did look into the map09 star. Turns out the angles on the split seg in there is recomputed per seg. This means that ZenNode does things differently from DoomBSP. I will be changing ZokumBSP to behave like DoomBSP, since it seems to be the correct way anyway.

As for the high-quality pick near-int intersection algorithm, I think BSP already does this by adding it as another criteria for partition lines. It will rate the partition line poorly IF it leads to splits that are less than ideal precision wise. It might end up having to do that equally bad splits further down the line, it has no backtracking.

I could probably add this as a 4th criteria in ZokumBSPs partition algorithm.