2
\$\begingroup\$

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?).
Improve this question
\$\endgroup\$
7
  • \$\begingroup\$ Are all textures the same size? \$\endgroup\$
    – Bojidar Marinov
    Jan 16, 2016 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, 2016 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, 2016 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, 2016 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, 2016 at 3:40

1 Answer 1

Reset to default
1
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .