Search In
• More options...
Find results that contain...
Find results in...

# Question about the trigonometry in the Doom source

## Recommended Posts

I've been looking through the Doom source code to get a sense for how things work. What immediately stood out to me was two things:

1. This "fixed_t" data type is used an awful lot.

2. Trig functions are done via lookup table

From what I can tell, the fixed_t data type is really a 32-bit unsigned int where the rightmost 16 bits are used to represent a fractional-part numerator (where the implied denominator is 2^16 = 65536), and the leftmost 16 bits represent the actual whole number in question. So a fixed_t is like an encoded form of w + f/65536 where w and f are whole numbers. The actual value stored in the fixed_t data type is basically (w + f/65536) * 65536.

Angles in DOOM appear to be done in a way where the unit circle is broken up to fill an entire unsigned 32-bit integer from 0 all the way up to 0xffffffff (0 to just under 360 degrees). So 45 degrees would be 0x20000000, 90 degrees 0x40000000, etc. Once nice side effect being that you can add/subtract angles and you get the modulo / wrap-arounds for free due to the data type used. But then when this angle is actually used for anything involving trig functions, it gets bitshifted down by 13 bits first, mapping us to a range from 0 all the way up to 8192 (providing a resolution of (1 / 8192) * 360 = about .04 degrees.)

All that said, if you give me an angle x that's already been reduced to the 8192 range, the corresponding fixed_t value in the sine table should be:

floor(sin((x / 8192) * 2 * pi) * 65536)

If x = 0 then the result of this should still be 0. But in the table it's actually represented as 25, which means that sin(0) in Doom is really more like 25/65535 = 0.0003814755!

I didn't know why this was the case because the output is pretty close to the hardcoded values but not quite there, but by chance found that the values match if I add 0.5 to x first:

floor(sin(((x + 0.5) / 8192) * 2 * pi) * 65536)

My question is basically "Why?" Why have these values been offset like this? Keeping the table symmetrical while avoiding any possibility of divide-by-zero errors, or something else?

Edited by DoomNoob

This has been noted for a long time but I don't think we are aware of Carmack's reasoning for it. IIRC, the values present in the tables would correspond roughly to the middle of the range of values that map down to that index in the table. My guess then would be that the idea was to "average out" the loss of precision in a manner of speaking.

Quasar's answer is spot on. The 25 is most-likely a "fudge factor". With all the possible view angles and texturing widths and heights, not to mention all the other uses of these tables, having a hard 0 in there invites some diabolical situations: Trying to texture map walls with 0 thickness really piss off those calculations. And, yes, divide-by-zero checks can sometimes be avoided by not having zeroes.

If I had to guess, I would think that Carmack added the + 0.5 in an attempt to fix an immediate issue he encountered while building the renderer. And, it was probably forgotten afterwards.

If you think about it, there are some weird occurrences that can happen - for example the 0-thick wall. Doom's walls have no thickness, so if you're looking down the side of a wall with zeros in your sine table, your index into the texture table cannot be calculated - it is both 0 and infinite! So you test for this case. But, if you're test is slightly off, you get a slime trail. Carmack worked hard to avoid slime trails, so he could paint the floors/ceilings via something like a flood-fill. Adding a small fudge factor here and there can solve some problems, even if a bit inaccurately.

Edited by kb1