Алгоритм упаковки текстур

Что такое хороший алгоритм упаковки текстур? Технически, бен упаковка является NP-трудной , поэтому эвристика , что я действительно после.

Я провел несколько месяцев на одной работе, придумывая лучший алгоритм упаковки текстур.

Алгоритм, с которого мы начали, был прост. Соберите все элементы ввода. Сортируйте их по общему количеству пикселей, от большого к маленькому. Разложите их в вашей текстуре в порядке строки развертки, просто проверив материал от верхнего пикселя до верхнего пикселя, сдвинув линию вниз и повторив, возвращаясь к верхнему пикселю после каждого успешного размещения.

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

Итак, у нас был этот алгоритм, и я решил его улучшить. Я попробовал несколько дурацких эвристик - пытаясь найти объекты, которые совмещались бы вместе, выполняя определенную нагрузку на кучу желаемых свойств пространственной упаковки, вращая и переворачивая. После всей моей работы, буквально трех месяцев работы, я сэкономил 3% пространства.

Да уж. 3%.

И после того, как мы запустили нашу подпрограмму сжатия, она фактически стала больше (что я до сих пор не могу объяснить), поэтому мы выбросили все это и вернулись к старому алгоритму.

Сортируй предметы, вставляй текстуру в порядке сканирования. Там твой алгоритм. Его легко кодировать, быстро запускать, и вы не станете намного лучше без огромного количества работы. Эта работа не имеет смысла, если в вашей компании не менее 50 человек, а возможно и больше.

И как примечание, я только что реализовал этот алгоритм (фиксированная ширина 512 пикселей) буквально для того же самого приложения, которое вы делаете (без ftgles, но с помощью openfl-рендеринга глифов свободного типа). Вот результат. Это выглядит размыто, потому что мой использует алгоритм рендеринга текста на основе поля расстояния Valve , который также учитывает дополнительное пространство между глифами. Очевидно, что осталось не так много пустого пространства, и оно отлично справляется с тем, чтобы втиснуть вещи в открытые места.

Весь код для этого лицензирован BSD и доступен на github .

Докторская диссертация Андреа Лоди озаглавлена ​​« Алгоритмы для двумерных задач упаковки и назначения бинов» .
Тезис охватывает некоторые из сложных форм этой проблемы. К счастью, упаковка текстур является самой простой версией. Лучший алгоритм, который он нашел, был назван « Трогательный периметр» .

Цитировать со страницы 52:

Алгоритм, называемый периметром касания (TPRF), начинается с сортировки элементов в соответствии с неубывающей областью (разрыв связей с помощью неубывающих значений min {wj, hj}) и их горизонтальной ориентации. Затем вычисляется нижняя граница L для оптимального значения решения, и L пустых бинов инициализируется. (Непрерывная нижняя граница L0, определенная в предыдущем разделе, очевидно, справедлива и для 2BP | R | F; лучшие оценки предлагают Dell'Amico, Martello и Vigo [56].) Алгоритм упаковывает по одному элементу за раз, либо в существующем контейнере или путем инициализации нового. Первый предмет, упакованный в корзину, всегда помещается в нижний левый угол. Каждый последующий элемент упакован в так называемую нормальную позицию (см. Кристофис и Уитлок [41]), т.е.
Выбор корзины и позиции упаковки осуществляется путем оценки количества очков, определяемого как процент от периметра предмета, который касается ящика и других уже упакованных предметов. Эта стратегия отдает предпочтение моделям, в которых упакованные предметы не «захватывают» небольшие области, что может быть трудно использовать для дальнейшего размещения. Для каждой позиции упаковки кандидата оценка оценивается дважды, для двух ориентаций элементов (если они возможны), и выбирается самое высокое значение. Связи очков нарушаются, выбирая корзину с максимальной упакованной площадью. Общий алгоритм выглядит следующим образом.

touching_perimeter:
  sort the items by nonincreaseing w,h values, and horizontally orient them;
  comment: Phase 1;
  compute a lower bound L on the optimal solution value, and open L empty bins;
  comment: Phase 2;
  for j := 1 to n do
     score := 0;
     for each normal packing position in an open bin do
        let score1 and score2 be scores with tow orientations;
        score := max{score,score1,score2};
     end for;
     if score > 0 then
        pack item j in the bin, position and orientation corresponding to score;
     else
        open a new bin and horizontally pack item j into i;
     end if;
  end for;
end;

Также интересно, что в статье описан алгоритм определения размера оптимально упакованной текстурной карты. Это было бы полезно, чтобы определить, можно ли даже разместить все текстуры в одном атласе 1024x1024.

Если кому-то все еще интересно, я полностью переписал библиотеку rectpack2D, чтобы она стала более эффективной.

Он работает, сохраняя std::vectorпустые места в атласе, начиная с некоторого начального максимального размера (как правило, максимально допустимого размера текстуры на конкретном графическом процессоре), разделяя первое жизнеспособное пустое пространство и сохраняя разбиения обратно в вектор.

Прорыв в производительности произошел благодаря использованию вектора, вместо сохранения целого дерева, как это было сделано ранее.

Процедура подробно описана в README .

Библиотека находится под MIT, поэтому я рад за вас, если вы найдете это полезным!

Пример результатов:

Тесты проводились на процессоре Intel® Core ™ TM i7-4770K с тактовой частотой 3,50 ГГц. Двоичный файл был собран с помощью clang 6.0.0 с использованием ключа -03.

Произвольные игровые спрайты + японские глифы: всего 3264 предмета.

Время выполнения: 4 миллисекунды.
Потраченные впустую пиксели: 15538 (0,31% - эквивалент квадрата 125 x 125)

Выход (2116 x 2382):

В цвете:
(черный - пустое пространство)

Японские глифы + некоторые спрайты GUI: 3122 предметов.

Время выполнения: 3,5 - 7 мс.
Потери пикселей: 9288 (1,23% - эквивалент квадрата 96 x 96)

Выход (866 x 871):

В цвете:
(черный - пустое пространство)

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

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

Вот пример визуализации вывода для моего упаковщика на случайный набор изображений из каталога дампа изображений моего сайта :).

