Dynamic wiggle/Tall Sector fix for fixed-point software renderer

Linguica said:

More to the point, tantoangle[] is only 2048 values long, so when the vertice is very far away, dist relies on a very precise measurement of the angle between the player and that vertice that just can't be had. Say the vertice is 8,192 units away, it's clear that there's just no way the angle used for the calculation will be able to reflect position changes of less than 8192/2048 = 4 units.

8192 units' distance is in fact the exact point at which projection starts to break down. This was determined from behavior of unpatched PrBoom-Plus and Eternity while trying to run the utterly massive Sunder MAP10: The Hag's Finger, which has an open space well in excess of this. Being in the wrong place and turning to the wrong angle would cause half the level to fail to render, due to complete data loss (not just precision problems) reversing sidedness decisions in the BSP traversal.

In any event, is it just me or is the algorithm for determining rw_distance totally insane? It takes a (possibly very far off) vertice, and calculates the distance to that vertice, and calculates the angle to that point using a tangent, and then takes the cosine of that angle, etc.

All rw_distance is, is the length of a line drawn from the player's position perpendicular to the line being considered, to the intersection point with that line. So to determine this, we just need the player's position (which we have), the slope and position of the line in question (which we have), and the point where the line and our perpendicular line intersect (which we need to calculate). But this is just, like, algebra / trigonometry 101 stuff! We HAVE the slope / position of the line we're looking at, and we can trivially calculate the slope / position of a perpendicular line passing through the player, and finding the point of intersection is just setting the two line equations equal to each other and seeing what X and Y values pop out. Then call R_PointToDist() on THAT point, and you're done.

Linguica said:

...and finding the point of intersection is just setting the two line equations equal to each other...

I wonder if the calculations involved in that would have been too slow in 1993?

Quasar said:

8192 units' distance is in fact the exact point at which projection starts to break down. This was determined from behavior of unpatched PrBoom-Plus and Eternity while trying to run the utterly massive Sunder MAP10: The Hag's Finger, which has an open space well in excess of this. Being in the wrong place and turning to the wrong angle would cause half the level to fail to render, due to complete data loss (not just precision problems) reversing sidedness decisions in the BSP traversal.

Interesting. And, thanks - I've been looking for a nice test-case map!

Linguica said:

In any event, is it just me or is the algorithm for determining rw_distance totally insane? It takes a (possibly very far off) vertice, and calculates the distance to that vertice, and calculates the angle to that point using a tangent, and then takes the cosine of that angle, etc...

Mock it up! :) It might be better to calculate the left side of the wall, then the right, and then interpolate distance as you trace left to right, kinda like what Doom does now.

To be realistic, Quasar and SoM have already pretty much solved these issues, I think, with their Cardboard renderer. At some point, one has to give in to the reality that the converting the renderer to use floating point, and proper trig, is the only real way to go. I have not gone that route yet for these reasons:

1. I am concentrating on other Doom development at the moment.
2. This rewrite demands a large chunk of dedicated attention and time.
3. I like to stretch the "vanilla" way to its limits.
4. Speed. I don't want to slow down the renderer any more than necessary, and I like knowing that it'll run good on old hardware.
5. Nostalgia. I am kinda proud of what JC accomplished, and how he accomplished it.

Point is, eventually I'll give in and do a Cardboard-ish rewrite, probably after carefully studying what Quasar and SoM have accomplished. (Good job, guys! Great stuff.) So I am reluctant to fix more than absolutely necessary with the original renderer (WiggleFix was absolutely necessary - man that looked like shit).

But, yeah, fixing the rw_distance just might fix Long Wall error, and Carmack's 90-degree slime line. Wouldn't that be nice? It's worth a shot.

Quasar said:

I wonder if the calculations involved in that would have been too slow in 1993?

Oh, yeah - square root, sin and cos? Out of the question. Especially with the math coprocessor-less 386 and 486SX (sucks). On these setups, trig was done in software. Even today, you've got to be careful. But, if done right, floating-point and trig can be quite acceptable.

