Jump to content
Search In
  • More options...
Find results that contain...
Find results in...
Quasar

Solution to wobbly line problem that *doesn't* involve Build code?

Recommended Posts

I'm curious if anyone has developed a mathematically rigorous system for projection of segs in DOOM that doesn't resort to using code that was taken from the Build engine. DOOM's normal system of sloppily clipping angles to the vertices into range results in severe numeric instability when one vertex is behind the player, causing stuff that looks like this to happen:

http://doomworld.com/eternity/engine/screenshots/spazzed_midtex.png

The problem seems to be amplified by higher screen resolutions and so it's starting to go beyond my tolerance level (fixes to this have also been requested by Mordeth and the Millennium team).

Unfortunately I'm not very good with trig, especially not when it comes to 3D projections, so I am hoping somebody has some pointers to give.

Share this post


Link to post

Is the aversion to using Build code just because of the license? The Duke3D code is GPL, if that's case.

Share this post


Link to post

Yes, I was apparently wrong. Only the Duke specific stuff is GPL, not the base engine. I don't understand Ken Silverman's insistence on using his own wonky license.

Share this post


Link to post

The first thing you should try is to use higher precision math functions, e.g. replace M_Cos and M_Tan with versions that use cos() and tan() instead of the lookup tables. Do it temporarily (not worrying about performance yet) and see if the problem goes away.

For other ways of rendering, you could try "DUMB", a doom engine written from scratch. It is under the GPL. The rendering is not based on angles (more conventional in a sense).

Share this post


Link to post

Well the deal is, the code in question does not use sine or cosine. It uses the finetangent table via the viewangletox lookup table. This lookup table gives you an x coordinate given an angle. It's imprecise, and worst of all, it clips the data prematurely. If you notice in that screenshot, there's a debug message showing x2=960. This means the screen coordinate for the 2nd vertex is being calculated as 960, or "off the screen". However this result doesn't give mathematically correct behavior the best I can tell. I suck at this kind of math so I'm not sure how to rewrite this to use trig functions instead of the lookup table.

EDIT: I went to the DUMB homepage, but the link to download its source code is broken. Any attempt to use that FTP server keeps answering "connection reset by peer".

Share this post


Link to post

I had forgotten about that nasty viewangletox stuff!

My feeling is that the basic math is OK, but the inaccuries from using fixed-point math and small look-up tables is the cause of the wobbles.

Re: DUMB, if you can't find a downloadable version, you could try "WT" by Chris Laurel which DUMB is based on. I've got a copy of WT if you can't find it.

Share this post


Link to post

I managed to find a surviving mirror of DUMB on samba.org. It is quite similar to DOOM in some respects, and not so similar in others. It appears to use some dot product operations to perform this particular step in the projection, although it utilizes it in a way that's not immediately DOOM compatible (it is dealing with a single column when it does this; DOOM is trying to project the entire linedef at this point). I may have to do some serious thought experiments to adapt this approach.

I honestly *do* believe the viewangletox translation is not mathematically correct. It clips anything it determines to be out of range to 0 or viewwidth, even if the actual position of the vertex off-screen is nowhere near the horizontal screen boundary. I would expect this to create distortion in the texture mapping similar to what's being seen. I could be mistaken, of course, since as I've noted, this stuff makes my head spin.

The thing is, I looked at the tangent table, and it is reasonably accurate. It works for mlook well enough, for example. It's no more coarse than the finesine or finecosine tables, and this kind of severe distortion can't be explained by fixed-point either. DUMB uses fixed point math of the same sort as DOOM, and yet it apparently doesn't suffer this problem.

Share this post


Link to post
Quasar said:

I honestly *do* believe the viewangletox translation is not mathematically correct. It clips anything it determines to be out of range to 0 or viewwidth

Remember that segs are clipped to the view range (clipscope) before viewangletox is used on them. I see that piece of code as simply being doubly sure that bad x values are not used. I presume we're talking about this:

t = FixedMul (finetangent[i], focallength);
t = (centerxfrac - t+FRACUNIT-1)>>FRACBITS;

if (t < -1)
   t = -1;
else if (t>viewwidth+1)
   t = viewwidth+1;
This situation you describe (the player sitting on a linedef) can also be tricky for a more conventional renderer (like the one in DUMB).

this stuff makes my head spin.

Which probably means trying to code up a brand new rendering method wouldn't be a good idea :).

I don't know exactly what causes this problem. but I'd bet money that a loss of accuracy somewhere is the root cause.

Share this post


Link to post