Числа в квадратах - это идентификаторы содержащихся блоков в дереве, поэтому вы можете получить представление о порядке вставок. Первый - это идентификатор «3», потому что это первый листовой узел (только листья содержат изображения) и, следовательно, имеет 2 родителя).

        Root[0]
       /      \
   Child[1]  Child[2]
      |
    Leaf[3]

Лично я просто использую первую жадную систему "самый большой блок, который подходит". Это не оптимально, но это хорошо.

Обратите внимание, что если у вас есть достаточное количество текстурных блоков, вы можете исчерпывающе искать лучший порядок, даже если самой проблемой является NP.

Что-то, что я использовал, и это хорошо работает даже для нерегулярных УФ-карт, - это превращение УФ-патча в растровую маску и сохранение маски для самой текстуры, ища первую позицию, в которую будет вписываться УФ-патч. Я упорядочиваю блоки в соответствии с некоторой простой эвристикой (высота, ширина, размер и т. Д.), И разрешаю повороты блоков, чтобы минимизировать или максимизировать выбранную эвристику. Это дает управляемое пространство поиска для грубой силы.

Если вы можете затем повторить эту попытку, используя несколько эвристик, и / или применить случайный фактор при выборе порядка и повторять, пока не истечет некоторое время.

С помощью этой схемы вы получите маленькие ультрафиолетовые островки, упакованные в зазоры, образованные большими, и даже в отверстиях, оставленных в самих одиночных УФ-пластырях.

Недавно мы выпустили скрипт на python, который будет упаковывать текстуры в несколько файлов изображений заданного размера.

Цитируется из нашего блога:

«Хотя существует множество упаковщиков, которые можно найти в Интернете, наша трудность заключалась в том, чтобы найти любой, который мог бы обрабатывать большое количество изображений в нескольких каталогах. Таким образом, появился наш собственный упаковщик атласа!

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

Вы можете достаточно легко изменить размер атласа (строка 65), формат изображений, которые вы хотите упаковать (строка 67), каталог загрузки (строка 10) и каталог сохранения (строка 13), не имея опыта работы с Python. Как небольшой отказ от ответственности, это было сделано за несколько дней, чтобы работать именно с нашим двигателем. Я призываю вас запрашивать функции, комментировать собственные варианты и сообщать о любых ошибках, но любые изменения в сценарии произойдут в мое свободное время ».

Не стесняйтесь проверить полный исходный код здесь: http://www.retroaffect.com/blog/159/Image_Atlas_Packer/#b

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

Ум становится более важным, когда вы упаковываете изображения очень разных размеров. Затем вы хотите иметь возможность упаковать в пропуски и т. Д. Даже в этом случае простой алгоритм, такой как поиск порядка строк сканирования, который обсуждался ранее, даст очень разумные результаты.

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

Идите просто и переходите к чему-то, где ваши усилия будут лучше вознаграждены

Если это специально для текстур шрифтов, то вы, вероятно, делаете что-то неоптимальное, но приятное и простое:

Сортировка символов по высоте, сначала самая высокая

Начните с 0,0 Поместите первый символ в текущие координаты, продвиньте X, поместите следующий, повторяйте, пока мы не сможем подогнать другой

Сбросьте X к 0, продвиньте Y вниз на высоту самого высокого символа в строке и заполните другую строку

Повторяйте до тех пор, пока у нас не закончатся символы или не поместится другой ряд.