Linguica said:

I doubt it - each node contains one subsector, and each subsector is just a list of segs. All you would have to do is have the engine examine the list while setting up the level, and if any of the segs are too long, just chop it up into multiple segs.

I am at it. I am currently at a point where I could split a too-long seg into shorter parts by adding intermediate vertexes and introducing new segs between these vertices. What is still missing is inserting the newly added segs into the consecutive (!) list of segs that make up the subsectors.

This means, for every seg, check if it is too long. If yes, add N intermediate vertices and N new segs to connect these vertices. For each new seg, find out which subsector the original seg belonged to. Break up the segs[] array to insert the N new segs, modify the numlines value for the corresponding subsector and the firstline values for every (!) subsequent subsector. Repeat for all segs.

Doesn't sound like fun, does it?

That said, I don't think that would fix anything anyway. I think the real problem is in R_StoreWallRange():

But isn't this the exact point? If you split your offending, say 8192 units long, wall into 8 shorter segments of 1024 units length each, then this calculation will become precise enough again for each of these segments.

fabian said:

But isn't this the exact point? If you split your offending, say 8192 units long, wall into 8 shorter segments of 1024 units length each, then this calculation will become precise enough again for each of these segments.

The problem is when a linedef's first vertice is too far away, it has nothing directly to do with the segs. You would have to split too-long linedefs into new shorter linedefs, and rebuild nodes.

Maybe you could edit the source so it uses the implicit vertices for the current seg instead of the linedef vertices for distance calculations...

Linguica said:

Maybe you could edit the source so it uses the implicit vertices for the current seg instead of the linedef vertices for distance calculations...

Heh? I though it was already doing that?! o_O

Yeah, you're right, I don't know what I was thinking. I think I saw the name "curline" and had a brain fart.

Oh hai I fixed long wall error. Well, minimized it in any event. I had to do some gross wigglehack-esque dynamic resizing, but with fixed point that's really the only way.

fixed_t dx, dy, a, c, ac, rwd_x_offset, rwd_y_offset;
fixed_t recentered_v1_x, recentered_v1_y, recentered_v2_x, recentered_v2_y;
char scaling_fudge;

[...]

// if wall is horizontal or vertical, finding the distance
// to it is trivial
if(curline->v1->y == curline->v2->y)
{
  rw_distance = abs(viewy - curline->v1->y);
}
else if(curline->v1->x == curline->v2->x)
{
  rw_distance = abs(viewx - curline->v1->x);
}
// use old code for short walls and for walls that
// arent too oblique-- fixes weird Map09 slime trail
// these are pretty arbitrary values though
else if(hyp < 1024<<FRACBITS && sineval > 2000)
{
  rw_distance = FixedMul (hyp, sineval);
}
else
{
  // recenter world on player at (0,0)
  recentered_v1_x = curline->v1->x - viewx;
  recentered_v1_y = curline->v1->y - viewy;
  recentered_v2_x = curline->v2->x - viewx;
  recentered_v2_y = curline->v2->y - viewy;

  // resize world if it's too big so that the FixedMul later
  // doesn't overflow
  scaling_fudge = 0;
  while(abs(recentered_v1_x) >= 128<<FRACBITS ||
        abs(recentered_v1_y) >= 128<<FRACBITS ||
        abs(recentered_v2_x) >= 128<<FRACBITS ||
        abs(recentered_v2_y) >= 128<<FRACBITS)
  {
    recentered_v1_x >>= 1;
    recentered_v1_y >>= 1;
    recentered_v2_x >>= 1;
    recentered_v2_y >>= 1;
    scaling_fudge++;
  }

  dx = recentered_v2_x - recentered_v1_x;
  dy = recentered_v2_y - recentered_v1_y;

  // so now we should have a world centered on the player at (0,0)
  // and the vertices of the line are all within 128 units
  // we are using an imaginary perpendicular line going from
  // (0,0) to (-dy, dx) for calculations
  a = FixedMul(recentered_v1_x,recentered_v2_y) - 
      FixedMul(recentered_v1_y,recentered_v2_x);
  c = FixedMul(dx,dx) + FixedMul(dy,dy);
  if(!c) c=1; // just in case
  ac = FixedDiv(a,c);

  //if necessary, inflate coordinates back to real world
  rwd_x_offset = FixedMul(ac,-dy)<<scaling_fudge;
  rwd_y_offset = FixedMul(ac, dx)<<scaling_fudge;

  rw_distance = R_PointToDist(viewx + rwd_x_offset, viewy + rwd_y_offset);
}

