PRBOOM Graphical Glitches

I have been having a really annoying graphical bug when I try to use PRBOOM. I will provide a screenshot later in this post. The problem is simple, whenever I come to look at any ledge at a certain angle, (say, if I am standing on stairs, and look at the lower step sideways) the side of that ledge/step will bug out, and the side of it will become warped. This is really annoying when walking across thin walkways, as it becomes very noticeable.
Here is a link to the image, I did not embed it, due to the size:
http://i.imgur.com/zpootUV.png

Any help on how to fix this?

That issue exists in Vanilla / Chocolate DOOM too, and probably other some software source ports. It is caused by limited precision of fixed point math, and is not easily fixable.

I believe it has been fixed in the Eternity source port.

Or you could use an OpenGL source port.

That crap happens for me in Doom Legacy. I noticed it within 4 seconds of enabling mouselook.

Is it seriously a known bug? Oh hell no.

Is there an more detailed explanation for that bug somewhere besides "because math"? I see it in prboom-plus pretty often, and sometimes it's REALLY noticeable, like way more than I remember it being an issue.

The problem scales with screen resolution. It's barely noticeable in 320x200.

ZDoom is also among the source ports that fixed it.

Da Werecat said:

The problem scales with screen resolution. It's barely noticeable in 320x200.

ZDoom is also among the source ports that fixed it.

Any way to fix it for a 1920x1080 monitor.
I know I may sound stubborn, but there is no way I can run 320x200 on my system.

bleh

Linguica said:

Is there an more detailed explanation for that bug somewhere besides "because math"? I see it in prboom-plus pretty often, and sometimes it's REALLY noticeable, like way more than I remember it being an issue.

Doom doesn't use a proper projection on vertices. Instead it fools around with angles and uses a black magic routine called R_ScaleFromGlobalAngle to figure out where the endpoints of a seg should be on-screen. The arrays used by this (tantoangle, xtoviewangle) are terribly inaccurate, but the method also yields strange results for vertices that are behind the view frustum, which get stranger the further behind the near clip plane they are (think of it as if everything behind you is mapped to a singularity, basically, so the more deviation between that mapping and reality, the worse of a model it becomes).

All this probably barely makes sense. Just suffice it to say it's the result of someone with no formal training in linear algebra writing a 3D renderer. Carmack himself admitted that was essentially the reason for it - he didn't fully understand vectors, matrices, or projections at that point. He had til Quake to figure out all that nonsense :P

lmao god this code

return den > num>>16 ? (num = FixedDiv(num, den)) > 64*FRACUNIT ? 64*FRACUNIT : num < 256 ? 256 : num : 64*FRACUNIT;

YUP, SEEMS LEGIT

Linguica said:

lmao god this code

return den > num>>16 ? (num = FixedDiv(num, den)) > 64*FRACUNIT ? 64*FRACUNIT : num < 256 ? 256 : num : 64*FRACUNIT;

YUP, SEEMS LEGIT

Replacing "64" with "256" in this code already helps a lot. I think this is what Doom Retro did up to the current release, right?

fabian said:

Replacing "64" with "256" in this code already helps a lot. I think this is what Doom Retro did up to the current release, right?

That.... seems to help, actually. WTF? What is going on in this code?

fabian said:

I think this is what Doom Retro did up to the current release, right?

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.

I should record a demo of me dying on a map that uses an 8 point border around the floor. Watching the players corpse slide across the detail looks like he's bending the world around him.

Linguica said:
[ code ]

It wasn't written like that in the original game, but it has the sign any Doom engine source diver learns to fear and dread.

// killough 5/2/98: reformatted, cleaned up

40oz said:

I should record a demo of me dying on a map that uses an 8 point border around the floor. Watching the players corpse slide across the detail looks like he's bending the world around him.

Do it! I want to die and bend the world!

jongo said:

Do it! I want to die and bend the world!

Here's a test wad with a crappy demo.

There may be better examples in other wads but I can't think of any offhand. But in general, it requires an inset floor sector, and some kind of impassible fence texture on the outside so the dead player glides across the border with his vision affixed against the offending glitch.

Killoughcode is a lot of fun. Attempts to edit MBF quickly drained my will to live.

Da Werecat said:

Killoughcode is a lot of fun. Attempts to edit MBF quickly drained my will to live.

The best part is when his "cleaned up" code generates far worse assembly because the compiler can't come up with optimal register allocations due to all his temporaries, side effects, and deeply embedded conditionals.

To be fair, I think that most compilers of 1998 weren't that good at optimizing so that his convoluted messes didn't matter that much. It's still horrible what he did.