Odd, I was fighting with viewangletox just this weekend. My visual problem is a bit different, I'm using a d3d9 renderer, and from certain angles the sky is getting through between the walls. I managed to repair the lines handled by R_ClipPassWallSegment by changing the following in r_bsp:

// Does not cross a pixel?
// killough 1/31/98 -- change == to >= for robustness
if ( x1 > x2 ) // my change
return;

It's just a hack not tested well. I found no solution to R_ClipSolidWallSegment though.

I don't use any of the original sine, tangent tables, generate them at startup, but it makes no difference.

Share this post


Link to post

Ajapted: No. That's the code used to generate the viewangletox table in R_InitTextureMapping. That is not used when drawing the segs themselves (the table is used, not the code).

The code I'm referring to is the code in R_AddLine that actually uses viewangletox. It is too long to paste here. The purpose of R_AddLine is to clip and add for rendering line segments, so your assertion about the lines having already been clipped I find to be false.

This is the main heart of the code, short of all the long-winded angle determination:

   // The seg is in the view range,
   // but not necessarily visible.
   
   angle1 = (angle1 + ANG90) >> ANGLETOFINESHIFT;
   angle2 = (angle2 + ANG90) >> ANGLETOFINESHIFT;
   
   // killough 1/31/98: Here is where "slime trails" can SOMETIMES occur:
   // SoM: This is also where all the line rendering bugs come from.
   // bouncy wall bugs are caused by the left vertex being WAAAY of the screen and the LUT
   // at that point becomes unstable and highly inaccurate. 
   x1 = viewangletox[angle1];
   x2 = viewangletox[angle2];
SoM says unstable an inaccurate; I'm strengthening that to mathematically incorrect. This is because in mapping everything to a plane prematurely, it causes a vertex that is BEHIND you to be mapped to a screen coordinate that is far to the right of you (such as the x2=960 visible in that screenshot).

No other 3D game engine ever written tries to project lines in this method, and it's no wonder because it's pure crap. I now understand that this is the part of the code Carmack was referring to when he talked about his mistake with using "polar coordinates" for clipping -- though that name doesn't really make sense in a strict math sense.

Share this post


Link to post
rpeter said:

Odd, I was fighting with viewangletox just this weekend. My visual problem is a bit different, I'm using a d3d9 renderer, and from certain angles the sky is getting through between the walls. I managed to repair the lines handled by R_ClipPassWallSegment by changing the following in r_bsp:

// Does not cross a pixel?
// killough 1/31/98 -- change == to >= for robustness
if ( x1 > x2 ) // my change
return;

It's just a hack not tested well. I found no solution to R_ClipSolidWallSegment though.

I don't use any of the original sine, tangent tables, generate them at startup, but it makes no difference.



That's because the clipper is not precise enough for hardware rendering. Its precision is in screen pixels but you'd need a lot more. If you want to do hardware rendering it's better to skip any code in the software renderer completely and write your own.

Share this post


Link to post
Quasar said:

SoM says unstable an inaccurate; I'm strengthening that to mathematically incorrect.

If the math was incorrect, it wouldn't work!

SoM's comment says the LUT is too inaccurate, which is exactly my point, use more accurate math and the problem will be fixed.

Edit: just to clarify something:

it causes a vertex that is BEHIND you to be mapped to a screen coordinate that is far to the right of you (such as the x2=960 visible in that screenshot).

Imagine if the screen was infinitely tall, then the right side of the screen is where that line should logically end. In other words, no vertical clipping has been done yet.

Share this post


Link to post

But it doesn't work; as soon as one vertex is behind you it totally freaks out. Clearly it cannot handle this case properly. If the entire line is visible, there's little or no distortion even when you're close to the line. This sounds incorrect to me.

It's ultimately not that important anyway. Incorrect or otherwise, it's not working to my satisfaction.

Share this post


Link to post
Ajapted said:

SoM's comment says the LUT is too inaccurate

Wait what?

I only ever complained :P

Actually I don't even remember that, unless it was Espi who noticed when portals HOM'd due to this.

Share this post


Link to post

Heheh. Of course, that LUT stands for look-up table :P Anyways I'm not making much progress on this. It might have to wait for post-3.33.50 :(

Share this post


Link to post

The problem is NOT the precision of the viewangletox-table.

i replaced

   // The seg is in the view range,
   // but not necessarily visible.
   
   angle1 = (angle1 + ANG90) >> ANGLETOFINESHIFT;
   angle2 = (angle2 + ANG90) >> ANGLETOFINESHIFT;
   
   // killough 1/31/98: Here is where "slime trails" can SOMETIMES occur:
   // SoM: This is also where all the line rendering bugs come from.
   // bouncy wall bugs are caused by the left vertex being WAAAY of the screen and the LUT
   // at that point becomes unstable and highly inaccurate. 
   x1 = viewangletox[angle1];
   x2 = viewangletox[angle2];
