PRBOOM Graphical Glitches

Linguica said:

If we increase it to, say, 256*FRACUNIT, we're just making the Doom engine clip the scaling earlier and prevent the scaling factor from getting quite as huge and from making the fairly coarse sine and tangent lookup tables go crazy. This can cause problems elsewhere but that's another kettle of fish.

prboom+ on Voodoo Guns after replacing 64 with 256:

Thank God EE doesn't have that routine in its code any more. What a cluster.

Quasar said:

Thank God EE doesn't have that routine in its code any more. What a cluster.

I know that this is a bit off topic, but I've been looking for a place to download the Eternity engine, but all of the downloads on the official website 404 whenever I try to use them.
Any idea where I can find it?

It's pinned in the Eternity subforum here:
http://www.doomworld.com/vb/eternity/67069-eternity-engine-3-40-46-bifrost/

Best software renderer!

Also I wasn't really thinking about this aspect, but because num in PrBoom+ is

num = FixedMul(projectiony, finesine[angleb>>ANGLETOFINESHIFT]);

Then this problem really is directly tied to your resolution. (Screen size too, I guess...) Which seems like a double whammy: not only are you at a higher resolution so you can notice the problem more readily, but being at that higher resolution actually makes the problem even more extreme.

Seems like you could replace projectiony (which is the resolution scaling factor) with a value that corresponds to a 320x200 resolution, and then once you've calculated the scaling factor, multiply it by another high-resolution scaling factor. That way the value would at least clip the same amount as in the original exe, right?

Yup, it's definitely MUCH worse in higher resolutions.

I am really beginning to think that at least when it comes to very high resolutions, it's a fool's errand to try and stick with the original Doom rendering code at all. glBoom isn't perfectly faithful to the original renderer, but it's pretty darn close, and it sidesteps so many of these dumb issues that crop up when you try and make the software renderer do things it was never intended to do.

Actually, the software ZDoom renderer doesn't have this wiggling line problem, at least not anywhere near as badly. What is it doing instead?

Linguica said:

Actually, the software ZDoom renderer doesn't have this wiggling line problem, at least not anywhere near as badly. What is it doing instead?

Something completely different.

rh-log.txt:
January 30, 2001
- Fixed xtoviewangle generation in R_InitTextureMapping(). (It was phase
shifted 90 degrees)
- Removed R_ScaleFromGlobalAngle(), rw_distance, rw_angle1, and
rw_normalangle.

