Deciphering R_ScaleFromGlobalAngle

I've been running through the renderer from Chocolate Doom with a basic square map trying to visualise what each function is doing. Everything was falling into place until I hit R_ScaleFromGlobalAngle. I just can't seem to work out what anglea and angleb represent.

At first, I thought adding 90 degrees converted both angles from the xtoviewangle style -> viewangletox, but attempting to draw that out in SketchUp from a top down perspective results in a completely unintelligible result. After running through various permutations, I am still no closer to figuring out what's going on.

projection is also proving to be a bit of a head scratcher. My guess is that it's being used here to represent the distance from the player to the vertex (or closest angle to it), or the screen width distance to the wall/seg from the player's 3D perspective.

I suspect I've missed something fundamental, so I am hopeful that someone can point me in the right direction.

It's a very screwed up approach, really. SoM could tell you a lot more about it than I can, but I understood enough about it to figure out it's partially responsible for the way 2S linedefs warp terribly if one of the vertexes is behind the view frustum and you're nearly on top of the line (that, and inaccuracies in the xtoviewangle and tantoangle tables).

It's explicitly what Carmack is referring to in the original code release's README file when he talks about use of "polar coordinates for clipping" - he means getting the two angles from the view point to the ends of the line and using those to determine a 3D projection - instead of using a proper matrix multiplication operation like a modern 3D pipeline would.

Ah, yes, that rings a bell - I think another thread was talking about the warped lines issue. In my educational remake, I am planning on using proper floating point values, so hopefully that'll make things look a little better. TBH, I am not all that fussed. At this stage, anything old that gives me more flexibility than the Wolf3D engine would be great.

That makes sense on the README. For anyone else that's curious, Carmack mentions polar coordinates in this paragraph.

I considered giving up and going for a more modern approach using matrices, but that just takes the fun out of it ;-) In all seriousness, I've been banging my head against a wall for a few weeks now. I'll keep at it for a bit longer but if I continue to come up empty, I think I'll have to resort to something like that. Plenty of books, tutorials, etc that go into it in detail.

An an aside, and in case it helps anyone else, the best resources I've found so far for linear algebra related topics are 3D Math Primer for Graphics and Game Development, 2nd Edition mixed in with a few videos from Khan Academy.

Can't comment directly on Chocolate code, but there is some interesting angle comments in PrBoom about the angle functions.
My testing showed that at large distances (Europe.wad and longdays.wad) the angle of textures edges has only 3 bits of accuracy (out of 32 bit fixed point).
The original code cannot maintain angle order either, so at large distances the texture edges (as an angle) reliably fail an order test, resulting in distant textures not displayed, or displayed enormous.

PrBoom and DoomLegacy have improvements to the angle functions.
I was able to get it up to 13 bit accuracy by using 64 bit math in the angle determination code. Using the atan2 library function is the best solution. It is slow but accurate.

Matrix solutions are fine for math classes and theoretical discussions, but I do not recommend using them in real-time rendering code. Expand the matrix into separate statements and simplify the multiplications of 1 and 0. You will end up with only a dozen statements and no loop overhead.

I dug out the source for R_ScaleFromGlobalAngle from PrBoom-plus, but it's fairly similar to Chocolate Doom other than a few formatting changes, and using projectiony instead of projection.

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]);
// proff 11/06/98: Changed for high-res
  fixed_t num = FixedMul(projectiony, finesine[angleb>>ANGLETOFINESHIFT]);
  return den > num>>16 ? (num = FixedDiv(num, den)) > 64*FRACUNIT ?
    64*FRACUNIT : num < 256 ? 256 : num : 64*FRACUNIT;
}

The comments above the function also appeared to be pretty much identical and didn't really add much, so I've omitted them.

It sounds like you might be a bit ahead of me here. I'd just be happy to understand the basics of how things currently work, but I'll keep your matrix simplification comments & the idea of using a 64-bit type in mind for the future :-)

R_ScaleFromGlobalAngle is not the one that causes trouble.

The one that causes render problems generates the angle from two parameters. I don't have source here to look up the actual name in PrBoom. They created two versions of the function. The original is used in code that might affect a demo. A modified version is used for rendering, due to the gross errors it has at long distances.
Just search for atan2.

wesleyjohnson said:

R_ScaleFromGlobalAngle is not the one that causes trouble.