with
   x1 = my_viewangletox(angle1);
   x2 = my_viewangletox(angle2);

   angle1 = (angle1 + ANG90) >> ANGLETOFINESHIFT;
   angle2 = (angle2 + ANG90) >> ANGLETOFINESHIFT;
   
   // killough 1/31/98: Here is where "slime trails" can SOMETIMES occur:
   // SoM: This is also where all the line rendering bugs come from.
   // bouncy wall bugs are caused by the left vertex being WAAAY of the screen and the LUT
   // at that point becomes unstable and highly inaccurate. 
   //x1 = viewangletox[angle1];
   //x2 = viewangletox[angle2];
Note that i take the angles before 19 bits of precision is ditched. (the + ANG90 is just because the finetangent table goes from -90 degrees to +90 degrees instead of 0 to 180 as one would expect)

my_viewanglex()
extern fixed_t focallen_x;

int my_viewangletox(angle_t angle) {
	int ret;
	double t;

	double tang = tan((double)angle * M_PI / (double)ANG180);

	if (tang > 2)
		ret = 0;
	else if (tang < -2)
		ret = viewwidth;
	else {
		t = ((double)centerxfrac - tang * (double)focallen_x) / (double)FRACUNIT;

		if (t < 0)
			ret = 0;
		else if (t > viewwidth)
			ret = viewwidth;
		else
			ret = (int)t;
	}

	return ret;
}
The code is taken from the viewangletox generation, but modified to use doubles and tan() and all 32 bits of precision in the angle instead of just 13.

I don't see any difference in the wobbling lines after this change, so the problem must be something else then the precision of the LUT.

Share this post


Link to post
Anders said:

I don't see any difference in the wobbling lines after this change, so the problem must be something else then the precision of the LUT.

Fair enough.

Try rewriting R_ScaleFromGlobalAngle() in r_main.c using 'double' math, as well as the xtoviewangle[] lookup that appears in the calls to R_ScaleFromGlobalAngle in R_StoreWallRange in r_segs.c.

Edit: actually that may not be enough, as rw_scale, rw_scalestep, topfrac, topstep, bottomfrac and bottomstep will still be in 16.16 fixed point. Ideally replaced these variables with 'double' too.

Share this post


Link to post

If you are concerned about angle precision another thing to consider is to replace R_PointToAngle2 with:

angle_t R_PointToAngle2 (fixed_t x1, fixed_t y1, fixed_t x, fixed_t y)
{
	return (angle_t)(int)((float)atan2f(y-y1, x-x1) * ANG180/M_PI);
}

The precision of the original function is just plain awful and at least with hardware rendering contributed to a lot of rendering glitches. I can't say how much it might affect the software renderer though. Of course you have to use the old imprecise formula when angles are used in demo-compatibility-sensitive code.

On the other hand, I never had issues with fixed point or binary angle precision. But if the values that go in are imprecise the code has no chance of calculating precise results.

Share this post


Link to post

I already know this is not a precision problem, and I told you guys this about 5 posts ago. I do thank Anders for the effort and trouble of proving this for me, however ^_^

The problems are:
1. Using angles to the vertices instead of cartesian coordinates transformed into screenspace.
2. Clipping the angles using the table.

From what I've read, you apparently cannot properly deal with primitives spanning across the near-clipping plane even in polygon-based renderers without using a homogeneous coordinate system (this means a 4x4 transformation matrix with the extra "homogeneous" coordinate w). The alternative is to have messed up texture mapping.

I have read just about everything there is to read about projection and I've identified many key things in DOOM already, such as the distance to the projection plane (already calculated as focallen_x). I know how to do the translation step, but not the rotation.

This is because I don't know how to deal with the fact that DOOM's coordinate system is different from the kind usually used (ie, [x,y] starts in the upper left hand corner in screenspace coordinates, and in world coordinates, the z axis is up rather than y). All examples given on Wikipedia and in most textbooks are for the "normal GL" axes with screenspace origin in the lower left corner, and the y axis up in world coordinates.

ZDoom's already fixed this, and according to Heit's changelog he started it before he added any Build code. However, it seems to have been modified since that point so I cannot easily tell whether or not it has been tainted, so to speak. Also the calculations being used are different from any I've so far derived and thus I don't understand them, and as a human I tend to dislike what I don't understand :P

Share this post


Link to post
Quasar said:

I already know this is not a precision problem