Now, from a simple grepping, it seems R_ScaleFromGlobalAngle() is only called at one place in Boom (well, two places, but they're next to each other): R_StoreWallRange()

  // calculate scale at both ends and step

  ds_p->scale1 = rw_scale =
    R_ScaleFromGlobalAngle (viewangle + xtoviewangle[start]);

  if (stop > start)
    {
      ds_p->scale2 = R_ScaleFromGlobalAngle (viewangle + xtoviewangle[stop]);
      ds_p->scalestep = rw_scalestep = (ds_p->scale2-rw_scale) / (stop-start);
    }
  else
    ds_p->scale2 = ds_p->scale1;

And that's where you'd have to look at what ZDoom is doing, because it still has R_StoreWallRange(). But it has become completely different from Doom's original or Boom's version. Notably, scale and step calculation no longer seems to be done within that function.

Yeah I am not even going to start trying to figure out the ZDoom code...

Really, without even getting into floating point stuff, seems like the easiest brute force solution would just be to make the value for scaling textures 64-bit instead of 32-bit. It wouldn't SOLVE the problem, but I don't even know what kind of obscene resolutions would be required to make it noticeable then.

It's interesting how painstakingly preserving the original rendering code actually leads to inaccurate/incorrect rendering. eg. PrBoom+ at 1600x1200 is demonstrably not just a scaled-up, more accurate version of the original at 320x200.

Yeah, at very high resolutions it gets totally crazy:



I'll also quote this explanation I gave elsewhere:

Without getting too much into it (lol), Doom doesn't have anything resembling a near clipping plane and will happily attempt to draw a wall infinitesimally close to the point singularity that is the camera. Doom always draws lines according to screen space, and when you're standing on top of a line, that basically means the engine is trying to draw the super janky line:

 
^                                                  ^
|                                                   |
|                                           start drawing here
all the way to here

It might be better if you imagine that line as having a middle texture like a grate or whatever, and that the engine is trying to draw the texture all the way across most of the player's screen. You can imagine that as you get towards the left edge of the screen, the scale of the line is OBSCENELY BIG, because it is like three nano-angstroms away from the player viewpoint. And the Doom engine uses normal integers that can't get nearly big enough, so it hits the scaling cap on the left side. And since the engine just interpolates the scale between the left edge and the right edge of the line when drawing it, that makes the line appear to be more sloped than it really is.

Here's a quick illustration:



And since PrBoom calculates the scaling factor with the screen resolution as a component, that means that the higher the resolution, the higher all the numbers are, and the more quickly and severely you hit the integer cap.

That is about what I remember.
Many of the table usages in the vanilla doom have all the table access details visible in each usage. In some places optimized into some other part of the expression. This results in strange adaptations in the expressions like the (90-x).

In the latest DoomLegacy I made macros to access these tables, which hides some of the table details and makes the math a little clearer.

When the line you are viewing goes right to the players feet, the denominator goes to 0. A divide by 0 would be program terminal so that must be prevented. Their means of coping with this is inadequate and leads to other display errors. Not going to get specific on anything here as everything depends upon whose version that you are viewing.

ABS() because COS is symmetrical but the cosine lookup in the tables is not and cannot allow negative numbers. Aside: But they actually do allow some negative number lookup in one table by adding an offset, but it has such a limited range it is barely usable.

The only sane way to look at the sine and cosine table lookups is to write a function or macro to do the SIN and COS accesses, with negative and large angle handling, and see how much of that code is present in the expression. You will find that trying to make do with one SIN access function leads to problems and choices because they optimized some of this table access code into the expression and some of the neighboring code too.

For what it's worth, Carmack kinda feels bad about it http://youtu.be/EaN4wUii0T0?t=1h1m

entryway said:

prboom+ on Voodoo Guns after replacing 64 with 256:[/B]

Gez said:
[B]Now, from a simple grepping, it seems R_ScaleFromGlobalAngle() is only called at one place in Boom (well, two places, but they're next to each other): R_StoreWallRange()

Andrey, has the animated screenshot that you have posted really been taken at 640x480 resolution?

Does it help if you increase the types for ds_p->scale1, ds_p->scale2, rw_scale, ds_p->scalestep and rw_scalestep to int64_t or will it simply overflow at another occasion?

bradharding said:

Yup! In fact, this fix has been in since v1.0. Changing the value to 1024 gives even better results, but unfortunately can cause an overflow. This overflow can result in part or all of the screen show a weird moire pattern, or a crash. I've tried fixing these overflows more recently by using a further little "hack" by kb1, discussed here: http://www.doomworld.com/vb/source-ports/38425-solution-to-wobbly-line-problem-that-doesnt-involve-build-code/. Seems to work for most levels.

Heh heh - you're brave! Didn't think anyone else would dare throw that code in their port, but, I gotta admit, it works pretty damn good! (Hope my code snippet provided enough clarity without actual source).

Basically, with the wiggle hack code, you're trading the floor wiggle, for a different kind of wall height wiggle, by dynamically "sliding" the fixed-point decimal to give you as much precision as you can get in 16.16 format. It's dynamic, in the sense that it self-adjusts to each level.

If it's set up right, it will actually prevent the overflow, in all but the most crazy levels (levels that would crap out in vanilla anyway).

At one time I was considering getting it to self-adjust per-frame, but it's just not worth it, especially when the real fix is obvious: Use floating point.

I have yet to convert over to floating-point, so I'm still using the wiggle hack. Glad to see that someone else is getting some use out of it! That made my day :)

Funny thing is: The wiggle problem is hardly noticeable at vanilla resolutions. Going hi-res pushes the bug into overdrive.

EDIT: You know, in thinking about this some more, I think an easier 'fix' (hack) is possible, while still using fixed-point: If the angle becomes steep, an inverse function could be used, that performs better when the line becomes parallel. The best analogy is the automap line drawer, which has separate routines, one for large X change, and one for large Y change.

If I get some time, I'll look into mocking it up, and see if an optimized fix is practical.

fabian said:

Andrey, has the animated screenshot that you have posted really been taken at 640x480 resolution?

Yes

fabian said:

Does it help if you increase the types for ds_p->scale1, ds_p->scale2, rw_scale, ds_p->scalestep and rw_scalestep to int64_t or will it simply overflow at another occasion?

No, it doesn't. You can check revision r4249 for seeing what I tried.

kb1 said:

Heh heh - you're brave! Didn't think anyone else would dare throw that code in their port, but, I gotta admit, it works pretty damn good!
...

LOL! This particular bug has annoyed me for a while, and your hack works quite well! It fixed a few overflows that I noticed in some maps, as well as one that caused a complete crash. My implementation is here.

... If I get some time, I'll look into mocking it up, and see if an optimized fix is practical. ...

That would be awesome!

entryway said:

No, it doesn't. You can check revision r4249 for seeing what I tried.

Hm, and yet it shows those rendering artifacts.

Do you know where it overflows?

Are these artifact map-specific (or, why did you choose to test with Voodoo guns)?

I am playing with 256*FRACUNIT for quite some time and have not yet seen such artifacts.

fabian said:

Do you know where it overflows?

No.

fabian said:

Are these artifact map-specific (or, why did you choose to test with Voodoo guns)?

I reverted because of bug report
http://sourceforge.net/p/prboom-plus/bugs/209/

Just tried kb1's 'hack'. Looks like it fixes issue on Voodoo Guns which is mentioned above.


Hell Ground, map06

Before:
https://dl.dropboxusercontent.com/u/235592644/clip/2014-09-09_21.37.25.png

After:
https://dl.dropboxusercontent.com/u/235592644/clip/2014-09-09_21.36.50.png

fabian said:

I am playing with 256*FRACUNIT for quite some time and have not yet seen such artifacts.

Forget about it. A crash in R_MapPlane has just been reported which was caused by an overflow due to this change, so I had to revert it.

entryway said:

Hell Ground, map06

Looks like an improvement, at least.

I wonder if the crash you're getting is genetically related to the numeric overflow crash? It's usually triggered by extremely tall areas, but extreme texture scales might also do the same thing.

In short, it causes the game to draw outside the framebuffer by forcing out-of-range values into the clipping arrays. There are three possible failure modes depending on how things align - a crash in R_DrawColumn, a crash in R_DrawSpan, or a massive memory corruption error in R_MakeSpans which will wipe out most of the BSS segment.

Yes, increasing the test from 64*FRACUNIT to 256*FRACUNIT reduces the maximum sector height difference to 1/4 original. By allowing the texture calculation to be 4x as large, yopu must compensate by changing the scale used: HEIGHTBITS (and, therefore heightunit). In vanilla, HEIGHTBITS is set to 12, which allows for 20.12 fixed point math - 20 integral bits, and 12 decimal bits. If you go from 64 to 256, you must compensate by reducing HEIGHTBITS to 10, which provides 22.10 fixed point math.

Please see the WiggleHack I posted in 2006, or, better yet, Brad's implementation posted above in this thread.

Essentially, it sets these variables automatically, increasing the 64*FRACUNIT, and correspondingly decreasing HEIGHTBITS, as much as possible, without creating the possibility of sector height difference overflow.

All of these factors are tied together: tall area overflow, texture scale overflow, steep view angle, and screen vertical resolution. They all work against each other. The real issue is that 32 bit integer math is just not enough. Carmack did a good job choosing 64*FRACUNIT, and HEIGHTBITS 12, because he was targetting 320x200 resolution, and vanilla Doom maps. You'll notice that in 320x200, you can barely see the bug at all. He balanced the numbers to give the best bang for the buck, with minimal wiggling, on average height levels.

If you implement the WiggleHack, and use it on a level with very tall height differences, you will see the wiggling move from the floor to the walls. Something's got to give - 32 bits is just not enough.


bradharding: I wanted to ask you what the (den >> 8) > 0 was for in your ScaleFromGlobalAngle? I think maybe I'm confused, cause here's your code, with the (den >> 8) > 0:

static fixed_t R_ScaleFromGlobalAngle(angle_t visangle)
{
 int anglea = ANG90 + visangle - viewangle;
 int angleb = ANG90 + visangle - rw_normalangle;
 int den = FixedMul(rw_distance, finesine[anglea >> ANGLETOFINESHIFT]);
 fixed_t num = FixedMul(projectiony, finesine[angleb >> ANGLETOFINESHIFT]);

 return ((den >> 8) > 0 && den > (num >> 16) ? ((num = FixedDiv(num, den)) > max_rwscale ?
  max_rwscale : MAX(256, num)) : max_rwscale);
}

And, here's what I got:

fixed_t R_ScaleFromGlobalAngle(angle_t visangle)
{
	int     anglea = ANG90 + (visangle - viewangle);
	int	angleb = ANG90 + (visangle - rw_normalangle);
	int	den = FixedMul(rw_distance, finesine[anglea >> ANGLETOFINESHIFT]);
	fixed_t num = FixedMul(projectiony, finesine[angleb >> ANGLETOFINESHIFT]);

	fixed_t scale;
	
	// [kb] fix the wobbly lines
	if (den > (num >> 16))
	{
		scale = FixedDiv(num, den);

		if (scale > max_rwscale)
			scale = max_rwscale;
		else if (scale < 256)
			scale = 256;
	}
	else
		scale = max_rwscale;

	return scale;
}

Maybe I'm being stupid, but it looks like it could be an important additional test. Does it maybe test for lines behind the viewer? I don't seem to need it in my port, but maybe I've corrected for it somewhere else, or maybe it is actually causing me issues? Any ideas? Did it come from Boom?

Linguica said:

Then this problem really is directly tied to your resolution

....

Seems like you could replace projectiony (which is the resolution scaling factor) with a value that corresponds to a 320x200 resolution, and then once you've calculated the scaling factor, multiply it by another high-resolution scaling factor. That way the value would at least clip the same amount as in the original exe, right?

A lot of things are resolution-dependent in the Doom engine, with the most infamous being the lighting: all ports with higher-than-vanilla resolutions need to apply some sort of hack to keep a factor being computed as if the screen resolution was still 320x200,otherwise lighting gets all funked up (very noticeable on MAP01 of Doom II, on the columns).

It's just that it's tempting to leave those SCREENWIDTH and SCREENHEIGHT constants everywhere....even if in some cases they were really not meant to be part of scalable factors.

@kb1: being that the renderer does not (?) affect gameplay, there could be 64-bit fixed-point ops defined for just a few special places. That's really a compromise between a full rewrite/floating point conversion, though.

kb1 said:

I wanted to ask you what the (den >> 8) > 0 was for in your ScaleFromGlobalAngle?

...

Maybe I'm being stupid, but it looks like it could be an important additional test. Does it maybe test for lines behind the viewer? I don't seem to need it in my port, but maybe I've corrected for it somewhere else, or maybe it is actually causing me issues? Any ideas? Did it come from Boom?

That extra test is something Nerve put into the Doom source, which can be seen here. The comment accompanying that test is:

// DHM - Nerve :: If the den is pretty much 0, don't try the divide

I'm not entirely sure if its necessary, and actually recently took it out again. It seems you have a much better idea of what's going on than I do :) so it may be worth keeping after all...

bradharding said:

That extra test is something Nerve put into the Doom source, which can be seen here. The comment accompanying that test is:

// DHM - Nerve :: If the den is pretty much 0, don't try the divide

I'm not entirely sure if its necessary, and actually recently took it out again. It seems you have a much better idea of what's going on than I do :) so it may be worth keeping after all...

