[Перевод] Реализация алгоритма двумерной упаковки Skyline

info@vsetut.pro

О проекте

Вернуться

21.11.2024 06:16:53 | Хабр

Хабы: Алгоритмы, Работа с 3D-графикой, Программирование

Упаковка 2D-прямоугольников в прямоугольники большего фиксированного размера необходима в большинстве мультимедийных проектов. В программировании GPU изменение текстур (binding) — затратный процесс. Поэтому при рендеринге текста не стоит использовать по одной текстуре на глиф, вместо этого желательно упаковать глифы в единую текстуру, называемую атласом. В 2D-играх содержащие спрайты атласы называются листами спрайтов (spritesheet). Листы спрайтов также используются для веб-сайтов, потому что скачивать один большой файл удобнее, чем по одному файлу на каждый значок/логотип.

Поначалу я думал, что это достаточно нишевая проблема, но оказалось, что она влияет и на целые отрасли. Сколько рекламных объявлений можно уместить на этой странице газеты? Сколько фигур можно вырезать из этого куска дерева? Сколько посылок поместится в кузов грузовика? Поэтому задача двухмерной упаковки изучалась и в научных кругах.

Самым ценным ресурсом из найденных мной стал превосходный обзор Юкки Йулянки. В нём описано четыре типа алгоритмов и их практическая оценка. Выделяются из них два:

MAXRECTS если вы знаете заранее, какие прямоугольники будете упаковывать («офлайн-упаковка»)

SKYLINE если не знаете («онлайн-упаковка»)

Офлайн-упаковка оптимальнее, потому что сортировка прямоугольников перед упаковкой сильно помогает. Однако в некоторых ситуациях реализовать её невозможно. В моём сценарии мне хотелось кэшировать растеризированные из шрифта глифы, но я не знал заранее все глифы, которые будут использоваться для каждого шрифта и каждого формата (полужирный/курсив/размер...).

Именно поэтому я остановился на алгоритме skyline. Он применяется в stb_rect_pack.h, fontstash, а значит, и в nanovg.

В этой статье объяснён алгоритм skyline и представлена его реализация. Реализация доступна онлайн и в общественном достоянии (UNLICENSE).

Подробнее