WebGL texture slots allocation

A bit about WebGL texture

For those who don't know how it works.

In WebGL, the way we show an image is by placing it on a texture, and sending it to the GPU.

The code looks something like this:

      this.gl.texSubImage2D(
        GL.TEXTURE_2D,
        0,
        dstX,
        dstY,
        dstWidth,
        dstHeight,
        GL.RGBA,
        GL.UNSIGNED_BYTE,
        mediaInfo.texImgSrc,
      );

And while this seems a bit complex, the main thing to note is that we just apply the image mediaInfo.texImgSrc and place it within a certain rectangle [dstX, dstY, dstWidth, dstHeight].

The image source is generally an image, but it can also be a canvas, or even a video.

The bad news is, there's a limited number of texture (Only 16 on most computers). Just imagine creating your game and you have to choose only 16 images to show on screen. On top of that, if your animation takes 8 frames, you're left with just 2 sprites to show.

Ok I'm exaggerating. Nobody really write programs like that. But the main point is that to show multiple sprites on the screen, you need to treat your texture as a sprite-sheet. That means, put several images on one of the 16 textures, and the shader will know which section to select.

Now how many sprites can you put on a texture? Well that depends on the size of your sprite. Let's say a nice looking sprite is at least 256x256. The good news is that textures can be huge. On most computer, is a whooping 4096x4096 pixels! So let's see how many sprites you can fit:

$(16 * 4096 * 4096) / (256 * 256) = 4096$ sprites

Not bad!

At this point, if you want to just use 256x256 sprites, you can pretty easily skip the remaining of this article that I spent a lot of effort writing, because splitting the texture into 256x256 chunk is not that difficult.

