Usually texture atlases are built either:

  • as a seperate content pre-processing step
  • or once when the game starts

What I want to do is create and update atlases on the fly when:

  • A new texture file appears on the disk (or when a file gets removed)
  • Pixel data and/or size of the texture changes (file gets changed)

As a seperate use-case - it's also useful when all assets can't be loaded in memory at once:

Different subsets of textures are used within different levels (yet are not set in stone as player can bring new assets from another level, or find a random drop which introduces a new texture from a vast library).

There a wealth of information on texture-packing algorithms in a all at once scenarios.

What algorithms are there for packing atlases dynamically (add/remove/resize texture)?

What rectangle packing with removal algorithms are there?

  • Textures of arbitrary size
  • Multiple power-of-two bins
  • Both adding and removing has to be fast and online
  • Removal operation should NOT trigger repacking of the whole atlas. Moving an occupied rectangle or two is acceptable (but better avoided?).
  • \$\begingroup\$ Are all textures the same size? \$\endgroup\$ – Bojidar Marinov Jan 16 '16 at 21:50
  • 1
    \$\begingroup\$ Not of the same same, if the textures were of the same size, the solution would be trivial - fragmentation of free space (from removal of textures) would be a non-issue \$\endgroup\$ – JBeurer Jan 16 '16 at 21:55
  • 2
    \$\begingroup\$ It sounds like you should try to add more details to your question, so that a specific answer is possible. Just exhaustively listing algorithms is a search engine's job, and as we know the bin-packing problem is hard even when we're only doing it once, let alone when we need to rearrange & defrag on the fly, so it's likely there's no perfect concise solution. ;) Any constraint you can offer may help get us to a more tractable case. For instance, are your textures always power-of-two sizes, between some min & max? Are there any constraints on their aspect ratios? Do they need padding? etc. \$\endgroup\$ – DMGregory Jan 17 '16 at 4:26
  • \$\begingroup\$ Am I entering the wrong keywords for the search engine? Rectangle packing WITH removal doesn't bring up almost anything. I would not be asking if it was the case. \$\endgroup\$ – JBeurer Jan 17 '16 at 21:03
  • \$\begingroup\$ It sounds like you don't need to be able to remove textures. You can start from a blank atlas whenever the player loads a new level. \$\endgroup\$ – user253751 Jan 18 '16 at 3:40

I ended up implementing a Guillotine rectangle packing algorithm (with heuristic for picking free rectangles with smallest area) GUILLOTINE-BAF with some modifications:

  1. When a texture gets removed - the freed up space gets merged with other free rectangles that are adjacent and their width or height matches (this is done multiple times until there's nothing left to merge with the freed rect).
  2. When there's no free space for the new rectangle to be packed a new bin (atlas) is added.
  3. When a dimension of a texture is changed (with filesystem change notification), the rectangle is repacked in the current atlas, if not - it's moved to another atlas with free-space.
  4. Each atlas stores largest free pixel area, biggest rectangle width and height to find if atlas has enough space for a particular rectangle without going through the free rectangles list.

This method is simple to implement, online, it is fairly fast (fast enough). It does introduce some fragmentation.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.