Algoritmo de embalagem de textura

O que é um bom algoritmo de empacotamento de textura? Tecnicamente, empacotar caixas é difícil para NP , então uma heurística é o que eu realmente busco.

Passei alguns meses em um trabalho criando um melhor algoritmo de empacotamento de textura.

O algoritmo com o qual começamos era simples. Colete todos os itens de entrada. Classifique-os pelo total de pixels consumidos, de grande a pequeno. Coloque-os em sua textura na ordem da linha de varredura, apenas testando itens do pixel topleft ao pixel superior direito, movendo-se para baixo de uma linha e repetindo, redefinindo o pixel topleft após cada posicionamento bem-sucedido.

Você precisa codificar uma largura ou criar outra heurística para isso. Em uma tentativa de preservar a quadratura, nosso algoritmo começaria em 128, depois aumentava em 128s até chegar a um resultado que não era mais profundo do que amplo.

Então, nós tínhamos esse algoritmo, e eu decidi melhorá-lo. Tentei um monte de heurísticas malucas - tentando encontrar objetos que se encaixassem, ponderando um monte de propriedades desejadas de empacotamento de espaço, girando e girando. Depois de todo o meu trabalho, literalmente três meses de trabalho, acabei economizando 3% de espaço.

Sim. 3%

Depois que executamos nossa rotina de compactação, ela acabou ficando maior (o que ainda não consigo explicar), então jogamos fora tudo e voltamos ao antigo algoritmo.

Classifique os itens, atole na textura na ordem da linha de verificação. Aqui está o seu algoritmo. É fácil de codificar, rápido de executar, e você não ficará muito melhor sem uma quantidade incrível de trabalho. Esse trabalho simplesmente não vale a pena, a menos que sua empresa tenha pelo menos 50 pessoas e provavelmente mais.

E, como observação complementar, acabei de implementar esse algoritmo (largura fixa de 512 pixels) para literalmente exatamente o mesmo aplicativo que você está fazendo (sem ftgles, mas com glifos de tipo livre renderizados em opengl). Aqui está o resultado. Parece embaçado porque o meu está usando o algoritmo de renderização de texto baseado em campo à distância da Valve , que também é responsável pelo espaço extra entre os glifos. Obviamente, não resta muito espaço vazio, e ele faz um bom trabalho de amontoar as coisas em locais abertos.

Todo o código para isso é licenciado por BSD e está disponível no github .

A tese de doutorado de Andrea Lodi é intitulada Algoritmos para problemas de atribuição e embalagem em caixote bidimensional .
A tese trata de algumas das formas mais difíceis desses problemas. Felizmente, a embalagem de textura é a versão mais fácil. O melhor algoritmo que ele encontrou foi chamado Touching Perimeter .

Para citar a partir da página 52:

O algoritmo, chamado Touching Perimeter (TPRF), começa classificando os itens de acordo com a área não crescente (rompendo os laços por valores mínimos {wj, hj}) e orientando-os horizontalmente. Um limite inferior L no valor ideal da solução é calculado e L caixas vazias são inicializadas. (O limite inferior contínuo L0 definido na seção anterior também é obviamente válido para 2BP | R | F; limites melhores são propostos por Dell'Amico, Martello e Vigo [56].) O algoritmo inclui um item por vez, também em uma bandeja existente ou inicializando uma nova. O primeiro item embalado em uma lixeira é sempre colocado no canto inferior esquerdo. Cada item subsequente é embalado na chamada posição normal (consulte Christo fi des e Whitlock [41]), ou seja,
A escolha do compartimento e da posição da embalagem é feita através da avaliação de uma pontuação, definida como a porcentagem do perímetro do item que toca o compartimento e outros itens já embalados. Essa estratégia favorece padrões nos quais os itens compactados não “prendem” pequenas áreas, o que pode ser difícil de usar para outras colocações. Para cada posição de empacotamento do candidato, a pontuação é avaliada duas vezes, para as duas orientações do item (se ambas são viáveis) e o valor mais alto é selecionado. Os empates de pontuação são quebrados ao escolher a posição que possui a área máxima embalada. O algoritmo geral é o seguinte.

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;

Também interessante, o artigo descreve um algoritmo para determinar o tamanho de um mapa de textura otimizado. Isso seria útil para determinar se é possível encaixar todas as texturas em um atlas de 1024x1024.

Se alguém ainda estiver interessado, reescrevi completamente a biblioteca rectpack2D para que ela seja muito mais eficiente.

Ele funciona mantendo um std::vectorespaço vazio no atlas, começando com um tamanho máximo inicial (normalmente, o tamanho máximo permitido de textura em uma GPU específica), dividindo o primeiro espaço vazio viável e salvando as divisões de volta ao vetor.

O avanço do desempenho ocorreu com o uso de um vetor, em vez de manter uma árvore inteira, como foi feito anteriormente.

O procedimento é descrito em detalhes no README .

A biblioteca está sob o MIT, por isso estou feliz por você, se você achar útil!

Resultados de exemplo:

Os testes foram conduzidos em uma CPU Intel (R) Core (TM) i7-4770K a 3,50 GHz. O binário foi construído com o clang 6.0.0, usando uma opção -03.

Sprites arbitrários de jogos + glifos japoneses: 3264 indivíduos no total.

Tempo de execução: 4 milissegundos
Pixels desperdiçados: 15538 (0,31% - equivalente a um quadrado de 125 x 125)

Saída (2116 x 2382):

Em cores:
(preto é espaço perdido)

Glifos japoneses + alguns sprites da GUI: 3122 sujeitos.

Tempo de execução: 3,5 - 7 ms
Pixels desperdiçados: 9288 (1,23% - equivalente a um quadrado de 96 x 96)

Saída (866 x 871):

Em cores:
(preto é espaço perdido)

Um bom algoritmo heurístico pode ser encontrado aqui . Quando estava tentando algo semelhante recentemente, achei isso referenciado como o ponto de partida básico para a maioria das implementações que vi.

Funciona particularmente bem com lotes de itens de tamanho regular e de formato regular ou com uma boa mistura de imagens pequenas e menos grandes. O melhor conselho para obter bons resultados é lembrar de classificar sua entrada em termos de tamanho da imagem e depois agrupar do maior para o menor, pois as imagens menores serão agrupadas no espaço ao redor das imagens maiores. Como você decide isso e pode depender de seus objetivos. Eu usei perímetro em vez de área como uma aproximação de primeira ordem, pois entendi que imagens altas + finas / curtas + amplas (que teriam uma área baixa) são realmente muito difíceis de serem colocadas mais tarde em um pacote, então, usando o perímetro, você empurra essas formas estranhas na frente da ordem.

Aqui está um exemplo de visulização da saída do meu empacotador em um conjunto aleatório de imagens do diretório de despejo de imagens do meu site :).

