What bug is Carmack describing here?

[Linguica]

I'm looking at the official Doom strategy guide and there's a weird little chapter where Carmack goes into some detail about the engine. He mentions this:



His description of the problem - a line being drawn almost parallel to the player's viewpoint, and overflowing the range available - sounds like the wall wiggle bug, but his description of the symptom (a column stretching all the way across the screen) sounds more like the slime trail bug. So I assumed Carmack was just mixing up two different bugs here. But then he goes on to say:



This is clearly describing the slime trail bug. So what's the first bug he's describing?

[FireFish]

that first description resembles something i could see one of my experimental wads (the orange sky wad thing). I thought it was a slimetrail. a 1 pixel wide (or so) slime trail like line caused by the stairs in the opening.

[Zed]

This question and the fact that this thread hasn't received a "full" answer yet, makes me wonder something.

How hard is it to find this kind of bugs? I'm obviously no expert, but if things like the one Ling is describing are still undocumented 20+ years after Doom, that makes me think there may be some more undocumented oddities in the Doom engine.

[Ryback]

Is he describing something like this? (You can't see it very well in this screenshot, but the lower half of the black 1px column is a shimmering HOM effect.)

[Linguica]

I decided to actually check out this bit of the slime trail wiki page:

A slime trail can occasionally be so severe as to span the entire screen, in which case the floor texture can be seen to meet the ceiling texture in the center of the screen. This type of slime trail is very rare, but one can be spied when the view angle is tangent to one of the sides of the star near the exit of Doom II MAP09: The Pit.

So here it is in Chocolate Doom:



So there's that. HOWEVER, the description is wrong - you can sort of tell that the bottom part of the slime trail isn't a floor texture, but is in fact the wall texture on the side of the star, stretched severely. At certain angles it even only stretches partway to the bottom of the screen. This is almost certainly the bug Carmack is describing, but I don't know what causes it or if it's fundamentally a different bug than the "normal" slime trail effect.

edit: and here it is in PrBoom-plus for comparison:



Here you can see it doesn't even go to the bottom of the screen. FWIW, the bug was MUCH harder to view in PrBoom-plus, and I never got the classic slime trail effect on the upper half of the screen.

[Maes]

Well, sometimes certain bugs are mistaken for other, similar bugs but with different causes. For example, there are two kinds of Tutti Frutti bugs with different causes, and different solutions, yet only one of them is ever accurately described, even in the wikis.

[Linguica]

The source code includes a comment that sounds like Carmack was trying to fix it but gave up:

if (stop > start )
{
	ds_p->scale2 = R_ScaleFromGlobalAngle (viewangle + xtoviewangle[stop]);
	ds_p->scalestep = rw_scalestep = (ds_p->scale2 - rw_scale) / (stop-start);
}
else
{
	// UNUSED: try to fix the stretched line bug
#if 0
	if (rw_distance < FRACUNIT/2)
	{
		fixed_t trx,try;
		fixed_t gxt,gyt;
		trx = curline->v1->x - viewx;
		try = curline->v1->y - viewy;
		gxt = FixedMul(trx,viewcos);
		gyt = -FixedMul(try,viewsin);
		ds_p->scale1 = FixedDiv(projection, gxt-gyt)<<detailshift;
	}
#endif
	ds_p->scale2 = ds_p->scale1;
}

[printz]

Interesting. Does this possibly rare bug do nasty undefined stuff, or is it harmlessly cosmetic?

[Linguica]

Seems cosmetic.

It's weird, because the usual cause of a wrongly sized wall texture, aka the "wall wiggle" bug or whatever the proper term for it is, generally only happens when you have a line stretching from in front of the player to behind the player. Here, however, the line is entirely in front of the player, so the code shouldn't go crazy trying to draw it.

This is just a guess, but it does seem like it's related to the slime trail bug in how it arises. I'm assuming that a generated vertice right there has a rounding error, so that at this point, there's an open subsector that causes a slime trail. However, there's also a wall being drawn along one of the segs next to the discontinuity in the subsector, and the engine somehow doesn't know how to scale the wall because the open subsector. So it breaks down and draws a stretched out line for that little bit of wall texture.

I don't have a real grasp on how the slime trail bug manifests in terms of the code called, so it's difficult for me to try and figure it out further.

[Linguica]

Here's a GIF from Chocolate Doom, low resolution mode.



It almost looks like... imagine if the nearly-vertical line on the side of the star actually continued all the way to the player's position. There is a sliver of texture that appears to be drawn in the proper position / scale as if that were the case. You can see the top of the texture move down, and the flat bleed trailing behind it to fill in the space.

I had been wondering if the engine was doing the thing where it maxed out the scaling factor at 64*FRACUNIT, but the texture sliver does not look nearly stretched out enough for that to be the case. So I don't actually know if this is the bug Carmack was referencing, since he explicitly says that the column goes to the maximum possible scale.

[Szymanski]

I've seen these quite a few times but always assumed they were a node builder issue, it's difficult to tell

[fabian]

Linguica said:

Here you can see it doesn't even go to the bottom of the screen. FWIW, the bug was MUCH harder to view in PrBoom-plus, and I never got the classic slime trail effect on the upper half of the screen.

Well, maybe this is because PrBoom-Plus has the following code in P_SetupLevel() in p_setup.c:

  if (compatibility_level>=lxdoom_1_compatibility || prboom_comp[PC_REMOVE_SLIME_TRAILS].state)
    P_RemoveSlimeTrails();    // killough 10/98: remove slime trails from wad

This code moves vertices towards their corresponding linedefs in order to close open subsectors and it is pretty successful with it. If you try again with "-complevel 2" the slime trails should be as visible as with Chocolate Doom.

[kb1]

I'm pretty sure it's related to the wall wiggle bug (the star, I mean). It doesn't have to have one vertex behind the player. Basically, by looking directly down an arm of the star, you're asking the engine to draw a 0-width, or nearly-0-width texture.

One has to be careful fixing this bug, to not cause vertical HOM lines (slime trails). The fix involves making sure you either don't attempt to draw this line, or just draw one vertical sliver (not two). And, draw it using the proper height, by special-casing the renderer.

The "FixSlimeTrails" function doesn't help in this case, the vertices are fine, you just can't draw a 0-width wall.

I'll look into it when I get some time.

[Linguica]

Right, we know that Carmack was experimenting with some special-case code to try and fix it.

#if 0
	if (rw_distance < FRACUNIT/2)
	{
		fixed_t trx,try;
		fixed_t gxt,gyt;
		trx = curline->v1->x - viewx;
		try = curline->v1->y - viewy;
		gxt = FixedMul(trx,viewcos);
		gyt = -FixedMul(try,viewsin);
		ds_p->scale1 = FixedDiv(projection, gxt-gyt)<<detailshift;
	}
#endif

This turns out to be very similar to code in R_ProjectSprite:

 // transform the origin point
tr_x = thing->x - viewx;
tr_y = thing->y - viewy;

gxt = FixedMul(tr_x,viewcos);
gyt = -FixedMul(tr_y,viewsin);

tz = gxt-gyt;

// thing is behind view plane?
if (tz < MINZ)
	return;

xscale = FixedDiv(projection, tz);

So I guess Carmack was intending to try and reuse the code for scaling things onscreen to the proper size in order to scale thin slivers of walls, but it didn't work right for whatever reason.

[fabian]

Maybe this is some kind of a round-off error. The segs rendered to the visible left and right of the line in question do not touch but leave a 1px wide gap, which in turn is going to get filled by the line in question. But this line is so narrow that its rendered width is close to 0px, so from a certain perspective the renderer decides not to draw it at all and the 1px HOM becomes visible.

Is this what you mean?

[Linguica]

fabian said:

Is this what you mean?

Look at the animated GIF. You can tell that the one-pixel-wide gap is drawing a small sliver of METAL6, but in the totally wrong position. That's not just a HOM or a slime trail, and the engine isn't failing to render the line - the engine *is* drawing METAL6, just in the wrong place, and where it draws it varies based on small changes in view angle.

[kb1]

Ok, I think I know more about it now, but not enough to fix it yet. What I can say is that, no, it's not exactly related to the Wiggle Fix. And, I am convinced that the problem is in R_AddLine, or one of the subroutines it calls.

The following points are only educated guesses - I have not found time to investigate it enough to say for sure. Maybe someone else can do a "SlimeFix" solution like the WiggleFix.

Ok, here's those points:

* R_AddLine exits early, based on a number of conditions.
* R_AddLine uses Doom's crappy pre-calculated angle lookups. Remember the fact that DoomGuy cannot walk down an axis exactly, because of the inaccuracy of the angle lookups?
* If I muck around with those early exit conditions, I can degrade/improve the slime line.
* In PrBoom+, Entryway made a new function for more accurate rendering:

// e6y
// The precision of the code above (R_PointToAngle2) is abysmal so use the CRT atan2 function instead!

// FIXME - use of this function should be disabled on architectures with
// poor floating point support! Imagine how slow this would be on ARM, say.

angle_t R_PointToAngleEx(fixed_t x, fixed_t y)
{
	static int old_y_viewy;
	static int old_x_viewx;
	static int old_result;

	int y_viewy = y - viewy;
	int x_viewx = x - viewx;

	if (old_y_viewy != y_viewy || old_x_viewx != x_viewx)
	{
		old_y_viewy = y_viewy;
		old_x_viewx = x_viewx;

		old_result = (int)(atan2(y_viewy, x_viewx) * ANG180/M_PI);
	}
	return old_result;
}

This code does an expensive atan2 call, but it vastly improves the issue seen in E1M1, right in front of the exit room, when the light flickers, and you can see the floor "wiggle", where the lit and unlit visplanes meet. I think this code is the reason that the slime line we are discussing is much less of an issue in PrBoom+.

I feel strongly that this bug can be fixed, by improving the math in and around R_AddLine.

The slime line you're seeing is flat being drawn because the wall was not properly clipped away. For someone looking to try to fix it, let me try to put my thoughts in words:

In the room with the star, notice the star wall lines furthest from the player. The walls are not drawn at all, because they are on the back side. However, Doom has to consider them, to properly draw the flat on top of the star.

I think what's happening is that the player is standing on "one side of the faulty angle lookup", and the star wall is "on the other side". The angles are just far off enough that Doom does not properly mark the clip array.

Remember, most any problem with flat drawing is really a problem with wall drawing, cause flats are used to fill in gaps where wall is not drawn. Which, if you think about it, is quite brilliant :) I've tried my hand at many different software 3d render methods, and most all of them had seams and gaps that were very difficult to avoid. But, with Doom's flat drawing method, 99.9% of all of that is handled.