Turns out this also partially fixed the big slime trail on Map09 too.

Linguica said:

Oh hai I fixed long wall error. Well, minimized it in any event. I had to do some gross wigglehack-esque dynamic resizing, but with fixed point that's really the only way.

....

This is incredible Linguica! Awesome work! Just tested it out by putting the code in Doom Retro: it works well!

bradharding said:

This is incredible Linguica! Awesome work! Just tested it out by putting the code in Doom Retro: it works well!

Thanks! I edited the code paste a bunch of times though, so make sure you didn't copy one of the revisions that didn't actually work quite right.

Linguica said:

Thanks! I edited the code paste a bunch of times though, so make sure you didn't copy one of the revisions that didn't actually work quite right.

Actually, I copied the code, refreshed the page, and realised you had tweaked it a bit. Just double-checked: yep, I have the code as it is now. :)

It just occurred to me that there's still a potential overflow in the code I wrote:

 c = FixedMul(dx, dx) + FixedMul(dy, dy);

dx and dy can both be up to 256 since even when rescaled the vertices can still range from -128 to +128, so c can go far above 32,767.

I guess I could check the sizes of dx and dy and optionally do an extra bitshift to them and increment scaling_fudge, but really the easiest solution is just to clamp the vertices down to within 64 units from the origin, I suppose. Also I guess it should be <64, not <=64, to ensure it stays below 32,768. I'll try out the change later but I don't think it will make any visible difference.

