Dynamic Texture Atlas


After some discussion in https://github.com/AnalyticalGraphicsInc/cesium/pull/54, we decided to revisit our texture atlas packing algorithm so it supports incremental additions. Right now, it needs to know all the images up front. It basically sorts them by height, then packs then left to right, top to bottom -
https://github.com/AnalyticalGraphicsInc/cesium/blob/master/Source/Renderer/TextureAtlas.js. Adding an image later requires recreating the entire atlas.

Instead, we plan to keep a free list of rectangles in the atlas, heuristically pick one when an image is added, and put the subdivided rectangle remainders back on the free list. If a suitable rectangle can’t be found, then the atlas needs to be recreated like std::vector. I’ll call it amortized constant time without proof :). I also won’t make any formal claims about optimal use of atlas space; however, in trivial cases when the images are all the same size, it will be very good like the current algorithm.

Texture atlas packing is actually the bin packing problem, which is NP hard. Jukka Jylank has great writeups on it, http://clb.demon.fi/files/RectangleBinPack.pdf and
http://clb.demon.fi/projects/even-more-rectangle-bin-packing. The algorithm we propose is similar to http://blackpawn.com/texts/lightmaps/default.html and http://codesuppository.blogspot.com/2009/04/texture-packing-code-snippet-to-compute.html.

Ian is doing the implementation work.


I forgot to attach my notes.