PRBOOM Graphical Glitches

[kb1]

Graf Zahl said:

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

Graf is correct.

fabian said:

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

Not exactly. WiggleHack is simply re-adjusting the renderer texture scaling code, to compensate for increased resolution, and extreme wall heights.

The adjustments in question are:
1. The ScaleFromGlobalAngle clamp value (64*FRACUNIT).
2. The scaling done by HEIGHTBITS.

These values were hard-coded in vanilla, and chosen very carefully by Carmack. He knew his target resolution was 200 vertical, and he wanted to allow sectors to be pretty tall (or deep).

Doom draws wall textures by drawing stretched vertical strips of texture, one at a time, panning from left-to-right (or right-to-left). Let's consider left-to-right:

Doom first calculates the vertical stretch for the left-most strip, and remembers that value (x1). Then, it calculates the vertical stretch for the right-most strip, and remebers that value (x2).

Then, (x2-x1) is the delta of vertical texture stretch. This difference is 0 when looking directly at a wall, and the wall is rendered as a rectangle. But, when looking at an angle, this delta is non-zero. As doom is drawing the wall in strips, the texture stretch is interpolated through the pan. ((x2-x1)/horizontal_width) is the amount of stretch change from left to right. The stretch is x1 for the first strip, halfway between x1 and x2 for the middle strip, and x2 for the right-most strip.

However, if you are looking down a wall, this delta value is very large, and the horizontal_width is nearly zero. That's when the ScaleFromGlobalAngle clamp comes into play - when you are looking nearly straight down a wall. The amount of change of vertical stretch goes exponentially large.

Carmack's quick fix for this is the clamp to 64*FRACUNIT. What is say is basically: If the amount of change of vertical stretch is too large, let's just say that it is 64*FRACUNIT. This prevents the large values from overflowing the texture calculations.

With higher resolutions, the numbers are naturally larger, for a given scene, so the clamp value should be greater. Now, you can increase the clamp to compensate for this, but you risk overflowing texture calcs.

Now, you can compensate for this by changing the way you interpret the numbers - by changing the scale used. That's what changing HEIGHTBITS does.

The WiggleHack code sets these values automatically, by providing as much clamp as possible, and by changing the scale as much as possible, without allowing texture calculations to overflow.

So, yes, it's a give-and-take. You're trading texture stretch precision for the ability to view tighter angles. You're re-adjusting the renderer appropriately for the increased resolution you're asking it to handle. You're basically recalibrating for higher resolutions. This would yield near-perfection, if overflows were not a concern. There's just not enough bits in a 32-bit int to handle all cases.

Now, as long as levels don;t have 8,192-unit deep pits, or massive skyscrapers, you actually get a more-precise render, for free. The only time the WiggleHack causes undesirable rendering is when there's huge adjacent sector height differences. In that case, you'll see some texture wobbling. But, in vanilla, it would crash!

So, I don't see it as "pushing the error" from one place to another. To me, the code optimizes the renderer dynamically, to the best values possible.

Optionally, you could just assume that everyone will be using at least Nx800 resolution (4x original). You could increase the clamp to 256*FRACUNIT, and decrease HEIGHTBITS from 12 to 10. That would allow vanilla maps to work just like vanilla, with 4x less floor wiggle.

(Damnit, I wrote another big-ass post).

[LordMeow]

Threads like this always make me think about the Cardboard renderer... Quasar, are you sure that SoM does not have the original? Where is SoM anyway, has he left the community?

[Quasar]

kb1 said:

...Now, as long as levels don;t have 8,192-unit deep pits...

I am afraid 8192 is far more than is necessary. The pit at the end of Hexen's Caves of Circe is around 2400-2500 units deep and there is a very strong chance of crashing the game here if you jump into the pit and slide along the wall just properly. The scale of the 2S lower textures on the lines here can become drastically large and ends up trying to put values such as 32790 into the clip arrays. That's too big. The code as written, even with the 64*FRACUNIT limit, is *not* safe.

[kb1]

Quasar said:

I am afraid 8192 is far more than is necessary...

I'll investigate it this weekend. When I posted the WiggleHack code in 2006, I think I commented that some additional bounds checking may be necessary. When I wrote the hack, I already had lots of renderer changes, which, if I remember correctly, did in fact contain some clipping checks.

[kb1]

Taking a quick look at the WiggleHack code, it will reduce the clamp down from 64*FRACUNIT to 8*FRACUNIT if necessary, which will look awful, but should not crash. Int64 or double float is really the way to properly correct the issue, but I intend to try a few more int32 things first :)