(Calculating a distance based on segs resized into a 128x128-mapunit square seems kind of puny, but it's still, what, 23 bits of precision compared to 11 bits in the arctangent table. So over 4,000 times as precise...)

Wow, nice! Can you describe what you see happening with the bug and the fix? Seems like you're translating the lines so they have small values, as if the map was centered around the player, which keeps the math small?

Some questions:
1. Do you feel like it's complete, or do you think some more analysis/tweaking is necessary in some cases?
2. Is the "128" arbitrarily small, or do you need that value to keep the math in range?

I'm surprised that the downscaling doesn't create another kind of wobble, or distorted distance, since the least significant bits are dropped. I would think they would need to be preserved, and added back, but maybe not.

A good test is to have a 64x64 centered flat (like a teleport), and see if a long wall, that runs right beside it in the map editor, lines up in all positions and directions.

           |
    .----. |
    |    | |
    | 64 | |
    |    | |
    .----. |
           |  <- long wall
           |

Test 2 could be using a diagonal 64x64 sector. The flat would not line up, but the wall should:

      /\     /
     /  \   /
    / 64 \ /   <- long wall
    \    //
     \  //
      \//
       /
      /
     /

This is awesome! Whipping that old renderer into shape! We're running out of things that need fixing. I need to finish my RL projects before you take away all my fun :) Good job!

(sorry double post)

More ideas:
1. So, what happens if you use your new formula for all lines? Sure would make things consistent.

2. Maybe add a toggle key to turn the new formula on and off - that's the best way to see the difference.

3. Something about your formula screams to me that there's an algebraic optimization/cancellation there, but I cannot pinpoint it. You're squaring dx and dy to get c (pythagorean theorem, right?), which is where a new overflow can happen rarely, but that can be done with sin/cos... which is imprecise in the Doom tables, which is why you algo works better, right?

(oops - forgive my ramblings - my mind is blown)

It's not that hard actually. If you have 2 lines, and you know 2 points on each line, the intersection point is just algebra: http://en.wikipedia.org/wiki/Line%E2%80%93line_intersection#Given_two_points_on_each_line



NBD, right?

This can be rewritten with some additional variables, of course. I found some C code which implements this:

x12 = x1 - x2;
x34 = x3 - x4;
y12 = y1 - y2;
y34 = y3 - y4;

a = x1 * y2 - y1 * x2;
b = x3 * y4 - y3 * x4;
c = x12 * y34 - y12 * x34;

x = (a * x34 - b * x12) / c;
y = (a * y34 - b * y12) / c;

Now there's a couple of things I can do with this to simplify it further:

* Since I need 2 line segments to define 2 lines, I can shift the coordinates around to make it easier to deal with, so long as I remember to shift the coordinates back at the end. I might as well set one of the vertices to (0,0), and the player's position is the natural choice. If we say the player's position is vertice 3, then x3 and y3 are 0. That means b is always going to be 0 and we can get rid of it.

x12 = x1 - x2;
x34 = x3 -x4;
y12 = y1 - y2;
y34 = y3 -y4;

a = x1 * y2 - y1 * x2;
b = x3 * y4 - y3 * x4;
c = x12 * y34 - y12 * x34;

x = (a * x34 - b * x12) / c;
y = (a * y34 - b * y12) / c;

* Remember that we want a line perpindicular to the seg we're dealing with, and now we want it to go through the origin since that's where the player is. Well, it's a simple geometric property that you can rotate something around the origin by 90 degrees just by negating the y value and then swapping x and y:



With this in mind, we can imagine moving our line segment so that one end is at the origin. The other end is then at (x2-x1, y2-y1) or (dx, dy). Then we can rotate it 90 degrees to (-dy, dx) and the resulting line segment defines a line passing through the origin that is perpendicular to the original. dx and dy were defined in the code snippet here as x12 and y12 so I can substitute:

x12 = x1 - x2;
x34 = -y12;
y12 = y1 - y2;
y34 = x12;

a = x1 * y2 - y1 * x2;
c = x12 * x12 + y12 * y12;

x = (a * -y12) / c;
y = (a * x12) / c;

* We also know that since we're dealing with fixed point, we have a maximum whole-number portion of 2^15-1 or 32,767. Looking at the equations, we can see that, say, c is an addition of two squares. So if we don't want to overflow, each square must be less than 16,384, and sqrt(16384) is 128. So dx and dy should be less than 128, and so the range for x and y should be -64 to 64. We can accomplish that by bitshifting them down if they're bigger in order to basically shrink them, keeping track of the bitshifts, and then reversing the process at the end to expand the final distance.

* a and c can both end up quite large, so to make sure we don't overflow, we should calculate a/c first, and only then multiply. (It's possible this could still overflow anyway? I'm not sure what the range is on what ac could be.)

x12 = x1 - x2;
x34 = -y12;
y12 = y1 - y2;
y34 = x12;

a = x1 * y2 - y1 * x2;
c = x12 * x12 + y12 * y12;
ac = a/c;

x = ac * -y12;
y = ac *  x12;

It also occurred to me that I forgot that I call to R_PointToDist() at the end to find the actual distance anyway, so I really don't gain any precision beyond the arctangent table that was the cause of the long wall error in the first place; I'm just defining a better domain for that error to be spread over.

Linguica said:

Oh hai I fixed long wall error. Well, minimized it in any event. I had to do some gross wigglehack-esque dynamic resizing, but with fixed point that's really the only way.

Über-impressive, Linguica! Thank you so much for doing this. Damn, I wasn't even aware of the fact that rw_distance was the culprit. I guess my segs-splitting code can go down the drain. ;)

if(curline->v1->y == curline->v2->y)

Isn't this already calculated as

curline->dy == 0

?

I guess this (i.e. horizontal and vertical lines) already covers most of the occurances of this bug in the wild. In every non-trivial geometry, diagonal lines should already get chopped by the node builder, or not?

  // recenter world on player at (0,0)
[...]

I have to admit I don't like this part of the code. Mostly, because I don't understand it. I am sure there are easier (and faster?) ways to calculate this. E.g. with the law of congruent triangles, calculating with half the hypothenuse should result in half the distance or something like this.

I couldn't imagine how complex it would be to archive wobbling walls like Blood's into Doom, you know the ones in the flesh tunnel of the secret map from Blood E1?

fabian said:

Isn't this already calculated as

curline->dy == 0

?

curline is of type struct seg_t, and there's no dy member. There *is* an "angle" member, though, and when I first wrote the code I actually had the test as "if curline->angle == ANG90" etc.

I guess you could do "if(!curline->linedef->dy)" or whatever though, I hadn't really thought about it.

I guess this (i.e. horizontal and vertical lines) already covers most of the occurances of this bug in the wild. In every non-trivial geometry, diagonal lines should already get chopped by the node builder, or not?

Yeah, I would imagine that just checking for horizontal / vertical walls would fix 90% of cases of this in the wild, but that's just because people generally use horizontal / vertical lines. The node builder doesn't care about angles, though, and will split things up however it feels like, so angled long walls aren't fundamentally any different.

I have to admit I don't like this part of the code. Mostly, because I don't understand it. I am sure there are easier (and faster?) ways to calculate this. E.g. with the law of congruent triangles, calculating with half the hypothenuse should result in half the distance or something like this.

That's essentially what I'm doing! Because I'm using fixed point arithmetic I just need to make sure the values are small enough, and if they're too big, then I do the calculations on a half, or a quarter, or an eighth or whatever. And just like with congruent triangles, the answer is fundamentally no different except in scale. But in fixed point arithmetic, a smaller scale means less precision.

It's possible there is a better / easier way to do this, but it was the "obvious" way in my mind.

Probably some int64 math instead of while(...)?
http://pastebin.com/f9q9F6ii

Linguica said:

curline is of type struct seg_t, and there's no dy member. There *is* an "angle" member, though, and when I first wrote the code I actually had the test as "if curline->angle == ANG90" etc.

Yes, this would be "if (!curline->linedef->dy)", sorry. This "seg_t *line" is really confusing!

Linguica said:

That's essentially what I'm doing! Because I'm using fixed point arithmetic I just need to make sure the values are small enough, and if they're too big, then I do the calculations on a half, or a quarter, or an eighth or whatever. And just like with congruent triangles, the answer is fundamentally no different except in scale. But in fixed point arithmetic, a smaller scale means less precision.

I have played around with printf() a bit and found out that sineval is the real culprit: finesine[] is simply too coarse for very small angles and distangle is losing 19(!) bits of precision when it is inserted into this LUT. If you are standing close to a very long wall and move towards this wall, the change in angle is too small to cause a change in "distangle>>ANGLETOFINESHIFT" so the value returned by "finesine[]" remains constant. So, the wall moves towards you as "hyp" changes. Then, suddenly, the change in angle is enough to cause "finesine[]" to return a different value and the wall "hops" back.

My idea is to rotate the vertex coordinates back around the wall's own angle so it stands vertical and the simple abs() rule could be used to determine rw_distance. But I have no implementation yet.

@Linguica: This is good stuff! But I just thought up a different approach which, if it works, it's gonna blow your mind :) Your method is mathmatically sound, and mine is an utter hack. There's a good chance it won't work, but, we'll see. Stay tuned.

I've tried most simple solution and looks like it's faster than code above. I got 51 fps instead of 49 on open area of sunder.wad map14.

fixed_t R_DistToSeg(seg_t* seg)
{
  double dx = seg->v2->x - seg->v1->x;
  double dy = seg->v2->y - seg->v1->y;
  double dx1 = viewx - seg->v1->x;
  double dy1 = viewy - seg->v1->y;
  return D_abs((fixed_t)((dy * dx1 - dx * dy1) * seg->inv_length));
}

  if (curline->v1->y == curline->v2->y)
    rw_distance = D_abs(viewy - curline->v1->y);
  else if (curline->v1->x == curline->v2->x)
    rw_distance = D_abs(viewx - curline->v1->x);
  else
    rw_distance = R_DistToSeg(curline);

What's seg->inv_length? That's not a standard thing as far as I can tell.

Linguica said:

What's seg->inv_length? That's not a standard thing as far as I can tell.

it's precalculated 1/length.

  for (i=0; i<numsegs; i++)
  {
    seg_t *li = segs+i;
    double dx = li->v2->x - li->v1->x;
    double dy = li->v2->y - li->v1->y;
    li->inv_length = 1 / sqrt(dx*dx + dy*dy);
  }

That's an implementation of , right? Nice... if you're into that whole floating point thing, that is....

Linguica said:

That's an implementation of , right? Nice... if you're into that whole floating point thing, that is....

Nothing wrong with using floating point at level load, to be able to avoid it during the game. Pretty similar to using pre-calculated trig lookups. Of course, you could do it all with fixed-point, if you had to :)