For me it's normally that any time I have to make changes of his obfuscations I'll first revert them to something saner.

But still... comparing the assembly output Visual C++ produces of PrBoom's (Killough's) R_PointToAngle functions with the one from the original code should be a real eye opener...

fabian said:

Replacing "64" with "256" in this code already helps a lot. I think this is what Doom Retro did up to the current release, right?

Where in the code is this? I'm not really fluent with DOOM code, and have no idea where this is. My extent of knowledge for coding is throwing together new monsters/weapons in Slade.
I'd love to fix this.

The Civ said:

Where in the code is this?

For example:

https://github.com/fabiangreffrath/crispy-doom/commit/f8cfd1c2911896407083e9bd5cd7e4de805d724a

Quasar said:

The best part is when his "cleaned up" code generates far worse assembly because the compiler can't come up with optimal register allocations due to all his temporaries, side effects, and deeply embedded conditionals.

Apparently, he believed that less written C code resulted in less (and thus faster) compiled object code.

fabian said:

Apparently, he believed that less written C code resulted in less (and thus faster) compiled object code.

Aren't modern compilers smart enough to unravel all that stuff anyway?

Anyways, I was spending some time trying to figure out R_ScaleFromGlobalAngle() and it was driving me crazy so I decided to just mess with the values and see if that would help me understand.