Before I give up, want to try a dynamic WiggleHack that re-scales the renderer on-the-fly, to squeeze everything I can out of 32 bits. If I can make it efficient, it will do a good job on 99% of levels, which ain't bad.

[VGA]

LordMeow said:

Threads like this always make me think about the Cardboard renderer... Quasar, are you sure that SoM does not have the original? Where is SoM anyway, has he left the community?

What do you mean the original?

Eternity is using that renderer, right?

[fabian]

Gosh, is that complicated.

kb1 said:

The adjustments in question are:
1. The ScaleFromGlobalAngle clamp value (64*FRACUNIT).
2. The scaling done by HEIGHTBITS.

I have still not figured out how and why these two are connected, how and why they have to share 32 bits among each other for their business and how to assign them 64 bits so each can have 32 bits for himself and STFU.

[Maes]

It's all about stretching the limits *hint hint nudge nudge*

[LordMeow]

VGA said:

What do you mean the original?

Eternity is using that renderer, right?

According to the Eternity wiki, 'It was originally developed outside of the Eternity Engine as a stand-alone program which could draw Doom textures and flats in 32-bit color with dynamically calculated light fading.'

I don't know if a standalone renderer was ever produced, but if it was, preserving it on Github or something will be very interesting.

[VGA]

I believe the renderer is now part of Eternity, so it's GPL'd and available.

[kb1]

fabian said:

Gosh, is that complicated.

I have still not figured out how and why these two are connected, how and why they have to share 32 bits among each other for their business and how to assign them 64 bits so each can have 32 bits for himself and STFU.

Was that STFU for me?? :)

I was hoping that my "exponent adding" stuff was clear. You know how, if you multiply X digits by Y digits, the largest possible value will have X+Y digits? (99 * 999) = 98901 -> 2 + 3 = 5.

That's kinda what's going on with the exponents. I was trying to explain that, if you add 2 bits to the clamp (256*FRACUNIT vs. 64*FRACUNIT), you'd have to reduce heightbits by 2, to keep the maximum-allowable height the same. Does that make sense?

[fabian]

kb1 said:

Was that STFU for me?? :)

No, of course not! It was addressed at "the engine", I was mad at "the engine". I am thankful for every sentence that you write in this thread!

I was hoping that my "exponent adding" stuff was clear. You know how, if you multiply X digits by Y digits, the largest possible value will have X+Y digits? (99 * 999) = 98901 -> 2 + 3 = 5.

Sure, I got that.

That's kinda what's going on with the exponents. I was trying to explain that, if you add 2 bits to the clamp (256*FRACUNIT vs. 64*FRACUNIT), you'd have to reduce heightbits by 2, to keep the maximum-allowable height the same. Does that make sense?

Yes, it does. No, wait, it doesn't. Why isn't it possible to somehow disconnect scale clamp and maximum height? I have not yet wrapped my head around that...

[LordMeow]

VGA said:

I believe the renderer is now part of Eternity, so it's GPL'd and available.

Quasar once told me that not everything in Cardboard had made its transition to Eternity... though I may be wrong.

[kb1]

fabian said:

Yes, it does. No, wait, it doesn't. Why isn't it possible to somehow disconnect scale clamp and maximum height? I have not yet wrapped my head around that...

Ok, this might be a bad description, but I'll try. Here's how I understand it, anyway:

Say the renderer is going to paint a wall, say a stair step. This step was built 16 units tall, and has a 16-unit texture on it.

I'll use "pixel" for screen pixel, and "texel" for texture pixel. In this case, the texture is always 16 texels tall, and will be painted different heights, based on how close the viewer is to the wall. Very far away, a vertical strip may be painted only be 1 pixel tall, but, if the viewer is close to the wall, it may be painted 100 pixels tall or more.

Now, assume that each texel is numbered. In this case, for the first vertical strip, that gives you Texel 1 through Texel 16.

At a specific viewing distance, there will be a one-to-one relationship: Each vertical strip will be painted exactly 16 pixels tall - one pixel = one texel. In other words, on the screen, at the top of this wall, the first pixel will be painted with texel 1, the second pixel will be painted with texel 2, etc.

The Doom renderer has to determine that ratio, for each vertical strip of wall that it renders. But, instead of a ratio, Doom uses an increment. This is a number added to the last texel index, to determine the next texel, pixel by pixel.

For the 1-to-1 scenario, that increment is equal to 1, which is stored in a 32-bit fixed-point number. Something like this, for the 1-to-1, in pseudo Basic :)

Y = (top wall pixel)
H = 16 (wall height)
Texel_Index = 0
Texel_Increment = 1.000

For PixelY = 1 to H
ScreenPixel(Y) = Texel(Texel_Index)
Texel_Index = Texel_Index + Texel_Increment
Next


Now, if you move further away from the wall, Texel_Increment increases. Texel_Increment is 32 bits, but a large portion of those bits are fractional. Same goes for Texel_Index.

Now, Texel_Index purposely "rolls over" every 128 pixels eventually, which gives you repeating textures that you see on tall walls. And, Boom added code that let you use other heights to roll over, not just 128. But that rollover happens later - Texel_Index still needs to hold large numbers for tall walls. When part of the wall is "above the screen", Doom has to calculate where the texture starts.

So, moving further away increases Texel_Increment, but so does looking down the edge of a wall. At steep angles, the wall strip may be a single pixel (meaning that Texel_Increment = 16).

At steeper angles, the wall strip may be only a fraction of a pixel. We know that that is non-sensical, but the math gets performed anyway. Texel_Increment grows exponentially when the angle approaches 90 degrees.

If the math gets too large, you will have an unintended overflow of Texel_Index, which will cause a crash in a source port. The clamp value in ScaleFromGlobalAngle, (64*FRACUNIT) is used to prevent that from happening. The rendered results are incorrect (floor wiggle), but at least it doesn't crash (as often). That's why the clamp was added by Carmack.

A very similar set of related code is used to determine the height of the wall on-screen.

So, the moral is: The taller the wall, the better change of overflowing Texel_Index. The steeper the angle, the better chance of overflowing Texel_Increment (and, therefore, Texel_Index).

Changing the clamp from 64*FRACUNIT to 256*FRACUNIT allows tighter, steeper angles, but you've allowed the number to be 4 times as large, which makes a crash more likely.

However, if you also change HEIGHTBITS, you change the way Texel_Increment and Texel_Index are interpretted. It's like saying 5.4 meters, vs. 540 centimeters. Changing HEIGHTBITS effectively "moves the decimal point", which reduces the possibility of an overflow. But, you lose precision: 5.4 meters vs. 542 centimeters.

Moving from 32 bits to 64 bits would do two things:
#1: Retain the precision lost by fudging around with HEIGHTBITS.
#2: Allow walls to be maximum height, and allow for steep angles, without the possibility of overflowing. You may still need the clamp for ultimate safety, but it would set to such a huge number that you'd never see any wiggling (65536*FRACUNIT, or more).

When I get some time, I'll try to mock up a version with 64 bit ints. I just hope it doesn't slow down my renderer. 64 bit ints are quite a bit slower, in 32-bit code, anyway. Could be quite slow, since it would be used in the renderer's inner loop.

It may be possible to do the initial calculation in 64 bit, and then re-scale to 32 bit for the inner loop. There's a dozen ways to implement it, and it will require trying each of them, and profiling, optimizing, testing, etc. I am hoping to find some time to try soon.

Well, hope that makes it clear. Aargh, I wrote another book!

[kb1]

Ok, here's another way to think about it:

When you're real close to a wall, Texel_Increment needs a lot of precision to the right of the decimal point, because you traverse real slowly through the texture, in relation to how fast you draw pixels.

When real far away from a wall, Texel_Increment needs to have more bits to the left of the decimal point.

Think of a car: Cars have multi-gear transmissions. With each gear, you trade strength for speed.

The vanilla engine is hard-coded to, say, second gear: pretty good precision up close, able to render relatively tall walls, far away.

The WiggleHack is like putting an automatic 3-speed transmission on the original engine - it can down-shift if the level has really tall walls, or it can upshift to allow steep angles, but it's still coupled to a 4-cylinder engine.

Going 64 bit is like dropping an 8-cylinder monster in, with a 6-speed overdrive transmission. More power for the extremes, and more control over how it is used.

Changing HEIGHTBITS is like switching gears. But, with 32-bits, you can only shift so much, before you're out-of-range, one extreme or another.

[kb1]

A small update:

Some preliminary tests indicate that I can set WiggleHack values per wall, vs. per level. If it works out, it'll provide the best of both worlds, so to speak. It's basically an implementation of a poor man's floating point...

Give me a few days, and I'll see if I can make it work.