(Anyway the main purpose is the article is to show off some neat feature I implemented for my game engine, so you know how it's gonna go...).

Still reading? Good.

Some challenges

Fitting various sprite sizes

My goal was to allow various sprite sizes to be allocated into a texture. If I were to store them all into 256x256 slots, we might end up with small sprites taking more space that it needs, or large sprites having reduce image quality.

Texture slots alignment

While I could just pack textures next to each other, I need to align them in slots of sizes and position that are powers of 2. That means a 200x200 textures has to take a 256x256 slot, and that slot can only be at position: [0,0], [256,0], [256,256], [0,256], [512, 0] ... Basically the (x, y) must be a multiple of its size.

Here is the reason why:

Another limitation of WebGL is the amount of attributes we can pass per items we want to display. That limit is 16 attributes of 4 numbers each. And I got tons of things to pass to my sprites. The transform matrix is already taking 4 attributes because it's using 4x4 numbers.

So let's say I wanted to save a slot in a texture. The slot rectangle is defined as: [x, y, width, height]. We also need the texture index, so that's already 5 numbers.

By enforcing slots as powers of 2, we can can reduce the size it takes:

• $16, 32, 64, 128 ... 4096$ is $2^4, 2^5, 2^6 ... 2^{12}$ . So the width and height can just share one number.

slotWidth = pow(2, wh % 16);
slotHeight = pow(2, floor(wh / 16));

• Also, we can actually combine all x, y, textureIndex into one single number: The slotNumber. We can think of each slot aligned next to each other until the end, and after reaching the end of the row, wrap to the next row. Then once we reach the last slot in a texture, wrap to the next texture!

numCols = 4096 / slotWidth;
numRows = 4096 / slotHeight;
cellsPerTexture = numCols * numRows;

slotCol = slotNumber % numCols;
slotRow = floor(slotNumber / numCols) % numRows;

slotX = slotCol * slotWidth;
slotY = slotRow * slotHeight;
textureIndex = floor(slotNumber / cellsPerTexture);

So we can store all those 3 numbers into just 1.

The tradeoff is that we could waste a bit of space in the texture. For instance, our sprite is 200x200, and we need a 256x256 slot to fit that. (256x256 - 200x200 pixels). I found however that when packing texture in slots that aren't powers of 2, we tend to get imperfect cuts. A sprite might end up either missing some pixels, or getting extra pixels from the sprite next to it. So the choice of making all slots power of 2 also also pros in terms of visuals.

Performant sprite animation

In WebGL, it's best to reduce the amount of texture updates performed. So when I want to animate a sprite, I store the entire sprite-sheet into the texture.

Here's an example of sprite-sheet from Dobuki's Epic Journey

Now since those are small sprites, I could have just stored them willy nilly anywhere in the textures, and keep updating the slotNumber every frame.

However, even updating the slotNumber attribute of a sprite can be costly. Imagine you have 10000 sprites all animating at the same time. You would have to send 10000 updates every frame.

So to address that, we have to do a few things:

• The sprite-sheet is packed as one big image, split into frames that are powers of 2. In the sprite-sheet above, we could choose the sprites to be 256x256. Since we have 14 rows of 16 it would pretty much take an entire 4096x4096 texture.
• The attributes sent for each sprite should contain all the information it needs to animate:
  • frameWidth / frameHeight: Width and height of a frame of animation. Note that this is a smaller chunk of the big sprite allocated in the texture.
  • animCols: Number of columns in the frames table.
  • frameRate: Frames per second
  • startFrame: First frame of animation
  • endFrame: Last frame of animation

With that, to know the current frame to show, we do some math:

currentFrame = startFrame + (time * frameRate) % (endFrame - startFrame + 1)

time is a uniform that is sent every frame. Since it's a uniform, we only send it once per frame, even to animate 10000 sprites.

Then given the currentFrame, we can figure out the offset:

col = currentFrame % animCols
row = floor(currentFrame / animCols)
// offset the x, y by the animation
animX = col * frameWidth
animY = row * frameHeight

Now we have the position of the frame. We still need to incorporate the width and height of the frame into our code.

For that, we need to send a (x, y) pair for each vertex that represent the 4 corners of our frame. The 4 corners that represent top-left, top-right, bottom-right, bottom-left will be: [0, 0], [1, 0], [1, 1], [0, 1].

Those values never change, and they are the same for all sprites. So let's say those values are stored as the variable corner, we can now calculate the final texture position that gets passed to the fragment shader:

textureX = slotX + animX + corner.x * frameWidth;
textureY = slotY + animY + corner.y * frameHeight;

Texture slot allocator

Fitting those image into the texture

So now that we figured out a way to use those allocated slots, we need a way to allocate properly.

For that, I built a package that does the allocation given a set of images:
https://github.com/jacklehamster/texture-slot-allocator

To use it:

textureSlotAllocator = new TextureSlotAllocator();
...
const slot = textureSlotAllocator.allocate(width, height);

The slot then contains:

• size: a two element array representing width and height. This gets passed to the shader.
• slotNumber: The slot number to pass to the shader.
• x, y: Use this to figure out where to place your image on the texture (by calling texSubImage2D). This does not need to be passed to the shader.
• textureIndex: The texture index to use, from 0..15. This also does not need to be passed to the shader.

How does this work

The textureSlotAllocator initially has 16 big free slots of 4096x4096 pixels. When it needs to allocate a slot (let's say 200x100 for instance), it will continuously split one of the big slot in half.
4096x4096 => 4096x2048 => 2048x2048 => 2048x1024 ... 256x128

We end up with 15 big slots left, and several smaller slots. The next time we need to allocate, we will iterate through all those slots, finding the smallest one that fits.

When we split a slot in half, the two smaller slots are siblings. When deallocating a slot, we check if the sibling is also deallocated. If that's the case, we can merge the siblings into a bigger free slot, and we keep doing this recursively. As a result, if we were to allocate a small slot and deallocate it immediately, all the small slots would merge and we would end up with just the 16 big 4096x4096 slots that we had originally.

The result

We end up with a bunch of sprites packed with a bit of space in-between. With 100 sprite of random size between 1 and 1000, we occupy 2 entire textures sheets.

Demo

I think in most case, this will work out fine. 16 sheets of 4096x4096 pixels is a lot to go through, so even when we're losing a bit of space between sprites, we can still store a lot.

Another texture packing package

If there's a need to pack the texture even tighter, I do have a separate package, which is what I previously used for packing texture:

https://github.com/jacklehamster/texture-manager

Demo

Since it's not restricted to size of powers of 2, it can store textures much tighter. That package was used for games using my old game engine such as World of Turtle or The Impossible Room.

That said, as I mentioned, I'm moving to a new packing model so that I can send fewer attributes to the shaders. And I really need room to send other attributes, because I need to pass information on how the sprite animates so I don't need to update my shader attributes every frame.

Game engine progress

So there you have it. But this is just a small part of my overall game engine. Please check out the progress here:

• Repo: https://github.com/jacklehamster/bun-engine
• Demo: https://jacklehamster.github.io/bun-engine/example/ (use AWSD + arrow keys to move).

On the roadmap, I plan to first provide an engine that let's you just define a world with a big JSON object. You will be able to generate the world, animate and interact with just that.

Eventually, I will also incorporate some code logic using a new programming language that I call NAPL, which will also be serializable just as a JSON object.

When that happens, I hope y'all get to build beautiful games with that engine. Until then, feel free to just contribute to any of those projects by sending a pull request. Unless it's really bizarre, I'll make sure to incorporate your change!

Thanks for reading.