# Powers of Two

Some graphics libraries expect textures to have resolutions that are powers of 2, like 1024 by 256. Texture looks up are faster if you follow this constraint. Let's explore a few reasons why this might be.

What is $$5 \ll 1$$? The value 5 is being shifted left 1 bit. In binary, that's $$101_2 \ll 1$$, which is $$1010_2$$ or $$10_{10}$$. Extending this, $$5 \ll 2$$ is $$10100_2$$ or $$20_{10}$$. $$5 \ll 3$$ is $$101000_2$$ or $$40_{10}$$.

Shifting a binary number leftward is the same as multiplying by a power of 2. A left-shift of 1 bit is the same as multiplying by 2. A left-shift of 2 bits is the same as multiplying by 4. A left-shift of 3 bits is the same as multiplying by 8. A left-shift of $$n$$ bits is the same as multiplying by $$2^n$$.

If you've got integer texture coordinates row and column and an image of a particular width stored in row-major order, then you turn your 2D coordinates into a 1D index into the pixel buffer using this equation:

$$i = \mathrm{row} \times \mathrm{width} + \mathrm{column}$$

However, if you know the width is $$2^n$$, then you can express this multiplication as a left-shift:

$$i = \mathrm{row} \ll n + \mathrm{column}$$

Shifting is generally faster than multiplication in hardware. That's why many graphics libraries either require or suggest textures have resolutions that are powers of 2. WebGL allows non-power of 2 textures (NPOT), but texel lookups may be slower.

Additional, you cannot use gl.REPEAT or gl.MIRRORED_REPEAT for wrapping coordinates on NPOT textures. Only gl.CLAMP_TO_EDGE. Why might this be? Suppose you have a texture that is 64 texels wide. Column 50 on the first tile repeats on the next tile at column 50 + 64. And then again at column 50 + 64 + 64. These are the binary representations of the coordinates on the first four tiles that map to 50:

$$\begin{array}{lcr} 50 &=& 110010_2 \\ 50 + 64 \times 1 &=& 1110010_2 \\ 50 + 64 \times 2 &=& 10110010_2 \\ 50 + 64 \times 3 &=& 11110010_2 \end{array}$$

You can see from the binary representations how to get the coordinates back in the [0, 64) range: you mask out the six lower-order bits. The mask is 111111, which is 63 in decimal. In general, you calculate your in-range coordinate like this:

$$s' = s \text{ & } (\mathrm{width} - 1)$$

Mirroring only works when the size is a power of 2 because only then will masking put the texture coordinates back in range.

If you have an NPOT texture and are considering using it in a renderer, you have several options:

1. Live with it, accepting that looking up texels may be slower and not all texturing options may be supported.
2. Pad the image so that its dimensions round up to the nearest higher powers of 2 in your graphics editor. The padding wastes disk and increases download times.
3. Pad the image to the nearest higher powers of 2 at runtime. JavaScript's Image class doesn't give you much direct control over pixels. However, its canvas element does. You draw an NPOT texture into a POT canvas and extract the new image with this function:
function padToPot(image) {
const canvas = document.createElement('canvas');
const context = canvas.getContext('2d');
canvas.width = powerOfTwoCeiling(image.width);
canvas.height = powerOfTwoCeiling(image.height);
context.drawImage(image, 0, 0);
return context.getImageData(0, 0, canvas.width, canvas.height);
}
4. Allocate a texture on the GPU whose dimensions are the nearest higher powers of 2 and upload the texels as a sub-image within the texture:
gl.texImage2D(gl.TEXTURE_2D, 0, gl.RGBA, powerOfTwoCeiling(image.width), powerOfTwoCeiling(image.height), 0, gl.RGBA, gl.UNSIGNED_BYTE, null);
gl.texSubImage2D(gl.TEXTURE_2D, 0, 0, 0, image.width, image.height, gl.RGBA, gl.UNSIGNED_BYTE, image);

The code in several of these solutions requires you to compute power-of-2 ceilings, such as these:

\begin{align} 97 &\rightarrow 128 \\ 129 &\rightarrow 256 \\ 1992 &\rightarrow 2048 \\ \end{align}

You compute the nearest power of 2 that's greater than or equal to a number by taking the number's base-2 logarithm, rounding up, and raising 2 to that power. This function does the trick:

function powerOfTwoCeiling(x) {
return Math.pow(2, Math.ceil(Math.log2(x)));
}

The options that involve padding the image generally require you to adapt the texture coordinates since they require changing the image resolution. The proportions need to account for the new resolution.

Someday these limitations on NPOT textures may go away. The practical concerns that led to these limitations might not even be relevant on modern hardware, yet libraries and developers continue to abide by them for backward compatibility.