Embalaje de datos de imágenes rectangulares en una textura cuadrada

Question

Tengo N elementos de datos de imágenes en 2D que serán rectangulares y quiero empacarlos en una sola potencia de 2 texturas de la manera más eficiente posible.

Una simple implementación no eficiente e ingenua de un algoritmo para empaquetar estas recetas sería fácil de acelerar, pero estoy seguro de que la gente ha creado algoritmos para hacerlo de la manera más eficiente posible. He encontrado varias referencias al empaquetamiento de mapa de luz que es similar a lo que estoy buscando, pero los algoritmos para el mapeo ligero tienden a tener en cuenta imágenes no rectangulares que realmente complican las cosas más de lo que necesito que sean.

¿Alguien tiene pistas? ¿Nombres de algoritmos o autores de papel que debería buscar en Google?

Gracias.

Answer 1

Su problema en 1D se llama Bin Packing. Tal vez ese sea un buen comienzo para su búsqueda.

Tenga en cuenta que el problema que desea resolver es realmente difícil (es NP-difícil). Por lo tanto, no debe buscar la solución óptima, sino algún algoritmo heurístico inteligente.

Creo que la programación dinámica bottom-up es posible para el embalaje de bandejas 1D, pero no para el caso 2D.

Puede pensar en simplificar su problema resolviendo solo el problema 1D, haciendo restricciones como cortar las texturas en varias divisiones (de tamaño variable) en 1 dimensión.

Otra posibilidad es ejecutar la optimización meta-heurística, como Algoritmos Evolutivos o Optimización de Enjambre de Partículas.

Answer 2

He tenido que hacer esto mismo que usted describe.

Este es el código Python he usado, es una receta en el libro de cocina de Python:

Recipe 442299: pack multiple images of different sizes into one image

Answer 3

que tenía un problema similar, pero estaba empacando cuadrados. Pruebe esto: http://www.mrashid.info/blog/stacking-squares-problem.php

El código C++ no es muy elegante, pero al menos se obtiene la idea básica de cómo abordar este problema.

Answer 4

Muy bueno y sencillo algoritmo de embalaje se puede encontrar aquí: http://www.blackpawn.com/texts/lightmaps/

Su aplicación sólo toma 200 de C++ líneas, no más (supongo que usted tiene las rutinas de manipulación de mapa de bits ya).

Para la teoría detrás hay una introducción de Jukka Jylänki (busque las "Mil maneras de empacar la papelera").

El autor del documento proporciona la biblioteca de C++ que está realmente hinchada desde mi punto de vista, pero por otro lado tiene muchas opciones y está muy bien documentada.