Os números nos quadrados são os IDs dos blocos contidos na árvore, para que você tenha uma idéia da ordem das inserções. O primeiro é o ID "3" porque é o primeiro nó da folha (apenas as folhas contêm imagens) e, consequentemente, possui 2 progenitores).

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

Pessoalmente, eu apenas uso um sistema ganancioso do maior bloco que se encaixa. Não é o ideal, mas funciona bem.

Observe que, se você tiver uma quantidade razoável de blocos de textura, poderá procurar exaustivamente a melhor ordem, mesmo que o problema em si seja NP.

Algo que usei, que funciona bem mesmo para mapas UV irregulares, é transformar o adesivo UV em uma máscara de bitmap e manter uma máscara para a própria textura, procurando a primeira posição em que o adesivo UV se encaixará. Ordeno os blocos de acordo com algumas heurísticas simples (altura, largura, tamanho, o que for) e permito que as rotações dos blocos minimizem ou maximizem a heurística escolhida. Isso fornece um espaço de pesquisa gerenciável para força bruta.

Se você pode iterar a tentativa de várias heurísticas e / ou aplicar um fator aleatório na escolha da ordem e iterar até que algum tempo acabe.

Com esse esquema, você terá pequenas ilhas de UV embaladas nas lacunas de grandes dimensões e até mesmo em buracos deixados nas próprias manchas de UV.

Recentemente, lançamos um script python que compactará texturas em vários arquivos de imagem de um determinado tamanho.

Citado em nosso blog:

"Embora existam inúmeros empacotadores que podem ser encontrados on-line, nossa dificuldade foi encontrar um que pudesse lidar com um grande número de imagens em vários diretórios. Assim, nasceu nosso próprio empacotador de atlas!

Como é, nosso pequeno script iniciará no diretório base e carregará todos os .PNGs em um atlas. Se esse atlas for preenchido, ele cria um novo. Em seguida, tentará ajustar o restante das imagens em todos os atlas anteriores antes de encontrar um local no novo. Dessa forma, cada atlas é o mais apertado possível. Os atlas são nomeados com base na pasta da qual suas imagens são.

Você pode alterar o tamanho do atlas (linha 65), o formato das imagens que deseja compactar (linha 67), o diretório de carregamento (linha 10) e o diretório de salvamento (linha 13) com bastante facilidade, sem experiência em Python. Como um pequeno aviso de isenção de responsabilidade, isso foi reunido em alguns dias para funcionar especificamente com nosso mecanismo. Convido você a solicitar recursos, comentar com suas próprias variações e relatar erros, mas qualquer alteração no script ocorrerá no meu tempo livre. "

Sinta-se livre para conferir o código fonte completo aqui: http://www.retroaffect.com/blog/159/Image_Atlas_Packer/#b

É muito fácil empacotar fontes porque todas (ou a grande maioria) das texturas de glifos são quase do mesmo tamanho. Faça a coisa mais simples que lhe ocorrer e será muito próximo do ideal.

A clareza se torna mais importante quando você empacota imagens de tamanhos muito diferentes. Então, você deve poder preencher lacunas, etc. Mesmo assim, um algoritmo simples, como a pesquisa de pedidos da linha de varredura discutida anteriormente, produzirá resultados muito razoáveis.

Nenhum dos algos avançados é mágico. Eles não serão 50% mais eficientes do que um simples documento, e você não obterá benefícios consistentes a menos que tenha um número impressionante de folhas de textura. isso ocorre porque os pequenos aprimoramentos feitos por algoritmos melhores serão vistos apenas em conjunto.

Vá simples e vá para algo em que seus esforços serão melhor recompensados

Se for especificamente para texturas de fonte, você provavelmente fará algo não ideal, mas agradável e simples:

Classificar caracteres por altura, mais alto primeiro

Comece com 0,0 Coloque o primeiro caractere nas cordas atuais, avance X, coloque o próximo, repita até não cabermos em outro

Redefina X para 0, avance Y para baixo pela altura do caractere mais alto da linha e preencha outra linha

Repita até ficarmos sem caracteres ou não caber em outra linha.