Why were the textures sized this way?

I was thinking about this the other day, and I'll bet someone here knows the technical reasons behind this.

So in a modern game, textures tend to be in powers of two because that's how graphics cards handle them. Even if the engine itself "could" support textures with odd dimensions, the hardware actually forces the dimensions of the textures.

But, what actually set the limits for textures in Doom? There were a number of wall textures and sprites that were various odd-sizes, and yet the walls were usually 64x128, powers of two. But they apparently didn't have to be. And if there were no arbitrary restrictions for sizes, using powers of two seems like an odd choice when you could have made the walls be 50x100 or some dimension that makes sense to humans.

Was there actually some sort of technical reason most walls were 128 texels tall? Why then were some a different size?

The core drawing function is hardcoded to use 128 texel high wall textures, because it's incredibly easy to make textures repeat vertically that way by just looking at the last 7 bits of the texel position you're at. The original DOS version included a specially handcoded ASM version of the core rendering loop to make sure this was as fast as possible.

Here's my attempt at a lay explanation (I'm assuming you're a non-programmer).

Textures are divided up into thin slices (columns), each a pixel wide. So if you have a 128x128 texture, you can think of that as being 128 columns, each of which is 1x128 in size. If we have a line representing a wall, we can map each point on the line to one of these columns, and that's the slice of texture we'll draw at that point.

So suppose you have a line representing a wall. Maybe the line is 300 units long. The line starts at one point (vertex) and ends at another. Suppose you pick a particular point on that line, and you want to find which column of texture you want to draw for that point. Let's say the distance from the start of the line to the point you're interested in is 203 units, so just over 2/3 of the way along the line. Which column should we draw?

It turns out that to find out, we want to divide by the texture's width, but what we really want is the remainder, not the result of the division. So in the example above, we're at point 203, our texture is 128 wide, 203 / 128 = 1 + remainder 75. In programming we usually use % to represent the remainder function, so 203 % 128 = 75.

For humans, dividing by certain values is very easy. For example, 2000 / 10 = 200, and 9382 / 100 = 93.82. It's easy to do because the divisor is a power of 10 and we think and write in base-10. So it's just a matter of moving the decimal point. It's also similarly easy to calculate the remainder function if we're dividing by a power of 10. For example, 2000 % 10 = 0, 9382 % 100 = 82. You just take the least-significant digits from the number. Computers operate in base-2 instead. So just like we find it easy to divide by powers of 10, it's easy for them to divide by powers of 2 in a very efficient way.

Back in the '90s, doing divide operations (including remainder) was very expensive. CPUs were quite slow back then and divide operations were slow. So if you check the Doom engine source code for example, you'll probably find that divides are pretty rare. But the one thing it is possible to do quickly and efficiently is dividing by or taking the remainder of a power of 2 (just like it's easy for us with base-10). So to tie it all together, it's possible to make the game run more efficiently and find the texture column of a particular point on a line if you assume that textures are always powers of two in width.

By the way, here's the code that does what I've been describing. The & there is conceptually a %, but using bitwise operations to avoid a proper divide instruction.

Marscaleb said:

using powers of two seems like an odd choice when you could have made the walls be 50x100 or some dimension that makes sense to humans

People who code, and that loosely includes Doom level designers, are not your typical human. Powers of two make perfect sense to [most of] them.

Bad King John said:

People who code, and that loosely includes Doom level designers, are not your typical human. Powers of two make perfect sense to [most of] them.

Or rather; Computers don't work in base 10, they work in base 2 (you know, binary) which converts well with base 16 (hexadecimal), where powers of two make for the simplest algorithms.

Marscaleb said:

you could have made the walls be 50x100 or some dimension that makes sense to humans.

Don't take the numbers literally, but with vintage-1993 CPUs the speed difference between

"y = y % 100" // wrapping a 100 pixel texture
and
"y = y & 127" // wrapping a 128 pixel texture, this can be done with a far cheaper operation because 128 is a power of two.

was probably 30-40x, yes, that single modulus cost more than the actual rendering. The binary and was nearly free. Even on today's computers it still makes sense to have special cases for this but the difference has become less critical as CPUs got faster.

But for a commercial game of its vintage it was not necessary to write a perfectly flexible texture renderer, just something that worked well enough if the limitations could be communicated to the artists.

It's also worth remembering that most, if not all, things have half-widths ( or radius, though it's not actually a typical radius since the hitboxes are, well, boxes ) and heights that are multiples of 2, 4, 8, or 16. Because of this, having base-10 textures would lead to less cohesion between geometry and actors, which may not sound like a big deal but I'm sure anyone who's made maps can tell how nice it is how all those things just fit together so well.

Bad King John said:

People who code, and that loosely includes Doom level designers, are not your typical human. Powers of two make perfect sense to [most of] them.

Well, yeah, I'm more comfortable with working in powers of two than I am in base ten, but that comes from all my time spent building levels in powers of 2. Doom, Duke 3D, Unreal Tournament... Yeah it is easy for me.
But even so, it's a learned skill. And when Id was building Doom, they didn't have ten years of experience building maps for Unreal Tournament that shifted how they thought of these levels. So I was thinking back, and wondering why they set up the game this way.

Thanks fraggle; that's a very good explanation.
And I'd consider myself an amateur programmer, but still that was an effective explanation.

y'seemed to have forgotten the first three words of what you quoted there bud

( especially when you consider what era of coding we're talking about and the era which a lot of id coders got started in - when you're working with DOS and older, working with binary is essential for anything minutely complicated )

And to be more explicit:

fraggle said:

By the way, here's the code that does what I've been describing. The & there is conceptually a %, but using bitwise operations to avoid a proper divide instruction.

Graf Zahl said:

"y = y % 100" // wrapping a 100 pixel texture
and
"y = y & 127" // wrapping a 128 pixel texture, this can be done with a far cheaper operation because 128 is a power of two.

The & operation does a comparison on each bit. If both are true (1), the result is true. In other words: 0 & 0 = 0, 0 & 1 = 0, 1 & 1 = 1. Since it works on each bit, it can be thought of as a mask that allows to only see certain bits from a value, making sure the other bits will be considered to be 0. When you do y = y & 127, look at the binary representation of 127: 01111111. What you do this way is make sure that the number you get will be between 0 and 127, values from 128 to 255 would require the first bit to be 1 and you know you won't get that. In essence, what it does is:

Linguica said:

just looking at the last 7 bits

And mathematically, y = y & 127 will give you exactly the same results as y = y % 128. However, you get to not use a remainder operation, which means you get to not use a division. It was back then a very useful optimization. If you look at the Doom source code, you'll find a lot of such bitmasks here and there, because it's very handy to be able to skip a division. However, mathematically, that only works for powers of two: x & 63 will be the same as x % 64, for example; but x & 37 will not be the same as x % 38! So, to be able to use this optimization, they had to use powers of two.

Likewise, they use a lot of multiplication and divisions by powers of two because they can be replaced by the left and right shift. In the same way that you can multiply a number by a power of 10 just by adding or removing 0s, a computer can do the same for powers of 2. And shifting bits left or right so as to add or remove zeroes is faster than actually multiplying or dividing by two. It's because there are these bit functions that are faster than arithmetic functions that powers of two were so popular back then.

It was done that way for programming optimization, but it also makes it convenient to build levels with proportions of 1/4, 1/8, etc.

Not everybody does it that way, though. Just the other day I discovered CROSS.WAD, which was the first Deathmatch level ever made (by hand, without an editor!) If you look at the vertex coordinates, you'll see that they are actually aligned to a 50x50 grid.

Graf Zahl said:

was probably 30-40x, yes, that single modulus cost more than the actual rendering. The binary and was nearly free. Even on today's computers it still makes sense to have special cases for this but the difference has become less critical as CPUs got faster.

Actually, rather than CPUs becoming faster in terms of clock speeds, it helped that most architectures converged towards a pipelined RISC paradigm, so that most CPU instructions could now be executed more or less in 1 CPU cycle (or even execute more than one per clock cycle, IPC>1.0) -with Intel, the first CPU to do that was the i486, so this particular optimization was fairly critical for 386s.

That being said, any decent optimizing compiler even back in the day would've optimized away that modulo operation with a bitwise AND anyway, as soon as it realized the circumstances (modulo with a off-by-minus-one power-of-two constant). With hand-written assembler code, it's a bit of a different story, as most assemblers aren't supposed to alter the code they receive in any way, so the only viable way to force a modulo operation in that specific circumstance would be to actually hand-code it in assembly and say to the assembler "no questions asked, I really want THIS to be executed, not a functional equivalent".

komojo said:

(by hand, without an editor!)

komojo said:

actually aligned to a 50x50 grid.

Probably cause and effect right there. It's pretty likely that the actual dimensions of things weren't exactly pretty clear, nor was there much concern for texture alignment when all you're doing is hex editing or whatever. So, it'd only be natural to assume the default vertices ( if those were even given any attention ) weren't placed according to any pattern, and that something human-sensible would be a good standard.

Marscaleb said:

There were a number of [...] sprites that were various odd-sizes, and yet the walls were usually 64x128, powers of two.

Unlike wall textures, sprites don't tile, and the % (respectively &) operation is in place specifically to guarantee proper tiling.

fraggle said:

Here's my attempt at a lay explanation (I'm assuming you're a non-programmer).

Textures are divided up into thin slices (columns), each a pixel wide. So if you have a 128x128 texture, you can think of that as being 128 columns, each of which is 1x128 in size. If we have a line representing a wall, we can map each point on the line to one of these columns, and that's the slice of texture we'll draw at that point.

So suppose you have a line representing a wall. Maybe the line is 300 units long. The line starts at one point (vertex) and ends at another. Suppose you pick a particular point on that line, and you want to find which column of texture you want to draw for that point. Let's say the distance from the start of the line to the point you're interested in is 203 units, so just over 2/3 of the way along the line. Which column should we draw?

It turns out that to find out, we want to divide by the texture's width, but what we really want is the remainder, not the result of the division. So in the example above, we're at point 203, our texture is 128 wide, 203 / 128 = 1 + remainder 75. In programming we usually use % to represent the remainder function, so 203 % 128 = 75.

For humans, dividing by certain values is very easy. For example, 2000 / 10 = 200, and 9382 / 100 = 93.82. It's easy to do because the divisor is a power of 10 and we think and write in base-10. So it's just a matter of moving the decimal point. It's also similarly easy to calculate the remainder function if we're dividing by a power of 10. For example, 2000 % 10 = 0, 9382 % 100 = 82. You just take the least-significant digits from the number. Computers operate in base-2 instead. So just like we find it easy to divide by powers of 10, it's easy for them to divide by powers of 2 in a very efficient way.

Back in the '90s, doing divide operations (including remainder) was very expensive. CPUs were quite slow back then and divide operations were slow. So if you check the Doom engine source code for example, you'll probably find that divides are pretty rare. But the one thing it is possible to do quickly and efficiently is dividing by or taking the remainder of a power of 2 (just like it's easy for us with base-10). So to tie it all together, it's possible to make the game run more efficiently and find the texture column of a particular point on a line if you assume that textures are always powers of two in width.

By the way, here's the code that does what I've been describing. The & there is conceptually a %, but using bitwise operations to avoid a proper divide instruction.

A nice, clear, clean layman's explanation, fraggle. Well done!