The function wants to return an amount by which to scale each end of a linedef. Since in Doom, walls are always straight up and down, it can show a wall at an angle by determining how much to stretch the wall at vertex A, and how much to shrink the wall at vertex B, and then just smoothly stepping between these values along the length of the wall. (This works by screen space so it's not always going from vertex A to vertex B, but whatever.)

Anyways, so the function tries to find the scaling amount by taking one value and dividing it by another value: a numerator and a denominator. Here's some simplified pseudocode:

num = sine(angleb)
den = rw_distance * sine(anglea)

I'm ignoring what "rw_distance" and "anglea" and "angleb" are meant to represent for now. Anyways, the important part is that we can see that both the numerator and denominator are being scaled by a sine value. The sine wave goes from 1 to -1, but I'm going to assume that Doom is careful not to try and mess with negative values for scaling (what would that even mean?) and so we're really looking at turning anglea and angleb into a number between 0 and 1.

So my thought is: well, let me try setting one or the other to always being 1, and see what happens.

First, the denominator:

num = sine(angleb)
den = rw_distance * sine(anglea)1



OK, this is making the screen sort of look like a fisheye lens. We can tell from this that the denominator's function, at least in part, is to correct for this distortion. This makes sense: we can assume that "rw_distance" is some measure of distance to the linedef or some part of the linedef, so the further away the linedef is, the greater the distance, and thus the greater the denominator and the smaller the scaling value. But imagine you're directly facing a flat wall: the portion of the wall at the edge of your viewpoint is further away from you than the portion of wall directly in front of you, so the wall should appear to get smaller at the edges of your view! The sine value in the denominator falls off from 1 as you get further from the center of the screen, and effectively cancels out this shrinkage, making the flat wall actually look flat.

Next, the numerator:

num = sine(angleb)1
den = rw_distance * sine(anglea)



OK, now we're getting two effects. First, the fisheye distortion is now reversed and looks like... walleye distortion? I dunno if there is a term for this. Also, all the linedefs now appear to be facing the player, rather than going along their normal trajectory.

The denominator here is inflating values towards the edge of the screen, so we know that the numerator, normally, is shrinking those values towards the edge of the screen, which sort of makes sense from the previous picture anyway. In any event this is making things look weird and harder to think about, so I'll move on to the next step.

Finally, both top and bottom:

num = sine(angleb)1
den = rw_distance * sine(anglea)1



OK, now things look nice and orthogonal, and we can really tell how crazy the linedefs look when they're flattened out like this.

One interesting effect is that despite removing the sine values from the top and bottom, and thus removing any reference to "anglea" and "angleb", the walls perpendicular to the player's view are totally unaffected! However, look at the side walls of the 2 pillars. The one on the right looks almost like what you might imagine, except it is stretched a little bit. The one on the left, though, is stretched like crazy. We know that these two pillars are pretty close to the same distance away from the player, so why is that linedef so stretched?

Well, from the "normal" view, we can tell that that linedef is at a more oblique angle to the player's view. So it stands to reason that "rw_distance" is not just the distance from the player, but instead has something to do with the angle as well.

So let's look up what rw_distance is...

rw_distance = hyp * cosine(offsetangle)

Alright, what's offsetangle?

offsetangle = (line angle + 90) - (view angle to line vertex 1)
if abs(offsetangle) > 90 then offsetangle = 90

Ummm... OK then, moving on, what's hyp? I assume a hypotenuse of something?

hyp = R_PointToDist (line vertex 1 x-pos, line vertex 1 y-pos)

...OK, what does R_PointToDist() do?

hyp = abs(dx) / sine(arctan(abs(dy)/abs(dx))+90)
unless abs(dy)/abs(dx) > 1 then switch dx and dy

OH FUCK THIS DUMB BULLSHIT

DoomLegacy got a fix to some of that angle code, but not the specific problem mentioned in the original post. It annoys me too and is on my hit list.

If you play large wads like Europe, or this particular wad I was working on, far walls are affected. Tries to render a far distant plane right in front of the player's face due to an overflow. That is what did get fixed, but it was much more complicated than replacing 64 with 1024. Had to use 64 math to stop the overflow errors.

The point is that this problem exists because they were trying to avoid overflow with a limited 32 bit math. They downshift some parameters and end up losing too many significant bits in the denominator of their slope ratios.
Changing to 64 bit math helps some, but it is not adequate.

Probably double float or an entirely reworked projection function is needed. At least that would keep the fractional parts of the intermediates in their calculations.

fabian said:

Apparently, he believed that less written C code resulted in less (and thus faster) compiled object code.

No, of course not. I think he was just a fan of one-liners.

OK, I feel like I see what the hyp thing is doing now. It's taking the coordinates of a vertex in respect to the player, making dx and dy positive, and making dy greater than dx - in other words, it's flipping the coordinates into the first 45 degrees.



It then takes the arctan(o/a) to find the angle there. It then rotates this angle 90 degrees (so the angle is now between 90 and 135 instead of 0 to 45) and finds the sin of this angle. This is equivalent to the sin of 180 - the angle.



Then it returns

hyp = longer axis / sin angle

which is indeed the hypotenuse of this triangle if I remember my SOHCAHTOA, and the absolute distance from the player to this vertex.

So why go all this roundabout trouble? Why not just use the pythagorean theorem and find sqrt((pow(x,2) + pow(y,2))?

Let me guess, fixed point math and the possibility of overflows, right?

Linguica said:

So why go all this roundabout trouble? Why not just use the pythagorean theorem and find sqrt((pow(x,2) + pow(y,2))?

Let me guess, fixed point math and the possibility of overflows, right?

Because sqrt cannot be effectively tablified for use with fixed-point, and if done in float, would A. be horribly slow, especially in 1993, and B. inflict the requirement of a coprocessor, whereas DOOM stated minimum requirement 386.

Oh God, I finally did it. I finally reasoned out this algorithm using nothing more than the rudiments of high school trigonometry I could remember. My brain hurts.

Let's start again. Remember that we are trying to plumb the mysteries of R_ScaleFromGlobalAngle(). Or more specifically

R_ScaleFromGlobalAngle(instant_fov_angle)

Where I am using instant_fov_angle to represent the idea that the function is only concerned with one very specific spot on the player screen, representing an angle within the player's FOV, where a line is going to either start or end.

This time I am taking stuff from the original Doom source, not the PrBoom source. This is actually sort of important for a reason I will come to later.

anglea = 90 + (instant_fov_angle - player_angle);
angleb = 90 + (instant_fov_angle - line_normal_angle);
sinea = sin(anglea);	
sineb = sin(angleb);
num = (projection * sineb) << detailshift;
den = rw_distance * sinea;

This time, the first thing I will deal with is num. Two things, especially:

• "detailshift" is a value entirely controlled by the screen resolution. so we can sort of ignore it here.
  
• "projection" is dependent on where we are on the x-axis of the screen. Since R_ScaleFromGlobalAngle() is only ever called to evaluate a line at a given x-position, "projection" is effectively a constant as well. So we can basically write num as
  

num = sineb * (a constant * another constant);
den = rw_distance * sinea;

and we can basically extract them out so we can properly scale the value at the end, and end up with

num = sineb;
den = rw_distance * sinea;

OK, so what are these remaining values? Let's take them one by one.

sinea = sin(anglea);
anglea = 90 + (instant_fov_angle - player_angle);

If we look at anglea, we see something interesting: the only variables involved have to do with the player! The line we care about isn't involved at all! This means that no matter what happens with the line, anglea and thus sinea is always going to be the same thing. This means we can treat sinea as yet another scaling constant:

num = sineb * (a constant * another constant);
den = rw_distance * (yet another constant);

and end up with

num = sineb;
den = rw_distance;

Wow, this is looking a lot simpler now. Anyways, next let's look at rw_distance:

rw_distance = hyp * sin(distangle);

I don't want to go too much into it, but "hyp" is just the distance from the player position to the line's first vertex. So just trust me on that one. So we can rename "hyp" as "vertex1distance" just to make it more clear.

rw_distance = vertex1distance * sin(distangle);
distangle = 90 - offsetangle;
offsetangle = abs(line_normal_angle - vertex1angle);
line_normal_angle = lineangle + 90;
[combine them...]
rw_distance = vertex1distance * sin(90 - abs(line_normal_angle - vertex1angle));

So we can see right away that rw_distance has two components: first is vertex1distance which is a relatively large value entirely dependent on physical distance. Then we have a sin calculation that's gonna return a scaling factor for vertex1distance between 0 and 1.

But look at what's inside that sin calculation: line_normal_angle and vertex1angle. Both of these values have nothing to do with which direction the player is looking! line_normal_angle is a fundamental property of the line itself, and vertex1angle is which direction the vertex is in regards to the player at the moment. So rw_distance, and therefore the entire denominator, has nothing to do with where the player is looking -- it's entirely a description of the line itself in relation to the player's position. We'll come back to this in a bit.

Next, let's look at sineb:

sineb = sin(90 + (instant_fov_angle - line_normal_angle));

OK, now we finally have something that combines both the player and the line. There's also something interesting that you can notice:

num = sineb =                         sin(90 + (instant_fov_angle - line_normal_angle));
den = rw_distance = vertex1distance * sin(90 - abs(line_normal_angle - vertex1angle));

You'll notice that both numerator and denominator have thing going on where before taking the sin, they add 90 to the value. This took me a while to realize, but this looks an awful lot like the old trigonometry equality:

cos(x) = sin(90°-x)
sin(x) = cos(90°-x)

So what if these are better served as being cosines? We can try, at least:

num =                   sin(90 - (line_normal_angle - instant_fov_angle));
den = vertex1distance * sin(90 - abs(line_normal_angle - vertex1angle));

num =                   cos(line_normal_angle - instant_fov_angle);
den = vertex1distance * cos(abs(line_normal_angle - vertex1angle));

OK, that makes things look a little simpler, even though we still have no idea what these values are doing or why a sine versus a cosine makes a difference. (This is actually where using the PrBoom code before confused me, because it actually changes one of these to a cosine, but not the other.) And actually, we can rewrite this slightly to help think about it:

num =         1       * cos(line_normal_angle - instant_fov_angle);
den = vertex1distance * cos(abs(line_normal_angle - vertex1angle));

OK, from this, we can see what our equation has been reduced to: a small fractional value that is inversely proportional to the distance from the player to a vertex, and one cosine value divided by another cosine value. Note that since cosines go from 0 to 1, this value can be literally anything from zero to infinity. (I know that cosine values actually go from -1 to +1, but I am putting my faith in the programmer that the variables are such that the cosines will never end up being negative. I could try and explain it more rigorously but it's not terribly relevant.)

OK, so returning to this portion:

den = vertex1distance * cos(abs(line_normal_angle - vertex1angle));

Remember from before that we noticed that line_normal_angle and vertex1angle have nothing to do with the direction the player is looking. We also can notice the weird caveat that we need an absolute value:

abs(line_normal_angle - vertex1angle)

What does this really mean? Well, what we're really left with is the difference between these two angles.

den = vertex1distance * cos(difference between line_normal_angle and vertex1angle);

...OK? So what does this mean? Well, I've resisted it until now, but we finally need some pictures to help:



OK, I've drawn a crude approximation of a scene. The player is at the origin, and there's a line nearby facing the player. I've labeled vertexes 1 and 2, and indicated the normal of the line as well.



Now I've drawn lines indicating vertex1angle and line_normal_angle as drawn from the player position. But wait... isn't what we're really concerned with the difference between line_normal_angle and vertex1angle? I can mark that specifically:



I've also added a little mark to make explicit that line_normal_angle is at right angles with the line. So, what does this look like? Doesn't this look a whole lot like a right triangle??

If we remember our high school trig again, specifically SOH CAH TOA, we know that CAH means that the cosine of an angle is equal to the length of the adjacent line divided by the length of the hypotenuse. So let me just mark these:



The hypotenuse here, conveniently, is vertex1distance. So if we have

cos(difference between line_normal_angle and vertex1angle) = a / vertex1distance

then

a = vertex1distance * cos(difference between line_normal_angle and vertex1angle)

Huh...



so

den = vertex1distance * cos(difference between line_normal_angle and vertex1angle);
a   = vertex1distance * cos(difference between line_normal_angle and vertex1angle);
den = a;

That's right, the denominator of what we're looking for is just the distance between the player and wherever the line is perpendicular to the player. This happens to be the closest the line ever comes to the player, and so this means the denominator simply indicates how "far away" the line is from the player in a general sense. Note that it doesn't matter if the line actually does have a point where it's perpendicular to the player, the value is the same regardless!

OK, so now we have

num = cos(line_normal_angle - instant_fov_angle);
den = nearest distance the line could ever come to the player

Alright, so let's look at the numerator again.

num = cos(line_normal_angle - instant_fov_angle);

What does this mean, exactly? Well, we know that if instant_fov_angle happens to be looking directly at the sliver of wall perpendicular to the player, we would have:

num = cos(line_normal_angle - line_normal_angle) = cos(0) = 1

So we know that looking dead-on the wall ends up with num = 1. And come to think of it, we can rewrite num as

num = cos(difference between line_normal_angle and instant_fov_angle);

It doesn't have to be absolute, because the cosine function is symmetrical around 0. So no matter if the difference is positive or negative (depending on how we're calculating it), it has no effect on the ultimate answer! (This also makes me wonder why the calculation for the denominator actually did use an abs() function, since it was fed into a cosine function anyway. Belt and suspenders, or making sure to avoid an overflow? I dunno.)

So what does this mean? Well, if the difference between line_normal_angle and instant_fov_angle is 0, then num is 1. And in the theoretical case that the difference between line_normal_angle and instant_fov_angle was 90, then num would be 0. But this would mean that the player was looking riiiiight down the direction of the wall and the sight line only baaaarely intercepted it. (And in this scenario, the interception would happen infinitely far away and so the wall's scaling amount would logically be 0.)

So basically cos(difference between line_normal_angle and instant_fov_angle) is actually telling us the amount you are looking along the wall instead of directly towards it!

So now we have

num = amount you are looking along the wall instead of directly towards it
den = nearest distance the line could ever come to the player

Well, we've managed to entirely abstract away all the math. Finally we can think about what this means. We want to know how much to scale a sliver of wall, right? And from these values, we know how far away the wall is (given in den) and what the slant of the wall is (from num). You can think of this as imagining the wall as infinite in length. den describes how far away the wall is from you, and num describes how far you should turn along the length of the wall to equal the point (and thus the scaling factor) you want. This entirely describes this sliver of wall, so we're done!

Now finally we can examine these magic numbers and figure out what they're doing.

if (den > num>>16)
{
	scale = FixedDiv (num, den);
	if (scale > 64*FRACUNIT)
		scale = 64*FRACUNIT;
	else if (scale < 256)
		scale = 256;
}
else
	scale = 64*FRACUNIT;
 return scale;

What is this basically saying? Well, the first conditional is only ever entered if the numerator isn't totally huge. We divide num by 2^16, and then if num is STILL too large, this conditional fails. We know what num means, so we can modify this to say

if you're not looking down the wall TOO obliquely
{
	scale = FixedDiv (num, den);
	if (scale > 64*FRACUNIT)
		scale = 64*FRACUNIT;
	else if (scale < 256)
		scale = 256;
}
else
	scale = 64*FRACUNIT;
 return scale;

OK, what's the next if-else logic? It's taking num / den and if that value is too large, then do something. In other words, if num is too large or den is too small, the inner conditional is true. And we know what num and den mean:

if you're not looking down the wall TOO obliquely
{
	scale = num / den;
	if you are looking along the wall pretty obliquely, and/or the
            line would come TOO close to the player at its closest
            point, and it ended up making the scaling factor too
            damn large
		scale = some max value;
	else if this whole mess would end up scaling the wall REALLY small
		scale = some minimum value;
}
else you are looking down the wall too obliquely, just give up
	scale = some max value;
 return scale;

Now we can finally see why changing 64*FRACUNIT to a different value actually works. All 64*FRACUNIT is is a maximum scaling factor for a sliver of a wall that the Doom engine will accept. If we increase it to, say, 256*FRACUNIT, we're just making the Doom engine clip the scaling at a higher value and allow lines to appear to get even closer to the player's center, and thus not jump around as much. This can cause problems elsewhere but that's another kettle of fish.

*phew*

Damn, one day, I’ll use this for a pupil’s homework. ;-)