Bullshit. Unless you've tried the suggestions above, using more accurate math everywhere, you can't say you know it isn't a precision problem.

From what I've read, you apparently cannot properly deal with primitives spanning across the near-clipping plane even in polygon-based renderers without using a homogeneous coordinate system (this means a 4x4 transformation matrix with the extra "homogeneous" coordinate w).


You must clip any segs which cross the viewplane to the viewplane (looking at everything in 2D, from above, the viewplane is just a line). You don't have to use matrices, and you don't have to use a 'w' coordinate.

. I know how to do the translation step, but not the rotation.

x2 = x * cos(angle) - y * sin(angle)
y2 = y * cos(angle) + x * sin(angle)

Share this post


Link to post

Sorry about my post above, I spent most of saturday to figure out r_bsp and I think I got it now.

I also found some unused code in Legacy that tried to replace viewangletox with some projection calculation, but it didn't work for me.

My visual problem with a d3d renderer was solved by doing the clipping with angles Doomsday-style.

Share this post


Link to post

I have found the definite cause of the wobbly lines.

It is this line in R_ScaleFromGlobalAngle:

if (scale > 64*FRACUNIT)
    scale = 64*FRACUNIT;
When I raise this limit, the effect improves, e.g. 128 is twice as good, 256 is four times as good, 1024 is very good.

This was testing a modified PrBoom using doubles for the rw_scale, rw_scalestep, topfrac, topstep (ETC) variables in r_segs.c. It is going to take some work to figure out how to actually increase the range of rw_scale without messing up rest of the fixed-point math.

Share this post


Link to post

O_o

EDIT: I tried it and it does help, but it doesn't *fix* it. There's still line wobbling, it's just less pronounced. Why is the scale factor limited to 64*FRACUNIT? o_O

Share this post


Link to post

Well here (with the double math) the wobble is reduced to around a single pixel, and that's probably no worse than a more conventional renderer.

It is limited to 64*FRACUNIT because of this:

topfrac = (centeryfrac>>4) - FixedMul (worldtop, rw_scale);
if rw_scale is not limited, then the multiplication with worldtop may overflow (which would be much worse). The higher the rw_scale limit, the lower the tallest wall can be (when rw_scale is near that limit anyway).

Maybe the more conventional geometry handling (like in DUMB or WT) will give better results, but it's a very major job to replace the angle stuff in DOOM.

Share this post


Link to post

I would say all those precision problems come from rw_distance and R_ScaleFromGlobalAngle and all calculations based on it. If this could be rewritten without using angles and with proper clipping at the right places, then the wobbling, the near wall distortions and the rendering bugs with tall sectors could all be solved.

Share this post


Link to post