The best way to fix this is to make a save game while looking at one of these slime trails, then add tons of debugging (log to file) around the drawing of those walls. That should make the problem stick out like a sore thumb.

Unfortunately, I don't have the time to do it now, but I'll get to it eventually, if no one else does.

[Use]

Really loving these Linguica investigative Carmack-fuckup threads.

[kb1]

Use3D said:

Really loving these Linguica investigative Carmack-fuckup threads.

Carmack didn't fuck up. He used what he had to work with (his brain, 'cause none of this existed before), and proceeded to create a blindingly-fast, full-screen textured-mapped 3d engine that many millions loved and still love to this day. And, he did it pretty quickly.

Everything has bugs, but I can't complain. I know it was meant to be a joke, but, seriously, has anyone ever stopped to think about just how marvelous it all was and is? That's an awful lot of pixels. Just drawing static full-screen bitmaps was a chore on those old processors. And he's shading and stretching them, doing hidden surface removal, and projecting them in 3d. Hell, Carmack's fuckups work better than most people's finished products :)

And, sure, one can look back and gawk at all of the hard-coded limits in the engine. But, here's the thing: Their goal was to develop and sell a product. And his engine does that very thing pretty well. And, for the user-made limit-breaking levels, he released the source for us to remove those limits.

I can't complain. By the way, I love these threads too.

