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

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

47 голосов | спросил deft_code 17 AM000000120000004731 2010, 00:32:47

9 ответов


52

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

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

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

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

Да. 3%.

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

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

alt text

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

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

ответил ZorbaTHut 17 AM00000090000002931 2010, 09:54:29
17

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

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

  

Алгоритм, называемый Touching   Периметр (TPRF) начинается с сортировки   предметы в соответствии с невозрастающими   площадь (разрыв связей невозрастающим   min {wj, hj}) и   горизонтально ориентируя их. Нижняя   связанный L с оптимальным значением решения   затем вычисляется, а L пустых бункеров   инициализируется. (Непрерывное понижение   связанный L0, указанный в предыдущем   очевидно, для 2BP | R | F   также; лучшие оценки   Dellâ € ™ Amico, Martello и Vigo [56].)   Алгоритм упаковывает один элемент в   времени, либо в существующем ящике, либо   инициализация нового. Первый пункт   упакованный в корзину, всегда помещается в   нижний левый угол. каждый   последующий элемент упаковывается в   так называемое нормальное положение (см.   Christoï¬ des and Whitlock [41]), т. Е.   с нижним краем, касающимся   дно бункера или верхний край   другого предмета и его левой   край, касающийся либо левого края   бункер или правый край другого   пункт.
  Выбор бункера и   положение упаковки выполняется путем оценки   оценка, определяемая как процентная доля   периметр предмета, который касается   bin и другие предметы, уже упакованные.   Эта стратегия благоприятствует шаблонам, где   упакованные предметы не «мелкие»   областях, которые могут быть трудно использовать для   дальнейшие размещения. Для каждого кандидата   положение упаковки, оценка   оценивается дважды, для двух элементов   ориентации (если оба они возможны),   и выбирается самое высокое значение.   Связи с оценкой ломаются, выбирая   бин, имеющий максимальную площадь упаковки.   Общий алгоритм выглядит следующим образом.

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.

ответил deft_code 21 AM00000040000001631 2010, 04:14:16
11

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

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

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

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

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

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

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

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

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

Выход (2116 x 2382):

3

Цвет:
(черный - впустую)

4

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

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

Выход (866 x 871):

5

Цвет:
(черный - впустую)

6

ответил Patryk Czachurski 14 PM00000050000003131 2012, 17:05:31
5

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

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

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

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

        Root[0]
       /      \
   Child[1]  Child[2]
      |
    Leaf[3]
ответил xan 21 PM000000120000003731 2010, 12:57:37
3

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

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

ответил drxzcl 17 AM000000120000005831 2010, 00:47:58
3

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

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

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

ответил JasonD 17 AM00000010000001731 2010, 01:13:17
1

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

Цитаты из нашего блога:

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

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

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

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

ответил dcarrigg 21 AM00000080000003031 2010, 08:32:30
1

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

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

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

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

ответил 8 12010vEurope/Moscow11bEurope/MoscowMon, 08 Nov 2010 22:09:48 +0300 2010, 22:09:48
0

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

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

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

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

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

ответил bluescrn 18 AM00000020000004831 2010, 02:43:48

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132