Упаковка 2D-прямоугольников в прямоугольники большего фиксированного размера необходима в большинстве мультимедийных проектов. В программировании GPU изменение текстур (binding) — затратный процесс. Поэтому при рендеринге текста не стоит использовать по одной текстуре на глиф, вместо этого желательно упаковать глифы в единую текстуру, называемую атласом. В 2D-играх содержащие спрайты атласы называются листами спрайтов (spritesheet). Листы спрайтов также используются для веб-сайтов, потому что скачивать один большой файл удобнее, чем по одному файлу на каждый значок/логотип.
Поначалу я думал, что это достаточно нишевая проблема, но оказалось, что она влияет и на целые отрасли. Сколько рекламных объявлений можно уместить на этой странице газеты? Сколько фигур можно вырезать из этого куска дерева? Сколько посылок поместится в кузов грузовика? Поэтому задача двухмерной упаковки изучалась и в научных кругах.
Самым ценным ресурсом из найденных мной стал превосходный обзор Юкки Йулянки. В нём описано четыре типа алгоритмов и их практическая оценка. Выделяются из них два:
MAXRECTS
если вы знаете заранее, какие прямоугольники будете упаковывать («офлайн-упаковка»)
SKYLINE
если не знаете («онлайн-упаковка»)
Офлайн-упаковка оптимальнее, потому что сортировка прямоугольников перед упаковкой сильно помогает. Однако в некоторых ситуациях реализовать её невозможно. В моём сценарии мне хотелось кэшировать растеризированные из шрифта глифы, но я не знал заранее все глифы, которые будут использоваться для каждого шрифта и каждого формата (полужирный/курсив/размер...).
Именно поэтому я остановился на алгоритме skyline. Он применяется в stb_rect_pack.h, fontstash, а значит, и в nanovg.
В этой статье объяснён алгоритм skyline и представлена его реализация. Реализация доступна онлайн и в общественном достоянии (UNLICENSE).