[Quasar]

This is not a problem with flat drawing, we've established that several times now.

[kb1]

Quasar said:

This is not a problem with flat drawing, we've established that several times now.

Correct, Doom is failing to draw/consider the end sliver of a wall that's nearly perpendicular to the view angle. And, the trick is going to involve either detecting and special-casing the issue, or improving precision, without causing undesirable side-effects.

If no one beats me to it, I'll eventually be able to understand exactly what's happening, and suggest a fix, but I just don't have the time at the moment. I'm convinced it's in R_AddLine. Takers, anyone?

[Linguica]

I hacked the Chocolate Doom source to add a screenshot dump at the start of R_RenderSegLoop and got the following:



So yeah, the "slime trail" at the bottom is clearly a line being drawn wrong. You can see this line is actually 2 units wide, however - the left half seems to be drawn correctly, but the right half is all screwed up.

Then I added some output code to R_StoreWallRange and got:

sidedef = 46288388, start = 108, stop = 148, scale1 = 91104, scale2 = 43992
sidedef = 46288428, start = 149, stop = 219, scale1 = 42891, scale2 = 36530
sidedef = 46288348, start = 106, stop = 107, scale1 = 80801, scale2 = 148591

(etc). Yeah those sidedef values are just memory addresses (I think) but whatever. So clearly on the third line, you can see scale2 is way bigger than it ought to be, but not, like, incredibly big. (Actually, both scale1 and scale2 are bigger than they ought to be.) After adding some more code it looks like it's arising from the LUT (again) in that the game is calculating a sine angle extremely close to 0, so the granular LUT value is off. But that still doesn't really explain why it only happens on *this* line.

Oh and I neglected to mention the *fourth* sidedef that the game tries to draw, which comes out like:

sidedef = 49106416, start = 106, stop = 106, scale1 = 256, scale2 = 256

So it's starting and stopping at x=106, which is where the previous line started, and it's... incredibly small?

[Linguica]

Going further, this line is supposed to start at 1280, -256 and end at 1152, -288. I thought I should just check and I found that instead, the game thinks the line goes from 1265, -259 to 1152, -288. Same end point but the start point is different.



My first thought: OK, the game added additional vertices when building the nodes, that's what I'm seeing. But then I checked the subsectors in the map:



?? Why is GZDoom Builder showing that there isn't a subsector split? Is it there or isn't it there?

[kb1]

When you wrote "Where game thinks", is that line really split there? That could be a clue. Ok, you got me interested - I may just have to blow off some real work, heh heh :)

scale1 is the left-most sliver, and scale2 is the right-most. So, in that scale2 = 148591 line, your numbers say that the line is getting bigger from left to right, by a large amount. That's definitely the clue, but, why? 80801 actually looks about right, and you can see the left sliver is about the right height, though it looks like it starts too high up. Even the right sliver has the right texture on it, it's just too tall.

I would like to see the corresponding R_AddLine values in that output, alongside the R_StoreWallRange values.

Unfortunately, between R_PointToAngle, and viewangletox[], we have some very ugly values to work with. Replacing it with proper trig would probably fix it, but would definitely slow it down.

Maybe it's possible to detect this specific case, and have a separate LUT for all angles near 90 degrees, with a much higher precision. Or just do full floating-point trig. Shouldn't slow things down much if detected properly, since it's such a rare case. Again, I'd like to know the angles involved (in R_AddLine), and see just how far off they really are.

It makes sense that problems would occur near 90 degrees, because the angle and precision become much more critical near 90 degrees, and the scale values change much quicker and larger when you approach 90. And, again, it's those off angles that prevent DoomGuy from walking exactly along an axis, so, yes, it makes sense. A high-precision alternate set of lookup table for, say, 85 to 90 degrees or so may be the answer.

You may even convince Doom that the angle is, say 88 degress when it's really closer to 90 - that may be enough fudging to get it to just fill in the gap, without a lot of extra work.

[Linguica]

WTF, is this GZDoom Builder plugin wrong?

GZDoom Builder view of root node division:



doomwiki illustration of E1M1 root node division:



That's not even remotely close. The hell?

edit oh my GOD does GZDoom Builder AUTOMATICALLY rebuild nodes when you use the node viewer? What the fuck?

[Linguica]

Yup, I think the node *VIEWER* automatically functions as a node *BUILDER*. Great.

[Linguica]

Turns out I partially fixed this bug basically by accident: http://www.doomworld.com/vb/post/1340126