There's more than one problem in the Doom renderer and use of this function/approach to scaling and clipping does cause several of them.

The problem *you* are suddenly off on is the R_PointToAngle problem. That function ceases to function with distances > 8192 units at certain angles, due to numeric overflow. The solution for that is to use the overflow-prone implementation only for playsim code, preserving demo compat, and in the renderer use a solution that falls back to atan2() if the arguments are in the numeric range that the less accurate fixed_t table lookup cannot handle. This is totally unrelated to the conversation that was in progress previously.

Also I cannot believe you honestly thought that by matrix multiplication I earlier meant that it should be implemented using a college textbook matrix multiply algorithm. Give me a break. Those are always simplified down to fit the needed operation where such is possible due to given elements being identities or zeroes. Saying that in the manner you did is insulting to my intelligence.

I avoid getting into replying to other replies, only the original poster.
I replied to a newbie who wrote this (and not to anyone else).

I considered giving up and going for a more modern approach using matrices, but that just takes the fun out of it ;-)

and this

I think another thread was talking about the warped lines issue. In my educational remake, I am planning on using proper floating point values, so hopefully that'll make things look a little better.

The R_ScaleFromGlobalAngle > 64 stuff is precisely the cause of wobbling lines when you are looking straight down a line. Yes, it's a fixed-point, precision issue.

You can actually change the scaler (see HEIGHTBITS), and give yourself some more bits of precision, but if you go too far, now, instead of line wobble looking straight down the line, you now get wobble at the top and bottom of walls looking directly at a wall.

Carmack chose a happy medium between the two, but, essentially, there's just not enough precision at modern resolutions. At 320x200, it's hardly noticeable unless you're looking for it.

I think the projectiony vs projection thing makes look up/look down work.

From reading R_ProjectSprite I guessed that projection is something like "the distance from the viewer's eye to an imaginary plane onto which the game world is projected". Things nearer than that distance are magnified, and things further away are shrunk.

I think projectiony exists to take Doom's graphics aspect ratio into account. Its value is projection scaled by 6/5, the ratio of pixel height to pixel width in DOS, which apparently had non-square pixels. I think if you remove the calculation and just set projectiony = projection, then running the game in a 4:3 aspect ratio resolution would make everything look short and fat.

projection also seems to be related to focal length. I've found using its value in R_InitTextureMapping, instead of the focallength parameter the function calculates internally, gives the same results in 4:3 modes. Furthermore, this appears to maintain a 4:3 aspect ratio even if one runs the game in a widescreen resolution (no stretching of the player view horizontally, but increasing the field of view).

I discovered this by accident when trying to do non-4:3 aspect ratio screen/window sizes in my engine. My notes say: Honestly I don't know why this works. It was determined empirically by trial and error, and by comparing with PrBoom+. The focal length is half the view width when the field of view is 90° - "think of a right-angled isoceles triangle" - but is this actually relevant, or just coincidence?

To get the angle any projection plane can be used for the atan.
At far distances they x and y are so large that the division suffers.
Rescaling by any means would also recover some precision.

Rescale possibility:

  // Fixed point x and y.
  uint64_t rd = ((uint64_t)x + (uint64_t)y) >> 26;
  if( rd > 1 )
  {
     x = x/rd;
     y = y/rd;
  }

This would rescale the x and y. However it is similar to the arbitrary rescale already used, and that results in losing so many bits of precision in the angle.

I think most of the atan library functions first spend time rescaling the x and y to maximize precision, and that is why they are so much better.

If a 128 bit divide could be accomplished it would yield more usable bits.

EDIT: I fixed your code tags -Quasar

From reading R_ProjectSprite I guessed that projection is something like "the distance from the viewer's eye to an imaginary plane onto which the game world is projected". Things nearer than that distance are magnified, and things further away are shrunk.

I was thinking something similar a while ago, and increasing the value of projection does seem to make things bigger.

I think projectiony exists to take Doom's graphics aspect ratio into account. Its value is projection scaled by 6/5, the ratio of pixel height to pixel width in DOS, which apparently had non-square pixels. I think if you remove the calculation and just set projectiony = projection, then running the game in a 4:3 aspect ratio resolution would make everything look short and fat.