I honestly think floating point will offer the best chance to do that. DOOM suffers from ridiculous integer overflow problems because it insists on using 16.16 fixed point, which is less precision than single-precision float and can't deal with the necessary intermediate results. Lee Killough already added intermediate 64-bit math in several places during work on BOOM and that still wasn't enough (it's also not fast on x86 32-bit processors either).

Share this post


Link to post

Here's a hack that works pretty well for me. Someone please improve it...this code performs a per-level adjustment vs. being based on view position. WARNING: It may also be necessary to apply the "dropoff overflow" fix in PrBoom Plus (search the PRBoom Plus source for "dropoff overflow"). Then again, it may not be necessary, since dropoff overflow is what this code attempts to avoid.

**********************************************************************IN R_SEGS.C:
* place the block of code below -somewhere appropriate- in r_segs.c
* change all instances of HEIGHTBITS to heightbits
* find instances of >>4 and >>=4 in R_StoreWallRange, and change to >>invhgtbits and >>=invhgtbits.

I think this is all of them (in my port, anyway):

worldtop >>= invhgtbits;
worldbottom >>= invhgtbits;
topfrac = (centeryfrac>>invhgtbits) - FixedMul (worldtop, rw_scale);
bottomfrac = (centeryfrac>>invhgtbits) - FixedMul (worldbottom, rw_scale);
worldhigh >>= invhgtbits;
worldlow >>= invhgtbits;
pixhigh = (centeryfrac>>invhgtbits) - FixedMul (worldhigh, rw_scale);
pixlow = (centeryfrac>>invhgtbits) - FixedMul (worldlow, rw_scale);

********************************************************************************************

//[kb] hack to improve rendering precision (wall wiggle)
int max_rwscale = 64*FRACUNIT;
int heightbits = 12;
int heightunit;
int invhgtbits;

//[kb] Adjusts renderer wall/texture precision based on the maximum difference in height
// of all adjoining sectors. P_SetupWiggleFix() passes max_diff, which is what is needed
// to make the renderer as precise as possible without overflowing the 16.16 fixed point
// coordinate system. As a bonus, this also allows the render to display sectors that are
// up to 32767 units tall (or greater, maybe), improving an old bug. Doom doesn't allow
// anything to pass through a sector any taller than 32767 units, so this limit is ok.
// Of course, levels with sectors this large WILL suffer from some wall wiggle...
void R_SetWiggleHack(int max_diff)
{
int max_scale, h_bits;

if (max_diff < 256)
max_diff = 256;

h_bits = 12;
max_scale = 0x80000 / max_diff;

//[kb] scale calculation. The higher the max_scale the better, but go too far and
// overflow the texture scaling variables. Attempt to get max_scale at least to
// 1024. On the other side, h_bits is made less precise - go too far and the top
// and bottom of textures start to wiggle. Originally set to 12, 11 and 10 seem ok.
// Only use 9 for levels with really tall walls, because that is where height
// precision starts to become apparent.
while(max_scale < 2048 && h_bits > 9)
{
max_scale <<=1;
--h_bits;
}

max_rwscale = max_scale<<FRACBITS;
heightbits = h_bits;
heightunit = (1<<heightbits);
invhgtbits = 16 - heightbits;
}

*************************************************************
IN P_SETUP.C:

* Place the block of code below -somewhere- in p_setup.c
* Put this line into P_SetupLevel, after P_GroupLines + P_RemoveSlimeTrails:
P_SetupWiggleFix(); // [kb] adjust wiggle fix as necessary

//[kb] Determine the maximum height difference between all adjacent sectors and adjust the
// renderer wall precision to attempt to prevent visible left-to right wiggling of walls, especially when
// looking straight down a linedef. Problem is, if the precision is adjusted too far, wall
// heights start to wiggle. It would be better to adjust per seg.

void R_SetWiggleHack(int max_diff);
void P_SetupWiggleFix (void)
{
int curmaxheight, curminheight;
int i = numlines;
line_t *ld = lines;
int maxdiff = 0;
int h;
for ( ; i--; ld++)
{
curmaxheight = -32768;
curminheight = 32767;

if (ld->frontsector)
{
h = ld->frontsector->ceilingheight>>FRACBITS;
if (curmaxheight < h)
curmaxheight = h;

if (curminheight > h)
curminheight = h;

h = ld->frontsector->floorheight>>FRACBITS;
if (curmaxheight < h)
curmaxheight = h;

if (curminheight > h)
curminheight = h;
}

if (ld->backsector)
{
h = ld->backsector->ceilingheight>>FRACBITS;
if (curmaxheight < h)
curmaxheight = h;

if (curminheight > h)
curminheight = h;

h = ld->backsector->floorheight>>FRACBITS;
if (curmaxheight < h)
curmaxheight = h;

if (curminheight > h)
curminheight = h;
}

if (maxdiff < (curmaxheight - curminheight))
maxdiff = curmaxheight - curminheight;
}

// adjust renderer based on max height difference
R_SetWiggleHack(maxdiff);
}

Share this post


Link to post

The main problems I've found are these (and yes, at this point I consider myself somewhat of an expert on the subject):

1. Doom itself gleans much information from the scale, however if you look in R_ScaleFromGlobalAngle you will notice that there is a max scale. Now, EVERYTHING about how a line will render is determined from this scale minus the screen x1 and x2 values. Doom NEVER clips lines but instead relies on the fact that it is so heavily angle based to avoid many of the problems with conventional x/z style projections and it renders obsurd lines that go off way behind the camera. If you will follow this to its logical conclusion you will find the possibility of lines with obsurdly large scale values and y pixel values which would almost definitely wrap and crash the game. To remedy this, Carmack simply LIMITED the scale values. So these capped scale values are used for y projection, texture scale, and so on, but they are wrong from the beginning. So you can imagine how these capped scale values are going to cause many problems! This is what causes the bug Quasar` showcased in his screenshot at the beginning of the thread. It is NOT precision related and good freaking luck fixing it without rewriting the renderer. So even if you find cases where you can increase max scale, you are still going to encounter wobbly lines. You may slightly lessen the severity of the wobble, but you won't fix the problem.

2. The large line wobble IS precision related but this is a problem with the step variables (scalestep, topstep, bottomstep) ect. and also the (once again) angle related math used to obtain said values. The problem I see is: If you use more accurate versions of the angle-math to render the scene you've lost ALL the speed advantage they had over conventional rendering methods.

Share this post


Link to post

Please sign in to comment

You will be able to leave a comment after signing in



Sign In Now
×