Nah, I'm not an authority - WiggleHack is a product of empirical engineering (and lots of debugging :)

(made a double-post to write a book...)

Theory:
P_SetupWiggleFix calculates maximum adjacent sector height difference (which is when wall height overflow occurs) in the current level, and passes it to R_SetWiggleHack. This value (max_diff) can be between 0 and 65535, though you'd have to noclip to pass through a height difference > 32767.


The math: (at least, this is how I understand it)
In R_SetWiggleHack, max_diff is clamped between 256 and 65535. Now, to prevent overflow, your exponents must not exceed 31, for 32-bit math. So, here's the exponents:

In ScaleFromGlobalAngle, the calculation is clamped at 64*FRACUNIT, or (2^6)*FRACUNIT.

So, if we define:
clamp_exponent = 6
ScaleFromGlobalAngle_clamp = (2 ^ clamp_exponent) * FRACUNIT
HEIGHTBITS = 12

...the tallest sector height difference can be calculated roughly as follows:
MAX_USABLE_BITS = 31 (when using an int32 in a signed way)
max_height_bits = MAX_USABLE_BITS - (clamp_exponent + HEIGHTBITS) = 13

31 - (6 + HEIGHTBITS) = 13

...so, the tallest sector difference = 2^13, or 8192.

Changing only the ScaleFromGlobalAngle clamp:
Now, if you change the clamp to 256*FRACUNIT, the wiggle will be much improved, but your wall heights now must not exceed 2048:

31 - (8 + HEIGHTBITS) = 11
2^11 = 2048

...unless, you also change HEIGHTBITS from 12 to 10, restoring your max sector difference back to 8192. This does 3 things:

1. Gives you back the taller sector capabilities.
2. Reduces the "floor wiggle", which was the goal.
3. Increases the "wall wiggle", which is usually more forgivable.

Performance:
So, how well does the WiggleHack perform?

For levels with <= 256 unit adjacent sector height changes, the clamp is increased from 64*FRACUNIT, to 2048*FRACUNIT, with no change in HEIGHTBITS, so floor wiggle is all but eliminated, and wall wiggle is as it always was.

For levels with maximum adjacent sector height changes, the clamp is decreased from 64*FRACUNIT, to 16*FRACUNIT (yikes), but HEIGHTBITS is reduced to 9. This reduction in HEIGHTBITS actually allows the reduced clamp to still be effective, but now you start to see a new wiggle: "wall wiggle". However, the level is renderable!

Conclusions:
1. Using my WiggleHack code in your source port can greatly reduce the ugly rendering glitch that occurs when looking down a linedef at a steep angle.

2. The code is quite safe and can be dropped in to most ports as-is.

3. Allows the rendering of the maximum possible sector height deltas without crash.

4. Works with things like Legacy 3d floors too. Just be sure to replace all instances of the constants and vars that WiggleHack affects. Also, you'd need to adjust P_SetupWiggleFix to scan the 3d floor heights as well.

