Упаковка произвольных квадратов в прямоугольник

Question

Чтобы обеспечить некоторый контекст, у меня есть несколько световых карт для разных объектов в 3D-сцене, которые я хочу упаковать в одну текстуру. Световые карты являются квадратными и имеют разные размеры, которые не обязательно имеют силу двух (хотя это ограничение может быть включено, если оно обеспечивает лучшее решение). Размер полученной текстуры произволен, но должен быть как можно более квадратным. Я должен оставаться идеальным пикселем и не могу использовать поворот. Скорость не вызывает беспокойства, это не используется в критическом по времени приложении.

Основной алгоритм я нашел over at GameDev.SE будет работать следующим образом:

1. Сортировка лайтмапы по районам, начиная большие
2. Переход через выходной текстуры [фиксированной ширины или увеличивать, как желаемая] в порядке сканирования растра
3. Место лайтмапа на первое возможное положение
4. Повторите со следующей Lightmap до сделано

Хотя это звучит разумно и легко реализовать, я задаюсь вопросом, является ли этот алгоритм хорошим выбором для моих целей или если есть еще более простое решение. В частности, меня интересует:

• Могу ли я использовать только квадратные текстуры?
• Есть ли способ заранее вычислить оптимальные квадратные размеры вывода?
• Могу ли я в значительной степени использовать только «силу двух» текстур?

Answer 1

Сортировка по высоте эвристическая по-прежнему работает. Даже эта немного более простая версия работает: сортируйте по высоте, разместите слева направо на том же y, каждый раз, когда вы достигаете правой стороны, вы увеличиваете y по самой большой текстуре, которая была на этой линии. Таким образом, вам даже не нужно искать позицию, вы уже знаете, куда ее поместить. Это отлично работает, если нет большого изменения высоты, но это может быть ужасно.

Насколько я знаю, нет возможности заранее рассчитать размер. Но, пытаясь это сделать, в любом случае это приведет к тому, что они не будут иметь силу. Угадайте размер (sqrt (общая площадь), округленное до двух мощностей) и увеличивая его в 2 раза, если не все может быть установлено, должно быстро найти лучший размер.

Если все вещи, которые вы упаковываете, имеют мощность в два раза, то вы можете сделать что-то еще более простое. Поместите все в кучу и попробуйте собрать группы из 4 одинакового размера вместе с блоком следующего размера. Не всегда будет 4, что означает некоторое пустое пространство в большем блоке.

Если они не являются полномочиями двух, вот альтернатива, которая может упасть немного лучше, чем трюк сортировки по высоте. Это значительно медленнее, и не стоит упаковывать только много мелких предметов, но я нашел это полезным, когда предметы имеют радикально разные размеры. Он основан на разбиении площадей и в этом отношении напоминает KD-деревья, но на самом деле это не так (потому что здесь речь идет о областях, нет «точек»). В любом случае вы используете дерево, где каждый внутренний узел представляет собой раскол, причем нечетные уровни расщепляются по одной оси и четные уровни, расщепляющиеся на другой оси. При размещении предмета рекурсивно найдите первое место, которое может поместиться.

Это основная вещь.Я счел полезным сначала попытаться поместить его где-нибудь «красиво» (чтобы он создавал менее 2 расколов, поэтому он подходит для определенной области по ширине или высоте или для обоих), и только в том случае, если такого места нет, в первую очередь, он подходит. Также я нашел полезным хранить свободную область, которую каждый узел имеет «и», и «фактический прямоугольник» в узле. Размеры и местоположение можно вычислить во время рекурсии, и область действительно не нужна вообще, но наличие фактического прямоугольника прямо там удобно и с лишними полками свободной области можно пропустить раньше. Сначала обратная сортировка по области может помочь уменьшить области, которые отделяются один раз, и тогда их никогда не использовать (тогда как мелкие предметы после больших не должны быть проблемой), но она по-прежнему практически не оптимальна.