Yep, I saw a few comments in one source release talking about projectiony taking the aspect ratio into account, although I thought it was more to do with handling more modern resolutions that aren't 4:3. Projectiony isn't present in Chocolate Doom, so I am guessing it also isn't present in the original source.

projection also seems to be related to focal length. I've found using its value in R_InitTextureMapping, instead of the focallength parameter the function calculates internally, gives the same results in 4:3 modes. Furthermore, this appears to maintain a 4:3 aspect ratio even if one runs the game in a widescreen resolution (no stretching of the player view horizontally, but increasing the field of view).

I discovered this by accident when trying to do non-4:3 aspect ratio screen/window sizes in my engine. My notes say: Honestly I don't know why this works. It was determined empirically by trial and error, and by comparing with PrBoom+. The focal length is half the view width when the field of view is 90° - "think of a right-angled isoceles triangle" - but is this actually relevant, or just coincidence?

Haha, yeah I know the feeling. Several times I thought I'd finally made some some progress on working out what R_ScaleFromGlobalAngle was doing, only to realise that my results were purely coincidental and meant nothing. It's an interesting idea, though. The comments just above the focallength assignment in R_InitTextureMapping state:

   // Calc focallength
    //  so FIELDOFVIEW angles covers SCREENWIDTH.

Sounds like it could be related. Hopefully someone can confirm or deny someday but for me, based on the amount of time I've spent investigating this, it's not quite enough to justify anymore effort. Thanks for mentioning it, though, and I am also grateful for all the comments that have been posted so far, even if they don't directly relate to the subject of the thread.

Maybe I'll revisit all this at some point in the future, but for now, I give up!

Anyone can shade some light on the math behind the polar coordinates mapping/projection?

Hello,

I have spent so much time trying to understand R_ScaleFromGlobalAngle, I have documented all my notes here 

 

https://github.com/amroibrahim/DIYDoom/tree/master/DIYDOOM/Week015/notes

 

my theories are slightly different than others :D  

Anyone is welcome to comment or even let me know if they think it is wrong! Hope to hear some feedback.

 

Edited September 19, 2020 by AngryCPPCoder

Figuring out what the reasoning is in the Doom code, is going to be subject to interpretation.  And someone else will likely have a different opinion.

I don't think it is a matter of using polar coordinates.

If the vertex were in polar coordinates at any time then that could be used for a projection to a sphere, and for large distances that could be approximated as the flat screen.

Just because they calculate angles does not make it polar coordinates.

 

The world coordinate system is obvious, and all the calculations can be understood in that coordinate system.

Any solving of distances would work.  If you use Algebra and some trigonometry, there are several resultant sets of equations, each would yield the same results.

But, Algebra assumes perfect numbers with indefinitely large precision and indefinitely large range.

The actual CPU available at the time was much more limited, and they wanted to draw this fast enough that it would not flicker.

Those needs are what drive the way this is calculated.

 

The basic technique is to calculate a few points correctly, and then interpolate the rest.

Distance does not interpolate correctly, but the 1/distance does much better.

By trial and error, other damaging effects were discovered and avoided using kludges.

To avoid losing precision, is was necessary to calculate intermediate values that retained good precision for as large a range of situations as possible.

The angles to the screen pixels happen to have a consistent relation to what is seen.  They don't end up calculating a large number of bits of precision that have no effect.

In this way the original algebraic equations get transformed to something that retains it values, does not overflow or underflow, or dive into small fractional values, over the expected viewing angles.  They could not afford to be doing this using 128 bit floating point math.  Everything had to work just using integer math.

 

They could not use the trig functions because they were too slow.  So lookup table approximations.  To save space those tables were collapsed as much as possible.

 

Everything else is just the details of that.

 

One obvious speed improvement was to not let Z in on the distance calculations.  It is not true 3d projection (they call it 2 1/2 d projection).

The scale only depends upon the X and Y.  The wall is constant over its Z.  This means that the scale does not change as a vertical texture is drawn.

Now, if they draw in columns too, they can interpolate the scale for a point along the floor, and use it for everything in that column.

That is just fast enough to get by on the hardware of the era, and most people don't notice the loss of vertical perspective.

You could only look up or down for the height of the screen, as they did not have free look at that time.

 

Edited October 13, 2019 by wesleyjohnson

On 9/16/2019 at 12:59 PM, AngryCPPCoder said:

Anyone can shade some light on the math behind the polar coordinates mapping/projection?