Compile with SSE codegen enabled and you can get away with a lot of floating point math. All modern games use floating point for pretty much everything. Sticking to it religiously for Doom is an exercise in frustration beyond a certain point.

I mean I look at it this way. If you're going to impose fixed point math as a strict limitation, then why not also impose DOS as a target platform? You're going back to 1993 pretty much. Even the bare bones Pentium could do floats a lot better than its predecessor - well enough for Quake to get written.

If this stuff is just an intellectual exercise, that's one thing. If it's meant to be taken seriously as the way that modern ports should lay out their development plan - being religious about fixed point - then I don't think that's a good idea at all. prboom-plus is about the fastest port there is, and even it uses floats where they're appropriate and really needed.

I know, I know. For a "modern" software renderer, there's no reason to not use int64 or floating point as appropriate to do stuff more quickly and effectively. But that sort of optimization is the province of real programmers, not a hobbyist like me.

Quasar said:

If this stuff is just an intellectual exercise, that's one thing.

Actually it kind of is, yeah. I'm partial to thinking about optimizations / improvements that *could* have been done in the original DOS engine in 1993. It's more interesting that way.

And really, developing / maintaining a software Doom renderer at all, especially one with uncapped FPS and high resolutions and so forth, is kind of an intellectual exercise in heroic coding...

