fitting variable sized sprites into fixed maximum size textures?

I was thinking of making something that would put a bunch of images on the screen, move them around, and animate them. Bees on flowers, for instance. What would be the best way to allocate those things to make most efficient use of textures? I learned that textures often have a dramatically low maximum size in video memory (256x256 even) and sprites not only have a frame size comparable to that, but they have multiple frames of animation. Their frames can be laid out in a finite state machine really, depending on what the sprite is doing. I also learned that switching which texture in use is expensive, so all sprites using a given texture should be rendered together, to minimize switches.

That led to some difficult problems I can’t quite wrap my head around. I was going to do something like this:

struct frame {
   int top;
   int left;
   int w;
   int h;

struct texture {
   GLuint tex;
   struct frame* frames;
   int num_frames;

struct texture* textures = NULL;
int num_textures = 0;

struct sprite {
  int tex;
  int frame;

Where each frame had a given texture, and each sprite had an index into the textures array, then the frames array for a texture. The problem is, some frames could have different sizes than others. Maybe not for a given sprite, if I wanted to limit myself that way, but some sprites might be larger than others, trees, buildings, that sort of thing.

What algorithm could I use for breaking up this texture into different sized frames? If I just allocated the frames left to right, then moved down a row, I’d have to make the row height the size of the largest frame. so in the first row, I’d have 6 32x32 frames, and 1 64x64 frame. Then I’d have to throw away space for 6 more 32x32 frames, since if I only moved 32 pixels down for row 2, I’d overlap the 64x64 frame. With 65K of pixels in a frame, I’d end up throwing away 24K of them, just for alignment issues.

Could I sort frames by size, to try to make as many rows as possible have the same height? Is there some algorithm I could use to find the ideal fit for a group of frames? It’s like one of those tangrams, so surely someone’s made a program to solve tangrams?

I could do all this calculation of what frame goes where in a texture once during compilation of course, so it doesn’t have to be done in real time speed. But at the same time I don’t want to have to feed my frames to Deep Blue just to get which ones go where. And what about when someone has a modern video card with more space per texture, like 1024x1024? In that case I could pretty easily just stuff 4 256x256 “textures” in that texture. But is there some reason to sort them differently, given 4*4 times the space?

And what about sprites larger than 256x256? I’d obviously have to make them out of multiple frames then, in multiple textures. So a “sprite” would have to be an abstraction over possibly multiple texture/frame pairs, any of which could be changed as the sprite’s animation was updated?

struct positioned_sprite {
  struct sprite parent;
  int top;
  int left;

struct super_duper_sprite {
  struct positioned_sprite* sprites;
  int num_sprites;

That’s really confusing terminology to me. A sprite that is sprites? I dunno what you’d call “one section of a sprite at one given point in its animation cycle.” Even the term “frame” seems wrong, since it’s no longer an animation frame, but now merely a piece of an animation frame. It makes me wonder if the underlying concept is flawed, if I can’t find the language to describe it.

256x256 is pretty tiny for maximum texture size. You can expect all graphics cards from 2004 an onwards to support a minimum of 2048x2048. This is what the Unity game engine does anyways. If you need separate frames you can also go with array textures to reduce the number of texture binds you need to do.

Your algorithmic problem is called the Packing Problem ( ) and there are already solutions for it on the internet. Just do some research.

[QUOTE=Cornix;1282402]256x256 is pretty tiny for maximum texture size. You can expect all graphics cards from 2004 an onwards to support a minimum of 2048x2048.[/QUOTE]Even on mobile devices? I actually like 256x256, because it only takes 2 bytes to store the index from the perspective of someone writing a hardware driver. It’s just tricky to figure out how to arrange everything. It’d be nice if I could assume 3 byte indexes were used though, allowing 4096x4096 texture sizes (or 2048x2048 if you take 2 bits away from that)

Your algorithmic problem is called the Packing Problem ( )
Yes! That’s what I was looking for. I could not for the life of me think what it would be called. Thanks!