Classic Doom source code questions

[M2m]

Is this a good place to go if you have questions about the Doom source code ?

 

I’m digging through the Doom source code, and there are some things i can’t figure out. I already looked in the GAME ENGINE BLACK BOOK DOOM from Fabien Sanglard but still I couldn’t get answers. 

 

Like for example I have a question in regard to the doom finesine table in tables.c. 
 

As I undertstand the table captures the full 360degrees for sine (and cosine - thats thats why it has 10240 elements in difference to 8192 elements; an additional offset by FINEANGLES/4 or pi/2).

 

Now my questions is: Wouldn't it be more efficient to only capture the 1st quadrant (90 degrees) in a lookup table and cosequently adjust the sign (+/-) and shift the lookup.

 

For example:

sin(37 deg) = -sin(217 deg) = -cos(127 deg) = cos(307 deg) = (+/-)0.60181502315

 

So you could either just have 1/4th of the original lookup table size or maybe higher precission with an equally long LUT.

 

Computationally you add 4 comparions (in which quadrant is the angle), a shift (substraction) and a mult by -1 vs a div by 4 for the cosine.

 

Is there a reason for the sine table going thorough all’s 4 quadrants ? 

[Sinshu]

That's what I want to know, too.

 

By the way, if only the 1st quadrant is used as the LUT, the table size can be further reduced by using unsigned 16-bit integers.

[RjY]

I don't know, I suppose on 1993 systems it was faster overall to have a bigger table, and the simplest possible calculation of offset for table lookup, with no branches, maybe even a single instruction. I think the relative latency of memory access was much lower in those days. Doom does seem to favour lookup tables over pure calculation, especially to avoid multiplications and divisions. Nowadays I think you have to care a lot more about cache misses, so you'd favour a more complex calculation of offset into a smaller table that fits into the CPU cache. Does that sound reasonable? I might be talking rubbish, sorry if that's the case.

[M2m]

I mean, I totally understand the need for LUT especially for trigonometric functions in 1993. I just figured that it'll work with a LUT of 1/4 length as well, but maybe I'm missing something ?

 

Another question:

Whats the input of tantoangle[2049] array ? It of course contains angles in BAM, being 45° (536870912, 0x20000000) at [2049] and 0° at [0]. But what kind of values are 'thrown' at tantoangle  (obviously values between 0 and 2049, but thats not what i mean) ?

[SaladBadger]

The code used to calculate it is still present in r_main.c, just commented out.

    int	i;
    long	t;
    float	f;
//
// slope (tangent) to angle lookup
//
    for (i=0 ; i<=SLOPERANGE ; i++)
    {
	f = atan( (float)i/SLOPERANGE )/(3.141592657*2);
	t = 0xffffffff*f;
	tantoangle[i] = t;
    }

The input is mainly used for R_PointToAngle which extracts an angle relative to the origin for a given x and y coords -- so basically an atan2 function. This function calculates the slope with SlopeDiv, which does a bounds check and also checks for a divide overflow on the denominator. Thinking about it, this should basically be the case that 0 corresponds to a slope of 0 and 2048 corresponds to a slope of 1, the inbetween values being linear (if you look at the values in the table, you can see they're indeed roughly linear), with it outputting 45. The function PointToDist just performs a FixedDiv and shifts down by DBITS, which converts a 16:16 fixed point value in the range 0-1 to that range.

Edited January 23, 2022 by SaladBadger