I converted it to fixed point. Precalculate section still need floats.

// in Boom based ports call it after P_RemoveSlimeTrails,
// because it changes vertexes
void R_CalcSegsLength(void)
{
  int i;
  for (i=0; i<numsegs; i++)
  {
    seg_t *li = segs+i;
    fixed_t dx = li->v2->x - li->v1->x;
    fixed_t dy = li->v2->y - li->v1->y;
    li->length = (fixed_t)sqrt((double)dx*dx + (double)dy*dy);
  }
}

fixed_t R_DistToSeg(seg_t* seg)
{
  // if wall is horizontal or vertical, finding the distance to it is trivial
  if (seg->v1->y == seg->v2->y)
    return D_abs(viewy - seg->v1->y);
  else if (seg->v1->x == seg->v2->x)
    return D_abs(viewx - seg->v1->x);
  else
  {
    // to avoid possibility of int64 overflow in dist calculation
    const int shift_bits = 1;

    int_64_t dx = (seg->v2->x - seg->v1->x) >> shift_bits;
    int_64_t dy = (seg->v2->y - seg->v1->y) >> shift_bits;
    int_64_t dx1 = (viewx - seg->v1->x) >> shift_bits;
    int_64_t dy1 = (viewy - seg->v1->y) >> shift_bits;
    int_64_t dist = (dy * dx1 - dx * dy1) / (seg->length >> shift_bits);

    return (fixed_t)(dist << shift_bits);
  }
}

rw_distance = R_DistToSeg(curline);