Pakowanie prostokątnych danych obrazu do tekstury kwadratowej

Question

Mam N pozycji 2D danych obrazu, które będą prostokątne i chcę spakować je w jedną moc 2 tekstury tak skutecznie, jak to możliwe.

Prosta, nieefektywna i naiwna implementacja algorytmu do spakowania tych rectów byłaby łatwa do zniesienia, ale jestem pewien, że ludzie wymyślili algorytmy, aby zrobić to jak najwyżej wydajnie. Znalazłem różne odniesienia do pakowania lightmap, które są podobne do tego, czego szukam, ale algorytmy lightmapingu uwzględniają nieprostokątne obrazy, które faktycznie komplikują rzeczy bardziej, niż ich potrzebuję.

Czy ktoś ma podpowiedzi? Nazwy algorytmów lub autorów papieru Mam google?

Dzięki.

Answer 1

Twój problem w 1D nazywa się pakowaniem pojemników. Być może to dobry początek wyszukiwania.

Zauważ, że problem, który chcesz rozwiązać, jest naprawdę trudny (jest NP-trudny). Więc nie powinieneś szukać optymalnego rozwiązania, ale jakiś sprytny algorytm heurystyczny.

Wydaje mi się, że programowanie dynamiczne w trybie bottom-up jest możliwe w przypadku pakowania w skrzyni 1D, ale nie w przypadku 2D.

Można pomyśleć o uproszczeniu problemu, rozwiązując tylko problem 1D, wprowadzając ograniczenia, takie jak cięcie tekstur na kilka (zmienne wielkości) plasterków w jednym wymiarze.

Inną możliwością jest optymalizacja meta-heurystyczna, na przykład algorytmy ewolucyjne lub Optymalizacja roju cząstek.

Answer 2

Potrzebowałem zrobić to, co opisujesz.

Jest to kod Pythona użyłem, to recepta na Python Cookbook:

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

Answer 3

miałem podobny problem, ale byłem pakowania kwadraty. Wypróbuj to: http://www.mrashid.info/blog/stacking-squares-problem.php

Kod C++ nie jest zbyt elegancki, ale przynajmniej masz podstawowy pomysł, jak podejść do tego problemu.

Answer 4

algorytm Bardzo dobry i prosty pakowania można znaleźć tutaj: http://www.blackpawn.com/texts/lightmaps/

Jego realizacja trwa tylko 200 C++ linie, nie więcej (I załóżmy, że masz już rutynowe manipulacji bitmapy).

Teoria za tym jest wprowadzeniem Jukka Jylänki (poszukaj "Tysiąc sposobów pakowania kosza").

Autor artykułu przedstawia bibliotekę C++, która jest naprawdę nadęty z mojego punktu widzenia, ale z drugiej strony ma wiele opcji i jest bardzo dobrze udokumentowana.