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

Question

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

Основной алгоритм, который я нашел на GameDev.SE, будет работать так:

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

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

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

Answer 1

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

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

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

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

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