5. It's about as good as I can make it with just 32 bits. It's tempting to replace it with int64 math, but I'm afraid of slowing down my port. By the way, WiggleFix does slow down rendering slightly, because constants are being replaced with variables, but it ain't much.

6. It's far from perfect. Extremely deep pits and tall towers reduce the effectiveness, and wall wiggle is ugly. Also, the code does not consider that levels can get taller, or deeper during play. There's a slight chance that this could cause an issue with overflow, or something, but I can't say that it's ever caused me any issues.

7. I admit that my rationale for not using int64 (or float) math is quite poor. A proper int64 fix would leave the ScaleFromGlobalAngle clamp, and HEIGHTBITS constant, and would avoid the level geometry check altogether. Both types of wiggle would be reduced to < 1/2 a pixel (i.e. none). Alternately, you could probably continue with int32 math, and just switch scales for steep angle walls.

If anyone tries int64, float, or a steep vs. non-steep scale switch, please let me know - I'm very interested to see new implementations!

Do you know if your WiggleHack is demo-safe? According to http://doomwiki.org/wiki/Long_wall_error, extremely long walls suffer from poor collision detection. Would WiggleHack worsen this problem?

Quasar said:

I wonder if the crash you're getting is genetically related to the numeric overflow crash?

Well, actually that "crash" was an I_Error() in the RANGECHECK code of R_MapPlane(), triggered because the value of y has overflowed to 65479. Not sure if the is related, but it doesn't sound too uncommon.

kb1 said:

Yes, increasing the test from 64*FRACUNIT to 256*FRACUNIT reduces the maximum sector height difference to 1/4 original.

So, this is really just shifting the problem from one point in the code to another. :/

plums said:

Do you know if your WiggleHack is demo-safe? According to http://doomwiki.org/wiki/Long_wall_error, extremely long walls suffer from poor collision detection. Would WiggleHack worsen this problem?

As it's purely a modification of the renderting, no, it won't have an effect on gameplay checks.